Strukture podataka 2007/08.

Kelegorm · **Poslato:** 16.04.2008. 17:03:13

Simpatique je napisao:

1.Kakva je kompleksnost algoritma za pretraživanje dvostruko spregnute liste koja ima n elemenata?
a. O(n2) b. O(log(n)) c. O(n) d. O(1) e. _____

2.Kakva je kompleksnost algoritma za pretraživanje jednostruko spregnute liste koja ima n elemenata?
a. O(1) b. O(log(n)) c. O(n) d. O(n2) e. _____

ATP je valjda apstraktni tip podataka...kad definises metode u interfejsu

@desperado: sto bi pretrazivao liste od kraja? Mislim da kod nizova ide od kraja, kod lista se to postize rekurzijom

1.Vidi koliko je za sekvencijalno pretrazivanje.Toliko je i za1 , kod ds liste primenjujes sekv pretrazivanje.
I kod JSliste mora sekvencijalno pretrazivanje, pa je isto kao pod 1.

Simpatique · **Poslato:** 16.04.2008. 17:08:37

znaci O(n) je u oba slucaja?

Kelegorm · **Poslato:** 16.04.2008. 17:11:07

Ja mislim da je tako.E sad to sto ja mislim i kako je stvarno, ne mora biti isto

bearman · **Poslato:** 16.04.2008. 17:15:56

(poc == niz.length) ? poc = 0 : poc++;
BTW sta predstavlja ovaj ? (upitnik)?

Simpatique · **Poslato:** 16.04.2008. 17:18:17

Sad sam nasla ono sto me je mucilo. Kada je metoda void, moze imati return; ali ne vraca nista, nego je to samo prekid metode, u suprotnom bi se morao hvatati Exception...tanananaaaa

Citiraj:

(poc == niz.length) ? poc = 0 : poc++;
BTW sta predstavlja ovaj ? (upitnik)?

vec sam napisala jasniju varijantu koda za ovo. Al nije na odmet da ponovim:
Ako je (poc == niz.length-1) onda je poc=0, u suprotnom (to su ove dve tacke) poc++

meni normalnije je pisati to lepo sa if/else[/quote]

bearman · **Poslato:** 16.04.2008. 17:31:50

ma samo me je interesovalo sta znaci ?. shvatio sam i prvi put kad si mi napisala kako radi

Desperado · **Poslato:** 16.04.2008. 17:54:12

Simpatique je napisao:

@desperado: tek sad sam uocila da je nova lista DS...moze i bez rekurzije, strpas obe liste u novu sortiras...

...ma bre samo kazes da je poslednji element u stvari prvi...ehehheheh

E jesam

... Da se krecem unazad kroz JSListu... c c c...
Nego vadim redom iz rastucih JS, od pocetka elemente i stavljam ih na kraj DS liste... I gradim listu od kraja ka pocetku... Zaboravio sam na tu divnu osobinu DSListe.... :taptap:

Simpatique · **Poslato:** 16.04.2008. 18:03:52

A sta bi bilo kad bi nova lista bila JS, u opadajucem, a imas dve JS u rastucem?
E, kako se definisu dve promenljive istog tipa

cvorJSListe P3=null; novi=null;
Tako je Kosta pisao na tabli...el moze to tako?

urkes87 · **Poslato:** 16.04.2008. 19:38:56

Definishesh kao

cvorJSListe P3, novi;

ili
ako treba da im dodelish i vrednost
onda valjda ovako:

cvorJSListe P3 = null, novi = null;

mikelandjelo · **Poslato:** 16.04.2008. 20:57:17

evo nekih zadataka sa proslogodisnje pripreme za kolokvijum
zadaci

Mars · **Poslato:** 16.04.2008. 21:21:39

Simpatique je napisao:

znaci O(n) je u oba slucaja?

Jeste, pise u Userovoj skripti tako.

E sad koja je kompleksnost algoritma za interpolaciono pretrazivanje?

mikelandjelo · **Poslato:** 16.04.2008. 21:44:59

valjda je za interpolaciono log(logN) [naravno u osnovi 2]

mikelandjelo · **Poslato:** 16.04.2008. 22:13:40

evo jos jedan mini (lak) zadatak koji broji koliko ima objekata u listi (mozda zatreba za neki tezi zadatak na kolokvijumu)

