Si_15_elementarne Strukture

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Elementarne strukture podataka Softwersko Inˇzenjerstvo

dr Zlatko Petrovi´c, red. prof.

April 1, 2008

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Doma´ ci

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Elementarne strukture – 1/1

U elementarne strukture podataka se ubrajaju: Nizovi Vezane liste Stek Red C–jezik ima samo nizove “ugradjene” u sam jezik dok je rad sa listama podrˇzan preko pointera!

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Elementarne strukture – 1/1

U elementarne strukture podataka se ubrajaju: Nizovi Vezane liste Stek Red C–jezik ima samo nizove “ugradjene” u sam jezik dok je rad sa listama podrˇzan preko pointera!

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Elementarne strukture – 1/1

U elementarne strukture podataka se ubrajaju: Nizovi Vezane liste Stek Red C–jezik ima samo nizove “ugradjene” u sam jezik dok je rad sa listama podrˇzan preko pointera!

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Elementarne strukture – 1/1

U elementarne strukture podataka se ubrajaju: Nizovi Vezane liste Stek Red C–jezik ima samo nizove “ugradjene” u sam jezik dok je rad sa listama podrˇzan preko pointera!

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Elementarne strukture – 1/1

U elementarne strukture podataka se ubrajaju: Nizovi Vezane liste Stek Red C–jezik ima samo nizove “ugradjene” u sam jezik dok je rad sa listama podrˇzan preko pointera!

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Nizovi – 1/3 Karakteristike nizova: Direktna veza izmedju niza i memmorijske lokacije (potrebno je znati adresu samo jednog elementa niza ostale adrese se mogu izraˇcunati preko indeksa) Jedan dopunski parametar ukazuje na aktivni element niza (indeks). Pre upotrebe niza mora biti poznat maksimalni broj elemenata (niz se ne moˇze naknadno nastaviti – gubi se veza izmedju indeksa i memorijskog mesta) U C-u se elementi niza a prozivaju: a[i], gde je i indeks (spoljni parametar) na element niza Slede´ci slajd ilustruje primenu niza za odredjivanje prostih brojeva manjih od nekog unapred zadatog broja NMAX. dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Nizovi – 1/3 Karakteristike nizova: Direktna veza izmedju niza i memmorijske lokacije (potrebno je znati adresu samo jednog elementa niza ostale adrese se mogu izraˇcunati preko indeksa) Jedan dopunski parametar ukazuje na aktivni element niza (indeks). Pre upotrebe niza mora biti poznat maksimalni broj elemenata (niz se ne moˇze naknadno nastaviti – gubi se veza izmedju indeksa i memorijskog mesta) U C-u se elementi niza a prozivaju: a[i], gde je i indeks (spoljni parametar) na element niza Slede´ci slajd ilustruje primenu niza za odredjivanje prostih brojeva manjih od nekog unapred zadatog broja NMAX. dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Nizovi – 1/3 Karakteristike nizova: Direktna veza izmedju niza i memmorijske lokacije (potrebno je znati adresu samo jednog elementa niza ostale adrese se mogu izraˇcunati preko indeksa) Jedan dopunski parametar ukazuje na aktivni element niza (indeks). Pre upotrebe niza mora biti poznat maksimalni broj elemenata (niz se ne moˇze naknadno nastaviti – gubi se veza izmedju indeksa i memorijskog mesta) U C-u se elementi niza a prozivaju: a[i], gde je i indeks (spoljni parametar) na element niza Slede´ci slajd ilustruje primenu niza za odredjivanje prostih brojeva manjih od nekog unapred zadatog broja NMAX. dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Nizovi – 1/3 Karakteristike nizova: Direktna veza izmedju niza i memmorijske lokacije (potrebno je znati adresu samo jednog elementa niza ostale adrese se mogu izraˇcunati preko indeksa) Jedan dopunski parametar ukazuje na aktivni element niza (indeks). Pre upotrebe niza mora biti poznat maksimalni broj elemenata (niz se ne moˇze naknadno nastaviti – gubi se veza izmedju indeksa i memorijskog mesta) U C-u se elementi niza a prozivaju: a[i], gde je i indeks (spoljni parametar) na element niza Slede´ci slajd ilustruje primenu niza za odredjivanje prostih brojeva manjih od nekog unapred zadatog broja NMAX. dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Nizovi – 1/3 Karakteristike nizova: Direktna veza izmedju niza i memmorijske lokacije (potrebno je znati adresu samo jednog elementa niza ostale adrese se mogu izraˇcunati preko indeksa) Jedan dopunski parametar ukazuje na aktivni element niza (indeks). Pre upotrebe niza mora biti poznat maksimalni broj elemenata (niz se ne moˇze naknadno nastaviti – gubi se veza izmedju indeksa i memorijskog mesta) U C-u se elementi niza a prozivaju: a[i], gde je i indeks (spoljni parametar) na element niza Slede´ci slajd ilustruje primenu niza za odredjivanje prostih brojeva manjih od nekog unapred zadatog broja NMAX. dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Nizovi – 2/3

