Strukture za sve

parasite · **Poslato:** 14.06.2006. 01:04:05

S obzirom da mnogima pisanje algoritama za zadatke, a bez njih se ne moze poloziti usmeni, i ne ide bas evo nadam se jednog uspjesnog resenja! Svi koji su uradili zadatke neka ih post-uju tako da ih svi mogu vidjeti i komentarisati. Mnogima ce pomoci!
Nadam se da ce kolegijalnost doci do izrazaja! :cupavi:

Paf · **Poslato:** 20.06.2006. 09:36:00

Jel uspeo neko da resi ovaj zadatak?

Svaki element jedne jednostruko spregnute liste sadrži pokazivač na drugu jednostruko spregnutu listu. Ako je dat pokazivač na prvi element prve liste, koliko ukupno ima elemenata u svim listama. (25 poena)

Thunder · **Poslato:** 20.06.2006. 12:14:07

Da li je to cisto teorijsko pitanje ili treba da se kodira?

Postavka me asocira na "mozgalice", jer ako nam je data jedna jednostruko spregnuta lista koja ima N elementa, njen 1. element pokazuje na 2. element (odnosno na jednostruko spregnutu listu sa N-1 elementa), ... pa je resenje (ako racunamo posebno za svaku listu) N+N-1+N-2+...+1+0 ili nesto slicno (za poslednji ne znam kako da racunam). Ovo funkcionise samo pod uslovom da je i prazna lista jednostruko spregnuta lista.

Ma racunovodstvo mi je napravilo zbrku u glavi.

Ima li neko bolju ideju?

Scully · **Poslato:** 21.06.2006. 00:15:51

Thunder mislim da si lose zamislila problem... kodiranje treba sigurno.. ja bih ovako: for ili while petlja, za svaki element glavne listi ukupno = 1 (za taj element) + neka Count fja koja racuna broj elemenata u njegovoj podlisti;

kliford · **Poslato:** 21.06.2006. 16:35:40

Thunder je napisao:

Da li je to cisto teorijsko pitanje ili treba da se kodira?

Postavka me asocira na "mozgalice", jer ako nam je data jedna jednostruko spregnuta lista koja ima N elementa, njen 1. element pokazuje na 2. element (odnosno na jednostruko spregnutu listu sa N-1 elementa), ... pa je resenje (ako racunamo posebno za svaku listu) N+N-1+N-2+...+1+0 ili nesto slicno (za poslednji ne znam kako da racunam). Ovo funkcionise samo pod uslovom da je i prazna lista jednostruko spregnuta lista.

Ma racunovodstvo mi je napravilo zbrku u glavi.

Ima li neko bolju ideju?

Nenene, loshe si shvatio... Svaki cvor ima pokazivac na sledeci, ali kao sadrzaj cvora, value, pojavljuje se pokazivac na neku drugu listu... 'Ajde, okacicu kod za nekih 20-ak minuta, samo da ga odradim

kliford · **Poslato:** 21.06.2006. 19:11:38

E, obecao sam kod za 20-ak minuta, pa sam okacio kod sa nekim sintaksnim greskama, pa sam izbrisao poruku, pa sam bio malo sprecen, i evo konacno testiranog koda

Kod:

//metoda koja broji clanove u "podlistama"
//mislim da nije potre4bno objasnjenje ove metode :)
private static int subCount(LLNode node){
   if (node.next==null)
      return 1;
   return subCount(node.next) + 1;
   }
 
 
//metoda koja broji clanove "glavne liste"
//i clanove "podlista" na koje ovi pokazuju
public static int supCount(LLNode node){
    
   //provera da li je cvor "glavne liste" poslednji u listi
   //i da li on NE pokazuje na neku podlistu;
   //u tom slucaju vraca samo 1, tj broji samo taj clan
   if ((node.next==null)&&(node.value==null))
      return 1;
 
   //proverava samo da li je cvor "glavne liste" poslednji cvor
   //u tom slucaju metoda vraca 1 plus broj clanova "podliste"
   if (node.next==null)
      return subCount(node.value) + 1;
 
   //proverava da li cvor NE pokazuje na neku "podlistu"
   //u tom slucaju metoda vraca 1 plus broj ostalih clanova "glavne liste"
   if (node.value==null)
      return supCount(node.next)+1;
 
   //metoda vraca 1 (trenutni cvor)
   //plus broj clanova "podliste" na koju pokazuje
   //plus broj ostalih clanova "glavnog niza"
   return subCount(node.value)+supCount(node.next)+1;
   }