int Count(){
CvorListe B = H; //B je pomocni objekat kojim setamo do kraja, a H je ustvari head
int c = 0; //startni brojac podesen na nula
while(B!=null){ //dokle god ima objekata
B = B.sledeci; //za pomeranje na sledeci objekat
c++;}//zatvara while petlju
return c; //vraca novo vrednost c-ea
}//zatvara metodu Count

Grizzly · **Poslato:** 16.04.2008. 23:14:41

bearman je napisao:

grizzly podeli domaci sa nama

hvala znam da smaram

Ne mogu matori ne bi bilo fer prema ljudima koji su platili da im objasnim to, i jos vaznije ne bi bilo fer prema meni jer mi vise niko ne bi dosao

Ozbiljno, postavicu na sajt par dana pre poslednjeg termina, mislim da je to OK?

Simpatique je napisao:

poc = ++poc % niz.length; ili drugacije p=(p==niz.length-1)?0:p+1;
je skraceno od
if (p == niz.length-1) p=0;
else p++;

nadam se da nam ne bi zakinuo ako bi pisali to sa if/else

Nema sta da ti zakine ako program radi, a ovde je u pitanju samo nacin pisanja. BTW tvoj je bolji

Desperado je napisao:

Jel zna neko kako da se krecem unazad(s kraja na pocetak) kroz JSListu a da ne brisem poslednji element? tj, kako pomerati pokazivac? Konkretno, od dve rastuce JSListe treba napraviti, opadajucu DSListu... Znaci moram da pretrazujem JSListe s kraja...Pritom JSListe treba da ostanu netaknute...

::manjak je napisao:

^Пробај са рекурзијом.

Verovatno moze i rekurzijom ali zasto komplikovati ako ne mora. Idi kroz JSListe i smestaj elemente u DSListu ali ih ubacuj na pocetak DSListe. Tako ces poslednji element JSLista (najveci) ubaciti na pocetak DSListe to jest DSLista ce ti biti sortirana opadajucim redom.

bearman je napisao:

@Simpatique
Hvala puno

Ma vidim da je Grizli uradio taj zadatak, na mnogo laksi(jasniji) nacin.

radi slobodno kako ti je lakse, ali pazi da ne zeznes nesto

bearman je napisao:

(poc == niz.length) ? poc = 0 : poc++;
BTW sta predstavlja ovaj ? (upitnik)?

? : je trinarni operator u javi koji je zamena za if else. Preporucujem ti da ga zaboravis.

Simpatique je napisao:

ma bre samo kazes da je poslednji element u stvari prvi...ehehheheh

Nadam se da se salis

Desperado je napisao:

Simpatique je napisao:

@desperado: tek sad sam uocila da je nova lista DS...moze i bez rekurzije, strpas obe liste u novu sortiras...

...ma bre samo kazes da je poslednji element u stvari prvi...ehehheheh

E jesam

... Da se krecem unazad kroz JSListu... c c c...
Nego vadim redom iz rastucih JS, od pocetka elemente i stavljam ih na kraj DS liste... I gradim listu od kraja ka pocetku... Zaboravio sam na tu divnu osobinu DSListe.... :taptap:

Pa tako ces opet dobiti sortiranu u rastucem. Ako dodas 1 na kraj, pa 2 na kraj, pa 3 na kraj dobices 1,2,3...

Simpatique je napisao:

A sta bi bilo kad bi nova lista bila JS, u opadajucem, a imas dve JS u rastucem?
E, kako se definisu dve promenljive istog tipa

cvorJSListe P3=null; novi=null;
Tako je Kosta pisao na tabli...el moze to tako?

A da otkucas pa da vidis

bearman · **Poslato:** 16.04.2008. 23:48:24

@Grizzly
Totalno razumem care, nije frka kralj si.

E sada da mi kaze neko, koja je razlika izmedju iterativne i rekurzivne varijante kod sekvencijalnog/binarnog pretrazivanja/brojanja elemenata. Kakava je razlika kod niz i listi?
Koliko sam mogao da primetim kod nizova inerativne radi program sve sam, a kod rekurzivne mi zadajemo granice kod ulaznih argumenata?!

