Strukture za sve

fotosinteza · **Poslato:** 24.06.2008. 00:18:44

Izgleda isto kao tekucoj generaciji,cak su stariji,mislim i na stari program,mogli da izlaze na kolokvijume i brane domace zadatke.

smucka · **Poslato:** 24.06.2008. 01:13:07

Zanima me da li ovaj zadatak moze ovako da se uradi?!

Kod:

/**
    * Dat je pokazivac na poslednji cvor DS liste celih brojeva.
    * Napisati f-ju koja ce prvi cvor prebaciti na poslednje mesto.
    * @param Poslednji
    */
   public void Prebaci(CvorDSListe last){
      if(last != null && last.Prethodni != null){
         CvorDSListe temp = last;
         while(temp.Prethodni != null){
            temp = temp.Prethodni;
         }
         temp.Sledeci.Prethodni = null;
         last.Sledeci = temp;
         temp.Sledeci = null;
         temp.Prethodni = last;
         last = last.Sledeci;
         
      }
   }

Mislim da je ovo zadatak sa I kolokvijuma iz 2007..
Grizzly ga je uradio na slican nacin tj:
samo je u petlji while naveo uslov (temp.Prethodni.Prethodni != null) i ostatak algoritma pisao u skladu sa tim..
Meni moja verzija deluje skroz logicno al me pomalo muci ovo gore navedeno..
Bitno mi je skontam na jednom primeru posto se slican princip primenjuje na vise njih!
Hvala i laku noc!:)

bearman · **Poslato:** 24.06.2008. 19:19:16

Ne znam ko je pitao, ali za sortiranje bi trebalo da znate:
1.Bubble sort
2.Selection sort
3.Insertion sort
4.Shell sort
5. Heap sort
6. Merge sort
7. Quick sort

Za prva 4 nacina sortiranja morate da znate i kako rade u teoriji i kodove.
Za ostala 3 nacina sortiranja treba da se zna samo kako rade u teoriji. Znaci prva 4 su za zadatke.

