Kurs C++ #9



Kurs C++ #9


|======= #09 add. 1 ======|
+-------------------------+
| K U R S C + + |
+-------------------------+
l i s t a , s t o s
i k o l e j k a

...czyli struktury danych, o których wam już wspominałem. W tym dodatku postaram się przedstawić ich budowę, działanie i zastosowanie. A oto pierwszy z tych typów danych, czyli...

Lista

Sama lista jest tylko podzbiorem różnych struktur: wyróżniamy listy jednokierunkowe, dwukierunkowe, cykliczne, drzewa (również jako podzbiór - bo są i drzewa binarne, i potrójne...), macierze rzadkie... No cóż, my poznamy tylko listę jednokierunkową - każda następna opiera się na tym samym sposobie.

Lista to typ danych bardzo "elastyczny". W zasadzie odpowiada tablicy - również służy do przechowywania danych. Jednak od tablicy odróżnia ją to, że nie ma z góry ustalonego rozmiaru. Jej rozmiar ZAWSZE odpowiada ilości zapisanych elementów - od zera (a w zasadzie 4 bajtów - wielkość wskaźnika) aż do... końca pamięci.

Lista jednokierunkowa składa się z "głowy" i kolejnych członów (zwanych węzłami). Istota listy to dodatkowe pole w każdym węźle, które jest wskaźnikiem do kolejnego węzła. "Głowa" jest wskaźnikiem na pierwszy element listy, a "ogon" jest ostatnim elementem. W ogonie wskaźnik następnego węzła ma wartość NULL - czyli zero. Wygląda to mniej-więcej tak:

*początek