Postaviti sve lememente niza a[i] = 1 osim prvog a[1] = 0. Varirati indekse i i j tako da je i · j < NMAX . Postaviti a[i · j] = 0. Odˇstampati indekse i za koje a[i] 6= 0!

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Nizovi – 2/3

Postaviti sve lememente niza a[i] = 1 osim prvog a[1] = 0. Varirati indekse i i j tako da je i · j < NMAX . Postaviti a[i · j] = 0. Odˇstampati indekse i za koje a[i] 6= 0!

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Nizovi – 2/3

Postaviti sve lememente niza a[i] = 1 osim prvog a[1] = 0. Varirati indekse i i j tako da je i · j < NMAX . Postaviti a[i · j] = 0. Odˇstampati indekse i za koje a[i] 6= 0!

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Nizovi – 2/3

Postaviti sve lememente niza a[i] = 1 osim prvog a[1] = 0. Varirati indekse i i j tako da je i · j < NMAX . Postaviti a[i · j] = 0. Odˇstampati indekse i za koje a[i] 6= 0!

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Nizovi – 3/3 #include <stdio.h> #define NMAX 1000 int main() { int i, j, a[NMAX+1]; for(a[1]=0, i=2; i<=NMAX; i++) a[i] = 1; for(i=2; i<=NMAX/2; i++) for(j=2; j<=NMAX/i; j++) a[i*j]=0; for(i=1; i<= NMAX; i++) if(a[i]) printf("%4d",i); printf("\n\n"); system("PAUSE"); return 0; dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

}

Doma´ ci

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Vezane liste – 1/12

Dodavanjem virtuelnih elemenata na poˇcetku i na kraju liste u mnogome se olakˇsavaju operacije sa listama

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Vezane liste – 1/12

Dodavanjem virtuelnih elemenata na poˇcetku i na kraju liste u mnogome se olakˇsavaju operacije sa listama

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Vezane liste – 2/12

Promena redosleda pristupa elementima liste bez prebacivanja samog sadrˇzaja. dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Vezane liste – 2/12

Promena redosleda pristupa elementima liste bez prebacivanja samog sadrˇzaja. dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Vezane liste – 3/12

Slika ilustruje dodavanje i izbacivanje elemenata iz liste. dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Doma´ ci

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Vezane liste – 3/12

