Strukture podataka-2008/09

Malisa757 · **Poslato:** 25.08.2009. 11:19:28

da li mozes da nam objasnis ovaj kod:

Kod:

public static void stampaj(Stek s) {
if (s.Prazan()) return;
int broj = s.Izbaci();
stampaj(s);
System.out.println(broj);
}

Prvo, nije koriscena metoda ubaci, a pise u tekstu da moze (sto ne znaci da mora). Drugo, s.o.p nije u rekurziji, pa ce se samo jednom izvrsiti, a potrebno je odstampati sve elemente ne jedan samo.

Djeka · **Poslato:** 25.08.2009. 11:24:09

Dalje, ovo BST stablo i opadajući redosled listvovi:

Poenta je dakle štampati listove, jel tako? Pa dobro, štampaćemo listove. Posmatrajte ovo kao normalan prolaz kroz stablo, koji obezbeđuje prolazak po opadajućem redosledu (mislim da je postfix obilazak), a štampanje se dešava samo kada je čvor kojem pristupamo list (nema dece):

Koliko se sećam, postfix je DESNI KOREN LEVI:

public static void stampajListoveOpadajuce(Cvor c) {
if (c == null) return;
stampajListoveOpadajuce(c.desni);
if (c.desni == null && c.levi == null) System.out.println(c);
stampajListoveOpadajuce(c.levi);
}

P.S. Zašto ne rade ovi tagovi <i> i <b> ??? Ah vidim... BBCode[/quote][/u]

Djeka · **Poslato:** 25.08.2009. 11:26:58

A ovo sa stekom, hajde...

Koliko vidim, to je zadatak bio da se stek ištampa u obrnutom redosledu. Siguran sam da je Kosta stavio da mora stek ostati nepromenjen... Nisam razumeo šta znači skraćenica s.o.p nije u rekurziji, izvini...

Ali, metoda je ok, osim što fali vraćanje elementa u stek, odmah nakon štampanja... Onda je dobra!

Djeka · **Poslato:** 25.08.2009. 11:29:14

E, a ovaj palindrom, evo vam i to:

private boolean jednaki(Cvor c1, Cvor c2) {
if (c1 == null && c2 == null) return true;
if (c1 == null || c2 == null) return false;
if (c1.podatal != c2.podatak) return false;
return true;
}

private int prebrojBezBlanko(Cvor prvi) {
int broj = 0;
while(prvi != null) {
if (prvi.podatak != ' ') broj++;
prvi = prvi.sledeci;
}
return broj;
}

public static boolean jePalindrom(Cvor prvi) {
// provera da li postoji vise od jednog cvora
if (prvi == null || prvi.sledeci == null) return true;

int broj = prebrojBezBlanko(prvi);

Cvor poslednji = prvi.prethodni;

for (int i=0; i<broj/2; i++) {
if (!jednaki(prvi,poslednji)) return false;
prvi = prvi.sledeci;
while (prvi.sledeci.podatak == ' ') prvi = prvi.sledeci;
poslednji = poslednji.prethodni;
while (poslednji.prethodni.podatak == ' ') poslednji = poslednji.prethodni;
}
return true;
}

Mrzi me da kuckam objašnjenja, tj. nemam vremena, moram da učim. Ako nešto nije jasno, cimajte ovde, pa ako stignem odgovoriću. Kolege, srećno!

Djeka · **Poslato:** 25.08.2009. 11:30:00

I da, slučajno stoji da je metoda static, nepotrebno je, tj. morale bi sve biti static... Pozdrav!

Malisa757 · **Poslato:** 25.08.2009. 11:35:11

Djeka je napisao:

A ovo sa stekom, hajde...

Koliko vidim, to je zadatak bio da se stek ištampa u obrnutom redosledu. Siguran sam da je Kosta stavio da mora stek ostati nepromenjen... Nisam razumeo šta znači skraćenica s.o.p nije u rekurziji, izvini...

Ali, metoda je ok, osim što fali vraćanje elementa u stek, odmah nakon štampanja... Onda je dobra!

Da li je ovako ok?

Kod:

public static void stampaj(Stek s) {
if (s.Prazan()) return;
int broj = s.Izbaci();
stampaj(s);
System.out.println(broj);
broj=s.Ubaci();
}

s.o.p je system.out.println, i ono sto mene buni je sto se to stampanje samo jednom poziva (nakon zavrsetka rekurzije).

Djeka · **Poslato:** 25.08.2009. 11:42:07

Kako jednom? Zapravo, poziva se svaki put kada uđeš u rekurziju. Svaki put kada se pozove rekurzivna metoda (i izvrši), nakon toga ide štampanje...

Posmatraj, na primer, samo prvo pozivanje, pa će ti biti jasno. Evo, idemo u koracima:

1) pita da li je prazan stek (predpostavimo da nije, čisto da bi nešto radila metoda)
2) U promenljivu broj sačuvamo element sa vrha steka, čime smo smanjili broj elemenata
3) Pozovemo metodu stampaj(s)
- ovde više ne gledamo, tu će se nešto desiti, samo posmatraj kao običnu metodu
- dakle ona se izvršava, pa se izvršava....

4) Ištampamo element

Svaki ulazak u rekurziju daće ovakav algoritam, tako da će biti onoliko štampanja koliko puta se u rekurziju uđe se NEPRAZNIM stekom, a to je tačan broj elemenata...

Malisa757 · **Poslato:** 25.08.2009. 11:50:55

Znaci kod rekurzije cela metoda ce da se izvrsi do kraja, pa ce onda da se vrati na pocetak, a ne da ce deo napisan posle rekurzije da se izvrsi na samom kraju?

To kako si mi objasnio, mi izgleda kao obicno stampanje. Ali pretpostavljam da gresim. Da li bi mogao da prepravis taj kod da obicno stampa (u normalnom redosledu, tj posto je stek u pitanju sa vrha na dno), kako bih video gde gresim.

I zaboravio si da mi kazes da li je ovako dobro napisana metoda:

public static void stampaj(Stek s) {
if (s.Prazan()) return;
int broj = s.Izbaci();
stampaj(s);
System.out.println(broj);
broj=s.Ubaci();
}

Djeka · **Poslato:** 25.08.2009. 11:59:49

Zapravo, sve ti je odgovoreno. Prvo pitanje mi je toliko konfuzno, da nemam odgovor na njega. Dalje, nikako nije obično štampanje, pošto prvo ulaziš u štampanje sledećeg elementa. Obično bi izgledalo nekako ovako:

public static void stampaj(Stek s)
{
if (s.Prazan()) return;
int broj = s.Izbaci();
System.out.println(broj);
stampaj(s);
s.Ubaci(broj);
}

Nije ti dobra tvoja metoda, umesto broj=s.Ubaci(); treba da stoji s.Ubaci(broj); Napisao sam ti u nekoj od prethodnih poruka koja izmena je u pitanju...

Malisa757 · **Poslato:** 25.08.2009. 12:17:28

Evo kako ja tumacim taj kod za obrnuto stampanje koji me muci:

1. Linija metode prihvata dati stek, neka to bude 3,2,1 stek gde je 3 pocetak a 1 kraj
2. Proverava da li je prazan, ako jeste prekida se izvrsavanje metode
3. Poziva se metoda izbaci koja izbacuje 3
4. Nakon toga ide rekurzija koja ce izbaciti 2 pa 1 tako da na kraju rekurzije imamo stek 1,2,3
5. Linija je stampanje, koja prihvata promeljivu broj i stampa je. U ovom slucaju odstampace 1.
6. Linija ubacuje promenljivu broj u pocetni stek tako da ce sada 1 biti na dnu steka kao sto i treba po zadatku.

I to je to, ne vidim kada i zasto ce se odstampati ostatak steka.

Izvini sto sam dosadan, ali me zaista muci ova metoda.

Malisa757 · **Poslato:** 25.08.2009. 12:21:16

Benestanti je napisao:

Da li neko moze da mi objasni sta je postfiksniP i kako radi na sledecem primeru:

................................50
............................../.....\
............................ 25.....60
.........................../....\.......\
.........................10....30.....70

I za kraj, da li bi mogao ti, ili neko drugi od kolega da nam napise sta ce biti rezultat postfiksnog stampanja, prefiksnog i infiksnog stampanja ovog stabla?

Simpatique · **Poslato:** 25.08.2009. 12:31:51

piksifort je napisao:

Jel moze neko da objasni zasto kada implementiramo red preko niza u metodama izbaci i ispisi imamo onaj deo p=++p % niz.length; i kod for petlje i = ++i % niz.length tj sta ovi redovi znace (sta rade) ?

verovatno si mislio na ovo:

p=(p==niz.length-1)?0:p+1;
p=++p%niz.length;

to ti je skraceno za:

if(p==niz.length-1) p=0;
else p++;

sad pretpostavljam da znas sta znaci

Elem, zar red moze da se implementira i drugacije sem preko niza? Ne mogu da se setim...

Malisa757 · **Poslato:** 25.08.2009. 12:42:39

Moze preko liste.

Tin@ · **Poslato:** 25.08.2009. 12:51:16

Malisa757 je napisao:

Benestanti je napisao:

Da li neko moze da mi objasni sta je postfiksniP i kako radi na sledecem primeru:

................................50
............................../.....\
............................ 25.....60
.........................../....\.......\
.........................10....30.....70

