ALGORITMI I STRUKTURE PODATAKA

1. Podsećanje: Koji rezultat vraćaju funkcije floor(x), ceil(x) u programskom jeziku C, ako x=4.7?

Neka x∈ℝ. Važi da: x-1<⌊x⌋<=x<=⌈x⌉<x+1

Koliko je ⌊7.51⌋, ⌈7.51⌉?

Neka n∈ℕ. Važi da: ⌊n/2⌋+⌈n/2⌉=n

2. Podsećanje:

Odredite vremensku slozenost sledecih fragmenata programskog kôda.

Broj koraka prikazati u obliku polinomijalnog izraza i O notaciji.

if (x == 0)

for (i=0; i<=n-1; i++)

for (j=0; j<n; j++) A[i][ j] = 0;

else for (i=0;i<=n-1;i++) A[i][ i] = 1;

2 Strukture podataka: stek, povezana lista, red

Na pretprošlom času smo na primerima videli da programer izborom strukture podataka može da utiče na efikasnost konstruisanog algoritama.

Zato je važno poznavati tehnike rada sa strukturama podataka, ali i složenost pojedinih operacija nad strukturom podataka.

PROGRAM = ALGORITAM + STRUKTURA PODATAKA

Strukture podataka se mogu grubo klasifikovati:
linearne i nelinearne (ako se gledaju relacije elemenata u susedstvu)
      Navedite primer linearne i nelinearne strukture.
statičke i dinamičke (ako se gledaju kapaciteti i mogućnost izmene veličine)
      Navedite primer statičke i dinamičke strukture.

Podsećanje:

1. Koliko elemenata sadrži niz a definisan sa : int a [10][3][5]? A koliko bitova, ako int zauzima 2 bajta?

2. Koliki je maksimalan i minimalan ideks niza deklarisanog sa: char a [100]?

3. Koje podatke o povezanoj listi najčešće moramo da imamo?

4. Koje su najčešće operacije nad elementima liste?

5. Navedite načine na koje se liste mogu implementirati?

6. Kakva je prednost dvostruko povezanih lista u odnosu na obične (jednostruko povezane) liste?

7. Definišite kružnu listu? Gde se koristi?

8. Opišite FIFO i LIFO principe rada.

9. Koje podatke o steku najčešće moramo da imamo?

10. Koje su najčešće operacije nad elementima steka?

11. Navedite bar dve primene steka.

2.1 STEK

STEK - kolekcija podataka sa kojima se radi po LIFO(Last In First Out) principu;

Procedure za rad sa stekom

Da li je stek prazan

Postavi element na vrh steka (tzv. operacija PUSH)

Skini element sa vrha steka (tzv. operacija POP)

Stek je prazan ako mu se vrh nije pomerio iz inicijalnog stanja.

Funkcijom push se formira sadrzaj steka - dodavanjem elemenata na vrh steka.

Funkcijom pop elementi se uzimaju sa steka po LIFO redosledu (najpre se uzima element sa vrha steka)
Upotreba steka:

IV glava K&R - primer sa kalkulatorom i izračunavanje u postfiks notaciji (podsećanje: AB+ ~ A+B,         ABCD-*+EF-G*H/+ ~ A+B*(C-D)+(E-F)*G/H ) ,

provera uparenosti HTML etiketa,

provera uparivanja zagrada (leksička analiza,)

kod editora teksta (editovanje reda),

pri rekurziji i pozivu potprograma

Ako se pokuša skidanja elementa sa praznog steka, nastaje potkoračenje (underflow).

Stek ograničenog kapaciteta (sa MAX elemenata) se može implementirati pomoću niza Stek[0..MAX-1]
tako da element Stek[0] je na dnu steka, element Stek[MAX-1] je na vrhu steka.
Ako se pokuša umetanje elementa na poziciju MAX, nastaje prekoračenje (overflow).

1. NCP (napisati C program) koji će proveriti uparenost etiketa u ulaznoj HTML datoteci.
Složena etiketa A (poseduje otvaracA i zatvaracA) je korektno ugnježdena u etiketu B ako je otvaracA iza otvaracB i zatvaracA ispred zatvaracB.

Pretpostaviti da u ulaznoj datoteci nema prostih etiketa (onih koje nemaju zatvarac).

Jednostavnosti radi, pretpostaviti da maksimalna dubina ugnježdenosti je do nivoa 3

(dakle, nivo tipa <B><I>...</I> <I><p> </p></i></b> se pojavljuje, dok nivo tipa <B><I>...<p><a href="nesto.htm">...</A> </p></i></b> se ne pojavljuje). 

Pretpostaviti da nazivi etiketa su jednoslovni (P,Q,B,I,U,S,A,...).

Pri nailasku na nekorektno uparenu etiketu, prekinuti dalju proveru i ispisati poruku o grešci na standardni izlaz.
TEST PRIMER:
<P align="center">Pasus 1 </P>
<p><B><q>Citat 1</q> <A href="link1.htm"> Hiperveza 1 </a> <Q> Citat 2 </q> ... </b>...</p>
<p><q>Citat 2</Q> <A href="link2.html"> Hiperveza 2 </a> <B> <A href="link3.htm"> Hiperveza 3 </a>...</B> </P>

IDEJA: 

 Svaka otvorena etiketa stavi se na stek 
 Pri nailasku na zatvorenu etikete proveravamo da li je stek prazan. 
 Ako jeste,  nekorektna uparenost. 
 Takođe se proveri i  da li se na vrhu steka za tekucu zatvorenu etiketu nalazi odgovarajuca otvorena etiketa. 
 Ako ne, nekorektna uparenost. Ako da, skine se otvorena etiketa sa vrha steka. 
 

    Prazan stek