Slika ilustruje dodavanje i izbacivanje elemenata iz liste. dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Doma´ ci

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 4/12 Karakteristike: Osnovna prednost u odnosu na nizove da veliˇcina moˇze da reaste (da se smanjuje) po potrebi Prestruktuiranje je jednostavno, dok kod nizova treba premeˇstati veliku koliˇcinu podataka. Sporo nalaˇzenje specifiˇcnog elementa. Dugo vremena za pronalaˇzenje prethodnog elementa. Slede´ci primer prikazuje primenu kruˇzne vezane liste da bi se simuliralo deˇcije razbrojavanje (en–ten–tini). Element liste treba da nosi podatak o detetu (broj) i pokazivaˇc na slede´ci element liste (dete do deteta koje se razbrojava) dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 4/12 Karakteristike: Osnovna prednost u odnosu na nizove da veliˇcina moˇze da reaste (da se smanjuje) po potrebi Prestruktuiranje je jednostavno, dok kod nizova treba premeˇstati veliku koliˇcinu podataka. Sporo nalaˇzenje specifiˇcnog elementa. Dugo vremena za pronalaˇzenje prethodnog elementa. Slede´ci primer prikazuje primenu kruˇzne vezane liste da bi se simuliralo deˇcije razbrojavanje (en–ten–tini). Element liste treba da nosi podatak o detetu (broj) i pokazivaˇc na slede´ci element liste (dete do deteta koje se razbrojava) dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 4/12 Karakteristike: Osnovna prednost u odnosu na nizove da veliˇcina moˇze da reaste (da se smanjuje) po potrebi Prestruktuiranje je jednostavno, dok kod nizova treba premeˇstati veliku koliˇcinu podataka. Sporo nalaˇzenje specifiˇcnog elementa. Dugo vremena za pronalaˇzenje prethodnog elementa. Slede´ci primer prikazuje primenu kruˇzne vezane liste da bi se simuliralo deˇcije razbrojavanje (en–ten–tini). Element liste treba da nosi podatak o detetu (broj) i pokazivaˇc na slede´ci element liste (dete do deteta koje se razbrojava) dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 4/12 Karakteristike: Osnovna prednost u odnosu na nizove da veliˇcina moˇze da reaste (da se smanjuje) po potrebi Prestruktuiranje je jednostavno, dok kod nizova treba premeˇstati veliku koliˇcinu podataka. Sporo nalaˇzenje specifiˇcnog elementa. Dugo vremena za pronalaˇzenje prethodnog elementa. Slede´ci primer prikazuje primenu kruˇzne vezane liste da bi se simuliralo deˇcije razbrojavanje (en–ten–tini). Element liste treba da nosi podatak o detetu (broj) i pokazivaˇc na slede´ci element liste (dete do deteta koje se razbrojava) dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 4/12 Karakteristike: Osnovna prednost u odnosu na nizove da veliˇcina moˇze da reaste (da se smanjuje) po potrebi Prestruktuiranje je jednostavno, dok kod nizova treba premeˇstati veliku koliˇcinu podataka. Sporo nalaˇzenje specifiˇcnog elementa. Dugo vremena za pronalaˇzenje prethodnog elementa. Slede´ci primer prikazuje primenu kruˇzne vezane liste da bi se simuliralo deˇcije razbrojavanje (en–ten–tini). Element liste treba da nosi podatak o detetu (broj) i pokazivaˇc na slede´ci element liste (dete do deteta koje se razbrojava) dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 4/12 Karakteristike: Osnovna prednost u odnosu na nizove da veliˇcina moˇze da reaste (da se smanjuje) po potrebi Prestruktuiranje je jednostavno, dok kod nizova treba premeˇstati veliku koliˇcinu podataka. Sporo nalaˇzenje specifiˇcnog elementa. Dugo vremena za pronalaˇzenje prethodnog elementa. Slede´ci primer prikazuje primenu kruˇzne vezane liste da bi se simuliralo deˇcije razbrojavanje (en–ten–tini). Element liste treba da nosi podatak o detetu (broj) i pokazivaˇc na slede´ci element liste (dete do deteta koje se razbrojava) dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 5/12 Uˇcitati broj dece u krugu i duˇzinu pesmice za razbrojavanje u reˇcima. Kreirati element liste za dete br 1, zapamtiti to kao poˇcetak liste. Sukcesivno kreirati ostale elemente liste tako ˇsto ´ce pokazivaˇc pretposlednje kreiranog element pokazivati na novokreirani. Novokreiranom elementu liste dodeliti identifikaciju (ime deteta) Pokazivaˇc poslednje kreiranog elementa usmeriti na prvi element liste dokle god pokazivaˇc elementa ne pokazuje na samog sebe izbaci M–ti element iz liste. Oslobodi memoriju Odˇstampaj “ime” (broj) preostalog elementa! dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 5/12 Uˇcitati broj dece u krugu i duˇzinu pesmice za razbrojavanje u reˇcima. Kreirati element liste za dete br 1, zapamtiti to kao poˇcetak liste. Sukcesivno kreirati ostale elemente liste tako ˇsto ´ce pokazivaˇc pretposlednje kreiranog element pokazivati na novokreirani. Novokreiranom elementu liste dodeliti identifikaciju (ime deteta) Pokazivaˇc poslednje kreiranog elementa usmeriti na prvi element liste dokle god pokazivaˇc elementa ne pokazuje na samog sebe izbaci M–ti element iz liste. Oslobodi memoriju Odˇstampaj “ime” (broj) preostalog elementa! dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 5/12 Uˇcitati broj dece u krugu i duˇzinu pesmice za razbrojavanje u reˇcima. Kreirati element liste za dete br 1, zapamtiti to kao poˇcetak liste. Sukcesivno kreirati ostale elemente liste tako ˇsto ´ce pokazivaˇc pretposlednje kreiranog element pokazivati na novokreirani. Novokreiranom elementu liste dodeliti identifikaciju (ime deteta) Pokazivaˇc poslednje kreiranog elementa usmeriti na prvi element liste dokle god pokazivaˇc elementa ne pokazuje na samog sebe izbaci M–ti element iz liste. Oslobodi memoriju Odˇstampaj “ime” (broj) preostalog elementa! dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 5/12 Uˇcitati broj dece u krugu i duˇzinu pesmice za razbrojavanje u reˇcima. Kreirati element liste za dete br 1, zapamtiti to kao poˇcetak liste. Sukcesivno kreirati ostale elemente liste tako ˇsto ´ce pokazivaˇc pretposlednje kreiranog element pokazivati na novokreirani. Novokreiranom elementu liste dodeliti identifikaciju (ime deteta) Pokazivaˇc poslednje kreiranog elementa usmeriti na prvi element liste dokle god pokazivaˇc elementa ne pokazuje na samog sebe izbaci M–ti element iz liste. Oslobodi memoriju Odˇstampaj “ime” (broj) preostalog elementa! dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 5/12 Uˇcitati broj dece u krugu i duˇzinu pesmice za razbrojavanje u reˇcima. Kreirati element liste za dete br 1, zapamtiti to kao poˇcetak liste. Sukcesivno kreirati ostale elemente liste tako ˇsto ´ce pokazivaˇc pretposlednje kreiranog element pokazivati na novokreirani. Novokreiranom elementu liste dodeliti identifikaciju (ime deteta) Pokazivaˇc poslednje kreiranog elementa usmeriti na prvi element liste dokle god pokazivaˇc elementa ne pokazuje na samog sebe izbaci M–ti element iz liste. Oslobodi memoriju Odˇstampaj “ime” (broj) preostalog elementa! dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 5/12 Uˇcitati broj dece u krugu i duˇzinu pesmice za razbrojavanje u reˇcima. Kreirati element liste za dete br 1, zapamtiti to kao poˇcetak liste. Sukcesivno kreirati ostale elemente liste tako ˇsto ´ce pokazivaˇc pretposlednje kreiranog element pokazivati na novokreirani. Novokreiranom elementu liste dodeliti identifikaciju (ime deteta) Pokazivaˇc poslednje kreiranog elementa usmeriti na prvi element liste dokle god pokazivaˇc elementa ne pokazuje na samog sebe izbaci M–ti element iz liste. Oslobodi memoriju Odˇstampaj “ime” (broj) preostalog elementa! dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 5/12 Uˇcitati broj dece u krugu i duˇzinu pesmice za razbrojavanje u reˇcima. Kreirati element liste za dete br 1, zapamtiti to kao poˇcetak liste. Sukcesivno kreirati ostale elemente liste tako ˇsto ´ce pokazivaˇc pretposlednje kreiranog element pokazivati na novokreirani. Novokreiranom elementu liste dodeliti identifikaciju (ime deteta) Pokazivaˇc poslednje kreiranog elementa usmeriti na prvi element liste dokle god pokazivaˇc elementa ne pokazuje na samog sebe izbaci M–ti element iz liste. Oslobodi memoriju Odˇstampaj “ime” (broj) preostalog elementa! dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 5/12 Uˇcitati broj dece u krugu i duˇzinu pesmice za razbrojavanje u reˇcima. Kreirati element liste za dete br 1, zapamtiti to kao poˇcetak liste. Sukcesivno kreirati ostale elemente liste tako ˇsto ´ce pokazivaˇc pretposlednje kreiranog element pokazivati na novokreirani. Novokreiranom elementu liste dodeliti identifikaciju (ime deteta) Pokazivaˇc poslednje kreiranog elementa usmeriti na prvi element liste dokle god pokazivaˇc elementa ne pokazuje na samog sebe izbaci M–ti element iz liste. Oslobodi memoriju Odˇstampaj “ime” (broj) preostalog elementa! dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Vezane liste – 6/12 #include <stdio.h> struct node int key; struct node *next; ; int main() { int i, N, M; struct node *t, *x; printf("Unesi N(=9) i M(=5) : "); scanf("%d %d", &N, &M); t = (struct node *) malloc(sizeof *t); t->key = 1; x=t; for(i=2; i<= N; i++) { t->next=(struct node *) malloc(sizeof *t); t=t->next; t->key=i; } t->next=x; dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Doma´ ci

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Vezane liste – 7/12

