ALG3

5.5. Sterty i kolejki priorytetowe 143

Wystarczy bowiem dowolną tablicę do posortowania wpierw' zapamiętać w stercie używając metody wstaw, a następnie zapisać ją „od tylu” w miarę obsługiwania przy pomocy metody nbslur

(łinclude "stcrta.h"

int tab[14]»{12,J,-12, 9,34,23, 1,81,45, 17,9,23,11,4 ) ; void main()

{

Sterta s(145 ; for (int 1=0;i<14;i++) s.wstaw(tab[ i. ] ) ; for (i—14;i>0;i—) tab[i-l]=s.obsłuż(); cout<<"tablica posortowana:\n"; for (i=0;i<14;i++)

cout << "    " << tab[i];

)

Jest to oczywiście jedno z możliwych zastosowań sterty - prosta i efektowna metoda sortowania danych, średnio zaledwie dwa razy wolniejsza od algorytmu Quicksort (patrz opis algorytmu Ouicksort).

Powyższa procedur a może być jeszcze bardziej przyspieszona poprzez włączenie kodu metod wstaw i obsłuż wprost do funkcji sortującej, tak aby uniknąć zbędnych i kosztownych wywołań procedur alnych. W tym przypadku zachodzi jednak potrzeba zaglądania do prywatnych informacji klasy - tablicy t (patrz plik sterta.h), zatem procedura sortująca musiałaby być funkcją zaprzyjaźnioną. Łamiemy jednak w tym momencie koncepcję programowania obiektowego (separacja prywatnego „wnętrza” klasy od jej „zewnętrznego” interfejsu)!

Jest to cena do zapłacenia za efektywność - funkcje zaprzyjaźnione zostały wprowadzone do C++ zapewne również z uwagi na użycie tego języka do programowania aplikacji wyjściowych, a nie tylko do prezentacji algorytmów (jak to jest w przypadku Pascala, który zawiera celowe mechanizmy zabezpieczające przed używaniem dziwnych sztuczek... bez których programy działałyby zbyt wolno na rzeczywistych komputerach).

5.6. Drzewa i ich reprezentacje

Dyskusją na temat tzw. drzew można by z łatwością wypełnić kilka rozdziałów. Temat jest bardzo rozległy i różnorodność aspektów związanych z drzewami znacznie utrudnia decyzję na temat tego, co wybrać, a co pominąć. W ostatecznym rozrachunku zwyciężyły względy praktyczne: zostaną szczegółowo omówione te zagadnienia, które Czytelnik będzie mógł z dużym prawdopodobieństwem wykorzystać w codziennej praktyce programowania. Bardziej szczegółowe