C/C++ naloga "zahtevno"

4 naročniki

Zdravo, potrebujem pomoč pri realizaciji naloge, ki sem jo dobil pri programiranju2 na faksu. Programirali naj bi v C-ju, vendar bi mi tudi c++ rešitev prišla prav.

Torej, četudi znate rešiti samo del naloge prosim postajte kodo, hvala.

Treemap ©

Napišite program, ki implementira podatkovno strukturo TreeMap iz Jave, kjer namesto rdeče-črnih dreves uporabite navadno binarno drevo (binarni slovar). Za binarni slovar (binarno iskalno drevo) velja, da je ključ v korenu večji od ključa v levem poddrevesu in manjši od ključa v desnem poddrevesu za vsako vozlišče v drevesu.

Pri binarnem slovarju je potrebno implementirati konstruktor (ki ustvari prazno strukturo), destruktor (ki sprosti vse vire, ki jih je zasedla struktura, na primer pomnilnik), metode put(k,v), get(k), clear(), containsKey(k), containsValue(v), isEmpty(), remove(k) in size(). Vrednost elementa naj bo poljuben niz znakov, katerega dolžina ne presega 255 znakov, ključ pa je celo število. Število elementov v tej strukturi naj ne bo omejeno. Vse funkcije naj kot parameter prejmejo kazalec na strukturo.

Delovanje napisanih funkcij preverite v programu, ki najprej zgradi strukturo, katere elemente prebere iz datoteke. Elementi strukture so v datoteki zapisani po vrsticah. V vsaki vrstici je najprej eno celo število, ki predstavlja ključ elementa, temu pa sledi presledek in niz znakov (dolžine največ 255 znakov), ki predstavlja vrednost elementa. Niz z vrednostjo je zapisan v narekovajih. Ko slovar zgradite, ga izpišite (način izpisa je poljuben, le na začetku naj se v oklepaju izpiše tudi njegova dolžina). Operacije nad zgrajenim slovarjem so zapisane v drugi datoteki, vsaka v svoji vrstici, in sicer v naslednji obliki (vrednost je vedno zapisana v narekovajih, med oznako operacije, ključem in vrednostjo pa je presledek):

p ključ "vrednost" pomeni dodajanje elementa v slovar,
g ključ pomeni izpis vrednosti elementa s tem ključem,
k ključ vrne 1, če je podan ključ v slovarju, sicer vrne 0,
v "vrednost" vrne 1, če je podana vrednost v slovarju, sicer vrne 0,
r ključ pomeni brisanje elementa iz slovarja.

Pred brisanjem elementa iz slovarja vedno najprej preverite, ali ni slovar slučajno prazen.

Po vsaki operaciji naj program na zaslon izpiše rezultat operacije oziroma trenutno velikost slovarja (v oklepaju) in njegove elemente. Na koncu slovar tudi izpraznite in uničite (klic destruktorja). Imeni obeh datotek sta podani kot argumenta programa.

Primer datoteke z elementi slovarja:

5 "to je prvi niz"
1 "drugi niz"
7 "vrednost v slovarju"
3 "se ena vrednost ..."

Primer datoteke z operacijami nad slovarjem:

p 2 "dodamo ta niz"
p 2 "zamenjamo niz"
g 5
g 3
g 7
k 2
k 3
r 3
v "dodamo ta niz"

Primer izpisa za zgornjo datoteko (način izpisa slovarja je poljuben):

(4) 1 "drugi niz", 3 "se ena vrednost ...", 5 "to je prvi niz", 7 "vrednost v slovarju"
(3) 1 "drugi niz", 5 "to je prvi niz", 7 "vrednost v slovarju"
(4) 1 "drugi niz", 2 "dodamo ta niz", 5 "to je prvi niz", 7 "vrednost v slovarju"
(4) 1 "drugi niz", 2 "zamenjamo niz", 5 "to je prvi niz", 7 "vrednost v slovarju"
"to je prvi niz"
0
"vrednost v slovarju"
1
0
0

In kje se ti je ustavilo?

Če sem prav razumel, on hoče, da mu celo nalogo nekdo naredi ali pa vsak en del nje.

Pa ej, to sem danes na enem blogu videl, RSS no zapisa potem nisem bral :) .

mah kje se mi je ustavilo...na začetku. Pojma nimam kako bi se lotil zadeve.
Nek načrt bi mi zelo prav prišel...ne rabim cele kode(no škodila nebi).

Verjetno bi bilo za zacetek fino, ce ves, kaj je to TreeMap in kaj je to binarno drevo (binary tree) in kaj je to binarno iskalno drevo (binary search tree). Na tej zadnji povezavi na Wikipedio imas tudi nekaj primerov implementacij metod, ki jih od tebe zahteva naloga, v razlicnih jezikih, med drugim tudi v C++.

ok, hvala. Si bom pogledal, če bom imel kakšno vprašanje, pa sporočim.

Lp