while(t != t->next) { for(i=1; i < M; i++) t = t->next; printf("%d ",t->next->key); x=t->next; t->next = t->next->next; free(x); } printf("%d\n",t->key); system("PAUSE"); return 0; }

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Abstraktni

Doma´ ci

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Vezane liste – 8/12

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Vezane liste – 9/12

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 10/12 Osnovne operacije sa listama: Kreiranje liste Dodavanje elemenata listi Brisanje elemenata iz liste Pronalazenje specifiˇcnog elementa Prikaz liste Niz u sebi moˇze ˇcuvati viˇse listi U poˇcetku postoji samo jedna lista koja povezuje sve elemente niza (lista raspoloˇsivog prostora) Dodavanje elementa nekoj specifiˇcnoj listi zanˇc oduzimanje elementa listi slobodnog prostora Brisanje elementa iz neke liste znaˇci dodavanje elementa listi raspoloˇzivog prostora dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 10/12 Osnovne operacije sa listama: Kreiranje liste Dodavanje elemenata listi Brisanje elemenata iz liste Pronalazenje specifiˇcnog elementa Prikaz liste Niz u sebi moˇze ˇcuvati viˇse listi U poˇcetku postoji samo jedna lista koja povezuje sve elemente niza (lista raspoloˇsivog prostora) Dodavanje elementa nekoj specifiˇcnoj listi zanˇc oduzimanje elementa listi slobodnog prostora Brisanje elementa iz neke liste znaˇci dodavanje elementa listi raspoloˇzivog prostora dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 10/12 Osnovne operacije sa listama: Kreiranje liste Dodavanje elemenata listi Brisanje elemenata iz liste Pronalazenje specifiˇcnog elementa Prikaz liste Niz u sebi moˇze ˇcuvati viˇse listi U poˇcetku postoji samo jedna lista koja povezuje sve elemente niza (lista raspoloˇsivog prostora) Dodavanje elementa nekoj specifiˇcnoj listi zanˇc oduzimanje elementa listi slobodnog prostora Brisanje elementa iz neke liste znaˇci dodavanje elementa listi raspoloˇzivog prostora dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 10/12 Osnovne operacije sa listama: Kreiranje liste Dodavanje elemenata listi Brisanje elemenata iz liste Pronalazenje specifiˇcnog elementa Prikaz liste Niz u sebi moˇze ˇcuvati viˇse listi U poˇcetku postoji samo jedna lista koja povezuje sve elemente niza (lista raspoloˇsivog prostora) Dodavanje elementa nekoj specifiˇcnoj listi zanˇc oduzimanje elementa listi slobodnog prostora Brisanje elementa iz neke liste znaˇci dodavanje elementa listi raspoloˇzivog prostora dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 10/12 Osnovne operacije sa listama: Kreiranje liste Dodavanje elemenata listi Brisanje elemenata iz liste Pronalazenje specifiˇcnog elementa Prikaz liste Niz u sebi moˇze ˇcuvati viˇse listi U poˇcetku postoji samo jedna lista koja povezuje sve elemente niza (lista raspoloˇsivog prostora) Dodavanje elementa nekoj specifiˇcnoj listi zanˇc oduzimanje elementa listi slobodnog prostora Brisanje elementa iz neke liste znaˇci dodavanje elementa listi raspoloˇzivog prostora dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 10/12 Osnovne operacije sa listama: Kreiranje liste Dodavanje elemenata listi Brisanje elemenata iz liste Pronalazenje specifiˇcnog elementa Prikaz liste Niz u sebi moˇze ˇcuvati viˇse listi U poˇcetku postoji samo jedna lista koja povezuje sve elemente niza (lista raspoloˇsivog prostora) Dodavanje elementa nekoj specifiˇcnoj listi zanˇc oduzimanje elementa listi slobodnog prostora Brisanje elementa iz neke liste znaˇci dodavanje elementa listi raspoloˇzivog prostora dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 10/12 Osnovne operacije sa listama: Kreiranje liste Dodavanje elemenata listi Brisanje elemenata iz liste Pronalazenje specifiˇcnog elementa Prikaz liste Niz u sebi moˇze ˇcuvati viˇse listi U poˇcetku postoji samo jedna lista koja povezuje sve elemente niza (lista raspoloˇsivog prostora) Dodavanje elementa nekoj specifiˇcnoj listi zanˇc oduzimanje elementa listi slobodnog prostora Brisanje elementa iz neke liste znaˇci dodavanje elementa listi raspoloˇzivog prostora dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 10/12 Osnovne operacije sa listama: Kreiranje liste Dodavanje elemenata listi Brisanje elemenata iz liste Pronalazenje specifiˇcnog elementa Prikaz liste Niz u sebi moˇze ˇcuvati viˇse listi U poˇcetku postoji samo jedna lista koja povezuje sve elemente niza (lista raspoloˇsivog prostora) Dodavanje elementa nekoj specifiˇcnoj listi zanˇc oduzimanje elementa listi slobodnog prostora Brisanje elementa iz neke liste znaˇci dodavanje elementa listi raspoloˇzivog prostora dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Vezane liste – 10/12 Osnovne operacije sa listama: Kreiranje liste Dodavanje elemenata listi Brisanje elemenata iz liste Pronalazenje specifiˇcnog elementa Prikaz liste Niz u sebi moˇze ˇcuvati viˇse listi U poˇcetku postoji samo jedna lista koja povezuje sve elemente niza (lista raspoloˇsivog prostora) Dodavanje elementa nekoj specifiˇcnoj listi zanˇc oduzimanje elementa listi slobodnog prostora Brisanje elementa iz neke liste znaˇci dodavanje elementa listi raspoloˇzivog prostora dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Vezane liste – 11/12

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Vezane liste – 12/12

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Stek – 1/5