Samo da znate, ako hocete ovo da testirate, morate da napisete celu klasu LLNode (Linked List Node)... Znaci 2, 3 konstruktora, neke metodice uz pomoc kojih cete sve te cvorove (LLNode) spojiti u listu i sl....

Lske je napisao:

Sta sve treba da se sprema za strukture, koji su sve kodovi potrebni?

Mislim da je to vec prezvakano na forumu:
Od teorije treba skripta plus sve sto je radjeno na vezbama i predavanjima, a nema u skripti, nego nadjes na netu

Od kodova: pa, kodovi koji su radjeni na vezbama plus tako neki zadaci koji proizilaze iz tih oblasti za koje smo radili kodove...

Scully · **Poslato:** 21.06.2006. 20:24:54

Paf je napisao:

Jel uspeo neko da resi ovaj zadatak?

Svaki element jedne jednostruko spregnute liste sadrži pokazivač na drugu jednostruko spregnutu listu. Ako je dat pokazivač na prvi element prve liste, koliko ukupno ima elemenata u svim listama. (25 poena)

evo kako bih ja uradila, ali nek obavezno neko pregleda... ideju sam vec rekla...

Kod:

public static int subCount (LLNode aNode)
{
   if (aNode!=null)
      return 1 + subCount(aNode.next);
      return 0;
}

privete static int Count (LLNode aNode)
{
   int count = 0

   while (aNode!=null)
   {
      count = count + 1 + subCount(aNode.value);
      aNode = aNode.next;
   }
   
   return count;

}

@ kliford

mislim da je proveravanje da li element glavne sadrzi pokazivac na neku subListu suvisno zbog prve recenice zadatka...

kliford · **Poslato:** 21.06.2006. 21:54:39

Pa, dobro... volim ja da sve to tako sredim

Vezbaj da tako radis, ne moze da skodi

Inace, zanimljivo mi je to sto si iskombinovala iterativni i rekurzivni metod, ali dobro ti je resenje, isprobao sam ga kod sebe i radi

A, u principu, ti i ja imamo isto resenje, samo sam ja i u drugoj metodi koristio rekurzije...

btw, metoda Count() treba da ti bude public, kad je private ne moze biti pozvana iz (hipoteticke) main metode...

Scully · **Poslato:** 21.06.2006. 23:06:27

mislis za metodu subCount da bude public.. ok

tacno mi je? tacno.. jeeee! vrlo ohrabrujuce za mene jer nisam nista radila do sada..

i ja sam provalila ovo za rekurzivno i interativno.. :cool:

podseti me samo, jel rekurzija kad poziva samog sebe ili poziva u odviru sebe neku drugu metodu.. jer u principu ovo tvoje nije rekurzija, pa mi zato nije jasno kako ce ovo da ti radi:

Kod:

//proverava da li cvor NE pokazuje na neku "podlistu" 
   //u tom slucaju metoda vraca 1 plus broj ostalih clanova "glavne liste" 
   if (node.value==null) 
      return supCount(node.next)+1; 
  
   //metoda vraca 1 (trenutni cvor) 
   //plus broj clanova "podliste" na koju pokazuje 
   //plus broj ostalih clanova "glavnog niza" 
   return subCount(node.value)+supCount(node.next)+1; 

recimo za ovaj prvi deo ako glavna lista ima 3 clana, svaki element pokazuje na neku listu, i da svaka podlista ima pet clanova
kod
return subCount(node.value)+supCount(node.next)+1;

