ALG4

114 Rozdział 5. Struktury danych

stan—ZAKOŃCZ; else {

przcd=po;

po=po->nastepny;

I

Różnica pomiędzy tymi dwiema pętlami while tkwi wyłącznie w warunku instrukcji if. else. Idea naszego rozwiązania jest zatem następująca: napiszmy uniwersalną funkcję, która posłuży do odszukiwania wskaźników przed i po w celu ich późniejszego użycia do dokładania elementów do listy, jak również do ich usuwania. Funkcja ta powinna nam zwrócić oba wskaźniki - posłużymy się do tego celu strukturą LPTRINFO (patrz strona 112), umawiając się, że pole głowa będzie odpowiadało wskaźnikowi przed, a pole ogon - wskaźnikowi po.

Łatwo jest zauważyć, że operacje poszukiwania, wstawiania etc. rozpoczynamy od listy wskaźników, z której zdobędziemy adres rekordu danych (adres ten jest/zostanie zapamiętany w polu adres struktury LPTR. która stanowi element składowy listy wskaźników - patrz rysunek 5 - 9). Dopiero po zmodyfikowaniu wszystkich list wskaźników (a może ich być tyle, ile przyjmiemy kryteriów sortowania) należy zmodyfikować listę danych. Pracy jest - jak widać - mnóstwo, ale jest to cena za wygodę późniejszego użytkowania takiej listy! Pocieszeniem niech będzie fakt, że po jednokrotnym napisaniu odpowiedniego zestawu funkcji bazowych będziemy mogli z nich później wielokrotnie korzystać bez konieczności przypominania sobie, jak one to robią... Przejdźmy już do opisu realizacji funkcji odszukaj_wsk. która zajmie się poszukiwaniem wskaźników przed i po, zwracając je w strukturze LPTR INFO:

LISTA::LPTR_INFO* LISTA::odszukaj_wsk (LISTA::LPTR_INFO *inf,

SLSMSNT *q,

int(‘decyzja)(ELEMENT *ql,ELEMENT *q2>)

<

LPTR INFO *res=now LPTR_INFO;

res->glowa=res->ogon=NULL;

if (inf->glowa==NUT,T.)

return(res); // lisLa pusta!

else

{

LPTR *przed,*pos;

przcd-NULL;

pos=inf->giowa;

onum (SZUKAJ,ZAKOŃCZ) stan=SZUKAJ; while ((stan==S2UKAJ) ś& (pos!=NULL)) if (decyzja(pos-sadres,q)) stan=ZAKONCZ;

II znaleźliśmy miejsce w którym element else    // istnieje (albo ma być wstawiony)

(    // przemieszczamy sie w poszukiwaniach

przed-pos;

pos=pos->nastepny;