Za razliku od niza gde je pristup podatku (menjanje, brisanje) direktan (zavisi od indeksa), stek ima znatno ograniˇcenija pravila pristupa: Novi elementi se mogu dodati samo na vrh steka Elementi se mogu skidati samo sa vrha steka Smanjene mogu´cnosti manipulacije podacima (elementima)! dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Stek – 1/5

Za razliku od niza gde je pristup podatku (menjanje, brisanje) direktan (zavisi od indeksa), stek ima znatno ograniˇcenija pravila pristupa: Novi elementi se mogu dodati samo na vrh steka Elementi se mogu skidati samo sa vrha steka Smanjene mogu´cnosti manipulacije podacima (elementima)! dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Stek – 1/5

Za razliku od niza gde je pristup podatku (menjanje, brisanje) direktan (zavisi od indeksa), stek ima znatno ograniˇcenija pravila pristupa: Novi elementi se mogu dodati samo na vrh steka Elementi se mogu skidati samo sa vrha steka Smanjene mogu´cnosti manipulacije podacima (elementima)! dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Stek – 2/5 Treba prevesti aritmetiˇcke izraze kod kojih je redosled operacija u potpunosti determinisan zagradama (ne prioritetom operacija) iz “infix” notacije u “postfix” notaciju! Ovo je tipiˇcna primena za stek Kod postfiks notacije nisu potrebne zagrade Potrebno je prvo napraviti funkcije za Iniciranje steka Ubacivanje elementa u stek Vadjenje elementa iz steka Proveru da li je stek prazan

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Stek – 2/5 Treba prevesti aritmetiˇcke izraze kod kojih je redosled operacija u potpunosti determinisan zagradama (ne prioritetom operacija) iz “infix” notacije u “postfix” notaciju! Ovo je tipiˇcna primena za stek Kod postfiks notacije nisu potrebne zagrade Potrebno je prvo napraviti funkcije za Iniciranje steka Ubacivanje elementa u stek Vadjenje elementa iz steka Proveru da li je stek prazan

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Stek – 2/5 Treba prevesti aritmetiˇcke izraze kod kojih je redosled operacija u potpunosti determinisan zagradama (ne prioritetom operacija) iz “infix” notacije u “postfix” notaciju! Ovo je tipiˇcna primena za stek Kod postfiks notacije nisu potrebne zagrade Potrebno je prvo napraviti funkcije za Iniciranje steka Ubacivanje elementa u stek Vadjenje elementa iz steka Proveru da li je stek prazan

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Stek – 2/5 Treba prevesti aritmetiˇcke izraze kod kojih je redosled operacija u potpunosti determinisan zagradama (ne prioritetom operacija) iz “infix” notacije u “postfix” notaciju! Ovo je tipiˇcna primena za stek Kod postfiks notacije nisu potrebne zagrade Potrebno je prvo napraviti funkcije za Iniciranje steka Ubacivanje elementa u stek Vadjenje elementa iz steka Proveru da li je stek prazan

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Stek – 2/5 Treba prevesti aritmetiˇcke izraze kod kojih je redosled operacija u potpunosti determinisan zagradama (ne prioritetom operacija) iz “infix” notacije u “postfix” notaciju! Ovo je tipiˇcna primena za stek Kod postfiks notacije nisu potrebne zagrade Potrebno je prvo napraviti funkcije za Iniciranje steka Ubacivanje elementa u stek Vadjenje elementa iz steka Proveru da li je stek prazan

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Stek – 2/5 Treba prevesti aritmetiˇcke izraze kod kojih je redosled operacija u potpunosti determinisan zagradama (ne prioritetom operacija) iz “infix” notacije u “postfix” notaciju! Ovo je tipiˇcna primena za stek Kod postfiks notacije nisu potrebne zagrade Potrebno je prvo napraviti funkcije za Iniciranje steka Ubacivanje elementa u stek Vadjenje elementa iz steka Proveru da li je stek prazan

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Stek – 2/5 Treba prevesti aritmetiˇcke izraze kod kojih je redosled operacija u potpunosti determinisan zagradama (ne prioritetom operacija) iz “infix” notacije u “postfix” notaciju! Ovo je tipiˇcna primena za stek Kod postfiks notacije nisu potrebne zagrade Potrebno je prvo napraviti funkcije za Iniciranje steka Ubacivanje elementa u stek Vadjenje elementa iz steka Proveru da li je stek prazan

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Stek – 3/5 #include <stdio.h> struct Stek { int element; struct Stek *next; }; static struct Stek *head, *z, *t; StackInit(void) { head = (struct Stek *) malloc(sizeof *head); z = (struct Stek *) malloc(sizeof *z); head->next = z; head->element = 0; z->next = z; return; } dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Stek – 4/5 push(int v) { t = (struct Stek *) malloc(sizeof *t); t->element = v; t->next = head->next; head->next = t; return; } int pop(void) { int x; t = head->next; head->next = t->next; x = t->element; free(t); return x; } dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Doma´ ci

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Stek – 5/5 int StekPrazan(void) { return head->next == z;

}

