ALG 6

96 Rozdział 5. Struktury danych

Rys. 5 - 3.		FCOOh		FCI4h		FFEEh
Przykład listy jedno-kierunkowej (2).	FCOOh		2		-12		3
	FFEEh		FCMh		FFEEh		OOOOli

-ł- dane -►

Pole ogon struktury informacyjnej wskazuje na komórkę zawierającą 3 (ostatni! element listy). Pola te służą do przeglądania elementów listy i do dołączania I nowych. Oto jak może wyglądać procedura przeglądająca elementy listy, np. w poszukiwaniu wartości x (komórka informacyjna nazywa się info):

adres tmp—info.głowa

dopoki (adres_trap!=NULL) wykonuj

(

jeśli(adres_tmp.wartość==x) to I

Wypisz „Znalazłem poszukiwany element" opuść procedurę I

w przeciwnym przypadku

adres_tmp^adres_tmp.następny ł

Wypisz „Nie znalazłem poszukiwanego elementu"

W dalszej części rozdziału będziemy przeplatać opis algorytmów w pseu-dojęzyku programowania (takim jak wyżej) z gotowym kodem C++; kryterium wyboru będzie czytelność procedur (patrz uwagi zawarte w rozdziale 1). Oczywiście, nawet jeśli prezentacja algorytmu zostanie dokonana w' pseudo-kodzie, to wersja dyskietkowa będzie zawierała w pełni kompilowalne wersje w C++.

5.1.1 .Realizacja struktur danych listy jednokierunkowej

Poniższa implementacja struktur potrzebnych do programowej obsługi listy jednokierunkowej jest dokładnym odzwierciedleniem rysunku 5 - 2 i nie należy się tu spodziewać szczególnych niespodzianek. Osoby, które nie znają jeszcze zbyt dobrze składni języka C—+, powinny dobrze zapamiętać sposób deklaracji typów danych „rekurencyjnych” (tzn. zawierających wskaźniki do elementów swojego typu). Różni się on bowiem odrobinę od sposobu używanego na przykład w' Pascalu (patrz również dodatek A).

lis ta. li

typedof struct rob

(

int wartość;

struct rob *nasLepuy; II wskaźnik do następnego elementu } KI.KM?,NT; class LISTA I