Strukture za sve

markoh · **Poslato:** 01.04.2007. 18:55:36

Kosta je rekao da je greska pri copy/paste
i da metoda 'ubaci' koja ubacuje...

xXx · **Poslato:** 01.04.2007. 21:40:32

Maaaa...i ja takodje mislim da se jadni Kosta nista nije pito

Onaj profesor je *** ups (sorry Vojkane, za malo da me bannujes;))

I stvarnoooooo...ali adje da gledam sa vedrije strane na to. Mozemo zato svi da se pripremimo na drugi kolokvijum

Ja sam bio kod Koste pre 2 nedelje i prebacio mi je pitanja sa svih rokova u poslednjig 5-6 godina. A sva pitanja sto su sada bila su i na tim "rokovima". Znaci -> imam sva pitanja.
Jos mi samo treba 1 dan da ih sredim, i naravno neko ko bi to uradio

Pa da li ste da napravimo neku akciju ovde?

...Ima dosta vremena do II kolokvijuma...da onaj ko misli da zna polako resava sve zadatke i kaci ovde?

Eniac · **Poslato:** 01.04.2007. 23:34:57

jel moze neko da mi pomogne oko toga sta treba da se importuje da rade one metode .left .right kod drveta?

xXx · **Poslato:** 05.04.2007. 10:16:22

@Bumblebee

Moje misljenje je da ni jedna skripta nije dobra i da ne moze da se oslonis na njih...(jedino mozda teoretska pitanja mozes)

op · **Poslato:** 05.04.2007. 23:39:34

Jel pogledao neko one zadatke sto imamo za domaci(seminarski).Nerazumem ono oko pronalaska elemnta u cvoru. Sta ja tu treba da vratim, jel cvor u kome se nalazi trazeni element ili integer(npr. 3 - kao treci po redu od heda)???I kako da vratim u isto vreme i cvor gde se nalazi i index u nizu tog cvora gde je element????? :zbun:

kolji~voda~vri · **Poslato:** 09.04.2007. 08:59:49

Citiraj:

kako da vratim u isto vreme i cvor gde se nalazi i index u nizu tog cvora gde je element?????[/b]

1. mozes da napravis 2 metode od kojih jedna vraca broj cvora, a druga indeks elementa u tom cvoru...

2. moje resenje: napravis klasu Elementi koja cuva svaki pronadjen ceo broj iz strukture kao objekat sa osobinama (broj , indeks cvora, indeks elementa u cvoru), a sve nadjene elemente prikazes u GUI-u kao neku listu ili tabelu...

op · **Poslato:** 09.04.2007. 12:13:38

pise:"Operacija pretraživanja treba da prikaže u kom se cvoru i u kom elementu nalazi traženi
element (ako postoji)." Sto znaci ja pozovem metodu pretrazi a ona vrati 2 integera. Moze to sa dve metode da se napravi ali neverujem da je Kosta tako zamislio.

Jel sigurno treba GUI da se uradi??Jel moze samo test klasa, ko ce se smara sa guijem?!

kolji~voda~vri · **Poslato:** 09.04.2007. 22:01:02

Ne verujem da je cilj da se radi "onako kako je Kosta zamislio" vec je cilj da se resi postavljeni problem na svoj nacin!!!!
Nabavi Visual Editor za Eclipse i izrada sasvim pristojnog GUI-a ce ti trajati nekih 30-tak minuta.
Nije bitno samo to da ti program radi, vec i kako radi...

ARfon · **Poslato:** 11.04.2007. 10:31:02

Zna li neko kako se radi sledeci zadatak:

Dat je niz celih brojeva sortiran u opadajucem redosledu. Napisati operaciju koja ubacuje novi element u niz tako da niz ostane sortiran.Pretpostaviti da ima mesta da se nov element ubaci.

Ima resen slican:
Data je jednostruko spregnuta lista celih brojeva sortirana u opadajucem redosledu. Definišite ovu strukturu kao apstraktni tip i implementriajte operaciju za ubacivanje novog elementa tako da lista ostaje i dalje sortirana.
public static void insertSorted(LLNode n, int i){
if(n == null)
return;
if(n.value > i)
if(n.next.value < i){
LLNode newNode = new LLNode(i, n.next);
n.next = newNode;
} else
insertSorted(n.next, i);
new LLNode(i, n);
}

