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

Wyszukiwarka

Podobne podstrony:
ALG9 5,5. Sterty i kolejki priorytetowe 139 liczbę 99 (patrz etap 5). Drzewo ma już 5-clcmentów, za
ALG1 5.5. Sterty i kolejki priorytetowe 141 Treść procedury DoGory nie powinna stanowić niespodzian
ALG7 137 5.5. Sterty i kolejki priorytetowe Jednym z najłatwiejszych sposobów realizacji kolejek pr
ALG3 2.7. Myślenie rekurencyjne 43 Rckurcncyjność naszego zadania jest oczywista, bowiem program wy
p1020975 Co to jest wymiana? 3€ Na dysku znajduje się kolejka długookresowa procesów Z niej procesy
wsk3 Naprawa silników W2B i W! 143 Naprawa silników W2B i W! 143 Rys. 7.39. Dopuszczalne bida wnhi
19085 ZF Bień3 Analiza progu zysku 143 Takie graficzne ujęcie, uwzględniające założenia poprzednieg
4 (617) istnienia błędu indeksu. Wystarcza bowiem wykonać pomiar kąta w obu położeniach lunety i uśr
DSC03752 wieżowi nic wystarcza bowiem kousolacyjna w lar fi symboli- 1 orni W wtrc«ysiv „blask” » „Ż
Kalendarz nie wystarcza: Znaj swoje priorytety Nie wystarcza być zajętym -mrówki są też zajęte. Ważn
4sol 7.5. KOLEJKI PRIORYTETOWE rżenia pozostają kopcami, ale nowy korzeń może naruszać własność kopc
Kolejki i priorytety Procesy oczekujące na zwolnienie procesora mogą mieć różną ważność.
Dlaczego można latać balonem? Do uniesienia balonu wystarczy bowiem wykorzystanie w praktyce prawa f
ET3 9.1. Istota jakości usług 143 • jakość produktu turystycznego jako kompleksu świadczeń, wyrażaj
ALG
3 Przedmowa 13Rozdział 10 Elementy algorytmiki grafów Opis jednej z najciekawszych struktur dany
ALG3 1.3. Proces koncepcji programów 23 pisania jednej linii kodu. Pomijając już jednak tego typu s

więcej podobnych podstron