AiSD_2008_03m.pdf

2008-11-04

Podstawowe struktury dynamiczne

Algorytmy i struktury danych

Wykład 3.

Rok akademicki: 2008/2009

Struktura dynamiczna

• Struktura dynamiczna – struktura, która:

– tworzona jest w programie poprzez jawne użycie odpowiedniej

instrukcji (np. operatora new),

– może zmieniać swoją wielkość – liczbę elementów składowych (zmiana

ilości zajmowanej pamięci operacyjnej),

– jej likwidacja prowadzi do odzyskania zajmowanej przez nią pamięci.

2008-11-04

Struktury dynamiczne w języku Java

• kolekcja (Collection) - grupa obiektów (obiekty mogą się powtarzać),

• zbiór (Set) - grupa elementów (obiekty nie mogą się powtarzać),

• zbior posortowany (SortedSet) - jak zbiór, ale kolejność elementów jest

określona, możliwe jest pobranie następnego lub poprzedniego elementu

zbioru (np. uporządkowany alfabetycznie zbiór liter lub zbiór łańcuchów),

• lista (List) - kolekcja, w której elementy mogą się powtarzać, elementy listy

są uporządkowane; dostęp do nich jest również możliwy poprzez indeks.

Rodzaje struktur listowych: stos, kolejka, lista jednokierunkowa, lista

dwukierunkowa, lista cykliczna,

• tablica asocjacyjna (Map) – zbiór par (klucz, wartość), dostęp do elementu

jest możliwy po podaniu klucza,

• posortowana tablica asocjacyjna (SortedMap) - tablica asocjacyjna

zawierająca elementy uporządkowane według klucza.

• drzewa i grafy ã kolejne wykłady!!!

Definicja struktur dynamicznych w postaci interfejsów

2008-11-04

Interfejs Collection

Interfejs Iterator

public interface Iterator {

boolean hasNext();

Object next();

void remove();

}

2008-11-04

Wykorzystanie iteratorado usuwania elementów

Collection collection = ...;

Iterator iterator = collection.iterator();

while (iterator.hasNext()) {

Object element = iterator.next();

if (removalCheck(element)) {

iterator.remove();

}

Klasa AbstractCollection

• public abstract class AbstractCollection extends Object

implements Collection

• przy tworzeniu kolekcji niezbędne jest:

– określenie sposobu przechowywania danych

– zdefiniowanie metody iterator()

– zdefiniowanie metody size()

– zdefiniowanie metody add() - dostępna metoda add() generuje

wyjątek UnsupportedOperationException

– zdefiniowanie konstruktorów: Kolekcja() oraz Kolekcja(Collection

2008-11-04

Kolekcja –przykład 1/6

import java.util.Collection;

import java.util.AbstractCollection;

import java.util.Iterator;

import java.util.NoSuchElementException;

class KolekcjaLiterA extends AbstractCollection implements Iterator

{

private int ileLiter;

private int aktualnaLitera;

private boolean czyMoznaUsunac;

KolekcjaLiterA()

{

}

ileLiter = 0;

czyMoznaUsunac = false;

aktualnaLitera = 0;

Kolekcja –przykład 2/6

KolekcjaLiterA(Collection c) {

addAll(c);

}

public Iterator iterator() {

aktualnaLitera = 0;

return this;

}

public boolean hasNext() {

return (aktualnaLitera < ileLiter);

}

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: