en rozdzia│ jest teoretycznym wstΩpem do innych rozdzia│≤w dotycz▒cych dynamicznych struktur danych. PodajΩ tutaj klasyfikacjΩ listowych struktur danych na podstawie ksi▒┐ki L. Banachowskiego, K. Diksa i W. Ryttera Algorytmy i struktury danych.
en rozdzia│ jest teoretycznym wstΩpem do innych rozdzia│≤w dotycz▒cych dynamicznych struktur danych. PodajΩ tutaj klasyfikacjΩ listowych struktur danych na podstawie ksi▒┐ki L. Banachowskiego, K. Diksa i W. Ryttera Algorytmy i struktury danych.
Zapewne mia│e╢ kiedy╢ do czynienia z dynamicznymi strukturami danych. Prawdopodobnie konstruowa│e╢ bardziej z│o┐one struktury. W tym rozdziale wyja╢niam dok│adnie pojΩcia zwi▒zane ze strukturami listowymi, co ma na celu usystematyzowanie Twojej wiedzy na ten temat.
Najpierw - co to jest lista? Jest to sko±czony ci▒g element≤w. Graniczne elementy listy (te na jej ko±cach) nazywa siΩ odpowiednio lewym i prawym ko±cem listy. Ilo╢µ element≤w zapisanych w li╢cie to jest d│ugo╢µ, czyli rozmiar.
Na listach mo┐na dokonywaµ nastΩpuj▒cych operacji:
Wyr≤┐nia siΩ trzy rodzaje list:
kolejka - jest to taka lista, na kt≤rej mo┐na wykonaµ trzy operacje: pobranie lewego ko±ca listy, usuniΩcie lewego ko±ca listy oraz dodanie do listy nowego elementu na jej prawym ko±cu
stos - jest to taka lista, na kt≤rej mo┐na wykonaµ nastΩpuj▒ce operacje: pobranie lewego ko±ca listy, usuniΩcie go i do│▒czenie nowego elementu do lewego ko±ca. Co ciekawe, w czΩ╢ci podrΩcznik≤w obja╢niaj▒c stos, nie wiedzieµ czemu nie kojarzy siΩ go z listami
kolejka podw≤jna - jest to lista, na kt≤rej mo┐na wykonaµ nastΩpuj▒ce operacje: odczytanie lewego ko±ca, usuniΩcie go, do│▒czenie do listy nowego elementu z lewej strony, odczytanie prawego ko±ca listy, do│▒czenie nowego elementu na prawy koniec listy i usuniΩcie prawego ko±ca listy
Listy mo┐na konstruowaµ w dwojaki spos≤b. Pierwszy to po prostu tablica (tak tak, tablica jest list▒!), a drugi to struktura dowi▒zaniowa. Ta druga jest szczeg≤lnie interesuj▒ca, gdy┐ daje programi╢cie nieprawdopodobne mo┐liwo╢ci.
NajczΩ╢ciej u┐ywa siΩ czterech rodzaj≤w list dowi▒zaniowych: pojedynczej liniowej (najprostsza), pojedynczej cyklicznej (ostatni element wskazuje na pierwszy), podw≤jnej liniowej (dwukierunkowej - umo┐liwiaj▒cej przesuwanie siΩ zar≤wno do przodu, jak i wstecz) i podw≤jnej cyklicznej.
Po przeczytaniu tego teoretycznego rozdzia│u radzΩ dok│adnie przetestowaµ zdobyte wiadomo╢ci w praktyce. Zajrzyj w tym celu do moich artyku│≤w: Lista i Przyk│ad dynamicznej struktury danych. Powodzenia!!!
