ALG7
5.6. Drzewa i ich reprezentacje 147
Numery znajdujące się przy węzłach mają charakter wyłącznie ilustracyjny - ich wybór jest raczej dowolny i nie podlega żadnym szczególnym regułom... chyba żc sobie sami je wymyślimy na użytek konkretnej aplikacji. W ramach kolejnej konwencji umówmy się, że jeśli ojciec[x] jest równy*, to mamy do czynienia z pierwszym elementem drzewa.
Teraz, gdy już wiemy, jak reprezentować drzewa wykorzystując dostępne w C i i (oraz w każdym nowoczesnym języku programowania) mechanizmy, spróbujmy popatrzeć na możliwe sposoby przechadzania się po gałęziach drzew'...
5.6.1.Drzewa binarne i wyrażenia arytmetyczne
Nasze rozważania o drzewach będziemy prowadzić poprzez prezentację dość rozbudowanego przykładu, na podstawie którego zobrazowane zostaną fenomeny, z którymi programista może się zetknąć, oraz mechanizmy, z których będzie on musiał sprawnie korzystać w celu efektywnego wykorzystania nowo poznanej struktury danych.
Problematyka będzie dotyczyła kwestii zaanonsowanej już na rysunku 5 - 22. Zobaczyliśmy tam, że drzewo doskonale się nadaje do reprezentacji informatycznej wyrażeń arytmetycznych, bardzo naturalnie zapamiętując nie tylko informacje zawarte w wyrażeniu (tzn. operandy i operatory), ale i ich logiczną strukturę, która daje się poglądow-o przedstawić właśnie w postaci drzewa.
Przypomnijmy jeszcze raz typ komórki, który może służyć - zgodnie z ideą przedstawioną na rysunku 5 - 22 - do zapamiętywania zarówno operatorów (ograniczymy się tu do: * i do dzielenia wyrażonego przy pomocy : lub /),
jak i operandów (liczb rzeczywistych).
wyrazen.cpp
struct wyrażenie (
double val; char op;
wyrażenie *lewy,*prawy;
);
Inicjacja takiej komórki determinuje późniejszą interpretację jej zawartości. Jeśli w polu ‘op’ zapamiętamy wartość ‘0’, to będziemy uważali, że komórka nie jest operatorem i wartość zapamiętana w polu val ma sens. W odwrotnym zaś przypadku będziemy zajmowali się wyłącznie polem op’ bez zwracania uwagi na to, co znajduje się w val. Popatrzmy na rysunek 5 - 24, który ukazuje kilka pierwszych etapów tworzenia drzewa binarnego wyrażenia arytmetycznego.
Do tworzenia drzewa użyjemy dobrze nam znanego z poprzednich dyskusji stosu (patrz §5.3). Tym razem będzie on służył do zapamiętywania wskaźników do rekordów typu struci wyrażenie, co implikuje jego deklarację przez STOS<wyrażenie *> s (Jak widać warto było raz się pomęczyć i stworzyć stos w postaci klasy szablonowej).
Wyszukiwarka
Podobne podstrony:
ALG5 5.6. Drzewa i ich reprezentacje 145 sposobu korzystania z takiej reprezentacji. Otóż, dowolne
ALG9 5.6. Drzewa i ich reprezentacje 149 stwierdzeniem, że z punktu widzenia komputera ON P jest is
ALG1 5.6. Drzewa i ich reprezentacje 151 Jak łatwo zauważyć, w zależności od sposobu przechadzania
zem uznania dla ich wytężonej pracy i osiągnięć, znajduje się wielu naszych uczniów. W roku szkolnym
Scan5 27. Numery znajdujące się na tablicy ostrzegawczej wskazują: znaki czarne, tlo
Fiza 7 7. W pionowym cylindrze zamkniętym ruchomym tłokiem znajduje się ni=2kg tlenu. Po dc: — Tm do
49556 Scan16 102. Numery znajdujące się na tablicy barwy pomarańczowej wskazują: tło pomarańczowe zn
ozdabianie?korowanie potraw garnierowanie food?koration?co str 1 (76) Warzywa różne PRZYGOTOWANIE KA
84143 mleko biotechnologia1 szczepionki eliminującej ich hodowlę w zakładach mleczarskich. Znajdują
942874 01 djvu 354 ADOLF BECK nym znajduje się zbita wiązka włókien, które również ulegają zwyrodni
ALG!3 8.2. Nowe algorytmy poszukiwań 213 Analogiczny przykład znajduje się na rysunku 8-5. 8.2. Nowe
Ciałka bulawkowate - Golgiego W ścięgnach, w pobliżu ich przejścia w tkankę mięśniową, znajdują się
więcej podobnych podstron