ALG5

5.1 Listy jednokierunkowe 105

Na rysunku 5-7 możemy przykładowo prześledzić jak powinna być wykonywana fuzja pewnych dwóch list x-(1.3,9) i y=(2,3,14), tak aby w jednej z nich znalazły się wszystkie elementy * i y oczywiście posortowane (w naszym przykładzie w kierunku wartości niemalejących).

Najmniejszym z dwóch pierwszych elementów list jest 1 i on też będzie stanowił zaczątek „nowej” listy. „Następnikiem” tego elementu będzie fuzja dwóch list: x' = (3,9) i y=(2.3,14). Jak dokonać fuzji list a^-' i y? Dokładnie tak samo: bierzemy element 2, który jest najmniejszy z dwóch pierwszych elementów list x' i y... Można tak rekurencyjnie kontynuować aż do momentu, gdy natrafimy na przypadki elementarne: jeśli jedna z list jest pusta, to fuzją ich obu będzie oczywiście ta druga lista. Na tej zasadzie jest skonstruowana procedura fu-zja(obl,ob2), która wywołana z dwoma parametrami obi i oh2 zwróci w' liście obi sumę elementów list obi i ob2. Lista ob2 jest w wyniku tej operacji zerowana, choć jej całkowite usunięcie pozostaje ciągle w gestii programisty (taki jest nasz wybór - równie dobrze można by to zrobić od razu).

Rys. 3- 7.	etap 0
: Fuzja list
na przykładzie.	etap 1
	etap 2
	etap 3
	etap 4
	etap 5
	etap 6

CIHEKEh HHI>® HHIKU¹ Lć_HZ>0) HUTNIKU {EHE* OZHEM3⁴ EEIKIMIHnLhB)

Nasze zadanie wykonamy w dość nietypowy dla C++ sposób, który ma na celu ukazanie zakresu możliwych zastosowań tzw. funkcji zaprzyjaźnionych z klasą. Przypomnijmy, iż są to funkcje (lub procedury), które nie będąc metodami danej klasy, mają dostęp do zastrzeżonych pól private i protccted) obiektu, którego adres został im przekazany jako jeden z parametrów wywołania. Ponieważ nie są to metody, nie mogą być wywoływane w ramach notacji z kropką, a ponadto obiekt, na klóry mają działać, musi im zostać przekazany w sposób jawny - na przykład poprzez swój adres.

Fuzję list wykonamy w dwóch etapach. Wpierw przygotujemy prostą funkcję, która otrzymując dwie posortowane listy a i b. zwróci jako wynik listę, która