I za kraj, da li bi mogao ti, ili neko drugi od kolega da nam napise sta ce biti rezultat postfiksnog stampanja, prefiksnog i infiksnog stampanja ovog stabla?

Prefiksno (koren-levo-desno)
Infiksno (levo-koren-desno)
Postfiksno (levo-desno-koren)

Prefiksno: 50,25,10,30,60,70
Infiksno: 10,25,30,50,60,70
Postfiksno: 10,30,25,70,60,50

Evo, al' ako ne verujes meni, cekaj Djekica ili nekog drugog kolegu!

Malisa757 · **Poslato:** 25.08.2009. 14:43:16

ih...

verujem ja tebi!

ipak si ti,

tatina programerka:P

Sta vise, poklapa se sa onim sto sam ja napisao pre nego sto sam procitao tvoj odgovor.

Djeka · **Poslato:** 25.08.2009. 15:47:35

Malisa757 je napisao:

Evo kako ja tumacim taj kod za obrnuto stampanje koji me muci:

1. Linija metode prihvata dati stek, neka to bude 3,2,1 stek gde je 3 pocetak a 1 kraj
2. Proverava da li je prazan, ako jeste prekida se izvrsavanje metode
3. Poziva se metoda izbaci koja izbacuje 3
4. Nakon toga ide rekurzija koja ce izbaciti 2 pa 1 tako da na kraju rekurzije imamo stek 1,2,3
5. Linija je stampanje, koja prihvata promeljivu broj i stampa je. U ovom slucaju odstampace 1.
6. Linija ubacuje promenljivu broj u pocetni stek tako da ce sada 1 biti na dnu steka kao sto i treba po zadatku.

Pa ne znam kako si tako skapirao rekurzivnu metodu. Nije tako...

Pazi, ovaj korak 4. tvoj nije tačan! Na kraju rekurzije stek je prazan! Zato se poslednja pozvana metoda vraća nazad, izazivajući štampanje i ponovno punjenje steka, naopačke.

stek 3,2,1

stampaj(s) {
---nije prazan;
---broj = 3;
---stampaj(s) {
------nije prazan;
------broj = 2;
------stampaj(s) {
---------nije prazan;
---------broj = 1;
---------stampaj(s) {
------------prazan je; return;
---------}
---------STAMPAM broj (1);
---------UBACUJEM (1);
------}
------STAMPAM broj (2);
------UBACUJEM (2);
---}
---STAMPAM broj (3);
---UBACUJEM (3);
}

Malisa757 · **Poslato:** 25.08.2009. 22:13:16

Zna li neko da uradi 2. zadatak sa 1. kolokvijima ove godine?

Potrebno je ispisati elemente rede u redosledu od zadnjeg ubacenog do prvog.
Takodje, u istom zadatku potrebno je napisati klazu za red implementiran preko niza.

Kako?

LomaX · **Poslato:** 25.08.2009. 23:27:01

Zna li neko raspored po salama gde polazemo sutra???

Malisa757 · **Poslato:** 25.08.2009. 23:39:40

U junu nije izasao raspored ni na sajtu fona, ni sajtu struktura, ni na fakultetu... Nije ni sada. Videcemo sutra. To su jedine tri opcije gde moze da se pojavi.

Tin@ · **Poslato:** 25.08.2009. 23:42:21

Ne postoji raspored, udjes gde ima mesta!

Ajde, srecno vam bilo sutra! :srecno:

A ti mali, ne moras sve bas znati...

Benestanti · **Poslato:** 26.08.2009. 00:09:00

Jel moze neko da mi kaze da li roditelji u binarnom i BST stablu moraju da imaju dvoje dece ili nijedno, tj. da ne mogu da imaju samo jedno dete?

Molim vas da mi sto pre odgovorite, mnogo mi je bitno!!

Malisa757 · **Poslato:** 26.08.2009. 00:11:31

Ne. Mogu da imaju i jedno dete.

Malisa757 · **Poslato:** 26.08.2009. 00:32:31

Hajde molim Vas, napisite odgovore na sledeca pitanja:

8. Šta je hashing i kako se rešava problem kolizije ključeva otvorenim adresiranjem.

8. 8. Šta je hashing i kako se rešava problem kolizije ključeva olancavanjem.

Dobro bi bilo da napisete i primere za to. U junu je ovo bilo.

I ako je stablo reda 5, koliko najmanje moraju listovi da imaju kljuceva? Po formuli je to (n/2)-1, ali to je 1.5. Kako se zaokruzuje, na 1 ili na 2?

Benestanti · **Poslato:** 26.08.2009. 10:18:57

Hvala... Jos nesto, jel unutrasnji cvorovi predstavljaju cvorove koji imaju bar jedno dete?

Malisa757 · **Poslato:** 26.08.2009. 10:29:04

FONForum

Strukture podataka-2008/09

Ko je OnLine