Strukture podataka-2008/09

Gorbash · **Poslato:** 15.09.2009. 14:00:10

vlajkoZA je napisao:

http://www.postimage.org/image.php?v=gx1TyIv0
(Septembar2)

Jel' samo meni ne radi ova slika? Ako da, jel' moze neko opet da je uploaduje, meni nece da je otvori...

HYBRID · **Poslato:** 15.09.2009. 14:33:55

Jel zna neko da li mi vazi odbranjen prvi domaci i u ovom roku? (da li mogu samo teorijsko pitanje za drugi deo da radim ili moram i za prvi)?

Gorbash je napisao:

Jel' samo meni ne radi ova slika? Ako da, jel' moze neko opet da je uploaduje, meni nece da je otvori...

evo ti sve:
http://rapidshare.com/files/280410254/jun_i_septembar.rar

::SHOMY · **Poslato:** 15.09.2009. 15:09:29

^ ako to pitanje nisi radio na ispitu vaze ti bodovi i dalje, a ako si radio onda se ponistavaju..

HYBRID · **Poslato:** 15.09.2009. 15:30:19

::SHOMY,
sad prvi put izlazim na ispit. znaci, vazi mi?

::SHOMY · **Poslato:** 15.09.2009. 16:36:06

^ da, tako je rekao asistent kad smo polagali...al' ono mozes da mu posaljes mail da ti potvrdi sta znam..

Gorbash · **Poslato:** 15.09.2009. 20:19:07

Citiraj:

2. Dat je pokazivac na koren BST stabla celih brojeva. Napisati metodu koja ce istampati unutrasnje
cvorove stabla u rastucem redosledu.

Ajd nek neka dobra dusa ovo uradi, pliz.

NotoriouS · **Poslato:** 15.09.2009. 22:07:32

Da li moze da dodje zadatak iz sortiranja, ili sortiranje dolazi samo kao teorijsko pitanje za prvi deo?

Djeka · **Poslato:** 15.09.2009. 22:22:53

Gorbash je napisao:

Citiraj:

2. Dat je pokazivac na koren BST stabla celih brojeva. Napisati metodu koja ce istampati unutrasnje
cvorove stabla u rastucem redosledu.

Ajd nek neka dobra dusa ovo uradi, pliz.

Izvoli...

// Stampanje stabla BST u opadajucem redosledu (samo UNUTRASNJE cvorove)

public static void stampajUnutrasnjeRastuce(Cvor koren) {
stampaj(koren.desni);
stampaj(koren.levi);
}

private static void stampaj(Cvor cvor) {
if (cvor == null) return;
stampaj(cvor.desni);
if (!(cvor.levi == null && cvor.desni == null))
System.out.println(cvor);
stampaj(cvor.levi);
}

Djeka · **Poslato:** 15.09.2009. 22:24:16

I, ovaj sto vas mnogo muci:

// ONAJ za****

Analiza problema:

- imam pokazivac na koren
- imam pokazivac na neki cvor stabla
- tražim minimalni cvor koji je na putanji od korena do datog cvora

Sistematizacija:

- obican algoritam obilaska stabla
- dodatak je što se traži minimum
- dodatak je što se minimum traži samo kada je cvor na putanji!

Implementacija:

Ovo je "okružujuca" metoda:

public static int minNaPutanji(Cvor koren, Cvor cvor) {
return min(koren, cvor,Integer.MAX_VALUE);
}

Ona se poziva i zadužena je da vrati rezultat koji se daje u zadatku. E sad kako...

private static int min(Cvor cvor, Cvor poredni, int globalniMin) {
// provera da li cvor postoji
if ( cvor == null) return Integer.MAX_VALUE;
// provera da li je cvor na putanji do porednog cvora, ako nije, ne moram da ga proveravam uopste (niti njegovu decu)
if ( !naPutanji(cvor,poredni) ) return Integer.MAX_VALUE;
// provera da li je to taj cvor, ako jeste, njega ne racunam, samo one koji su na putu
if ( cvor == poredni ) return Integer.MAX_VALUE;
// uporedim vrednost iz cvora sa globalnim minimumom
if ( cvor.broj < globalniMin ) globalniMin = cvor.broj;
// vrsim proveru u svim potomcima cvora
int min = Math.min(min(cvor.levi,poredni,globalniMin),min(cvor.desni,poredni,globalniMin));
return min;
}

private static boolean naPutanji(Cvor cvor, Cvor poredni) {
if (cvor == null) return false;
if (cvor == poredni) return true;
return naPutanji(cvor.levi, poredni) || naPutanji(cvor.desni, poredni);
}

leptiric · **Poslato:** 16.09.2009. 08:33:58