btw mogli ste da nadjete neki sajt bez golih riba, da postavite taj link.

Simpatique · **Poslato:** 17.04.2008. 08:11:49

Grizzly:

Citiraj:

Simpatique ::
ma bre samo kazes da je poslednji element u stvari prvi...ehehheheh

Grizzly:
Nadam se da se salis

Jel obavzeno da pocetak DSListe bude na levoj strani? Kosta rece da je pocetak tamo gde mi odredimo, da sama lista ne brine bas sta joj je pocetak, sta kraj, jer je simetricna, i s obe strane ima null

illusion-87 · **Poslato:** 17.04.2008. 09:15:04

Cekaj bre!
Tek sad, kad sam video u kojim salama se radi, sam shvatio da, mi ne radimo na racunarima! Pisemo algoritme na papiru jel?!

markom · **Poslato:** 17.04.2008. 09:17:26

Tako je. Ma koliko to neverovatno zvucalo, na ispitu se ,,programira'' na papiru.

Grizzly · **Poslato:** 17.04.2008. 11:17:31

bearman je napisao:

E sada da mi kaze neko, koja je razlika izmedju iterativne i rekurzivne varijante kod sekvencijalnog/binarnog pretrazivanja/brojanja elemenata. Kakava je razlika kod niz i listi?
Koliko sam mogao da primetim kod nizova inerativne radi program sve sam, a kod rekurzivne mi zadajemo granice kod ulaznih argumenata?!

Ne znam da ti kazem neku znacajnu razliku, osim sto je jedno rekurzivno a drugo nije. Rekurzivna je sigurno dosta sporija metoda. Jesi li siguran da vov pitanje ima smisla?

Ovo sto kazes mi zadajemo granice nije bas tacno. Kod rekurzije ti moras sve podatke da proturis kroz zagrade, jer samo to ce novi poziv metode da vidi. Na pocetku ti samo das najmanji i najveci a on posle odredjuje levo i desno...

Grizzly · **Poslato:** 17.04.2008. 11:21:39

Simpatique je napisao:

Jel obavzeno da pocetak DSListe bude na levoj strani? Kosta rece da je pocetak tamo gde mi odredimo, da sama lista ne brine bas sta joj je pocetak, sta kraj, jer je simetricna, i s obe strane ima null

Imas DSListu koja po sadrzaju izgleda ovako:

1 <> 2 <> 3 <> 4 <> 5 <> 6

gde je pocetni pokazuje na cvor 1 a krajnji na cvor 6.

Ako ti sad kazes pocetak = kraj, sad ce ti i pocetak i kraj biti na 6, i tako si izbacila sve ostale elemente iz liste osim 6ice. Lista nema varijablu koja joj govori kako je orjentisana sto se tice smera, nego ti je to hard coded verovatno s leva na desno. Tvoj kod podrazumeva u pretrazivanju i ostalim akcijama da je pocetak prvi s leva, a kraj prvi s desna. Moze biti i obrnuto, ali ne mozes da menjas u jednoj listi to dinamicki...

bearman · **Poslato:** 17.04.2008. 11:30:53

pa pitanje ima smisla, jer gledam neke zadatke sto je radio Kosta(asistent), i vidim da je radio ista pretrazivanja na 2 nacina. Pa me ne bi cudilo da mi u zadatku zada nadji element u nizu ili listi, koristeci npr: binarnu rekurzivnu varijantu pretrazivanja.

Simpatique · **Poslato:** 17.04.2008. 11:50:09

Nisam mislila da kazem pocetak=kraj, nego recimo ako smo vec imali pocetak i kraj, onda kazem poslednji=pocetak i prvi=kraj i presaltam se na poslednji i prvi

sta program zna :fokus:

Grizzly · **Poslato:** 17.04.2008. 12:07:59

@ baerman

Pa OK imas u skripti i jedno i drugo pa mu napisi koje ti trazi

@ simpatique

Nemam pojma, ja bih rekao da ne moze...

Simpatique · **Poslato:** 17.04.2008. 13:23:03

Koliko se ja secam, lista ne moze binarno da se pretrazuje???

Butters · **Poslato:** 17.04.2008. 13:27:37

samo sekvencijalno!

FONForum

Strukture podataka 2007/08.

Ko je OnLine