int main() { char c; for(StackInit(); scanf("%c", &c) != EOF; ) { while(c >= ’0’ && c <= ’9’) { printf("%c", c); scanf("%c", &c); } if(c == ’)’) { printf(" %c", (char)pop()); } if(c == ’+’ || c == ’*’) push( (int) c ); if(c != ’(’) printf(" "); } if(!StekPrazan()) printf("=%c",(char)pop()); printf("\n"); system("PAUSE"); return 0; } dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Doma´ ci

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Postfix Interpreter – 1/4 Napisati postfiks interpreter koji: Uˇcitava postfiks zapis karakter po karakter Ukoliko je uˇcitani karakter praznina vra´ca se na prethodni korak Ukoliko se radi o ciframa konvertuje ih u broj i smeˇsta u numeriˇcki stek (ˇcita do prvog karaktera ” ”). Ukoliko se radi o binarnoj operaciji (+ ili *) skida dva broja sa steka izvrˇsava operaciju i vra´ca rezultat na stek Ponavlja prethodno sve dok ima postfiks zapisa (dok ne naidje na KRAJ) Rezultat izraˇcunavanja je na vrhu steka dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Postfix Interpreter – 1/4 Napisati postfiks interpreter koji: Uˇcitava postfiks zapis karakter po karakter Ukoliko je uˇcitani karakter praznina vra´ca se na prethodni korak Ukoliko se radi o ciframa konvertuje ih u broj i smeˇsta u numeriˇcki stek (ˇcita do prvog karaktera ” ”). Ukoliko se radi o binarnoj operaciji (+ ili *) skida dva broja sa steka izvrˇsava operaciju i vra´ca rezultat na stek Ponavlja prethodno sve dok ima postfiks zapisa (dok ne naidje na KRAJ) Rezultat izraˇcunavanja je na vrhu steka dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Postfix Interpreter – 1/4 Napisati postfiks interpreter koji: Uˇcitava postfiks zapis karakter po karakter Ukoliko je uˇcitani karakter praznina vra´ca se na prethodni korak Ukoliko se radi o ciframa konvertuje ih u broj i smeˇsta u numeriˇcki stek (ˇcita do prvog karaktera ” ”). Ukoliko se radi o binarnoj operaciji (+ ili *) skida dva broja sa steka izvrˇsava operaciju i vra´ca rezultat na stek Ponavlja prethodno sve dok ima postfiks zapisa (dok ne naidje na KRAJ) Rezultat izraˇcunavanja je na vrhu steka dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Postfix Interpreter – 1/4 Napisati postfiks interpreter koji: Uˇcitava postfiks zapis karakter po karakter Ukoliko je uˇcitani karakter praznina vra´ca se na prethodni korak Ukoliko se radi o ciframa konvertuje ih u broj i smeˇsta u numeriˇcki stek (ˇcita do prvog karaktera ” ”). Ukoliko se radi o binarnoj operaciji (+ ili *) skida dva broja sa steka izvrˇsava operaciju i vra´ca rezultat na stek Ponavlja prethodno sve dok ima postfiks zapisa (dok ne naidje na KRAJ) Rezultat izraˇcunavanja je na vrhu steka dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Postfix Interpreter – 1/4 Napisati postfiks interpreter koji: Uˇcitava postfiks zapis karakter po karakter Ukoliko je uˇcitani karakter praznina vra´ca se na prethodni korak Ukoliko se radi o ciframa konvertuje ih u broj i smeˇsta u numeriˇcki stek (ˇcita do prvog karaktera ” ”). Ukoliko se radi o binarnoj operaciji (+ ili *) skida dva broja sa steka izvrˇsava operaciju i vra´ca rezultat na stek Ponavlja prethodno sve dok ima postfiks zapisa (dok ne naidje na KRAJ) Rezultat izraˇcunavanja je na vrhu steka dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Postfix Interpreter – 1/4 Napisati postfiks interpreter koji: Uˇcitava postfiks zapis karakter po karakter Ukoliko je uˇcitani karakter praznina vra´ca se na prethodni korak Ukoliko se radi o ciframa konvertuje ih u broj i smeˇsta u numeriˇcki stek (ˇcita do prvog karaktera ” ”). Ukoliko se radi o binarnoj operaciji (+ ili *) skida dva broja sa steka izvrˇsava operaciju i vra´ca rezultat na stek Ponavlja prethodno sve dok ima postfiks zapisa (dok ne naidje na KRAJ) Rezultat izraˇcunavanja je na vrhu steka dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Postfix Interpreter – 2/4 #include <stdio.h> #define KRAJ ’;’ struct Stek { int element; struct Stek *next; }; static struct Stek *head, *z, *t; StackInit(void) { head = (struct Stek *) malloc(sizeof *head); z = (struct Stek *) malloc(sizeof *z); head->next = z; head->element = 0; z->next = z; return; } dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Doma´ ci

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Postfix Interpreter – 3/4 push(int v) { t = (struct Stek *) malloc(sizeof *t); t->element = v; t->next = head->next; head->next = t; return; } int pop(void) { int x; t = head->next; head->next = t->next; x = t->element; free(t); return x; } int StekPrazan(void) { dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

return head->next == z; }

