ALG 8

98 Rozdział 5. Struktury danych

W następnych paragrafach zostaną przedstawione wszystkie metody, które były wyżej wzmiankowane jedynie poprzez swoje nagłówki.

5.1.2.Tworzenie listy jednokierunkowej

Najwyższa już pora na przedstawienie sposobu dołączania elementów do listy. Posłuży nam do tego celu kilka funkcji, o mniejszym lub większym stopniu skomplikowania. Na początek zdefiniowaliśmy miniaturową funkcję usługową pusta, która pomimo swej prostoty ma szansę być dość często używana w praktyce. Z uwagi na małe rozmiary funkcja ta została zdefiniowana wprost w ciele klasy. Potrzeba sprawdzania czy jakieś elementy już są zapamiętane na liście, wystąpi przykładowo w funkcji dorzuci, która dołącza nowy element do listy.

Podczas dokładania nowego elementu możliwe są dwa podejścia: albo będziemy traktować listę jako zwykły „worek” do gromadzenie danych nieuporządkowanych (będzie to wówczas naukowy sposób na zwiększanie bałaganu), albo też przyjmiemy założenie, że nowe elementy dokładane będą w liście we właściwym, ustalonym przez nas porządku - na przykład sortowane od razu w kierunku wartości niemalejących.

Pierwszy przypadek jest trywialny - odpowiadająca mu procedura dorzuci jest przedstawiona poniżej:

tisUi.cpp

tinclude "lista.h"

void LISTA::dorzuci(int x)

(

II dorzucanie elementu bez sortowanie

ELEMENT ‘q=new ELEMENT;    // tworzenie nowej komórki

q->wartosc=x; q->nastepny=NULL;

if (inf.qlowa==NULL)    // lista pusta?

inf.glowa-inf.ogcn-q; else {

(inf.ogon)->nastepny=q; inf.ogon=q;

I

)

Działanie funkcji dorzuć1 jest następujące: w przypadku listy pustej oba pola struktury informacyjnej są inicjowane wskaźnikiem na nowo powstały element. W przeciwnym wypadku nowy element zostaje „podpięty” do końca, stając się tym samym ogonem listy.

Oczywiście, możliwe jest dokładanie nowego rekordu przez pierwszy element listy (wskazywanej zawsze przez pewien łatwo dostępny wskaźnik, powiedzmy ptr),