Strukture za sve

Vlacke · **Poslato:** 26.08.2007. 08:28:34

^znam da mi tu ide samo u desno podstablo. Ni ja nisam znao kako. Pogledaj na prethodnoj strani, Nemo je tacno resio taj zadatak.

Abraxus · **Poslato:** 26.08.2007. 12:02:17

OMFG! Da . . totalno sam propustio .. čestitke Nemo - sušta jednostavnost . . prelepo! a i sad sam rešio ovaj svoj ..

Doduše . .ne reče mi iz čega spremaš?

Gauco · **Poslato:** 26.08.2007. 12:47:39

Kod B i B* stabla kada npr ubacujemo novi element kako proveravamo da li nam je cvor u koji treba da ubacimo element pun, znaci kada se list cepa na dva dela a kada ne?

Vlacke · **Poslato:** 26.08.2007. 12:59:08

@Abraxus - teoriju iz skripte sa sajta. Zadatke iz sveske sa vezbi, starijih rokova, malo iz Userove skripte, i obavezno kodovi sa pocetka ove teme (ima ih dosta).

@Gauco - pogledaj u skripti sa sajta, tu je lepo objasnjena razlika izmedju ta dva stabla, a i pogledaj prve strane ove teme, tu imas tacno odradjene primere ubacivanja za obe vrste stabla.

Vlacke · **Poslato:** 26.08.2007. 18:34:39

Kod:

public TreeNode najDubList ( TreeNode aNode ){ 
   if ( aNode == null ) 
      return null; 
    
   if ( (aNode.Right == null) && (aNode.Left == null) ) 
      return aNode; 
   
    if ( height(aNode.Left) > height(aNode.Right) ) 
      return najDubList ( aNode.Left ); 
    
      else 
      return najDubList ( aNode.Right ); 
}

Zanima me jedna stvar - da li u ovom gore kodu, koji sam prezueo sa pocetnih strana ove teme, koji sluzi da vrati najdublji cvor u stablu, treba da dodam i sledecu petlju

Kod:

 if (height(koren.levo) == height(koren.desno))
return najDubList(koren.levo) || najDubList(koren.Desno)

Abraxus · **Poslato:** 26.08.2007. 19:54:07

pa ako su jednaki izbaciće desni po tvom kodu . .tako da ne mislim da je potrebno, a nisam siguran da će to uopšte da prodje . . . ne znam kako bi on izabrao . .

dying_bride · **Poslato:** 27.08.2007. 11:48:15

Koliko dugo se radi ispit?
:>

Gauco · **Poslato:** 27.08.2007. 11:57:20

Jel moze neko ko razume Bstabla da mi kaze zasto je npr. u skripti sa sjata strana 13, slika pod a) K list pun(4 kljuca) a prva slika na strani 15 list L pun sa 3 kljuca? Kako se to odredjuje?

miki47 · **Poslato:** 27.08.2007. 12:17:18

Na prvoj slici je red stabla n=4, a na drugoj n=3. Red stabla odredjuje broj elemenata u cvoru.

Vlacke · **Poslato:** 27.08.2007. 12:41:53

Abraxus je napisao:

pa ako su jednaki izbaciće desni po tvom kodu . .tako da ne mislim da je potrebno, a nisam siguran da će to uopšte da prodje . . . ne znam kako bi on izabrao . .

Da, tacno. Mislio sam da ce da vrati desni samo ako je visina desnog veca od visine levog. Ne postoji metoda u Javi koja izbacuje dva cvora, tako da mora da izabere neki. I kao sto si rekao, izbacice desni.

miki47 · **Poslato:** 27.08.2007. 14:10:52

Da li neko ima aprilski rok?

Gauco · **Poslato:** 27.08.2007. 16:36:20

@Miki47

Pa kako odredjujes to n?

Gauco · **Poslato:** 27.08.2007. 16:55:14

Sta je sa sortiranjem, nema ga po rokovima?

