ALG6

106 Rozdziała. Strukturydanjt 5.1

będzie ich fuzją. Rekurencyjny zapis tego procesu jest bardzo prosty i zbliża* stylem do rozwiązywania problemów listowych w takich językach jak Lisph Prolog:

ELEMENT ■‘sortuj (ELEMENT *a, ELEMENT »b)

(

if (a=-NULL) return b; if (b—NULL) return a;

if (a->wartosc<=b->wart03c)

i

a->nastepny=sortuj(a->nastepny,b); return a;

} a 1 se

{

b->nastepny=sortuj(b->nastepny,a); return b;

I

)

Dysponując już funkcją sortuj możemy zastosować ją procedurze fuzja, która będąc | „zaprzyjaźnioną” z klasą LISTA, może dowolnie manipulować prywatnymi] komponentami list x i y, które zostały jej przekazane w wywołaniu.

void fuzja(LISTA dx,LISTA Sy)

t

II listy a i b muszą być posortowane ELEMENT ■a=x.inf.gicwa,*b=y.inf.głowa;

ELEMENT *wynik=sortuj(a,b);

x. inf.glowa=wynik;

if(x.inf.ogcn->wartosc<=y.inf.ogon->wartosc) x.inf.ogon=y.inf.ogon; else

x.inf.ogon-x.inf.ogon;

y.    zeruj () ;

I

Celowo znacznie rozbudowana funkcja main ilustruje sposób korzystania z opisanych wyżej funkcji. Do ohu list są dołączane elementy tablic, następnie ma miejsce testowanie niektórych metod oraz sortowanie dwóch list poprzez ich

fuzję.

void main()

(

LISTA II,12; const n=6;

int tabl[n] = {2,5,-11,4,14,12};

II każdy element tablicy zostanie wstawiony do listy cout << "NnLl = ”;

for (int i=0; i<n; 11.dcrzuc2(tabl[i++]));

11.wypisz();    II wypisz 11

int tab2[n] = {9,6,77,1,7,4};