subCount(node.value) - ovo ce dati 5 za prvu podlistu
supCount(node.next) - ovo ce dati 4 jer ce racunati subCount na ostalih 4 elementa glavne liste..
+1 i to je to, nema rekurzije !?!

... i evo sad provalih... jesi siguran da umesto subCount(node.next) ne treba Count(node.next), onda je rekurzija... zato me je ovo tvoje zbunilo pa sam ja isla iterativno...

edit:

nego cekaj, tebi se obe metode isto zovu?!? why, why, why??? onda ovo gore vazi u slucaju da ti je druga metoda Count();... ali kako ce da zna u ovom poslednjem redu koju medotu da koristi.. jer po meni ce uvek pozivati samo sebe, a ne ovu prvu koju si isto nazvao :zbun:

kliford · **Poslato:** 21.06.2006. 23:35:06

nenenee... subCount() broji clanove podlista..
supCount broji elemente glavne liste...

sup=super

kao "nadLista"

subCount je i kod tebe i kod mene isto, a moje supCount je tvoje Count

Inace, rekurzija je kad u nekoj metodi pozivas nju samu, ne neku drugu..

Rekurzija:

Kod:

public void nekaMetoda(Node n){
   ...
   ...
   return nekaMetoda(n.next);
}

Nije rekurzija:

Kod:

public void nekaMetoda(Node n){
   ...
   ...
   return nekaDrugaMetoda(n.next);
}

Jeste rekurzija:

Kod:

public void nekaMetoda(Node n){
   ...
   ...
   return nekaMetoda(n.next) + nekaDrugaMetoda(Neki parametar);
}

Znaci, ti u svakoj metodi mozes da pozivas bilo koje metode... Nezavisno od toga da li vec psotoje u API-ju ili si ih ti isporgramirala... Cim je u nekoj metodi pozvana ona sama, to je rekurzivna metoda...

Scully je napisao:

recimo za ovaj prvi deo ako glavna lista ima 3 clana, svaki element pokazuje na neku listu, i da svaka podlista ima pet clanova
kod
return subCount(node.value)+supCount(node.next)+1;

subCount(node.value) - ovo ce dati 5 za prvu podlistu
supCount(node.next) - ovo ce dati 4 jer ce racunati subCount na ostalih 4 elementa glavne liste..
+1 i to je to, nema rekurzije !?!

Pazi, ima rekurzije zato sto je u SUP metodi sadrzano pozivanje SUB metode i SUP za sledeci cvor.. Ako imas cvorove n1, n2 i n3, a cvorovi pod niza su n11, n12, n13, n14, n15 pa n21-n25 i n31-n35..
pri tome znamo da n1.next=n2 i n2.next=n3..

Metoda supCount(n1) vraca:
return 1+subCount(n1.value)+supCount(n1.next),
onda ti dobijes 1+5+supCount(n2)
(1 je n1 cvor, a 5 je broj covorova liste na koju pokazuje n1)

kako supCount(n2) vraca
return 1+subCount(n2.value)+supCount(n2.next),
sto je ekvivalentno sa: 1+5+supCount(n3)

pa ukupno imamo:
1+5+1+5+supCount(n3)... I tako u krug (tj u rekurziju

)

Sad, zanimljiva je ova struktura koju imamo... Imamo jednostruko-spregnutu listu... Njeni cvorovi imaju pokazivace na sledece cvorove, a kao podatak (value, data) u svakom cvoru se opet javlja pokazivac, ali na druge liste... U stvari, imamo binarno stablo u kome cvorovi imaju po dva pokazivaca (value i next, sto je ekvivalent left i right u binarnim stablima), ali nemamo podatak koji ti cvorovi nose

Scully · **Poslato:** 21.06.2006. 23:52:28

Citiraj:

supCount

ovo p je bilo dovoljno...

note to myself: b ≠ p

Dylan · **Poslato:** 22.06.2006. 10:35:40

Ovako je radjeno na vezbama (aNode.Down je pokazivac na novu listu):

public int Count(ListNode aNode){
if(aNode==null) return 0;
return 1 + Count(aNode.Next) + Count(aNode.Down);
}