P

    push(P)
    pop(), provera </p > == pop()

P

    push(P)

P	B

    push(B)

P	B	Q

    push(Q)

P	B

    provera </q > == pop()

#include <stdio.h>
#include <ctype.h>
 
#define MAX  3  /*maksimalna dubina steka*/
void push(char); /*stavlja etiketu na stek */
char pop(void); /*vraca etiketu skinutu sa vrha steka */
 
/*globalne promenljive */
char Stek[MAX];  /*stek realizovan kao niz*/
int vrh;  /*naredna slobodna pozicija na steku */
int greska=0; /*indikator nailaska na pojavu nekorektne ugnjezdenosti*/ 
main()
{
    int c; /*znak sa ulaza*/
 int rez; /*rezultat skidanja sa steka*/
 
 while ( (c=getchar()) != EOF  && !greska)
 if (c=='<')
     {   if (isalnum(c=getchar()) )  push(toupper(c)); 
                 /*etiketa otvarac(<isalnum...) se stavlja na stek, 
 naziv se bez smanjenja opstosti
                   smesta veliki slovima u steku, zbog kasnijeg case insensitive 
 poredjenja naziva etiketa otvaraca i zatvaraca; ne zaboravite 
 da u HTMLu je naziv iste etikete i <Table> i <taBLE> */
 
 if (c=='/')  /*obrada zatvaraca, ali samo ako je oblika </slovo...> */
 { if (isalnum(c=getchar()) )  rez=pop();
 if (toupper(c) != rez)  {printf("Greska: etiketa %c\n", c);
 greska=1; }
             }
     }
 
 if (!greska) printf("\nKorektna uparenost unutar HTML datoteke\n");
}
 
void push(char c)  /*smesta etiketu c na vrh steka */
{    if (vrh<MAX) Stek[vrh++]=c;
 else { greska=1;
printf("\nGreska: stek je pun, dubina je %d, nemoguce je smestiti %c\n", MAX, c);
          }
} //T(n)=O(1), gde je n duzina steka
 
char pop(void) /*kao rezultat daje etiketu skinutu sa vrha steka*/
{
 if (vrh>0) return Stek[--vrh];
 else { greska=1; printf("\nGreska: stek je prazan\n");  return 0; }
 } //T(n)=O(1), gde je n duzina steka
 

2. Jednodimenzioni niz može se iskoristiti za smeštanje dva steka tako da prvi stek raste nagore od levog kraja niza,

a drugi stek raste nadole sa desnog kraja niza.

Implementirajte stek operacije (kreiranje steka, provera da li je stek prazan, provera da li je stek pun, umetanje elementa u stek, uklanjanje elementa sa steka) za ovaj niz.

Ocenite vremensku složenost svake operacije (O notacija). Pretpostaviti da niz pozitivnih celih brojeva je dimeznije n.

RESENJE:

Neka su globalne promenljive

A - niz pozitivnih celih brojeva dimenzije n koji se koristi za smeštanje stekova

S1- indeks člana niza A koji pripada steku koji raste nagore od levog kraja

S2 - indeks člana niza A koji pripada steku koji raste nadole od desnog kraja.

int Stack-Stvori1(void) { S1 = -1; return S1; }

int StackStvori2(int n) { S2 = n; return S2; }

int StackPrazan1(void) { if (S1 = = -1) return 1; else return 0; }

int StackPrazan2(int n) {if (S2 == n) return 1; else return 0; }

int StackPun(void) {if (S1 >= S2-1) return 1; else return 0; }

void PushS1(int x)

