stóg[kopiec]- sprawdzenie

iveldion
Użytkownik
Użytkownik
Posty: 48
Rejestracja: 8 cze 2008, o 14:27
Płeć: Mężczyzna
Lokalizacja: oświęcim
Podziękował: 9 razy

stóg[kopiec]- sprawdzenie

Post autor: iveldion »

Zilustruj kolejne kroki procedury budującej stóg dla następującej tablicy oraz napisz jak bd wyglądała tablica po budowie stogu:

Kod: Zaznacz cały

T=[ 21, 18, 49, 15, 37, 17, 27,51,20]
tak będzie wyglądało drzewo?
tablica będzie wyglądała

Kod: Zaznacz cały

51, 49, 37, 27, 21, 20, 18 , 17 , 15
dobrze zrobiłem to zadanie?
Crizz
Użytkownik
Użytkownik
Posty: 4094
Rejestracja: 10 lut 2008, o 15:31
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 12 razy
Pomógł: 805 razy

stóg[kopiec]- sprawdzenie

Post autor: Crizz »

Hmmm... czy przyjmujesz zasadę, że synowie węzła o indeksie \(\displaystyle{ i}\) znajdują się pod indeksami \(\displaystyle{ 2i+1,2i+2}\)?
iveldion
Użytkownik
Użytkownik
Posty: 48
Rejestracja: 8 cze 2008, o 14:27
Płeć: Mężczyzna
Lokalizacja: oświęcim
Podziękował: 9 razy

stóg[kopiec]- sprawdzenie

Post autor: iveldion »

nie, jak to mam zrobić z tym wzorem ;>
Crizz
Użytkownik
Użytkownik
Posty: 4094
Rejestracja: 10 lut 2008, o 15:31
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 12 razy
Pomógł: 805 razy

stóg[kopiec]- sprawdzenie

Post autor: Crizz »

Generalnie chodzi mi o to, czy wygląda to tak (strzałki wskazują synów węzła):



Uploaded with

Tablica, którą podałeś, odpowiada narysowanemu kopcowi. Rozumiem, że jednak kierowałeś sie powyższą zasadą.

Nie wiem, czy w zadaniu chodzi o to, że budujesz kopiec taki, jaki wynika z tej początkowej tablicy, a potem coś w nim poprawiasz, czy bierzesz po kolei elementy z tablicy i wrucasz do kopca. Jeśli chodzi o tę drugą opcję, to kopiec wyglądałby inaczej. Generalnie jak budujesz kopiec, to wstawiasz nowy element na pierwsze wolne miejsce w tablicy (tak, żeby nie miała "dziur") i od razu wiesz, gdzie umieszczany jest ten element w kopcu. Potem, jeśli wstawienie tego elementu powoduje naruszenie warunku nałożonego na kopiec (rozumiem, że warunek jest taki, że klucze synów są niewiększe niż klucz ojca, tak?), to przesuwasz go w górę kopca (zamieniasz go miejscami z jego ojcem, potem być może z jego nowym ojcem itd.), aż kopiec znów będzie OK.Przykładowo, dla podanej tablicy kilka pierwszych etapów:

[url=http://img109.imageshack.us/i/koplist2.png/][/url]

Uploaded with [url=http://imageshack.us]ImageShack.us[/url]

Jeśli budowałeś kopiec na tej danej tablicy, ale kierowaleś się taką zasmą zasadą zamieniania węzłów, to powinno być OK.
ODPOWIEDZ