kliford · **Poslato:** 26.06.2006. 16:02:32

E, imam problema... Postoji fora sa linearnim strukturama (kao i sa strukturama uopste) da trba da ralizkujemo fizicku impementaciju od logicke...
Recimo: jednostruko i dvostruko spregnuta lista su logicke linearne strukture, a niz, stack i queue (sta god ovo poslednje bilo) su fizicke implementacije onih gornjih... Valjda.. mozda sam i pogresio.. mene zanima koje smo sve te strukture radili (osim jednostruke i dvostruke spregnute liste) i koja je razlika... Recimo znam za stack da je to struktura koja radi po LIFO principu, a queue radi po FIFO... ali sve to mi je ono, razbacano, ne mogu da pokacim sve... tako, ako bi neko bio ljubazan da zapise sve te strukture (ima ih 5-6), bio bih zahvalan

Scully · **Poslato:** 29.06.2006. 20:06:35

jesi pogledao u ovoj skirpti by runner

btw queue ti je red. implementiura se preko liste ili niza..
i bilo je nesto na predavanjima kada je red pun kada je prazan:

start = ++start%array.lenght
start=end=0 //prazan
full=else //sta god ovo bilo, mozda nisam dobro prepisala
full=true //pun

:zbun:

User · **Poslato:** 29.06.2006. 23:23:16

mozda full=false (a ne else), mada je to sve gore navedeno nepovezano

Scully · **Poslato:** 30.06.2006. 12:32:39

znam...

baneizalfe · **Poslato:** 30.06.2006. 14:47:25

Ok pokusavao sam da uradim ovaj zadatak:
Dva binarna stabla su identična ako su oba prazna ili ako oba imaju koren čiji sadržaj je jednak a njihova leva i desna podstabla su identična. Napišite funkciju koja će proveriti da li su dva binarna stabla identična.

Kod:

private int jednaki(TreeNode aNode, TreeNode bNode, int uslov1, int uslov2){
   //Proverava da li su oba stabla prazna, ako jesu vraca 1 ako ne 0
   if(aNode==null && bNode==null){
      return 1;
   }else{
      return 0;
   }

   //Proverava da li je sadrzaj korena jednak, ako jeste uslov1 je zadovoljen
   //OVO NE ZNAM…Zapravo ne znam oznaku sadrzaja korena…idijot…
   
   //Proverava da li su leve I desne strane identicne, ako jesu uslov2 je zadovoljen
   if(aNode.Left==bNode.left && aNode.Right==bNode.Right){
      uslov2=1;
   }else{
      uslov2=0;
   }

   //Proverava da li su ispunjeni svi uslovi, ako jesu vraca 1, ako nisu 0
   if(uslov1==1 && uslov2==1){
      return 1;
}else{return 0;
}

Kako proveravam da li su koreni jednaki?

shredder · **Poslato:** 30.06.2006. 15:02:31

puno si se zapetljao...
moze to jednostavnije:

Kod:

static boolean identicnaStabla(TreeNode node1, TreeNode node2) {
      if (node1 == null && node2 == null)
         return true;
      if (node1 != null && node2 != null) {
         if (node1.Data == node2.Data)
            return identicnaStabla(node1.Left, node2.Left) && identicnaStabla(node1.Right, node2.Right);
      }
      return false;
   }

baneizalfe · **Poslato:** 30.06.2006. 18:04:08

aha, znaci node1.Data je za sadrzaj korena... ok to mi je i trebalo. znam da je malo komplikovanije, ali je preglednije sta radi sta, a ovde sam pokusao i drugima da pomognem. enivej, veceras cu da okacim i ostalo sto sam radijo, pa nek se ostali potrude da preprave netacno i ZAJEDNO CEMO POBEDITI!!! :cupavi:

P.S. Aj i ostali, okacite kodove programa koje ste odradili

baneizalfe · **Poslato:** 30.06.2006. 22:54:41

Evo sta sam jos radio

Ako je skup je implementiran preko jednostruko spregnute liste, napišite funkciju koja prihvata kao argumente dva skupa i vraća treći koji je njihova razlika.
Kapiram da posto je za presek kod:

Kod:

// presek dve liste. Funkcija vraća pokazivač na prvi element nove liste.
   public static ListNode Intersect(ListNode aNode1, ListNode aNode2)
   {
      if (aNode1 == null || aNode2 == null)
         return null;
      if (IsMember(aNode1.Data, aNode2))
         return new ListNode(aNode1.Data, Intersect(aNode1.Next, aNode2));
      else
         return Intersect(aNode1.Next, aNode2);
   }

onda je za razliku

Kod:

// razlika dve liste. Funkcija vraća pokazivač na prvi element nove liste.
   public static ListNode Intersect(ListNode aNode1, ListNode aNode2)
   {
      if (aNode1 == null || aNode2 == null)
         return null;
      if (!IsMember(aNode1.Data, aNode2))
 return Intersect(aNode1.Next, aNode2);
      else
         return new ListNode(aNode1.Data, Intersect(aNode1.Next, aNode2));
   }

Zar ne?

baneizalfe · **Poslato:** 30.06.2006. 22:58:12

I

Dat je pokazivač na koren binarnog stabla čiji čvorovi sadrže cele brojeve. Napisati funkciju koja će vratiti pokazivač na čvor list koji je na najvećoj dubini u stablu.

Kod:

Public int heigth(TreeNode aNode){
   if(aNode==null)
      return 0;
   return 1 + Math.max(height(aNode.Left), heigth(aNode.Rigth));
}

A po klifordu

Kod:

public static int findTreeDeepness(TNode n){   
if (!TNode.exist(n))
return 0;
if (n.isLeaf())
return 1;               
return Math.max(TNode.findTreeDeepness(n.left)+1,TNode.findTreeDeepness(n.right)+1);
}

Za najmanji element je valjda samo Math.min

baneizalfe · **Poslato:** 30.06.2006. 22:59:13

I jos

Dat je pokazivač na početni čvor dvostruko spregnute liste sortirane u rastućem redosledu koja sadrži pozitivne cele brojeve. Napisati funkciju koja će između svih onih elementa liste koji se po vrednosti razlikuju za više od 1 ubaciti u datu listu nove elemente tako da lista posle poziva operacije ima u sebi sukcesivne cele brojeve. Na primer ako lista sadrži 3, 5, 8 nakon poziva ove funkcije sadržaće 3, 4, 5, 6, 7, 8

Kod:

public static void insertInts(DLLNode aNode){
        DLLNode curr;
        if (aNode.next == null)
            return;
        if ((aNOde.value + 1) < aNode.next.value){
            curr = aNode.next;
            aNode.next = new DLLNode(aNOde.value+1);
            curr.addPrev(aNode.next);
        }
        insertInts(aNode.next);
    }

kliford...

baneizalfe · **Poslato:** 30.06.2006. 23:00:51

Jos...

Dva stabla su «slična kao u ogledalu» ako su oba prazna ili ako nisu prazna, ako je levo stablo svakog stabla «slično kao u ogledalu» desnom stablu onog drugog. Na sledećoj slici su prikazana dva «slična kao u ogledalu» stabla:

Napišite funkciju koja će proveriti da li su dva binarna stabla «slična kao u ogledalu».

Kod:

public static boolean ogledalo(TNode n1, TNode n2){
if ((n1==null)&&(n2==null))
return true;
if(((n1==null)&&(n2!=null))||((n1!=null)&&(n2==null)))
return false;
return (ogledalo(n1.left, n2.right) && ogledalo(n1.right, n2.left));
}

bug · **Poslato:** 30.06.2006. 23:01:17

Jedno prosto pitanje: Sta znaci kad su stabla slicna?
Ja mislim da je to kad su nodovi rasporedjeni na isti nacin a podaci su nevazni, jesam li u pravu?

baneizalfe · **Poslato:** 30.06.2006. 23:02:54

Jos...

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;
}

FONForum

Strukture za sve

Ko je OnLine