Verovatno je slicno… ali…

DJole · **Poslato:** 11.04.2007. 20:53:48

ARfon je napisao:

Zna li neko kako se radi sledeci zadatak:

Dat je niz celih brojeva sortiran u opadajucem redosledu. Napisati operaciju koja ubacuje novi element u niz tako da niz ostane sortiran.Pretpostaviti da ima mesta da se nov element ubaci.

Kod:

public void Insert(int value) // postavlja el. u niz
{
int j;
for(j=0; j<nElems; j++) // gleda gde da ubaci
if(a[j] > value) // (sekvencijalno trazi- moze i binarno zavisi kako trazi valjda)
break;
for(int k=nElems; k>j; k--) //pomera sve elemente za jedan nivo
a[k] = a[k-1];
a[j] = value; // ubacuje na j-to mesto
nElems++; // uvecava se brojac koji vodi racuna o broju elemenata u nizu
} 

To bi bilo to za niz u rastucem redosledu. Za niz u opadajucem samo menjas znak kod a[j]<value

m@rtin@ · **Poslato:** 11.04.2007. 22:04:25

Napisati program koji ubacuje novi element u binarno stablo (za pretraživanje) i javlja da li je stablo AVL.

Kod:

public void dodajCvor(TreeNode aNode, int aData){
  if(aNode == null)
    aNode = new TreeNode(aData);
  if(aData < aNode.Data)
    dodajCvor(aNode.Left, aData);
  if(aData > aNode.Data)
    dodajCvor(aNode.Right, aData);
}