PLEASE neka neko odgovori na ovo pitanje:
Koji sve tipovi sortiranja od ovih (Selection, Insertion, Bubble, Shell, Heap, Merge, Quick) treba da se nauce teorijski, a za koje od njih ce traziti kod?
:udri:

Raider · **Poslato:** 16.09.2009. 10:38:50

leptiric je napisao:

PLEASE neka neko odgovori na ovo pitanje:
Koji sve tipovi sortiranja od ovih (Selection, Insertion, Bubble, Shell, Heap, Merge, Quick) treba da se nauce teorijski, a za koje od njih ce traziti kod?
:udri:

Uci sve teorijski.

leptiric · **Poslato:** 16.09.2009. 11:40:24

Hvala puno! :yo:

A jel' zna neko neki primer za hashing algoritam- resavanje problema kolizije otvorenim adresiranjem ili olancavanjem zapisa???
To pitanje se provlaci skoro u svakom roku...

dzonizmaj · **Poslato:** 16.09.2009. 13:57:01

Dat je pokazivac na prvi element u jednostruko-spregnutoj listi celih brojeva. Napisati metodu "ubaci"
koja ubacuje novi element nakon prvog elementa koji je veci od njega. Ako takav
element ne postoji, novi element se ubacuje na kraj liste.

public static void Ubaci(Element e) {
if (prvi == null) {
prvi = e;
return;
}
Cvor tekuci = prvi;
while (tekuci.sledeci != null) {
if (tekuci.broj > e.broj) {
e.sledeci = tekuci.sledeci;
tekuci.sledeci = e;
return;
}
tekuci = tekuci.sledeci;
}
tekuci.sledeci = e;
}

- slucaj kada je lista dvostruko spregnuta, razlikuje se SAMO algoritam ubacivanja:

e.prethodni = tekuci;
e.sledeci = tekuci.sledeci;
tekuci.sledeci = e;
e.sledeci.prethodni = e;

- slucaj kada je lista dvostruko spregnuta, razlikuje se SAMO algoritam ubacivanja:

e.prethodni = tekuci;
e.sledeci = tekuci.sledeci;
tekuci.sledeci = e;
e.sledeci.prethodni = e;

Resenje od Milosa Djekica (mdjekic@gmail.com).
Ako iko zeli casove savetujem da odete kod njega mnogo dobro decko objasnjava i sa razumevanjem sto je najbitnije za ovaj predmet.

vladan · **Poslato:** 16.09.2009. 15:28:51

Jel zna neko ovaj zadatak:
Dat je pokazivac na koren BST stabla celih brojeva. Napisati metodu koja ce istampati listove stabala u opadajucem redosledu?

Da i primer za hashing algoritam- resavanje problema kolizije otvorenim adresiranjem ili olancavanjem zapisa? Sta se uopste smatra primerom ovde? U skirpti je bas lose objasnjeno tako da ... ima li neko predstavu sta bi bio odgovor na ovo?

Jel mozda neko pokusavao da debaguje primere sa stablima?
Koji je najbolji nacin da se isprobaju kodovi sa vezbi?

Thnks...

*ivy* · **Poslato:** 16.09.2009. 15:56:42

^ te zadatke imas uradjene par stranica nazad.

::SHOMY · **Poslato:** 16.09.2009. 17:12:08

Citiraj:

2. Dat je pokazivac na koren BST stabla celih brojeva. Napisati metodu koja ce istampati unutrasnje
cvorove stabla u rastucem redosledu.
// Stampanje stabla BST u opadajucem redosledu (samo UNUTRASNJE cvorove)

public static void stampajUnutrasnjeRastuce(Cvor koren) {
stampaj(koren.desni);
stampaj(koren.levi);
}

private static void stampaj(Cvor cvor) {
if (cvor == null) return;
stampaj(cvor.desni);
if (!(cvor.levi == null && cvor.desni == null))
System.out.println(cvor);
stampaj(cvor.levi);
}

A sta bi se menjalo u kodu kada bi pisalo u opadajucem redosledu? Moram da pitam

I kod onih pitanja sa sortiranjem, kada nam trazi primer, jel treba da se ispise onaj kod ili da se nacrta ona slika?

Raider · **Poslato:** 16.09.2009. 17:53:48

::SHOMY je napisao:

Citiraj:

2. Dat je pokazivac na koren BST stabla celih brojeva. Napisati metodu koja ce istampati unutrasnje
cvorove stabla u rastucem redosledu.
// Stampanje stabla BST u opadajucem redosledu (samo UNUTRASNJE cvorove)

public static void stampajUnutrasnjeRastuce(Cvor koren) {
stampaj(koren.desni);
stampaj(koren.levi);
}

private static void stampaj(Cvor cvor) {
if (cvor == null) return;
stampaj(cvor.desni);
if (!(cvor.levi == null && cvor.desni == null))
System.out.println(cvor);
stampaj(cvor.levi);
}

