2277150872

2277150872



Elementy takiej listy połączone są dwukierunkowo, co widać na poniższym rysunku:

NULL


Lista dwukierunkowa.Pole p wskazuje na element poprzedni, pole n na następny.

Wzdłuż całej listy dwukierunkowej można swobodnie poruszać się za pomocą wskaźników w obie strony. Dlatego, posiadając dowolny element listy dwukierunkowej, mamy dostęp do wszystkich pozostałych. Nie było to tak do końca możliwe w przypadku list j ednokierunkowych.

Ponieważ lista w ogólnym przypadku zaczyna się jakimś elementem i jakimś elementem się kończy (z wyjątkiem przypadków cyklicznych), początek listy przyjęto nazywać głową listy (head), zaś koniec - ogonem (taił). Dowolny element jest węzłem lub nodem (node).

Lista dwukierunkowa to tak jakby dwie listy jednokierunkowe zrealizowane wewnątrz jednej struktury. Charakterystyczne jest to, że wewnątrz jednego elementu wskaźniki pokazują na element poprzedni oraz na element następny. Jeżeli określimy inaczej, na co mają one wskazywać, np. oba na elementy następne, otrzymamy zamiast listy inną strukturę - drzewo.

KOLEJKI

Listy mogą być zależnie od sposobu obsługi traktowane inaczej. Znane są np. kolejki, czyli lista jednokierunkowa obsługiwana tak specyficznie, że pierwszy wstawiony element jest także pierwszym dającym się z listy odczytać (tzw. kolejka FIFO - First in, First out -dokładne odwzorowanie normalnej kolejki przed sklepem mięsnym w czasach kryzysu).

STOSY

Stos jest implementacją listy jednokierunkowej, która pozwana na wstawianie elementu do struktury, a potem na odzyskiwanie ich w odwrotnej kolejności - czyli pierwszy wstawiony jest ostatnim wyjętym, dokładnie tak, jakby ktoś rzucał dane na kupę, lub stos.

Jest to również wersja kolejki LIFO (last in - first out - ostatni wchodzi, pierwszy wychodzi, pasuje to trochę do pewnego rodzaju studentów).

DRZEWA

Drzewa oferują niezwykle mały czas dostępu do swoich elementów (zakładając, że są zoptymalizow ane, lub wyważone). Struktura węzła najprostszego drzewa jest identyczna jak w przypadku listy dwukierunkowej:

struct BTree {

BTree *lewy, *prawy;

/* .... dane ... */

}

Strona 5 z 41



Wyszukiwarka

Podobne podstrony:
2002 roku kurs euro stale rósł co widać na poniższym wykresie. W tym przypadku semiodchylenie, samo
ALG4 124 Rozdział 5. Struktury danych Co jednak z dołączaniem elementów do listy? Poniżej są omówio
skanuj0080 Opowiadanie dziecka jest konkretne, żaden element nie wykracza poza to, co widać na obraz
Przykłady połączeń warsztatowych elementów zginanych. -Styki warsztatowe są konieczne ze względu na
skanuj0004 jeden dziesięć Gdy dawniej podawano liczbę czegoś, mówiono np.: 11-jeden na dziesięcie, c
ĆWICZENIA REWALIDACYJNE (01) 1. Połącz kropki. Rozpoznaj, co jest na obrazku i pokoloruj
plaża, jezioro, lato kolorowanka (124) Co widać na niebie w ciepłe dni? Pokaż paluszkiem odpowiedn
Kwiat 2(1) Połącz punkty od Co zakwitło na Twojej kartce?

więcej podobnych podstron