Cześć!
W swoim programie mogę użyć jedynie tablic o maksymalnym rozmiarze 4096 bajtów (1024 inty). Implementuję drzewo binarne na tablicy(bez żadnych struktur), którego wysokość może wynosić nawet 30.
Jak rozwiązać ten problem? Myślę, że należy odpowiedniej strukturze pamiętać adresy przydzielonych tablic dla indeksów 0...1023, 1024...2047 itd. Tylko w jakiej i jak by to miało wyglądać?
Z góry dzięki. Pzdr
W sumie 30 to nie takie duze drzewo, daj po prostu tablice dynamiczna(malloc & free || new & delete). Natomiast ja bym zrobil z tej tablicy tablice wskaznikow na struktury dynamiczne, opisujace elementy drzewa ;)
No właśnie na tym polega problem, że nie mogę po prostu dynamicznie zaalokować zwykłej tablicy, bo żeby program działał dla drzewa o wysokości 30 to ta tablica musi mieć więcej niż 4096 bajtów, co jest niezgodne z warunkiem programu.
Użycie struktur do zaimplementowania drzewa również odpada.
Drzewo musi być zaimplementowane na tablicy, gdzie potomkami są odpowiednie indexy(2i - lewy syn, 2i +1 - prawy syn).
Struktur mogę użyć jedynie do zarządzania pamięcią, tylko nie wiem właśnie jak to zrobić...
Jak to nieduze drzewo ? Przy wysokosci 30 samych lisci bedzie 2^29 = 536870912 :/ nie wspominajac juz o wezlach "wewnetrznych" drzewa.
Moze mozesz zrobic cos takiego:
uzyj tej swojej tablicy do trzymania list elementow na danym poziomie drzewa - czyli: tab[0] = {korzen}, tab[1] = {dziecko 1 korzenia, dziecko 2 korzenia}, tab[2] = {wnuk 1 korzenia, wnuk 2 korzenia, wnuk 3 korzenia, wnuk 4 korzenia} itp.
Wtedy musisz jedynie zaimplemntowac (wykorzystac STL'a, jezeli mozesz) liste do trzymania elementow (zarzadzanie pamiecia ;p) i tyle. I mozesz trzymac elementy nawet w drzewie o 1024 poziomach.
Dzięki za odpowiedź, niestety nie mogę korzystać z STL, zapomniałem o tym wspomnieć :-|
A może jakieś rozwiązanie z tablicami wskaźników za tablice czy coś w tym stylu?
Z ta wysokoscia to jakies zacmienie mialem, bo policzylem 2*30+1 zapominajac o przyroscie na kazdym poziomie ;p
Co do tego, ze nie mozesz uzyc STL'a to sam zaimplementuj liste i po sprawie, ale dlaczego nie mozesz uzyc struktur to nie wiem, przeciez drzewo bedziesz mial na tablicy, z tym ze kazdy element tej tablicy by wskazywal na dany element drzewa, opisany struktura.
Co do tych list, to to trochę zbyt skompilkowane i na pewno można to zrobić o wiele prościej, wykorzystując tablice wskaźników. Ktoś ma pomysł jak to zrobić właśnie przy użyciu tablic wskaźników?
kopiec, ang. heap
Mam zaimplementować kopiec? Jakby ta struktura miała się do przechowywania indeksów tablicy?