A sta bi se menjalo u kodu kada bi pisalo u opadajucem redosledu? Moram da pitam

I kod onih pitanja sa sortiranjem, kada nam trazi primer, jel treba da se ispise onaj kod ili da se nacrta ona slika?

To i jeste kod za opadajuci redosled.Za rastuci samo stampaj(cvor.desni) i stampaj(cvor.levi) zamene mesta u kodu.

Raider · **Poslato:** 16.09.2009. 17:59:39

::SHOMY je napisao:

I kod onih pitanja sa sortiranjem, kada nam trazi primer, jel treba da se ispise onaj kod ili da se nacrta ona slika?

Ako znas da ispises kod ti napisi,ali dovoljno je da nacrtas sliku.

Raider · **Poslato:** 16.09.2009. 18:14:35

::SHOMY je napisao:

Citiraj:

2. Dat je pokazivac na koren BST stabla celih brojeva. Napisati metodu koja ce istampati unutrasnje
cvorove stabla u rastucem redosledu.
// Stampanje stabla BST u opadajucem redosledu (samo UNUTRASNJE cvorove)

public static void stampajUnutrasnjeRastuce(Cvor koren) {
stampaj(koren.desni);
stampaj(koren.levi);
}

private static void stampaj(Cvor cvor) {
if (cvor == null) return;
stampaj(cvor.desni);
if (!(cvor.levi == null && cvor.desni == null))
System.out.println(cvor);
stampaj(cvor.levi);
}

A sta bi se menjalo u kodu kada bi pisalo u opadajucem redosledu? Moram da pitam

Zaboravih.Naravno za rastuci i stampaj(koren.desni) i stampaj(koren.levi) menjaju mesta u kodu.

Oliver · **Poslato:** 16.09.2009. 18:16:12

Dat je pokazivac na vrh steka celih br, koji je implementiran kao js ciklicna lista. Napisati fju int Prebroj(cvorListe vrh) koja ce vratiti koliko elemenata steka ima vrednost vecu od elementa na vrhu steka.

Kod:

int prebroj(cvorListe vrh){
    if(vrh != null){
          cvorListe pom = vrh.sled;
          int vrVrh = vrh.pod;
          int br = 0;
          while(pom != vrh){
               if(vrVrh < pom.pod){
                      br++;
               }
               pom = pom.sled;
         }if(vrVrh < pom.pod)
               br++;
    }return br;
}

Je l je ovo tacno?

::SHOMY · **Poslato:** 16.09.2009. 18:32:39

@ Reider Hvala...

Gorbash · **Poslato:** 16.09.2009. 20:00:41

Citiraj:

public static void stampajUnutrasnjeRastuce(Cvor koren) {
stampaj(koren.desni);
stampaj(koren.levi);
}

private static void stampaj(Cvor cvor) {
if (cvor == null) return;
stampaj(cvor.desni);
if (!(cvor.levi == null && cvor.desni == null))
System.out.println(cvor);
stampaj(cvor.levi);
}

Sta znaci ! ispred cele zagrade? Jel' to dodje kao da je za oba slucaja u zagradi != ili sta?

I cemu uopste sluzi ovaj prvi deo?

*ivy* · **Poslato:** 16.09.2009. 20:15:28

^ negacija onog sto je u zagradi. Znaci ako nisu oba null.

Raider · **Poslato:** 16.09.2009. 20:27:53

Gorbash je napisao:

Citiraj:

public static void stampajUnutrasnjeRastuce(Cvor koren) {
stampaj(koren.desni);
stampaj(koren.levi);
}

private static void stampaj(Cvor cvor) {
if (cvor == null) return;
stampaj(cvor.desni);
if (!(cvor.levi == null && cvor.desni == null))
System.out.println(cvor);
stampaj(cvor.levi);
}

Sta znaci ! ispred cele zagrade? Jel' to dodje kao da je za oba slucaja u zagradi != ili sta?

I cemu uopste sluzi ovaj prvi deo?

Prvi deo ti sluzi da spreci stampanje korena koji nije unutrasnji cvor.

vladan · **Poslato:** 16.09.2009. 21:00:18

Hvala nisam detaljno pregledao prethodhe stranice promaklo mi ..

Ali me buni sledece:
Dat je pokazivac na koren binarnog stabla celih brojeva i pokazivac na neki cvor stabla.
Napisati metodu koja ce vratiti vrednost minimalnog cvora koji se nalazi na putanji od korena do datog cvora?

Da nema negde resenje ovog zadatka ili mozda neko ima ideju kako bi ovo moglo da se uradi?

FONForum

Strukture podataka-2008/09

Ko je OnLine