{ if (StackPun() {printf(“Prekoracenje “); exit(1); }

else { S1 = S1 + 1; A[S1] = x;}

}

void PushS2(int x)

{

if (StackPun() {printf(“Prekoracenje “); exit(1); }

else { S2 = S2 − 1; A[S2] = x;}

}

int PopS1(void)

{

int x=0; /* clan niza pozitivnih celih brojeva */

if (!StackPrazan1() ) /* ako nije 1. stek prazan */

{ x = A[S1]; S1--; return x;}

else {printf(“Potkoracenje “); exit(1); }

}

int PopS2(int n)

{ int x=0;

if (!StackPrazan2(n) ) /* ako nije 2. stek prazan */

{ x = A[S2]; S2++; return x;}

else {printf(“Potkoracenje “); exit(1); }

}

Vreme izvrsavanja svih operacija za rad sa stekom je O(1).

2.2 POVEZANA LISTA

Povezana lista je struktura podataka čiji su elementi uređeni linearno. Ali, za razliku od niza, čije linearno uređenje

je određeno nizom indeksa, kod povezane liste je uređenje određeno pokazivačem u svakom od objekata.

Liste su vrlo rasprostranjene u programiranju – lista događaja, lista poruka, predstavljanje polinoma,…

Lista može biti jednostruko, dvostruko povezana. Može biti sortirana ili ne, može biti kružna ili ne.

 
3. /* Rad sa povezanom listom - iterativne verzije funkcija za rad sa povezanom listom                 */
 
 
#include <stdio.h>
#include <stdlib.h>
typedef struct elem { int broj; struct elem *sled; } Elem; /*Element liste*/
 
int duz (Elem *lst);                    /* Broj elemenata liste.          */
void pisi (Elem *lst);                  /* Ispisivanje liste.             */
Elem *na_pocetak (Elem *lst, int b);    /* Dodavanje na pocetak.          */
Elem *na_kraj (Elem *lst, int b);       /* Dodavanje na kraj.             */
Elem *citaj1 (int n);    /* Citanje liste stavljajuci brojeve na pocetak. */
Elem *citaj2 (int n);    /* Citanje liste stavljajuci brojeve na kraj.    */
Elem *umetni (Elem *lst, int b);        /* Umetanje u uredjenu listu.     */
void brisi (Elem *lst);                 /* Brisanje svih elemenata liste. */
Elem *izostavi (Elem *lst, int b); /* Izostavljanje svakog pojavljivanja. */
 
 
void main () {
  Elem *lst = NULL; int kraj = 0, izbor, broj, n;
 while (!kraj) {
 printf ("\n1. Dodavanje broja na pocetak liste\n"
 "2. Dodavanje broja na kraj liste\n"
 "3. Umetanje broja u uredjenu listu\n"
              "4. Izostavljanje broja iz liste\n"
              "5. Brisanje svih elemenata liste\n"
              "6. Citanje uz obrtanje redosleda brojeva\n"
              "7. Citanje uz cuvanje redosleda brojeva\n"
              "8. Odredjivanje duzine liste\n"
              "9. Ispisivanje liste\n"
              "0. Zavrsetak rada\n\n"
              "Vas izbor? "
            );
 scanf ("%d", &izbor);
 switch (izbor) {
 case 1: case 2: case 3: case 4:
 printf ("Broj?      "); scanf ("%d", &broj);
 switch (izbor) {
      case 1: /* Dodavanje broja na pocetak liste: */ 
  lst = na_pocetak (lst, broj); break;
      case 2: /* Dodavanje broja na kraj liste: */
        lst = na_kraj (lst, broj);    break;
      case 3: /* Umetanje broja u uredjenu listu: */
        lst = umetni (lst, broj);     break;
      case 4: /* Izostavljanje broja iz liste: */
 lst = izostavi (lst, broj);   break;
      }
 break;
 case 5: /* Brisanje svih elemenata liste: */
 brisi (lst); lst = NULL; break;
 case 6: case 7: /* Citanje liste: */
 printf ("Duzina?    "); scanf ("%d", &n);
      printf ("Elementi?  "); brisi (lst);
      switch (izbor) {
      case 6: /* uz obrtanje redosleda brojeva: */
        lst = citaj1 (n); break;
      case 7: /* uz cuvanje redosleda brojeva: */
        lst = citaj2 (n); break;
 }
 break;
 case 8: /* Odredjivanje duzine liste: */
 printf ("Duzina=    %d\n", duz (lst)); break;
    case 9: /* Ispisivanje liste: */
      printf ("Lista=     "); pisi (lst); putchar ('\n'); break;
 case 0: /* Zavrsetak rada: */
      kraj = 1; break;
    default: /* Pogresan izbor: */
      printf ("*** Neozvoljeni izbor! ***\a\n"); break;
    }
  }
}
 
/* Definicije  funkcija za obradu lista (iterativno).    */
 
int duz (Elem *lst) {                   /* Broj elemenata liste.          */
  int n = 0; while (lst) { n++; lst = lst -> sled; } return n;
}
 
void pisi (Elem *lst) {                 /* Ispisivanje liste.             */
  while (lst) { printf ("%d ", lst->broj); lst = lst -> sled; }
}
 Elem *na_pocetak (Elem *lst, int b) {   /* Dodavanje na pocetak.          */
  Elem *novi = malloc (sizeof(Elem));
  novi->broj = b; novi->sled = lst;
  return novi;
}
 //T(n)=O(1), gde je n duzina liste
 
Elem *na_kraj (Elem *lst, int b) {      /* Dodavanje na kraj.             */
  Elem *novi = malloc (sizeof(Elem));
  novi->broj = b; novi->sled = NULL;
 if (!lst) return novi;
 else {
    Elem *tek = lst;
 while (tek->sled) tek = tek->sled;
 tek->sled = novi;
 return lst;
  }
}
 
Elem *citaj1 (int n) {   /* Citanje liste stavljajuci brojeve na pocetak. */
  Elem *prvi = NULL; int i;
  for (i=0; i<n; i++) {
    Elem *novi = malloc (sizeof(Elem));
 scanf ("%d", &novi->broj); novi->sled = prvi;
    prvi = novi;
  }
  return prvi;
}
 
Elem *citaj2 (int n) {   /* Citanje liste stavljajuci brojeve na kraj.    */
  Elem *prvi = NULL, *posl = NULL; int i;
 for (i=0; i<n; i++) {
    Elem *novi = malloc (sizeof(Elem));
 scanf ("%d", &novi->broj); novi->sled = NULL;
 if (!prvi) prvi = novi; else posl->sled = novi;
    posl = novi;
  }
  return prvi;
}
 

Elem *umetni (Elem *lst, int b) {       /* Umetanje u uredjenu listu.     */
  Elem *tek = lst, *pret = NULL, *novi;
  while (tek && tek->broj < b) { pret = tek; tek = tek->sled; }
  novi = malloc (sizeof(Elem));
  novi->broj = b; novi->sled = tek;
  if (!pret) lst = novi; else pret->sled = novi;
  return lst;
} //T(n)=O(n), gde je n duzina liste, jer u najgorem slučaju možda moramo da
//prođemo celu listu dok nađemo član sa informacionim poljem b
 
void brisi (Elem *lst) {                /* Brisanje svih elemenata liste. */
  while (lst) { Elem *stari = lst; lst = lst->sled; free (stari); }
}
 
 
 

Elem *izostavi (Elem *lst, int b){/*Izostavljanje svakog pojavljivanja clana b*/
  Elem *tek = lst, *pret = NULL;
  while (tek)
    if (tek->broj != b) { pret = tek; tek = tek->sled; }
 else {
      Elem *stari = tek;
      tek = tek->sled;
 if (!pret) lst = tek; else pret->sled = tek;
      free (stari);
    }
  return lst;
} //T(n)=O(n), gde je n duzina liste, jer moramo daprođemo celu listu dok nađemo 
//sve članove sa informacionim poljem b
 
 

4. /* Rad sa povezanom listom - REKURZIVNE verzije funkcija za rad sa povezanom listom; UPOREDITI SA PRETHODNIM  ZADATKOM               */ 

#include <stdio.h>
#include <stdlib.h>
 
typedef struct elem { int broj; struct elem *sled; } Elem; /*Element liste*/
 
int duz (Elem *lst);                    /* Broj elemenata liste.          */
void pisi (Elem *lst);                  /* Ispisivanje liste.             */
Elem *na_pocetak (Elem *lst, int b);    /* Dodavanje na pocetak.          */
Elem *na_kraj (Elem *lst, int b);       /* Dodavanje na kraj.             */
Elem *citaj1 (int n);    /* Citanje liste stavljajuci brojeve na pocetak. */
Elem *citaj2 (int n);    /* Citanje liste stavljajuci brojeve na kraj.    */
Elem *umetni (Elem *lst, int b);        /* Umetanje u uredjenu listu.     */
void brisi (Elem *lst);                 /* Brisanje svih elemenata liste. */
Elem *izostavi (Elem *lst, int b); /* Izostavljanje svakog pojavljivanja. */
 
void main () {
  Elem *lst = NULL; int kraj = 0, izbor, broj, n;
  while (!kraj) {
 printf ("\n1. Dodavanje broja na pocetak liste\n"
 "2. Dodavanje broja na kraj liste\n"
 "3. Umetanje broja u uredjenu listu\n"
              "4. Izostavljanje broja iz liste\n"
              "5. Brisanje svih elemenata liste\n"
              "6. Citanje uz obrtanje redosleda brojeva\n"
              "7. Citanje uz cuvanje redosleda brojeva\n"
              "8. Odredjivanje duzine liste\n"
              "9. Ispisivanje liste\n"
              "0. Zavrsetak rada\n\n"
              "Vas izbor? "
            );
    scanf ("%d", &izbor);
    switch (izbor) {
 case 1: case 2: case 3: case 4:
 printf ("Broj?      "); scanf ("%d", &broj);
 switch (izbor) {
 case 1: /* Dodavanje broja na pocetak liste: */
        lst = na_pocetak (lst, broj); break;
      case 2: /* Dodavanje broja na kraj liste: */
        lst = na_kraj (lst, broj);    break;
      case 3: /* Umetanje broja u uredjenu listu: */
        lst = umetni (lst, broj);     break;
      case 4: /* Izostavljanje broja iz liste: */
 lst = izostavi (lst, broj);   break;
      }
      break;
    case 5: /* Brisanje svih elemenata liste: */
 brisi (lst); lst = NULL; break;
 case 6: case 7: /* Citanje liste: */
 printf ("Duzina?    "); scanf ("%d", &n);
      printf ("Elementi?  "); brisi (lst);
      switch (izbor) {
      case 6: /* uz obrtanje redosleda brojeva: */
        lst = citaj1 (n); break;
      case 7: /* uz cuvanje redosleda brojeva: */
        lst = citaj2 (n); break;
 }
 break;
 case 8: /* Odredjivanje duzine liste: */
 printf ("Duzina=    %d\n", duz (lst)); break;
    case 9: /* Ispisivanje liste: */
      printf ("Lista=     "); pisi (lst); putchar ('\n'); break;
 case 0: /* Zavrsetak rada: */
      kraj = 1; break;
    default: /* Pogresan izbor: */
      printf ("*** Neozvoljeni izbor! ***\a\n"); break;
    }
  }
}
 
 
/* Definicije  funkcija za obradu lista (REKURZIVNO).    */ 
int duz (Elem *lst) {                   /* Broj elemenata liste.          */
  return lst ? duz (lst->sled) + 1 : 0;
}
 
void pisi (Elem *lst) {                 /* Ispisivanje liste.             */
  if (lst) { printf ("%d ", lst->broj); pisi (lst->sled); }
}
  
Elem *na_pocetak (Elem *lst, int b) {   /* Dodavanje na pocetak.          */
  Elem *novi = malloc (sizeof(Elem));
  novi->broj = b; novi->sled = lst;
  return novi;
}
 
Elem *na_kraj (Elem *lst, int b) {      /* Dodavanje na kraj.             */
  if (!lst) {
   lst = malloc (sizeof(Elem));
   lst->broj = b; lst->sled = NULL;
 } else
   lst->sled = na_kraj (lst->sled, b);
 return lst;
}
 
Elem *citaj1 (int n) {   /* Citanje liste uz obrtanje redosleda.          */
 if (n == 0) return NULL;
 else {
    Elem *novi = malloc (sizeof(Elem));
 novi->sled = citaj1 (n - 1); scanf ("%d", &novi->broj);
    return novi;
  }
}
 
Elem *citaj2 (int n) {   /* Citanje liste uz cuvanje redosleda.           */
 if (n == 0) return NULL;
 else {
    Elem *novi = malloc (sizeof(Elem));
 scanf ("%d", &novi->broj); novi->sled = citaj2 (n - 1);
 return novi;
  }
} 
Elem *umetni (Elem *lst, int b) {       /* Umetanje u uredjenu listu.     */
 if (!lst || lst->broj >= b) {
    Elem *novi = malloc (sizeof(Elem));
 novi->broj = b; novi->sled = lst;
    return novi;
  } else {
    lst->sled = umetni (lst->sled, b);
 return lst;
  }
}
 
void brisi (Elem *lst) {                /* Brisanje svih elemenata liste. */
 if (lst) { brisi (lst->sled); free (lst); }
}
 
Elem *izostavi (Elem *lst, int b){ /* Izostavljanje svakog pojavljivanja. */
  if (lst) {
    if (lst->broj !=  b) {
      lst->sled = izostavi (lst->sled, b);
    } else {
      Elem *stari = lst;
      lst = izostavi (lst->sled, b);
      free (stari);
    }
  }
  return lst;
}
 
 

2.3 DVOSTRUKO POVEZANA LISTA



Svaki element dvostruko povezane liste ima informaciono polje (npr. broj) i dva pokazivača: pret, sled. 
Ako pret=NULL, taj element nema prethodnika, tj. on je glava liste. 
Ako sled=NULL, taj element nema sledbenika, tj. on je rep liste.
 
Ponekad je pogodno da se kretanje kroz listu, od elementa do elementa vrši u oba smera (napred i nazad).
 U takvim slučajevima organizuju se liste sa dva pointera, jedan za kretanje unapred kao kod obične liste,
 i dodatni pointer za kretanje unazad, što je ilustrovano na sledećoj slici.
 

 
5.  
#include <stdio.h>
#include <stdlib.h>
 
typedef struct elem { int broj; struct elem *pret, *sled; } Elem;
typedef struct { Elem *prvi, *posl, *tek; } Lista;
typedef enum {NAPRED, NAZAD} Smer;
 
Lista stvori (void);                    /* Stavaranje prazne liste.       */
void na_prvi (Lista *lst);              /* Pomeranje na prvi element.     */
void na_posl (Lista *lst);              /* Pomeranje na poslednji element.*/
void na_sled (Lista *lst);              /* Pomeranje na sledeci element.  */
void na_pret (Lista *lst);              /* Pomeranje na prethodni element.*/
void nadji_sled (Lista *lst, int b);    /* Pomer. na sled. pojavljivanje. */
void nadji_pret (Lista *lst, int b);    /* Pomer. na pret. pojavljivanje. */
int ima_tekuci (Lista lst);             /* Da li postoji tekuci element?  */
int dohvati (Lista lst);                /* Dohvatanje tekuceg elementa.   */
void promeni (Lista lst, int b);        /* Menjanje tekuceg elementa.     */
void dodaj_poc    (Lista *lst, int b);  /* Dodavanje ispred prvog elemanta*/
void dodaj_kraj   (Lista *lst, int b);  /* Dodavanje iza poslednjeg elem. */
void dodaj_ispred (Lista *lst, int b);  /* Dodavanje ispred tekuceg elem. */
void dodaj_iza    (Lista *lst, int b);  /* Dodavanje iza tekuceg elementa.*/
void izbaci (Lista *lst, Smer smer);    /* Izbacivanje tekuceg elementa.  */
void brisi (Lista *lst);                /* Brisanje svih elemenata.       */
void pisi (Lista lst, Smer smer);       /* Ispisivanje liste.             */
void citaj (Lista *lst, int n, Smer smer); /* Citanje liste.              */
 
void main () {
  Lista lst = stvori (); int n, k;
  while (1) {
    printf ("n?        "); scanf ("%d", &n);
 if (n <0) break;
 printf ("Lista?    "); citaj (&lst, n, NAPRED);
 if (n == 0) putchar ('\n');
 printf ("Izostavljate?    "); scanf ("%d", &k);
    printf ("Napred=   "); pisi (lst, NAPRED); putchar ('\n');
    printf ("Nazad=    "); pisi (lst, NAZAD);  putchar ('\n');
 
    /* Izbacivanje svakog pojavljivanja datog broja: */
    na_prvi (&lst); nadji_sled (&lst, k);
    while (ima_tekuci(lst)) { izbaci (&lst, NAPRED); nadji_sled (&lst ,k); }
 printf ("Skraceno= "); pisi (lst, NAPRED); printf ("\n\n");
  }
}
 
Lista stvori (void)                      /* Stvaranje prazne liste.       */
  { Lista lst; lst.prvi = lst.posl = lst.tek = NULL; return lst; }
 
void na_prvi (Lista *lst)               /* Pomeranje na prvi element.     */
  { lst->tek = lst->prvi; }
 
void na_posl (Lista *lst)               /* Pomeranje na poslednji element.*/
  { lst->tek = lst->posl; }
 
void na_sled (Lista *lst)               /* Pomeranje na sledeci element.  */
  { if (lst->tek) lst->tek = lst->tek->sled; }
 
void na_pret (Lista *lst)               /* Pomeranje na prethodni element.*/
 { if (lst->tek) lst->tek = lst->tek->pret; }
 
void nadji_sled (Lista *lst, int b)     /* Pomer. na sled. pojavljivanje. */
 { while (lst->tek && lst->tek->broj != b) lst->tek = lst->tek->sled; }
 
void nadji_pret (Lista *lst, int b)     /* Pomer. na pret. pojavljivanje. */
 { while (lst->tek && lst->tek->broj != b) lst->tek = lst->tek->pret; }
 
int ima_tekuci (Lista lst)              /* Da li postoji tekuci element?  */
  { return lst.tek != NULL; }
 
int dohvati (Lista lst) {               /* Dohvatanje tekuceg elementa.   */
  if (! lst.tek) exit (1);
  return lst.tek->broj;
}
 
void promeni (Lista lst, int b) {       /* Menjanje tekuceg elementa.     */
  if (! lst.tek) exit (1);
  lst.tek->broj = b;
}
 
void dodaj_poc    (Lista *lst, int b) { /* Dodaj b ispred prvog elemanta*/
 Elem *novi = malloc (sizeof(Elem));
  novi->broj = b; novi->sled = lst->prvi; novi->pret = NULL;
  if (! lst->prvi) lst->posl = novi; else lst->prvi->pret = novi;
  lst->prvi = lst->tek = novi;
} //T(n)=O(1), gde je n duzina liste
 
void dodaj_kraj   (Lista *lst, int b) { /* Dodaj b iza poslednjeg elem. */
  Elem *novi = malloc (sizeof(Elem));
  novi->broj = b; novi->pret = lst->posl; novi->sled = NULL;
  if (! lst->posl) lst->prvi = novi; else lst->posl->sled = novi;
  lst->posl = lst->tek = novi;
} //T(n)=O(1), gde je n duzina liste
 
void dodaj_ispred (Lista *lst, int b) { /* Dodavanje ispred tekuceg elem. */
 Elem *novi = malloc (sizeof(Elem));
 if (! lst->tek) exit (1);
 novi->broj = b; novi->pret = lst->tek->pret; novi->sled = lst->tek;
  if (! lst->tek->pret) lst->prvi = novi; else lst->tek->pret->sled = novi;
  lst->tek->pret = lst->tek = novi;
}
 
void dodaj_iza    (Lista *lst, int b) { /* Dodavanje iza tekuceg elementa.*/
 Elem *novi = malloc (sizeof(Elem));
 if (! lst->tek) exit (1);
 novi->broj = b; novi->sled = lst->tek->sled; novi->pret = lst->tek;
  if (! lst->tek->sled) lst->posl = novi; else lst->tek->sled->pret = novi;
  lst->tek->sled = lst->tek = novi;
}
 
void izbaci (Lista *lst, Smer smer) {   /* Izbacivanje tekuceg elementa.  */
  Elem *stari = lst->tek;
  if (! lst->tek) exit (1);
  if (! lst->tek->pret) lst->prvi = lst->tek->sled;
    else                lst->tek->pret->sled = lst->tek->sled;
  if (! lst->tek->sled) lst->posl = lst->tek->pret;
    else                lst->tek->sled->pret = lst->tek->pret;
  lst->tek = (smer == NAPRED) ? lst->tek->sled : lst->tek->pret;
  free (stari);
}
 
void brisi (Lista *lst) {               /* Brisanje svih elemenata.       */
  while (lst->prvi) {
    Elem *stari = lst->prvi; lst->prvi = lst->prvi->sled; free (stari);
  }
  lst->posl = lst->tek = NULL;
}
 
void pisi (Lista lst, Smer smer){       /* Ispisivanje liste.             */
  if (smer == NAPRED)
    for (na_prvi (&lst); ima_tekuci (lst); na_sled (&lst))
      printf ("%d ", dohvati (lst));
  else
    for (na_posl (&lst); ima_tekuci (lst); na_pret (&lst))
      printf ("%d ", dohvati (lst));
}
void citaj (Lista *lst, int n, Smer smer) { /* Citanje liste.             */
  int i, b;
  brisi (lst);
  for (i = 0; i<n; i++) {
    scanf ("%d", &b);
 (smer == NAPRED) ? dodaj_kraj (lst, b) : dodaj_poc (lst, b);
 }
}

6. Opisati implementaciju steka koristeći jednostruko povezanu listu L.

Operacije PUSH i POP i dalje treba da budu složenosti O(1). /* rad sa  stekom unapred nepoznatog kapaciteta      */

RESENJE:

IDEJA: Operacija PUSH se implementira dodavanjem novog elementa na pocetak liste.

Operacija POP se implementira brisanjem prvog elementa liste.

 
 
#include <stdio.h>
#include <stdlib.h>
 
typedef struct elem { int broj; struct elem *sled; } Elem;
typedef Elem *Stek;
 
Stek stvori (void);                     /* Stvaranje praznog steka.       */
void stavi (Stek *stk, int b);         /* PUSH-Stavljanje broja na stek.  */
int uzmi (Stek *stk);                  /* POP-Uzimanje broja sa steka.    */
int prazan (Stek stk);                  /* Da li je stek prazan?          */
void pisi (Stek stk);                   /* Ispisivanje sadrzaja steka.    */
void prazni (Stek *stk);                /* Praznjenje steka.              */
void unisti (Stek *stk);                /* Unistavanje steka.             */
 
int main () {
  Stek stk = stvori (); int b, izbor, kraj = 0;
  while (! kraj) {
    printf ("\n1. Smestaj podataka na stek\n"
              "2. Skidanje podatka sa steka\n"
              "3. Ispisivanje sadrzaja steka\n"
              "4. Praznjenje steka\n"
              "0. Zavrsetak rada\n\n"
              "Vas izbor? "
            );
    scanf ("%d", &izbor);
    switch (izbor) {
    case 1: /* podatak na stek: */
      printf ("Broj?      "); scanf ("%d", &b); stavi (&stk, b);break;
    case 2: /* podatak sa steka: */
      if (! prazan (stk))  printf ("Broj=      %d\n", uzmi (&stk));
 else printf ("*** Stek je prazan! ***\a\n");      break;
    case 3: /* Ispisivanje sadrzaja steka: */
      printf ("Stek=      "); pisi (stk); putchar ('\n');      break;
    case 4: /* Praznjenje steka: */      prazni (&stk); break;
 case 0: /* Zavrsetak rada: */      kraj = 1; break;
    default: /* Pogresan izbor: */ printf ("*** Neozvoljeni izbor! ***\a\n"); 
 break;
    }
  }
  return 0;
}
 
Stek stvori () { return NULL; }         /* Stvaranje praznog steka.       */
 
void stavi (Stek *stk, int b) {         /* Stavljanje broja na stek.      */
  Elem *novi = malloc (sizeof(Elem));
  novi->broj = b; novi->sled = *stk; *stk = novi;
} //T(n)=O(1)
 
int uzmi (Stek *stk) {                  /* Uzimanje broja sa steka.       */
  Elem *stari; int b;
 if (*stk == NULL) exit (2); //potkoracenje, underflow
 b = (*stk)->broj; stari = *stk; *stk = (*stk)->sled; free (stari);
  return b;
} //T(n)=O(1)
 
int prazan (Stek stk) { return stk == NULL; } /* Da li je stek prazan?    */
 
 
void pisi  (Stek stk) { Elem *tek;      /* Ispisivanje sadrzaja steka.    */
  for (tek=stk; tek; tek=tek->sled) printf ("%d ", tek->broj);
}
 
void prazni (Stek *stk) {               /* Praznjenje steka.              */
 while (*stk) { Elem *stari=*stk; (*stk)=(*stk)->sled; free(stari); }
}
 
void unisti (Stek *stk) { prazni (stk); } /* Unistavanje steka.           */

7. Konstruisati nerekurzivnu proceduru složenosti O(n) koja obrće jednostruko povezanu listu od n elemenata.

Procedura ne treba da koristi više od konstantne dodatne memorije pored one potrebne za smeštanje liste.

Kako bi se implementirala procedura za dvostruko povezane liste?

8. Neka su elementima pridruženi brojevi iz opsega od 1 do n, pri čemu n nije veliko, pa je na raspolaganju memorija veličine O(n).

Svaki element može se pojaviti najviše jednom. Opisati realizaciju apstraktnog tipa podataka koji podržava sledeće operacije:

(a) umetni(x)

(b) ukloni(y) - uklanja se ma koji (proizvoljan) element iz strukture podataka i dodeljuje promenljivoj y.

Operacije treba da budu složenosti O(1).

2.4 Red – QUEUE

Za razliku od stekova, kod redova se dodavanje elemenata i uklanjanje elemenata ne vrši na istom kraju reda.

Redovima se implementira FIFO (first-in first-out) princip.

Dve osnovne operacije sa redovima:

–dequeue: brisanje elementa sa početka reda

–enqueue: dodavanje člana na kraj reda

Primene redova

o Printer redovi za čekanje na štampu

o Redovi za raspoređivanje rada procesora (FCFS-first come first served)

o Telekomunikacioni redovi

9. Realizovati red ograničenog kapaciteta korišćenjem niza.

IDEJA:

#include <stdio.h>

#include <stdlib.h>

/* Deklaracije funkcija za rad sa redovim ogranicenog kapaciteta. */

typedef struct { int *niz, kap, duz, prvi, posl; } Red;

/* niz=cuva elemente reda, kap=kapacitet reda, duz = dostignuta duzina reda, prvi=pocetak reda, posl=kraj reda*/

Red stvori (int k); /* Stvaranje praznog reda. */

void stavi (Red *rd, int b); /* Stavljanje broja u red. */

int uzmi (Red *rd); /* Uzimanje broja iz reda. */

int prazan (Red rd); /* Da li je red prazan? */

int pun (Red rd); /* Da li je red pun? */

void pisi (Red rd); /* Ispisivanje sadrzaja reda. */

void prazni (Red *rd); /* Praznjenje reda. */

void unisti (Red *rd); /* Unistavanje reda. */

int main () {

Red rd = stvori (10); int k, b, izbor, kraj = 0;

while (! kraj) {

printf ("\n1. Stavaranje reda\n"

"2. Stavljanje podatka u red\n"

"3. Uzimanje podatka iz reda\n"

"4. Ispisivanje sadrzaja reda\n"

"5. Praznjenje reda\n"

"0. Zavrsetak rada\n\n"

"Vas izbor? "

);

scanf ("%d", &izbor);

switch (izbor) {

case 1: /* Stvaranje novog reda: */

printf ("Kapacitet? "); scanf ("%d", &k);

if (k > 0) { unisti (&rd); rd = stvori (k); } else printf ("*** Nedozvoljeni kapacitet! ***\a\n");

break;

case 2: /* Stavljanje podatka u red: */

if (! pun (rd)) { printf ("Broj? "); scanf ("%d", &b); stavi (&rd, b); }

else printf ("*** Red je pun! ***\a\n");

break;

case 3: /* Uzimanje broja iz reda: */

if (! prazan (rd)) printf ("Broj= %d\n", uzmi (&rd));

else printf ("*** Red je prazan! ***\a\n");

break;

case 4: /* Ispisivanje sadrzaja reda: */ printf ("Red= "); pisi (rd); putchar ('\n'); break;

case 5: /* Praznjenje reda: */ prazni (&rd); break;

case 0: /* Zavrsetak rada: */

kraj = 1; break;

default: /* Pogresan izbor: */

printf ("*** Nedozvoljeni izbor! ***\a\n"); break;

}

}

return 0;

}

Red stvori (int k) { Red rd; /* Stvaranje praznog reda. */

rd.niz = malloc (k * sizeof(int)); rd.kap = k;

rd.duz = rd.posl = rd.prvi = 0;

return rd;

}

void stavi (Red *rd, int b) { /* Stavljanje broja u red. */

if (rd->duz == rd->kap) exit (1);

rd->niz[rd->posl++] = b; rd->duz++;

if (rd->posl == rd->kap) rd->posl = 0;

} //T(n)= O(1), n je broj clanova reda

int uzmi (Red *rd) { int b; /* Uzimanje broja iz reda. */

if (rd->duz == 0) exit (2);

b = rd->niz[rd->prvi++]; rd->duz--;

if (rd->prvi == rd->kap) rd->prvi = 0;

return b;

} //T(n)=O(1), n je broj clanova reda

int prazan (Red rd) { return rd.duz == 0; } /* Da li je red prazan? */

int pun (Red rd) { return rd.duz == rd.kap; } /* Da li je red pun? */

void pisi (Red rd) { int i; /* Ispisivanje sadrzaja reda. */

for (i=0; i<rd.duz; printf ("%d ", rd.niz[(rd.prvi + i++) % rd.kap]));

}

void prazni (Red *rd) { rd->duz = rd->posl = rd->prvi = 0; } /* Praznjenje*/

void unisti (Red *rd) { free (rd->niz); } /* Unistavanje reda. */

10. Opisati implementaciju reda koristeći jednostruko povezanu listu (za redove neogranicenog kapacieta).

IDEJA:

#include <stdio.h>

#include <stdlib.h>

typedef struct elem { int broj; struct elem *sled; } Elem;

typedef struct { Elem *prvi, *posl; } Red;

Red stvori (void); /* Stvaranje praznog reda. */

void stavi (Red *rd, int b); /* Stavljanje broja u red. */

int uzmi (Red *rd); /* Uzimanje broja iz reda. */

int prazan (Red rd); /* Da li je red prazan? */

void pisi (Red rd); /* Ispisivanje sadrzaja reda. */

void prazni (Red *rd); /* Praznjenje reda. */

void unisti (Red *rd); /* Unistavanje reda. */

int main () {

Red rd = stvori (); int b, izbor, kraj = 0;

while (! kraj) {

printf ("\n1. Stavljanje podatka u red\n"

"2. Uzimanje podatka iz reda\n"

"3. Ispisivanje sadrzaja reda\n"

"4. Praznjenje reda\n"

"0. Zavrsetak rada\n\n"

"Vas izbor? "

);

scanf ("%d", &izbor);

switch (izbor) {

case 1: /* Stavljanje podatka u red: */ printf ("Broj? "); scanf ("%d", &b); stavi (&rd, b);

break;

case 2: /* Uzimanje broja iz reda: */

if (! prazan (rd)) printf ("Broj= %d\n", uzmi (&rd));

else printf ("*** Red je prazan! ***\a\n");

break;

case 3: /* Ispisivanje sadrzaja reda: */ printf ("Red= "); pisi (rd); putchar ('\n'); break;

case 4: /* Praznjenje reda: */ prazni (&rd); break;

case 0: /* Zavrsetak rada: */ kraj = 1; break;

default: /* Pogresan izbor: */

printf ("*** Neozvoljeni izbor! ***\a\n"); break;

}

}

return 0;

}

Red stvori() {Red rd; rd.prvi=rd.posl=NULL; return rd;} /* Stvaranje reda.*/

void stavi (Red *rd, int b) { /* Stavljanje broja u red. */

Elem *novi = malloc (sizeof(Elem));

novi->broj = b; novi->sled = NULL;

if (! rd->posl) rd->prvi = novi; else rd->posl->sled = novi;

rd->posl = novi;

} //T(n)= O(1), n je broj clanova reda

int uzmi (Red *rd) { Elem *stari; int b; /* Uzimanje broja iz reda. */

if (! rd->prvi) exit (2);

b = rd->prvi->broj;

stari = rd->prvi; rd->prvi = rd->prvi->sled; free (stari);

if (! rd->prvi) rd->posl = NULL;

return b;

} //T(n)= O(1), n je broj clanova reda

int prazan (Red rd) { return rd.prvi == NULL; } /* Da li je red prazan? */

void pisi (Red rd) { Elem *tek; /* Ispisivanje sadrzaja reda. */

for (tek=rd.prvi; tek; tek=tek->sled) printf ("%d ", tek->broj);

}

void prazni (Red *rd) { /* Praznjenje reda. */

while (rd->prvi) {

Elem *stari = rd->prvi; rd->prvi = rd->prvi->sled;

free(stari);

}

}

void unisti (Red *rd) { prazni (rd); } /* Unistavanje reda. */

11. Objasniti kako je moguće implementirati red koristeći dva steka. Analizirati vreme izvršavanja operacija za red.

2.5 KRUŽNA LISTA

Kružna lista nastaje kada umesto da poslednji član liste ima NULL pointer (NULL pointer je pointer koji ne pokazuje ni na jedan element)

on sadrži adresu prvog člana.

Time se omogućava cirkularno kretanje kroz listu, kao što se možete uveriti posmatranjem sledeće slike.