1_DinStrPod (1)

1. Programski jezik C

Dinamičke strukture podataka

2. Dinamičke strukture podataka

• Dinamičke strukture podataka menjaju
svoju veličinu tokom vremena.
• Koriste memoriju koja se dinamički alocira
i oslobađa
– za to se koriste malloc i free funkcije
• Jednostruko povezane liste
– uređene jednostruko povezane liste
• Binarna stabla
• Stek

3. Alokacija memorije

• Koristi se kada se u toku pisanja programa ne
zna koliko memorije je potrebno.
• Alocirana memorija se mora dealocirati!
• Alokacija se vrši sistemskom funkcijom
malloc(br_bajtova).
• Dealokacija funkcijom free(pokazivac).
• Memorija se alocira sa heap-a.
– heap je blok memorije dodeljen svakom programu.

4. Primer alokacije memorije

int *p;
const int KOLIKO = 10000;
p = (int *)malloc(KOLIKO);
printf("%Broj alociranih bajtova je: %d\n",
KOLIKO);
printf("%Velicina int-a je: %d\n",
sizeof(int));
printf("%Broj alociranih int-ova je: %d\n",
KOLIKO / sizeof(int));
free(p);

5. Alokacija memorije

• Memorija se uvek alocira zadatim brojem bajtova.
• Funkcija malloc() vraća adresu bloka u memoriji
– ako tu adresu prihvatimo u pokazivač na int, onda se
taj blok memorije tretira kao niz int-ova
int
p1
p1+0
1000
1000
p2
char
1000
p1+1
p1+2
?
?
4
1
?
0
2
?
?
p2+0
p2+1
p2+2
p2+3
p2+4

6. Jednostruko povezane liste (jednostruko spregnute liste)

• Skup čvorova povezanih u jednom smeru
• Svaki čvor se sastoji iz dva elementa:
– informacija koju čvor nosi (informacioni deo) i
– pokazivač na sledeći element.
• Primer:
typedef char TIP;
typedef struct cvor_st
{
TIP inf;
struct cvor_st *sledeći;
} LCVOR;
...
LCVOR *pocetak_liste;

7. Primer

pocetak_liste
INF
INF
...
INF
NULL

8. Stanja jednostruko povezane liste

• Prazna lista
– pocetak_liste == NULL
• Lista ima jedan čvor (element)
– pocetak_liste prvi (i jedini) element NULL
• Lista ima više čvorova (elemenata)
– pocetak_liste prvi el. ... poslednji NULL

9. Prazna lista

pocetak_liste
NULL

10. Lista sa jednim čvorom

pocetak_liste
INF
NULL

11. Lista sa više čvorova

pocetak_liste
INF
INF
...
INF
NULL

12. Operacije sa listama

1. Dodavanje na početak
2. Dodavanje na kraj
3. Pronalaženje čvora
4. Brisanje čvora
5. Brisanje liste

13. 1. Dodavanje na početak

• Kreira se novi čvor
– novi = (LCVOR *)malloc(sizeof(LCVOR));
• novi->sledeci = pocetak_liste;
• pocetak_liste = novi;
pocetak_liste
INF
INF
...
INF
NULL
novi
INF

14. novi->sledeci = pocetak_liste;

novi->sledeci = pocetak_liste;
pocetak_liste
INF
INF
...
INF
NULL
novi
INF

15. pocetak_liste = novi;

dodajpoc.c
pocetak_liste
x
INF
INF
...
INF
NULL
novi
INF

16. 2. Dodavanje na kraj liste

• Kreira se novi čvor
– novi = (LCVOR *)malloc(sizeof(LCVOR));
• krene se od početka liste i sve dok je
tekuci != NULL
– prethodni = tekuci;
– tekuci = tekuci ->sledeci;
• kada je tekuci == NULL, tada prethodni
ukazuje na poslednji cvor

17. Dodavanje na kraj

• Kreira se novi čvor
– novi = (LCVOR *)malloc(sizeof(LCVOR));
pocetak_liste
INF
INF
...
INF
NULL
novi
INF

18. while (tekuci != NULL) { prethodni = tekuci; tekuci = tekuci->sledeci; }

while (tekuci != NULL)
{
prethodni = tekuci;
tekuci = tekuci->sledeci;
}
prethodni
tekuci
pocetak_liste
INF
INF
...
INF
NULL
novi
INF

19. while (tekuci != NULL) { prethodni = tekuci; tekuci = tekuci->sledeci; }

while (tekuci != NULL)
{
prethodni = tekuci;
tekuci = tekuci->sledeci;
}
tekuci
pocetak_liste
prethodni
INF
INF
...
INF
NULL
novi
INF

20. novi->sledeci = NULL; prethodni->sledeci = novi;

novi->sledeci = NULL;
prethodni->sledeci = novi;
dodajkraj.c
pocetak_liste
prethodni
INF
INF
...
INF
novi
INF
NULL

21. 3. Pronalaženje čvora

• krene se od početka liste i sve dok je
tekuci != NULL
– ako je tekuci->inf == trazena_inf, onda vrati
tekuci, inače
– tekuci = tekuci ->sledeci;
• ako se do kraja ne nađe traženi čvor,
tekuci će biti jednak NULL, pa funkcija to
vraća
proncvor.c

22. 4. Brisanje čvora

• Ako se briše prvi čvor, onda se
pocetak_liste preveže na drugog
• Inače se traži čvor, ali se pamti i pokazivač
na prethodnog
– preveže se prethodni na sledećeg od
nađenog

23. Brisanje prvog čvora

pocetak_liste
x
INF
x
INF
...
INF

24. Brisanje čvora

prethodni
nađeni
INF
INF
INF

25. Brisanje čvora

brisi.c
prethodni
nađeni
INF
x
INF
INF

26. 5. Brisanje liste

• Krene se od početka liste
– tekuci = pocetak_liste;
• dokle god je tekuci razlicit od NULL,
– pamti se tekuci
• tmp = tekuci
– pređe se na sledeći
• tekuci = tekuci->sledeci;
– obriše se tmp čvor
• free (tmp);

27. Bisanje liste

tekuci = pocetak_liste;
while (tekuci != NULL)
{
tmp = tekuci;
tekuci = tekuci->sledeci;
printf("brisem: %c\n", tmp->inf);
free(tmp);
}
pocetak_liste = NULL;

28. Uređena lista

• Ideja – dodavati nove čvorove tako da lista
ostane uređena (sortirana)
– to se postiže tako što se sadržaj novog čvora
poredi sa tekućim, i ako je manji ili jednak,
dodaje se ispred tekućeg
– inače se pomerimo na sledeći čvor i
ponovimo poređenje
dodajsrt.c - rekurzivno
dodajsr2.c - iterativno