Doma´ ci

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Postfix Interpreter – 4/4 int main() { char c; int x; for(StackInit(); (c=getchar()) != KRAJ; ) { x = 0; if(c==’ ’) continue; if(c==’+’) x = pop()+pop(); if(c==’*’) x = pop()*pop(); while(c>=’0’ && c<=’9’) { x = 10*x+(c-’0’); c = getchar(); } push(x); } x=pop(); printf("\nRezultat je: %d\n", x); system("PAUSE"); return 0; } dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Doma´ ci

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Redovi – 1/1 Joˇs jedan tip strukture podataka sa ograniˇcenim pristupom. Definisane su samo dve operacije: insert (umetni) remove (ukloni) Procesiraju se podaci redosledom ulaska u strukturu

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Redovi – 1/1 Joˇs jedan tip strukture podataka sa ograniˇcenim pristupom. Definisane su samo dve operacije: insert (umetni) remove (ukloni) Procesiraju se podaci redosledom ulaska u strukturu

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Redovi – 1/1 Joˇs jedan tip strukture podataka sa ograniˇcenim pristupom. Definisane su samo dve operacije: insert (umetni) remove (ukloni) Procesiraju se podaci redosledom ulaska u strukturu

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Implementacija reda nizom – 1/1 #define max 100 static int queue[max+1], head, tail; void put(int v) { queue[tail++] = v; if(tail > max) tail = 0; } int get() { int t = queue[head++]; if(head > max) head = 0; return t; } queue init() { head=; tail=0; } int queueempty() { return head==tail; } dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Abstraktni

