Strukture za sve

baneizalfe · **Poslato:** 30.06.2006. 23:04:12

Napisati funkcije UBACI i IZBACI nad redom celih brojeva koji je implementiran preko niza.

Kod:

public void Ubaci(Object obj)
      {
         if(!full)
            array[start = (++start % array.length)] = obj;
         if(start == end)
            full = true;
      }

public Object Izbaci()
      {         
         if(full)
            full = false;
         else if(IsEmpty())
            return null;
         return array[end = (++end % array.length)];         
      }

baneizalfe · **Poslato:** 30.06.2006. 23:06:05

Dat je pokazivač na neki čvor dvostruko spregnute ciklične liste koja je sortirana u rastućem redosledu. Napisati funkciju koja će vratiti pokazivač na drugi element u listi.

Kod:

// pomeranje pokazivaca na trazenu poziciju
   public void MoveTo(int aIndex){
      aIndex=1;
      mCurrent = GetNode(aIndex);
   }

Nekako mi je ovo bilo suvise lako, verovatno gresim!

baneizalfe · **Poslato:** 30.06.2006. 23:07:38

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

Meni pada na pamet samo ovo...

Kod:

public void transformisi(LinkedListStack s1,ArrayStack s2){
         if(s1.isEmpty())
            return 0;
         s2=s1.toArray();
      }

baneizalfe · **Poslato:** 30.06.2006. 23:10:12

E sad ono sto nisam znao...

Data je jednostruko spregnuta lista celih brojeva sortirana u rastućem redosledu. Definiše ovu strukturu kao apstraktni tip i implementirajte operaciju za ubacivanje novog elementa tako da lista ostaje i dalje sortirana.

Napišite funkciju int roditelj(cvor *k, cvor * p) koja prihvata pokazivač na koren binarnog stabla i pokazivač na neki čvor u stablu, a vraća pokazivač na roditelja čvora p (vraća NULL ako roditelj ne postoji). Pri tome čvor stabla ima samo pokazivače na svoju decu

Od dve jednostruke spregnute liste celih brojeva sortiranih u rastućem redosledu formirajte treću sortiranu u opadajućem redosledu i to tako da efikasnost algoritma bude O(n+m), gde su n i m brojevi elemenata u datim listama. Date dve liste tereba da ostanu kakve su bile (tj. ne uništavaju se).

Dat je pokazivač na koren binarnog stabla čiji čvorovi sadrže cele brojeve. Napisati funkciju koja će vratiti pokazivač na čvor u stablo kod koga je najmanji proizvod sadržaja čvorova iz njegovog desnog podstabla.

Scully · **Poslato:** 01.07.2006. 09:12:15

evo i ja malo da se ukljucim... za pocetak (u toku dana more to come)

Jun, 2004.
Napisite fju int nivo(cvor *k, cvor * p) koja prihvata pokazivac na koren binarnog stabla i pokazivac na neki cvor u stablu i vraca pokazivac na roditelja cvora p (vraca NULL ako roditelj ne postoji). //ovo je ustvari fja roditelj.. valjda.. kaze int nivo a trazi da se vrati pokazivac :zbun:

Kod:

int nivo(cvor k, cvor p)
{
   cvor trazilica = k; //cisto da ne izgubimo pokazivac na koren

   if (k.Data == p.Data || p == null)
   return null;

   while (trazilica.Left.Data != p.Data && trazilica.Right.Data != p.Data)
   {
       if (p.Data > trazilica.Data)
      {
        trazilica = trazilica.Right;
      }else{
        trazilica = trazilica.Left;
      }
   }
   return trazilica.Data;
}

nadam se da je dobro.. ako moze rekurzivno nek neko napise, mozda malo kasnije pokusam da provalim i tako..

@baneizalfe

tek cu da radim ove sto si ti radio pa cu da komentarisem..

kliford · **Poslato:** 01.07.2006. 10:52:16

baneizalfe je napisao:

Dat je pokazivač na koren binarnog stabla čiji čvorovi sadrže cele brojeve. Napišite funkciju koja će vratiti broj čvorova koji su po sadržaju veći od sadržaja svih svojih potomoka

Kod:

Public viod cvorIPotomak(TreeNode aNode, int count){
   count=0;
   if(aNode==null){
      return 0;
   if(aNode.Data>aNode.Left && aNode.Data>aNode.Right)
      count++;
   return count;
}

Na oko mi se cini da ti ovaj kod nece raditi.. Nemas ni rekurziju ni iteraciju.... (plus sto ne mozes da imas return INT ako ti je VOID metoda

)
ja bih to probao ovako:

Kod:

public static int potomci(TNode n){
 
   if (n==null)
      return 0;
   return (n.left.data>n.data)?1:0 + (n.right.data>n.data)?1:0 + potomci(n.left) + potomci(n.right);
}

Kod:

public static int potomci(TNode n){
   int p1, p2;
   if (n==null)
      return 0;
   if (n.left.data>n.data)
      p1 = 1;
      else p1 = 0;
   if (n.right.data>n.data)
      p2 = 1;
      else p2 = 0;
   return p1 + p2 + potomci(n.left) + potomci (n.right);

To su dve iste metode, samo prva verzija je optimalnija, a druga je chitljivija

Videcu da kasnije predjem i druge kodove koje je BaneIzAlfe() ostavio..

shredder · **Poslato:** 01.07.2006. 10:52:55

baneizalfe je napisao:

:bljak:

Dat je pokazivač na neki čvor dvostruko spregnute ciklične liste koja je sortirana u rastućem redosledu. Napisati funkciju koja će vratiti pokazivač na drugi element u listi.

Kod:

// pomeranje pokazivaca na trazenu poziciju
   public void MoveTo(int aIndex){
      aIndex=1;
      mCurrent = GetNode(aIndex);
   }

Nekako mi je ovo bilo suvise lako, verovatno gresim!

ne valja ti ovaj kod. Kod spregnutih listi ne mozes da pristupas elementima preko indexa. To moze kod nizova.
Evo glavni dio zadatka

Kod:

while (node.previous.Data < node.Data)
        node = node.previous;
return node.Next;

Mrzi me da sad gledam sve zadatke ali vidio sam da u nekim kodovima nemas ni petlju ni rekurziju. Ne moze tako, moras da prodjes kroz sve elemente.

kliford · **Poslato:** 01.07.2006. 11:04:54

baneizalfe je napisao:

:bljak:

Dat je pokazivač na neki čvor dvostruko spregnute ciklične liste koja je sortirana u rastućem redosledu. Napisati funkciju koja će vratiti pokazivač na drugi element u listi.

Kod:

// pomeranje pokazivaca na trazenu poziciju
   public void MoveTo(int aIndex){
      aIndex=1;
      mCurrent = GetNode(aIndex);
   }

Nekako mi je ovo bilo suvise lako, verovatno gresim!

Jednostavno, posto je ciklicna, a rastuca, svaki cvor je manji od sledeceg, osim poslednjeg... Znaci trazis onaj cvor koji je veci od sledeceg.. to je cvor n, onda je prvi cvor u listi n.next, a drugi je n.next.next...

Kod:

public static DLLNode drugi(DLLNode n){
   if (n==null)
      return null;
   if (n.data < n.next.data)
      return n.next.next.data; //da, ovde ima 2 next
   return drugi(n.next);
}

Sad, ovde je problem sto je ovo dvostruko spregnuta lista... Pa, ako mi kao ulaz dobijemo prvi i li drugi cvor, brze bi nam bilo da krenemo u nazad ili tako nesto... ali mislim da to malo komplikuje stvar.. ali ovaj algoritam radi

kliford · **Poslato:** 01.07.2006. 11:05:26

baneizalfe je napisao:

:bljak:

Dat je pokazivač na neki čvor dvostruko spregnute ciklične liste koja je sortirana u rastućem redosledu. Napisati funkciju koja će vratiti pokazivač na drugi element u listi.

Kod:

// pomeranje pokazivaca na trazenu poziciju
   public void MoveTo(int aIndex){
      aIndex=1;
      mCurrent = GetNode(aIndex);
   }

Nekako mi je ovo bilo suvise lako, verovatno gresim!

Jednostavno, posto je ciklicna, a rastuca, svaki cvor je manji od sledeceg, osim poslednjeg... Znaci trazis onaj cvor koji je veci od sledeceg.. to je cvor n, onda je prvi cvor u listi n.next, a drugi je n.next.next...

Kod:

public static DLLNode drugi(DLLNode n){
   if (n==null)
      return null;
   if (n.data < n.next.data)
      return n.next.next.data; //da, ovde ima 2 next
   return drugi(n.next);
}

Sad, ovde je problem sto je ovo dvostruko spregnuta lista... Pa, ako mi kao ulaz dobijemo prvi i li drugi cvor, brze bi nam bilo da krenemo u nazad ili tako nesto... ali mislim da to malo komplikuje stvar.. ali ovaj algoritam radi

shredder · **Poslato:** 01.07.2006. 11:12:03

Ajmo malo teorije. Jel zna neko odgovor na ova pitanja

Kada se kaže da algoritam ima kompleksnost O(n) onda to znači da:

a) Algoritam ima n ugnježdenih petlji
b) Vreme izvršavanja algoritma je manje od n sekundi
c) Algoritam je n puta sporiji od standardnog algoritma
d) Vreme izvršavanja algoritma je proporcionalno sa n

Koji od ponuđenih odgovora je tačan? (10 poena)