leopold · **Poslato:** 27.08.2007. 17:54:54

Napisati funkciju transformisi(STAK s1, STAK* s2) koja će od staka
koji je implementiran kao jednostruko spregunuta lista formirati novi
stak koji je implementiran preko niza.

Kod:

public static ArrayStack transform(
         LinkedListStack s1) {
      LinkedListStack temp = new LinkedListStack();
      int count = 0;
      Object element;
      while ((element = s1.Pop()) != null) {
         temp.Push(element);
         count++;
      }

      ArrayStack stek = new ArrayStack(
            count);
      while ((element = temp.Pop()) != null) {
         stek.Push(element);
      }
      return stek;

   }

   public static void clone( izvor, klon) {
      Object temp = izvor.Pop();
      if (temp == null)
         return;
      clone(izvor, klon);
      klon.Push(temp);
      izvor.Push(temp);

Interesuje me obrnut slučaj, dakle, imamo stak implementiran preko niza, a potrebno je formirati novi implementiran preko jednostruko spregnute liste.

Anyone?

miki47 · **Poslato:** 27.08.2007. 18:35:55

Gauco je napisao:

@Miki47

Pa kako odredjujes to n?

n je dato na pocetku zadatka.

balkan · **Poslato:** 27.08.2007. 18:47:20

kada nam je dat u zadatku red 4 jel to znaci da je max. br. kljuceva u listu 4-1=3? a minmalni broj 1?

poletn23 · **Poslato:** 27.08.2007. 19:15:52

Moze li neko malo da pojasni taj hashing?

dying_bride · **Poslato:** 27.08.2007. 22:10:53

Detaljno objasnjenje hashinga mozes naci u skripti koju mozes skinuti sa sajta predmeta.

blackmasterrr · **Pridružio se:** 31.05.2005. 13:49:25 **Postovi:** 24

Alo kolege jel zna neko ove zadatke iz Juna.
Ako neko zna neka okaci resenje najkasnije do srede popodne.Hvala

6.Napistai algoritam za ubacivanje elemanata u niz celih brojeva ako se
adresa ubacivanja odredjuje HASH funkcijom h(k)=k mod DuzinaNiza
a problem kolizije se resava otvorenim adresiranjem.

7.Objasni robusno interpolaciono pretrazivanje?

8.Objasniti postupak pretvaranja sume visegranskih stabala u jedno binarno
stablo i dati primer?

uzas · **Poslato:** 28.08.2007. 01:03:58

slazem se, lepo bi bilo da neko kome bas ovo ide uradi 'tacno' jer sam ja orbuo ceo forum, skoro sve teme i nasao 116 resenja za svaki zadatak. ko zna koje je tacno od svih njih...

robusno interpolaciono pretrazivanje ima u skripti to nije problem...
a ovo VST u binarno, sam pokusao kao sto je jedna devojka napisala i malo sam se pogubio, odnosno uradio sam sve kao sto je rekla, ali sam dobio neko izdegenerisano binarno stablo, ne znam da li je tacno (nikako nije izbalansirano), ali binarno jeste

verujem da ce rok biti dosta slican junskom, ako ne i isti... :bljak:

Abraxus · **Poslato:** 28.08.2007. 05:19:48

U skripti uopšte nije objašnjeno olančavanje . . ali evo kako ja shvatam hashing . . .

HashTable je niz u kome su indexi ono što se dobije haširanjem podatka koji se smešta, a članovi niza su ti podaci

otvoreno adresiranje:

Kod:

public int HashSearch(HashTable[] Tablica, int key) {
  for (int i=0; i<=Tablica.length; i++) {     // petlja će vrteti [i]i[/i] koje je offset u OA . . 
    int j = hash(key, i);                             // trebalo bi da stoji (ja mislim) j = hash(key)+i!
    if (Tablica[j] == key) {
      return j;                                           //ako ga ubode vraća njegov index
    }                                                       
    if (Tablica[j] == null) {                       // ako je naišao na prazno mesto, to znači da takav element nije ubacivan 
      break;                                             
    }
  }                                         //petlja služi da ako nije našao na tom mestu, pokuša na mestu do tog, pa na 
                                                                 mestu do tog, i tako dok ne stigne do kraja Hash tabele
  return null;                                                  
}

olanačavanje:

koliko kapiram u slučaju kolizije, kao element HashTabele (koja je niz) sa kolizionim indexom stavlja se pokazivač na listu. U toj listi će biti sadržani svi elementi sa istim ključem. zašto je u while petlji -1? zašto free broji od 0 do nazad i kako prilazi negativnom indexu niza?? :zbun:

ovo ne mogu . .

Kod:

public int SearchInsertCh(HashTable[] Tablica, int key) {
  int i = hash(key)                             
  int j = 0;
  int free = 0;

  while (Tablica[i].key != key && Tablica[i].next != -1) {
    i = Tablica[i].next;                       
  }

  if(Tablica[i].key = key) return i;      .

  if(Tablica[i].key == null) {
    j = i;
  } else {
    while (Tablica[free].key != null) {  
      free--;
    }
    j = free;
    Tablica[i].next = free;
  }
  Tablica[i].key = key;
  return 1;
}

grk · **Poslato:** 28.08.2007. 09:44:04

"rekurzija"

ako neko moze ukratko da pojasni.. sta je, koja je poenta, i kada se koristi... ???

Vlacke · **Poslato:** 28.08.2007. 10:27:46

objasnjeno by Nemo. Objasnjnenje je vezano za zadatak sa kloniranjem steka.

Rekurzija predstavlja ponovno pozivanje metode. Kada ponovo pozoves metodu(rekurzivno), sav kod koji je ostao nakon ponovnog pozivanja ce se zapamtiti u memoriji koja je odredjena za izvrsavanje ove metode(u ovom zadatku poslednja dva reda). Kada metoda izadje iz rekurzije, ona se vraca unazad(kao sto funkcionise stack, LIFO lista). Ovo je sustina rekurzije.

Konkretno, u ovom zadatku: objekti koji se nalaze na staku ce se izbacivati sa njega, sa vrha ka dnu i pakovati u obj tipa Object(oznacicemo ih 3,2,1).Nacrataj sliku, bice ti jasnije. Kada rekurzija naidje na null, odnosno kada se isprazni stack, prestaje izvrsavanje rekurzije i sada se izvrsava ono sto je ona zapamtila, ali unazad(ovo je veoma bitno). Sada ce se objekti vracati na stack izvor i stack klon metodom Push(obj). Znaci, posto idemo unazad vratice se prvo 1, posto je on poslednji izbacen, zatim 2, pa 3. I sada ti je 1 na dnu, 2 iznad, i 3 na vrhu. U sustini , dobio si isti stack i stack klon, sto je cilj zadatka.

jezgro · **Poslato:** 28.08.2007. 13:29:05

@ abrakus nije ti bas dobar kod. kod otvorenog adresiranja mozes da koristis while sa

Kod:

while (tablica[i]!=null && tablica[i]!=-1) //I uslov: prolazim kroz niz dok 
                                           // ne dodjem do zadnjeg i 
                                           // II uslov: niz nije prazan, razlicit od -1
{++ i}                                     // uvecaj i (idi na sledeci clan niza) 

otvorenom adresiranju je niz a u olancavanju je lista. tako da ne mozes za listu uslov sa -1.

Abraxus · **Poslato:** 28.08.2007. 15:01:56

kod je iz Userove skripte . . i isto radi što i tvoj, samo na drugačiji način . . osim što i dalje ne kapiram čemu služi poredjenje sa -1 ... ali ako kapiraš olačnavanje - bi li ga objasnio?

FONForum

Strukture za sve

Ko je OnLine