ALG 9

5.1. Listy jednokierunkowe 99

stawałby się on wówczas automatycznie głową listy i musiałby zostać zapa miętany przez program, aby nie stracić dostępu do danych:

ELEMENT    ¹q=new ELEMENT;    //    a)

q->wartosc=x;    //    b)

q->nastepny=ptr;    //    c)

W tym I dalszych przykładach przyjmowane jest założenie, że przydział pamięci ZAWSZE kończy się sukcesem. W rzeczywistych programach jest to przypuszczenie dość niebezpieczne i warto sprawdzać, czy istotnie po użyciu instrukcji ELEMENT ¹q=new ELEMENT wartości q nie zostało przypisane NULL! Z uwagi na chęć zapewnienia klarowności prezentowanych algorytmów, tego typu kontrola zostanie w książce pominięta, podczas realizacji „prawdziwego” programu takie niedopatrzenie może się okazać dość przykre w skutkach._ _

Kod ten może być zilustrowany schematem z rysunku 5-4.

Rys. 5-4.	a) Usta pierwotna	ptr
Dołączanie elementu na jej po	b) nowa komórka	q
czątek.	c) zmodyfikowana Usta	q

•GS- NULL

NULL

Sposób podany powyżej jest poprawny, ale pamiętajmy, że dokładając nowe elementy zawsze na początek listy tracimy istotną czasami informację na temat kolejności nadchodzenia elementów!

Rys. 5 - 5.

Dołączanie elementu listy z sortowaniem

Nowy element (narysowany pogrubioną kreską) może zostać wstawiony na początek (a), koniec (b) listy, jak i również gdzieś w jej środku (c). W każdym

1

wiele bardziej złożona jest funkcja dołączająca nowy element w takie miejsce, aby całość list)' była widziana jako posortowana (tutaj: w kierunku wartości niemalejących). Ideę przedstawia rysunek 5-5, gdzie możemy zobaczyć sposób dołączania liczby 1 do już istniejącej listy złożonej z elementów -1, 3 i 12.