Doma´ ci

Mozgalica

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Abstraktni tip podataka – 1/1

Kada se podaci opisuju operacijama nad njima, kaˇze se da se radi o abstraktnom tipu podataka. Za razliku od podataka koji se sre´cu za konkretnu aplikaciju! Ideja je da se razdvoji koncept od implementacije Sa podacima se komunicira preko funkcija, a ne direktno Ovo je vaˇzno za velike programe, jer se time uproˇs´cava njihova kompleksnost!

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Abstraktni tip podataka – 1/1

Kada se podaci opisuju operacijama nad njima, kaˇze se da se radi o abstraktnom tipu podataka. Za razliku od podataka koji se sre´cu za konkretnu aplikaciju! Ideja je da se razdvoji koncept od implementacije Sa podacima se komunicira preko funkcija, a ne direktno Ovo je vaˇzno za velike programe, jer se time uproˇs´cava njihova kompleksnost!

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Abstraktni tip podataka – 1/1

Kada se podaci opisuju operacijama nad njima, kaˇze se da se radi o abstraktnom tipu podataka. Za razliku od podataka koji se sre´cu za konkretnu aplikaciju! Ideja je da se razdvoji koncept od implementacije Sa podacima se komunicira preko funkcija, a ne direktno Ovo je vaˇzno za velike programe, jer se time uproˇs´cava njihova kompleksnost!

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Abstraktni tip podataka – 1/1

Kada se podaci opisuju operacijama nad njima, kaˇze se da se radi o abstraktnom tipu podataka. Za razliku od podataka koji se sre´cu za konkretnu aplikaciju! Ideja je da se razdvoji koncept od implementacije Sa podacima se komunicira preko funkcija, a ne direktno Ovo je vaˇzno za velike programe, jer se time uproˇs´cava njihova kompleksnost!

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Doma´ci zadatak – 1/1 Napiˇsi funkciju moveNextToFront(struct lista *t) za vezanu listu koja pomera element koji se nalazi iza onog na koji pokazuje t na sam poˇcetak liste (iza head) Napiˇsi funkciju exchange(struct lista *t, struct lista *u) za vezanu listu tako da izmenjuje poziciju elemenata koji se nalaze iza onih na koje pokazuju pointeri t i u! Napiˇsi funkcije za umetanje i brisanje elemenata iz dvostruko povezane liste (lista sa dva pointera: jedan pokazuje unapred drugi unazad) Napiˇsi funkcije za rad sa redom koriste´ci se vezanom listom

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Doma´ci zadatak – 1/1 Napiˇsi funkciju moveNextToFront(struct lista *t) za vezanu listu koja pomera element koji se nalazi iza onog na koji pokazuje t na sam poˇcetak liste (iza head) Napiˇsi funkciju exchange(struct lista *t, struct lista *u) za vezanu listu tako da izmenjuje poziciju elemenata koji se nalaze iza onih na koje pokazuju pointeri t i u! Napiˇsi funkcije za umetanje i brisanje elemenata iz dvostruko povezane liste (lista sa dva pointera: jedan pokazuje unapred drugi unazad) Napiˇsi funkcije za rad sa redom koriste´ci se vezanom listom

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Doma´ci zadatak – 1/1 Napiˇsi funkciju moveNextToFront(struct lista *t) za vezanu listu koja pomera element koji se nalazi iza onog na koji pokazuje t na sam poˇcetak liste (iza head) Napiˇsi funkciju exchange(struct lista *t, struct lista *u) za vezanu listu tako da izmenjuje poziciju elemenata koji se nalaze iza onih na koje pokazuju pointeri t i u! Napiˇsi funkcije za umetanje i brisanje elemenata iz dvostruko povezane liste (lista sa dva pointera: jedan pokazuje unapred drugi unazad) Napiˇsi funkcije za rad sa redom koriste´ci se vezanom listom

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Doma´ci zadatak – 1/1 Napiˇsi funkciju moveNextToFront(struct lista *t) za vezanu listu koja pomera element koji se nalazi iza onog na koji pokazuje t na sam poˇcetak liste (iza head) Napiˇsi funkciju exchange(struct lista *t, struct lista *u) za vezanu listu tako da izmenjuje poziciju elemenata koji se nalaze iza onih na koje pokazuju pointeri t i u! Napiˇsi funkcije za umetanje i brisanje elemenata iz dvostruko povezane liste (lista sa dva pointera: jedan pokazuje unapred drugi unazad) Napiˇsi funkcije za rad sa redom koriste´ci se vezanom listom

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka

Elem. strukt.

Nizovi

Vezane liste

Stek

Postfix

Redovi

Implementacija

Abstraktni

Doma´ ci

Mozgalica

Mozgalica – 1/1 U vre´cici se nalazi 25 zlatnika. Zna se da je jedan zlatnik lakˇsi od ostalih 24. Koliko je minimalno potrebno merenja na vagi sa tasovima da bi se pronaˇsao defektni zlatnik?

dr Zlatko Petrovi´ c, red. prof. Elementarne strukture podataka