Stablo za binarno pretraživanje ima ukupno M čvorova, a visinu K. Vreme potrebno za pronalaženje nekog čvora u stablu je proporcionalno sa:

a) M + K
b) M*K
c) M
d) K

Koji od ponuđenih odgovora je tačan? (10 poena)

Vercundus · **Poslato:** 01.07.2006. 11:21:11

Z prvo pitanje bi trebalo da je pod d) a za ovo drugo, mislim da je pod b) ali neka neko potvrdi/ispravi...

Scully · **Poslato:** 01.07.2006. 12:30:10

ajde nek neko ispise

Napisati operacije ubaci i izbaci nad redom koji je implementiran preko niza.

porfavor

donald · **Poslato:** 01.07.2006. 14:13:52

Mislim da je to ovo...

// Ubaci:

public void Enqueue(Object obj)
{
if(!full)
array[start = (++start % array.length)] = obj;
if(start == end)
full = true;
}

//Izbaci:

public Object Dequeue()
{
if(full)
full = false;
else if(IsEmpty())
return null;
return array[end = (++end % array.length)];
}

baneizalfe · **Poslato:** 01.07.2006. 14:32:29

Citiraj:

Mislim da je to ovo...

// Ubaci:

public void Enqueue(Object obj)
{
if(!full)
array[start = (++start % array.length)] = obj;
if(start == end)
full = true;
}

//Izbaci:

public Object Dequeue()
{
if(full)
full = false;
else if(IsEmpty())
return null;
return array[end = (++end % array.length)];
}

Pa da, i ja to mislim da je... iso sam logikom Winamp-a

baneizalfe · **Poslato:** 01.07.2006. 14:34:24

E sad

Dat je pokazivač na koren binarnog stabla čiji čvorovi sadrže cele brojeve. Napisati funkciju koja će vratiti pokazivač na čvor u stablo kod koga je najmanji proizvod sadržaja čvorova iz njegovog desnog podstabla.

Kod:

public int minDesni(TreeNode aNode){
   if(aNode==null)
      return 0;
   desniKrak=aNode.Right;
      return Math.min(desniKrak.Left.Data*desniKrak.Right.Data , minDesni(desniKrak.Left.Data*desniKrak.Right.Data));
} 

Kapiram da gresim jer mi pregleda samo ono sto je na desnoj strani... ne mogu da se setim drugo...

User · **Poslato:** 01.07.2006. 14:35:39

Citajte malo, vec je baneizalfe napisao to u ovoj temi, ovde:
http://www.fonforum.org/viewtopic.php?p=189400#189400

baneizalfe · **Poslato:** 01.07.2006. 14:41:00

Data je jednostruko spregnuta lista celih brojeva sortirana u rastućem redosledu. Definiše ovu strukturu kao apstraktni tip i implementirajte operaciju za ubacivanje novog elementa tako da lista ostaje i dalje sortirana.

Kod:

//Mislim da bi bilo najbolje da se element doda na pocetak liste,
//pa ako je veci od sledeceg, da zamene mesta i tako do kraja

// Dodavanje elementa na pocetak liste
   public void Add(Object aData){
      mHead = new ListNode(aData, mHead);
      mCurrent = mHead;
      while(mCurrent.Next!=null){
         if(mCurrent>mCurrent.Next){
            Object pom=mCurrent.Next;
            mCurrent.Next=mCurrent;
            mCurrent=pom;
         }
      }
      
   }

Ne znam kako da pretvorim ovo u pastraktni tip...

baneizalfe · **Poslato:** 01.07.2006. 14:41:55

Dat je pokazivač na neki čvor dvostruko spregnute liste koji je jedini ulazni podatak. Napisati funkciju koja će ukazani element prebaciti na pretposlednje mesto u listi.

Kod:

public void prebaci(DLL mCurrent){
   if(mCurrent==null)
      return 0;
   while(mCurrent.Next.Next!=null)[
      DLL pom=mCurrent.Next;
      mCurrent.Next=mCurrent;
      mCurrent=pom;
   }
}

kliford · **Poslato:** 01.07.2006. 14:51:52

Kod:

public static void izbaci(Queue q){
   if (q.array[0]==null)
      return;
   q.array[array.length-1] = null;

public static void ubaci(Queue q, Object b){
   if (q.array[0]==null)
      return;
   for (int i = array.length; i => 0; i--)
      q.array[i] = q.array[i-1];
   q.array[0] = b;

Kako sam ja skontao, svaki ArrayQueue (tj. red implementiran preko niza) u sebi sadrzi promenljivu array[] koja cuva njegove elemente, tj objekte u redu... Ne snosim nikakvu odgovornost za ove dve metode koje sam okacio

kliford · **Poslato:** 01.07.2006. 15:01:39

Kod:

array[start = (++start % array.length)]

Bice da sam kreten

Ovo mi uopste nije jasno!!! Sta se ovde radi?

mislim... cemu sve ovo sa ostatkom deljenja???

zar za metodu IZBACI ne brisemo poslednji element u nizu (tj array[array.length-1])????
a za UBACI sve elemente pomeramo za jedno mesto unapred, a na nulto mesto ubacujemo novi objekat?

baneizalfe · **Poslato:** 01.07.2006. 15:07:16

Citiraj:

Ovo mi uopste nije jasno!!! Sta se ovde radi?

mislim... cemu sve ovo sa ostatkom deljenja???

zar za metodu IZBACI ne brisemo poslednji element u nizu (tj array[array.length-1])????
a za UBACI sve elemente pomeramo za jedno mesto unapred, a na nulto mesto ubacujemo novi objekat?

Nigde se nije EKSPLICITNO reklo da treba da se izbaci POSLEDNJI ili da se ubaci NA PRVOM mestu, vec samo da se izbaci i ubaci... a kod sam nasao u materijalima sa vezbi...

Nego jel znate da uradite ovo:

Napisati funkciju koja prihvata pokazivač na koren AVL binarnog stabla i štampa sadržaj čvorova stabla u rastućem redosledu.

kliford · **Poslato:** 01.07.2006. 15:12:39

baneizalfe je napisao:

Citiraj:

Ovo mi uopste nije jasno!!! Sta se ovde radi?

mislim... cemu sve ovo sa ostatkom deljenja???

zar za metodu IZBACI ne brisemo poslednji element u nizu (tj array[array.length-1])????
a za UBACI sve elemente pomeramo za jedno mesto unapred, a na nulto mesto ubacujemo novi objekat?

Nigde se nije EKSPLICITNO reklo da treba da se izbaci POSLEDNJI ili da se ubaci NA PRVOM mestu, vec samo da se izbaci i ubaci... a kod sam nasao u materijalima sa vezbi...

A, pa cekaj malo, ko mene onda ovde pravi ludim????????? :zbun:

Zar ne pise lepo da je red FIFO struktura, tj objekti se ubacuju sa jedne strane, i izbacuj usa druge, kao u redu za mleko??????????????
Na koje mesto ti uopste ubacujes i izbacujes objekte iz reda????

Citiraj:

Nego jel znate da uradite ovo:

Napisati funkciju koja prihvata pokazivač na koren AVL binarnog stabla i štampa sadržaj čvorova stabla u rastućem redosledu.

To ti je infix obilazak pri cemu ispisujes sadrzaj svakog cvora koji obidjes

kliford · **Poslato:** 01.07.2006. 15:27:07

baneizalfe je napisao:

:fokus:

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

Meni pada na pamet samo ovo...

Kod:

public void transformisi(LinkedListStack s1,ArrayStack s2){
         if(s1.isEmpty())
            return 0;
         s2=s1.toArray();
      }

Pa, ono sto je trbalo da se uradi, ti si to sabio u funkciju toArray()

Ja bih to ovako uradio.. mozda nije najbolje reshenje, ali, eto, s nogu

Kod:

public static ArrayStack transform(LLStack s1){

   if (s1==null)
      return null;
   int i = 0;
   LLNode current = s1.head;
   ArrayStack s2 = new ArrayStack();
   for(;;){
      s2.array[i] = current.value;
      i++
      if (current.next == null)
         break;
      else
         current = current.next;
      }
   return s2;

Scully · **Poslato:** 01.07.2006. 16:33:51

shredder je napisao:

baneizalfe je napisao:

:bljak:

Dat je pokazivač na neki čvor dvostruko spregnute ciklične liste koja je sortirana u rastućem redosledu. Napisati funkciju koja će vratiti pokazivač na drugi element u listi.

Kod:

// pomeranje pokazivaca na trazenu poziciju
   public void MoveTo(int aIndex){
      aIndex=1;
      mCurrent = GetNode(aIndex);
   }

Nekako mi je ovo bilo suvise lako, verovatno gresim!

ne valja ti ovaj kod. Kod spregnutih listi ne mozes da pristupas elementima preko indexa. To moze kod nizova.

Moooze!!! Upravo gledam Vezbe 5, radili smo fju GetNode resava ovu stvar... mada baneizalfe ti ces moradi da pises i tu fju koju upotrebljavas u ovom slucaju GetNode! Naravno ni meni ovaj nacin nije pao na pamet dok nisam videla u svesku.. :fokus:

shredder · **Poslato:** 01.07.2006. 16:49:14

U pravu si, kasnije sam i ja vidio da moze. Ali mislim da je lakse da se napisu one 2 linije koda koje sam ja napisao i eventualno da se prije toga jos provjeri da li je argument metode null (znaci ukupno 4 linije koda), nego da se pisu 2 metode ili cak 3 jer mislim da GetNode() poziva jos neku metodu.

FONForum

Strukture za sve

Ko je OnLine