E sad imaju da se skinu slajdovi sa tih vezbi. I onaj Kostin program.
http://strukture.labis.fon.bg.ac.yu/download/sortiranje.zip
Ja sam bio na tom casu, ali ne razumem uopste kako rade. ;(
Ali da se ne lazemo nisam posteno ni pogledao.

E imam drugi problem gledam kostine zadatke. Onu njegovu malu skirptu od 15 strana. Da li neko moze da mi kaze kako radi Stack ili Red vezano za Jslistu. Znam kako rade u teoriji. Ali kako ce ovo:

Citiraj:

package Stack;

import Lista.*;

public class StakJSLista implements IStack
{
JSLista lista;

public StakJSLista()
{
lista = new JSLista();
}

public boolean PrazanStak()
{
return lista.PraznaLista();
}

public boolean PunStak()
{
return false;
}

public int BrojElemenata()
{
return lista.BrojElemenata();
}

public void Ubaci(int Podatak)
{
lista.UbaciNaPocetak(Podatak);
}

public int Izbaci()
{
return lista.IzbaciSaPocetka();
}

public int Peek()
{
if (!PrazanStak())
{
int a = this.Izbaci();
this.Ubaci(a);
return a;
}
return Integer.MIN_VALUE;
}

}

...da mi odradi zadatak. To mi nije jasno. Dakle Stack je kao spil karata uvek skidam gornju, a Red kao npr red na salteru 2 na FONu, prvi koji je dosao, prvi i izlazi.

Da li neko ima onaj papiric sa prvog kolokvijuma iz 2008?

I jos nesto. Koliko se secam Kosta je na zadnjim vezbama na kojima sam bio rekao da ce na ispitu, biti za svaki kolokvijum po 3 zadatka, koji zajedno nose 40 poena. Juce mi rece kolega da je njemu rekao da ce biti 4 zadatka i da ce svaki nosti po 10 poena, a ne kao do sada prvi 6, drugi 7, a ostali po 10ak. Pa me zanima da li je jos neko bio na zadnjim vezbama i da li imam dezinformaciju.

Da li je mozda rekao da li ce biti iste tezine kao na kolokvijumu ili tezi?
Poslao bih m@il Kosti ali posto cu dobiti m@il tipa: "Postovani kolega bice sve sto smo radili iz Linearnih struktura", onda mislim da bi bilo najbolje da Fortune, posto si ti ovakav "prekrsta prste" sa Kostom, da nam saznas to.

smucka · **Poslato:** 24.06.2008. 19:58:27

PRVI KOLOKVIJUM 2008
PRVA GRUPA

1. Napisati metodu "Gurni" koja implementira algortam za ubacivanje novog elementa u stak celih brojeva koji je implementiran kao jednostruko spregnuta lista. (6 poena)

2. Dat je niz celih brojeva sortiran u rastucem redosledu. Impelmentirati rekurzivni algoritam za binarno pretrazivanje datog niza. (7 poena)

3. Dat je pokazivac na neki cvor dvostruko spregnute liste. Napisati funkciju koja ce poslednji cvor prebaciti na prvo mesto. (Ne menjati samo vrednosti, vec pokazivace!) (10 poena)

4. Dati su pokazivaci na pocetak dve dvostuko spregnute liste celih brojeva. Napisati metodu koja ce napraviti jednostruko spregnutu listu koja predstavlja razliku (u smislu skupova) prve i druge liste i vratiti pokazivac na pocetak nove liste. (11 poena)

5. Kada se kaze da algoritam ima vremensku kompexnost O(n) onda to znaci ...

6. Sta je tip podatka, a sta struktura podatka?

DRUGA GRUPA
1. Metoda izbaci za red preko niza
2. Niz opadajuci, treba iterativni algoritam za binarno pretrazivanje.
3. isto samo sa prvog na poslednje mesto.
4. isto samo drugi razlika prvi.
5. isto.
6. razlika izmedju staka i reda.

Ovo sto si rekao za Stack i Red i meni nije jasno..
Da li ja tu treba da navedem i metodu iz klase JSLista i metodu iz klase StackJslista i da ih korigujem po potrebi ili sta???

Npr kako resiti ovaj zadatak?

Dat je pokazivač na vrh staka celih brojeva, koji je implementiran kao jednostruko spregnuta lista. Napisati funkciju int Prebroj(CvorListe Vrh) koja će vratiti koliko elemenata staka ima vrednost veću/manju od elementa na vrhu staka.
(12 poena)

bearman · **Poslato:** 24.06.2008. 20:17:44

hvala smucka

Lske · **Poslato:** 24.06.2008. 20:20:37

Pretpostavljam da je glupo pitanje, ali jbg ne znam. Data je jednistruko spregnuta lista od t elemenata ciji svaki cvor sadrzi niz od k elemenata. Koja je kompleksnost pretrazivanja ovakve strukture?

bearman · **Poslato:** 24.06.2008. 21:01:36

Crvenokosa Lske

salebab · **Poslato:** 24.06.2008. 21:15:21

smucka je napisao:

Npr kako resiti ovaj zadatak?

Dat je pokazivač na vrh staka celih brojeva, koji je implementiran kao jednostruko spregnuta lista. Napisati funkciju int Prebroj(CvorListe Vrh) koja će vratiti koliko elemenata staka ima vrednost veću/manju od elementa na vrhu staka.
(12 poena)

Ajde da prospem jednu misao dok ne dodje neko iskusniji da uradi zadatak.. Da nije mozda Vrh isto sto i prvi element u listi? Onda je extra lako uraditi ovo..

smucka · **Poslato:** 24.06.2008. 21:52:49

^
Pa deluje logicno al....kako bi ti ovo uradio? jel mozes napises?
Samo mi nije jasno kako elementi niza koji imaju svoje indexe mogu da pokazuju jedni na druge tj kako da jedan element pokazuje na svog sledbenika kao sto to imamo kod JSListe??? Da ne pokazuje mozda index nekog elementa na index sledeceg elementa??? Nikako ne mogu da skontam ove kombinacije Stekova/Redova i Lista/Nizova......

^^
kompleksnost sekvencijalnog pretrazivanja (koji se inace koristi za Liste) je O(n), a posto svaki element pokazuje na neki niz (a slozenost pretrazivanja niza je, ja mislim, O(log n)) onda bi trebalo da bude O(n*logn)..
nek me neko ispravi ako gresim il neka potvrdi...

mala_bara · **Poslato:** 24.06.2008. 22:13:08

koje su definicije za tip podataka i strukture podataka?

salebab · **Poslato:** 24.06.2008. 22:18:30

Pa recimo ovako - ako je vrh steka i prvi u listi.

Kod:

public int Prebroj (CvorListe Vrh) {
   
   int total = 0;
   int vrednost = Vrh.vrednost;
   
   while(Vrh != null) {
      // prebroj vece vrednosti
      if(Vrh.vrednost > vrednost) {
         total++;
      }
      Vrh = Vrh.sledeci;
   }
   
   return total;
}

E sad, ako vrh nije prvi element u listi, jedino mi pada na pamet da skidam svaki element sa vrha steka, pa da njega uporedjujem sa vrednost i povecavam total, ali ja nemam taj stek, i onda to sto je implementiran kao js lista mi nista ne znaci... a i deluje suvise za**** da bi se za njega dobilo 12 bodova

smucka · **Poslato:** 24.06.2008. 22:22:13

tip podataka =
skup objekata (vrednosti) i operacija nad njima.

strukture podataka =
Opis nacina organizacije podataka.
Nacin predstvljanja podataka u memoriji.
Slozeni tipovi podataka (nastali agregiranjem i na odredjeni nacin uredjeni), ali i operacije nad tim tipovima.

mala_bara · **Poslato:** 24.06.2008. 22:35:30

thanks smucka :yo:

smucka · **Poslato:** 24.06.2008. 22:46:00

@salebab

Stavio si da ti algoritam na pocetku while petlje proveri da li je vrh.podatak > vrh.podatak ...

Ja sam malo korigovao pa to izgleda ovako:

Kod:

public int Prebroj(CvorJSListe vrh){
      int total = 0;
      CvorJSListe temp = vrh.Sledeci;
      while(temp != null){
         if(temp.Podatak > vrh.Podatak)
            total++;
         temp = temp.Sledeci;
      }
      return total;
   }

Mada sad ne znam koja je uopste poenta pominjanja Stack-a kad je ova metoda vezana samo za JSListu...Ne razumem... :zbun:

salebab · **Poslato:** 24.06.2008. 22:49:05

smucka je napisao:

Samo mi nije jasno kako elementi niza koji imaju svoje indexe mogu da pokazuju jedni na druge tj kako da jedan element pokazuje na svog sledbenika kao sto to imamo kod JSListe??? Da ne pokazuje mozda index nekog elementa na index sledeceg elementa??? Nikako ne mogu da skontam ove kombinacije Stekova/Redova i Lista/Nizova......

Vidi ovako...
Elementi niza ne pokazuju direktno na susedne elemente, nego indirektno, preko pozicije.
Ako znas da se npr pera nalazi na petoj poziciji, znaces i ko se nalazi na 4 ili 6.

4 => Zika
5 => Pera
6 => Laza

Perina pozicija + 1 = Laza

A za taj zadatak, mozda su spomenuli stack samo da bi ti znao da je vrh = prvi element

Mozda je to neko pravilo, otkud znam, sve to treba neko iskusniji da potvrdi..

_blacksmith_ · **Poslato:** 25.06.2008. 00:04:55

Da li neko zna odgovoe na ovo pitanje : Objasniti postupak pretvaranja šume višegranskih stabala u jedno binarno stablo i dati primer! ?

smucka · **Poslato:** 25.06.2008. 00:45:44

da....zanimljivo..pa valjda je tako!!
hvala u svakom slucaju..

^
mrzi me da pisem postupak,mislim da ces skontati iz primera...

illusion-87 · **Poslato:** 25.06.2008. 08:08:56

A koja je fora kad ti od da brojeve u zadatku pa ti trebas da predstavljas korak-po-korak kako izgleda AVL stablo. Meni uvek stablo ispadne skroz zeznuto. Jel trebam nakon ubacivanja elemenata i da optimizujem.
Jeste glupo pitanje, ali bice jos gluplje ako padnem iz ovoga!

Mixa · **Poslato:** 25.06.2008. 08:22:39

http://webpages.ull.es/users/jriera/Doc ... applet.htm - evo ti aplet za vezhbanje avl-a (pored insert imash polje za upisivanje brojeva, pa ih ubacuj jedan po jedan)

bearman · **Poslato:** 25.06.2008. 08:50:31

4. Dati su pokazivaci na pocetak dve dvostuko spregnute liste celih brojeva.
Napisati metodu koja ce napraviti jednostruko spregnutu listu koja predstavlja razliku (u smislu skupova)
prve i druge liste i vratiti pokazivac na pocetak nove liste.

Da li neko zna kako da resim ovaj zadatak? Da li neko ima kod? Hvala

D`ebeli · **Poslato:** 25.06.2008. 09:27:01

Citiraj:

1.Bubble sort
2.Selection sort
3.Insertion sort
4.Shell sort
5. Heap sort
6. Merge sort
7. Quick sort

Jel' sortiranja dolaze u okviru pitanja vezanih za PRVI ili DRUGI kolokvijum?

bearman · **Poslato:** 25.06.2008. 10:27:38

Dolaze vezano za prvi deo.
Teorija ti je potrebna ako nisi odbranio prvi domaci.
A ova prva cetri su ti potrebna ako izlazis na prvi deo zadatke.

illusion-87 · **Poslato:** 25.06.2008. 10:33:06

Hvala Mixo kralju! :yo:

bearman · **Poslato:** 25.06.2008. 11:21:52

1. Da li je interpolaciono pretrazivanje isto sto i sekvencijalno?
2. Da li ima negde neki kod za ova sortiranja, a da nije onaj sa slajdova? posto slajdovi nece lepo da mi se otvore.
Pls neka mi neko odgovori!!!

urkes87 · **Poslato:** 25.06.2008. 11:28:48

1. Interpolaciono nije isto shto i sekvencijalno.

Sekvencijalno je pretrazhivanje element po element, a interpolaciono koristi divide and conquer metodu. Preko formule: mid = low + (high - low) * (kljuch – niz[low]) / niz[high] – niz[low] se dobije sredina i onda se dalje proverava da li je element koji se trazhi jednak mid-u ako jeste pretrazhivanje je zavrsheno, ako nije vrshi se promena HIGH i LOW promenljivih. (prochitaj dalje u skripti)

2.
Selection sort

Kod:

public void SelectionSort(int[] aArray)
{
    int i, j;
    int min, temp;
    for (i = 0; i < aArray.length - 1; i++)
    {
        min = i;
        for (j = i + 1; j < aArray.length; j++)
        {
            if (aArray[j] < aArray[min])
                min = j;
        }
        temp = aArray[i];
        aArray[i] = aArray[min];
        aArray[min] = temp;
    }}

Insertion sort

Kod:

public void InsertionSort(int[] aArray)
{
   int i, j, index;
   for ( i = 1; i < aArray.length; i++ )
   {
      index = aArray[i];
      j = i;
      while ( (j > 0) && (aArray[j-1] > index) )
      {
         aArray[j] = aArray[j-1];
         j--;
      }
      aArray[j] = index;
   }
}

Bubble sort

Kod:

public void BubbleSort(int[] aArray)
{   int i, j, temp;
   for ( i = 0; i < aArray.length -1; i++ )
   {
      for ( j = i + 1; j < aArray.length; j++ )
      {
         if ( aArray[i] > aArray[j] )
         {
            temp = aArray[i];
            aArray[i] = aArray[j];
            aArray[j] = temp;
         }}}}

Shell sort

Kod:

public void ShellSort(int[] aArray)
{
   int i, j, increment = 3, temp;
   while( increment > 0 )
   {
      for(i = 0; i < aArray.length; i++)
      {
         j = i;
         temp = aArray[i];
         while( (j >= increment) && (aArray[j-increment] > temp) )
         {
              aArray[j] = aArray[j - increment];
         j = j - increment;
         }
         aArray[j] = temp;
      }
      if( increment/2 != 0 )
         increment = increment/2;
      else if( increment == 1 )
         increment = 0;
      else
         increment = 1;
   }
}

FONForum

Strukture za sve

Ko je OnLine