// posto je stablo BST, treba proveriti samo da li je balansirano da bi bilo AVL
public static booelan isBalanced(TreeNode aNode){
  if(aNode == null)
    return true;
  if(Math.abs(height(aNode.Left) – height(aNode.Right)) <= 1)
    return (isBalanced(aNode.Left) && isBalanced(aNode.Right);
  return false;
}

Zasto ja mislim da ovo nije dobar kod ? Moze li neko da mi objasni u par reci kako radi, ako je taca. Ja nesto ne mogo da se snadjem. Zar ne treba da se def. prvo height?

Citiraj:

if(Math.abs(height(aNode.Left) – height(aNode.Right)) <= 1)

Ja ovo prevodim ovako: Po meni ovo znaci da se gleda abs. vrednost samo levo minus samo desno... Nesto mi def. fali u kodu, ali nisam pametna dovoljno

da sama provalim, zato I need help

Djole vidim da si raspolozen ?

ARfon · **Poslato:** 11.04.2007. 22:37:49

OK
Hvala DJole
Mada zasto: a[k] = a[k-1];
Meni je logicnije a[k] = a[k+1]; ... mozda gresim...ali ako se pomera u desno za po jedan...

A ovaj... Ima li neko resenje...
String je implementiran kao dvostruko-spregnuta lista. Implementirati f-ju Boolean iSPalindrome (ListNode Head) koja proverava da li je string palindrom. Ne sme se menjati sruktura liste, niti koristiti druge strukture. Palindrom je rec ili recenica koja se cita i sa leva udesno i s desna ulevo.

DJole · **Poslato:** 11.04.2007. 23:35:40

m@rtin@ je napisao:

Napisati program koji ubacuje novi element u binarno stablo (za pretraživanje) i javlja da li je stablo AVL.

Djole vidim da si raspolozen ?

Evo ovako bi to trebalo da se uradi

Kod:

  private int visina(Node node)   // Nalazi visinu stabla
        {
            if (node == null)
                return 0;
            else
                return 1 + Math.Max(visina(node.left), visina(node.right));
        }


        public bool IsAvl(Node node)  // Proverava da li je stablo AVL
        {
            if (node == null)
                return true;
            if (Math.Abs(visina(node.left) - visina(node.right)) <= 1)
                return (IsAvl(node.left) && (IsAvl(node.right)));
            else
                return false;
        }

Znaci samo fali kod za visinu tj dubinu.
I onda bi se pozivao insert,pa provera da li je balansirano koja salje odgovarajucu poruku.
I dovoljno je da se vidi po apsolutnoj vrednosti da li je balansirano.Moglo je da pise i Abs(visina(leva)-visina(desna))>1

DJole · **Poslato:** 11.04.2007. 23:40:54

ARfon je napisao:

OK
Hvala DJole
Mada zasto: a[k] = a[k-1];
Meni je logicnije a[k] = a[k+1]; ... mozda gresim...ali ako se pomera u desno za po jedan...

Zato sto a[k] jos ne postoji. Posto indeks niza ide od 0...n ti imas za poslednji a[n-1].

Evo npr: imas niz od 10 elemenata. a[0]...a[9] i ubacujes na mesto a[5]. To znaci da ces morati da pomeras sve u desno odnosno a[10] ce biti a[9] i tako dalje da bi na kraju a[5] bivse bilo a[6] i onda imas slobodno mesto da ubacis. Na kraju uvecas broj elemenata za 1.
Dakle nElems=11 ali niz ide od a[0] do a[10]. Aklo bi stavio k+1 imao bi situaciju a[11] =a[12] a ti elementi ne postoje u nizu tj null su.

laden · **Poslato:** 11.04.2007. 23:47:01

Jesu li nama predavali nesto iz drva kad pricate o tom, ili to tek krece na vezbama posle pauze?

DJole · **Poslato:** 11.04.2007. 23:59:46

m@rtin@ je napisao:

Napisati program koji ubacuje novi element u binarno stablo (za pretraživanje) i javlja da li je stablo AVL.

Inace malo sam se danas igrao sa AVL rotacijom pa evo koda za ubacivanje elemenata u AVL stablo i rotiranje istog ako nije balansirano.

Kod:

   public void InsertInAVL(int data)
        {
            root = insertInAVL(root, data);
        }


        private Node insertInAVL(Node node, int data)
        {


            if (node == null) node = new Node(data);
           
            else
            {
                if (data < node.data) node.left = insertInAVL(node.left, data);
                if (data > node.data) node.right = insertInAVL(node.right, data);
            }

            if ((visina(node.left) - visina(node.right) == -2)) // da li je debalans na levoj strani
            {
                if (node.right.right == null) //da li su potrebne dve rotacije
                {
                    node.right = RotateRight(node.right);
                    return node = RotateLeft(node);

                } //zarotiraj prvo u desno "node.right" pa onda u levo zarotiraj node
                else
                {
                    return node = RotateLeft(node); //zarotiraj "node" u levo
                }
            }
            if ((visina(node.left) - visina(node.right) == 2)) // da li je debalans na desnoj strani
            {
                if (node.left.left == null) da li su potrebne dve rotacije
                {
                    node.left = RotateLeft(node.left);
                    return node = RotateRight(node);

                }zarotiraj prvo u levo "node.left" pa onda u desno zarotiraj "node"
                else
                {
                    return node = RotateRight(node);
                }//zarotiraj "node" u desno
            }

            return node;
        }
        private Node RotateLeft(Node node)
        {
            Node noviKoren = node.right;
            node.right = noviKoren.left;
            noviKoren.left = node;
           
            return noviKoren;
        }


        private Node RotateRight(Node node)
        {
            Node noviKoren = node.left;
            node.left = noviKoren.right;
            noviKoren.right = node;

            return noviKoren;
        }

Left Rotation of node P:

Let Q be P's right child.
Set Q to be the new root.
Set P's right child to be Q's left child.
Set Q's left child to be P.

Right Rotation of node Q:

Let P be Q's left child.
Set P to be the new root.
Set Q's left child to be P's right child.
Set P's right child to be Q.

Citiraj:

Djole vidim da si raspolozen ?

Raspolozen za ispit he he. Imam jos dve noci i ceo dan

DJole · **Poslato:** 12.04.2007. 00:51:42

ARfon je napisao:

A ovaj... Ima li neko resenje...
String je implementiran kao dvostruko-spregnuta lista. Implementirati f-ju Boolean iSPalindrome (ListNode Head) koja proverava da li je string palindrom. Ne sme se menjati sruktura liste, niti koristiti druge strukture. Palindrom je rec ili recenica koja se cita i sa leva udesno i s desna ulevo.

Ideja je sledeca (mrzi me da kucam kod sada). Posto nam nije poznat rep vec samo glava, uvodimo pomocni tmp1 pokazivac i krecemo da bojimo elemente dok tmp1 ne dodje do kraja liste. Kada izbrojimo, izvrsimo celobrojno deljenje sa 2 i pamtimo ga u neku promenljivu susret.
Zatim dodelimo tmp2=head i dokle god je brojac manji od susreta(while count<=susret) uporedjujemo cvorove sa pocetka i kraja(if tmp1.data==tmp2.data). Prelazimo na sledece elemente tmp1=tmp1.previous i tmp2=tm2.next .Ako sve bude dobro imamo palindrom i vracamo true inace break kod if uslova i vraca false

ARfon · **Poslato:** 12.04.2007. 09:01:21

Zadatak iz januarskog roka...

Zna neko da ga resi? :udri:

m@rtin@ · **Poslato:** 12.04.2007. 09:21:58

Ako mi nije naglaseno da je stablo BST ili HEAP onda je najbolje da od stabla napravim listu ? Onda je lako da proveravam svaki element i trazim min, max element stabla. Ili treba preko stabla da se trazi min/max element? Kako bi onda izgledalo? Zna li neko

Ali ne verujem da moze da se da doje zadatak koji u binarnom stablu trazi da se vrati dubina stabla sa min/max vrednoscu ? To mi deluje komplikovano za pisati na papiru

DJole · **Poslato:** 12.04.2007. 09:48:00

Ako je stablo BST vrlo lako se nalazi min i max. Idemo samo levo ili desno do dubine.
Postoji resenje i za binarno stablo. Kod sledi uskoro, samo da testiram.

DJole · **Poslato:** 12.04.2007. 09:52:05

ARfon je napisao:

Zadatak iz januarskog roka...

Nisam siguran za teorijsko pitanje. Lici mi na index, ali treba proveriti posto nisam siguran. A sto se tice koda, trebalo bi da je ovo resenje

Kod:

public int CountList(ListNode node)
{
 if (node!=null) return 1 + CountList(node.next);
 return 0;
}

public int Count(TreeNode node)
{
  if (node!=null) return Count(node.left) + 1 + Count(node.right) + CountList(node.data)
  return 0;
}

webmaster1 · **Poslato:** 12.04.2007. 10:12:25

a sta se desava sa domacim...da li se to predaje na papiru ili treba nesto da se brani(na racunaru)? Koja je korist od tog domaceg? Da li ima neki slican kod? I konacno, da li ima neko da je uradio, a tako je dobre volje da bi to podelio sa mnom(pp)

op · **Poslato:** 12.04.2007. 10:45:22

Ne predaje se na papiru nego ga poneses na flesu ili necemu i kosta te ispiuje 2-3 minuta a kada ce to biti tek cemo znati.

Erin's_Child · **Poslato:** 12.04.2007. 12:55:29

I naravno ima koristi od toga: dobiješ deset poena za domaći i to ti se dodaje na zbir poena sa kolokvijuma...

webmaster1 · **Poslato:** 12.04.2007. 15:29:59

Samo da proverim da li sam dobro shvatio...

Citiraj:

Data je dvostruko spregnuta lista. Cvor liste kao element sadrži niz celih
brojeva (broj elemenata je proizvoljan, te ga treba proslediti kao parametar
konstruktora).

Dakle, dvostruko spregnuta lista čiji svaki čvor sadrži niz celih brojeva neodređene dužine pa se dužina niza daje kao argument u konstruktoru.

Citiraj:

Opisati ovakvu strukturu kao ATP

Sta je ATP?

Citiraj:

i implementirati operacije za
ubacivanje, izbacivanje, pretraživanje i prikazivanje svih elemenata. Operacija
pretraživanja treba da prikaže u kom se cvoru i u kom elementu nalazi traženi
element (ako postoji).

kao ok

Citiraj:

Operacije ubacivanja i izbacivanja implementirati tako da ovakva struktura ima ponašanje REDA.

DLL treba da se ponasa kao red ili i ti nizovi ? Tj. Da li se operacije ubacivanja i izbacivanja odnose na cvorove liste ili/i na članove niza celih brojeva unutar cvorova?

Citiraj:

Za ovu strukturu napisati i program koji ce omoguciti manipulaciju
strukturom (omogucava korisniku da manipuliše strukturom).

I sve to treba da može da se kompajlira i testira...

FONForum

Strukture za sve

Ko je OnLine