ALG0

100 Rozdział 5. Struktury danyi

z tych przypadków w istniejącej liście trzeba znaleźć miejsce wstawienia, tzn.I zapamiętać dwa wskaźniki: element, przed który mamy wstawić nową komo i element, za którym mamy to zrobić. Do zapamiętania tych istotnych infon cji posłużą nam zmienne przed i pu.

Następnie, gdy dowiemy się „gdzie jesteśmy", możemy dokonać wstawienia nowego elementu do listy. Sposób, w jaki tego dokonamy, zależy oczywiście od miejsca wstawienia i od tego, czy lista przypadkiem nie jest jeszcze pusta. Krótko I powiedziane, niestety realizacja jest dość złożona. Pewne skomplikowanie funkcji dorzuci wynika z połączenia w niej poszukiwania miejsca wstawienia z samym dołączeniem elementu. Równie dobrze można by te dwie czynności rozbić na osobne funkcje nie zostało to jednak uczynione w obecnej wersji.

Istnieją 3 przypadki „współrzędnych” nowego elementu w liście, symbolicznie przedstawione na rysunku 5-6 (zakładamy, że lista już coś zawiera).

Rys. 5 - 6. Wstawianie nowego elementu do	a)	LrH		H		H	-H -1
listy - analiza przypadków.	b)	po =	NULL		_rTL
	^c) I	I3H	Z3	K_	-

przed = NULL

3^JQ4

przed, po * NULL

W zależności od ich wystąpienia zmieni się sposób dołączenia elementu do listy. Oto pełny tekst funkcji dorzuci, która swoje działanie opiera właśnie na idei przedstaw ionej na rysunku 5-6:

void LISTA::dorzuc2(int x) t

II dołączamy rekord na właściwe miejsce II (ver.2 - z "sortowaniem"!

// tworzymy nowy element listy:

ELEMENT *q«new ELEMENT; q->wartosc=x; // wypełniamy jego zawartość

// Poszukiwanie właściwej pozycji na II wstawienie elementu if (pusta())

inf.glowa-inf.ogon-q; q->nastepny=NULL;

I

else //szukamy miejsca na wstawienie (