Sveuˇ
ciliˇ
ste u Zagrebu
Prirodoslovno Matematiˇ
cki Fakultet
- Matematiˇ
cki odjel
Robert Manger, Miljenko Maruˇ
si´
c
STRUKTURE PODATAKA
I ALGORITMI
skripta
Tre´
ce izdanje
(novo poglavlje o algoritmima za sortiranje)
Zagreb, oˇ
zujak 2007.
Sadrˇ
zaj
1
UVOD
3
1.1
Osnovni pojmovi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2
Elementi od kojih se grade strukture podataka . . . . . . . . . . . . . . . . . . . . . . .
5
1.3
Zapisivanje i analiziranje algoritma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2
LISTE
7
2.1
(Op´
cenita) lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.1.1
Implementacija liste pomo´
cu polja . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.1.2
Implementacija liste pomo´
cu pointera . . . . . . . . . . . . . . . . . . . . . . . .
10
2.2
Stog (stack) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.2.1
Implementacija stoga pomo´
cu polja
. . . . . . . . . . . . . . . . . . . . . . . . .
13
2.2.2
Implementacija stoga pomo´
cu pointera . . . . . . . . . . . . . . . . . . . . . . . .
14
2.3
Red (queue) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.3.1
Implementacija reda pomo´
cu cirkularnog polja . . . . . . . . . . . . . . . . . . .
16
2.3.2
Implementacija reda pomo´
cu pointera . . . . . . . . . . . . . . . . . . . . . . . .
17
3
STABLA
19
3.1
(Uredeno) stablo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
3.1.1
Obilazak stabla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
3.1.2
Implementacija stabla na osnovu veze “ˇ
cvor
→
roditelj” . . . . . . . . . . . . . .
23
3.1.3
Implementacija stabla na osnovu veze “ˇ
cvor
→
(prvo dijete, idu´
ci brat)” . . . . .
24
3.2
Binarno stablo
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3.2.1
Implementacija binarnog stabla pomo´
cu pointera . . . . . . . . . . . . . . . . . .
28
3.2.2
Implementacija potpunog binarnog stabla pomo´
cu polja . . . . . . . . . . . . . .
29
4
SKUPOVI
31
4.1
(Op´
ceniti) skup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
4.1.1
Implementacija skupa pomo´
cu bit-vektora . . . . . . . . . . . . . . . . . . . . . .
32
4.1.2
Implementacija skupa pomo´
cu sortirane vezane liste . . . . . . . . . . . . . . . .
32
4.2
Rjeˇ
cnik
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.2.1
Implementacija rjeˇ
cnika pomo´
cu bit-vektora . . . . . . . . . . . . . . . . . . . . .
33
4.2.2
Implementacija rjeˇ
cnika pomo´
cu liste
. . . . . . . . . . . . . . . . . . . . . . . .
33
4.2.3
Implementacija rjeˇ
cnika pomo´
cu rasute (hash) tablice . . . . . . . . . . . . . . .
35
4.2.4
Implementacija rjeˇ
cnika pomo´
cu binarnog stabla traˇ
zenja . . . . . . . . . . . . .
38
4.3
Prioritetni red . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
4.3.1
Implementacija prioritetnog reda pomo´
cu sortirane vezane liste . . . . . . . . . .
43
4.3.2
Implementacija prioritetnog reda pomo´
cu binarnog stabla traˇ
zenja . . . . . . . .
43
4.3.3
Implementacija prioritetnog reda pomo´
cu hrpe . . . . . . . . . . . . . . . . . . .
43
4.4
Preslikavanje i relacija . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
4.4.1
Implementacija preslikavanja pomo´
cu hash tablice ili binarnog stabla . . . . . . .
48
4.4.2
Implementacija relacije pomo´
cu bit-matrice . . . . . . . . . . . . . . . . . . . . .
50
4.4.3
Implementacija relacije pomo´
cu multi-liste . . . . . . . . . . . . . . . . . . . . . .
50
1
1
UVOD
1.1
Osnovni pojmovi
U raˇ
cunarstvu se susre´
cemo s dva osnovna pojma:
strukture podataka
. . .
“statiˇ
cki” aspekt nekog programa. Ono sa ˇ
cime se radi.
algoritmi
. . .
“dinamiˇ
cki” aspekt programa. Ono ˇ
sto se radi.
Strukture podataka i algoritmi su u nerazluˇ
civoj vezi: nemogu´
ce je govoriti o jednom a da se ne
spomene drugo. U ovom kolegiju prouˇ
cavat ´
cemo baˇ
s tu vezu: promatrat ´
cemo kako odabrana struktura
podataka utjeˇ
ce na algoritme za rad s njom, te kako odabrani algoritam sugerira pogodnu strukturu
za prikaz svojih podataka. Na taj naˇ
cin upoznat ´
cemo se s nizom vaˇ
znih ideja i pojmova, koji ˇ
cine
osnove raˇ
cunarstva.
Uz “strukture podataka” i “algoritme”, ovaj kolegij koristi joˇ
s nekoliko naizgled sliˇ
cnih pojmova.
Objasnit ´
cemo njihovo znaˇ
cenje i medusobni odnos.
tip podataka
. . .
skup vrijednosti koje neki podatak moˇ
ze poprimiti (npr. podatak tipa
int
moˇ
ze
imati samo vrijednosti iz skupa cijelih brojeva prikazivih u stroju).
apstraktni tip podataka (a.t.p.)
. . .
zadaje se navodenjem jednog ili viˇ
se tipova podataka, te jedne
ili viˇ
se operacija (funkcija). Operandi i rezultati navedenih operacija su podaci navedenih tipova.
Medu tipovima postoji jedan istaknuti po kojem cijeli apstraktni tip podataka dobiva ime.
struktura podataka
. . .
skupina varijabli u nekom programu i veza medu tim varijablama.
algoritam
. . .
konaˇ
cni niz instrukcija, od kojih svaka ima jasno znaˇ
cenje i moˇ
ze biti izvrˇ
sena u
konaˇ
cnom vremenu. Iste instrukcije mogu se izvrˇ
siti viˇ
se puta, pod pretpostavkom da same
instrukcije ukazuju na ponavljanje. Ipak, zahtijevamo da, za bilo koje vrijednosti ulaznih po-
dataka, algoritam zavrˇ
sava nakon konaˇ
cnog broja ponavljanja.
implementacija apstraktnog tipa podataka
. . .
konkretna realizacija dotiˇ
cnog apstraktnog tipa
podataka u nekom programu. Sastoji se od definicije za strukturu podataka (kojom se prikazuju
podaci iz apstraktnog tipa podataka) te od potprograma (kojima se operacije iz apstraktnog
tipa podataka ostvaruju pomo´
cu odabranih algoritama). Za isti apstraktni tip podataka obiˇ
cno
se moˇ
ze smisliti viˇ
se razliˇ
citih implementacija - one se razlikuju po tome ˇ
sto koriste razliˇ
cite
strukture za prikaz podataka te razliˇ
cite algoritme za izvrˇ
savanje operacija.
Svako od potpoglavlja 2.1–4.4 obraduje jedan apstraktni tip podataka. Promatraju se razne im-
plementacije za taj apstraktni tip podataka te njihove prednosti i mane. Na taj naˇ
cin upoznat ´
cemo
mnogo apstraktnih tipova podataka, te joˇ
s viˇ
se struktura podataka i algoritama. Daljnja potpoglavlja
5.1–5.4 obraduju algoritme za sortiranje. U oblikovanju algoritama za sortiranje primjenjuju se po-
jedini apstraktni tipovi odnosno strukture podataka iz prethodnih poglavlja. Preostala potpoglavlja
6.1–6.5 posve´
cena su op´
cenitim metodama (strategijama) koje mogu sluˇ
ziti za oblikovanje sloˇ
zenijih
algoritama. Znanje iz ovog kolegija trebalo bi nam omogu´
citi da bolje programiramo. Naime, razvoj
programa (metodom postepenog profinjavanja) moˇ
ze se promatrati u skladu sa sljede´
cim dijagramom.
3
4
1. UVOD
problem
.....
....
....
...
...
...
...
.
matematiˇ
cki
model
neformalno
opisani globalni
algoritam rjeˇ
savanja
problema
....
.....
....
...
...
...
...
.
apstraktni
tipovi
podataka
globalni algoritam
zapisan u pseudo
jeziku (poziva
operacije iz a.t.p.)
.....
....
....
...
...
..
...
..
strukture
podataka
globalni algoritam
zapisan u progr.
jeziku (operacije iz
a.t.p. pretvorene
u potprograme)
.....
....
....
...
...
...
...
.
rjeˇ
senje
problema
Slika 1.1
Postupak rjeˇ
savanja problema.
Iz ovog dijagrama vidi se uloga apstraktnih tipova podataka, struktura podataka i algoritama u pos-
tupku rjeˇ
savanja problema. Takoder se vidi da se programiranje u podjednakoj mjeri sastoji od razvi-
janja struktura podataka kao i od razvijanja algoritama.
Slijedi primjer za apstraktni tip podataka. Definiramo apstraktni tip podataka koji odgovara ma-
tematiˇ
ckom pojmu kompleksnih brojeva:
Apstraktni tip podataka COMPLEX
scalar
. . .
bilo koji tip za koji su definirane operacije zbrajanja i mnoˇ
zenja.
COMPLEX
. . .
podaci ovog tipa su uredeni parovi podataka tipa
scalar
.
ADD(z1,z2,&z3)
. . .
za zadane
z1,z2
tipa
COMPLEX
raˇ
cuna se njihov zbroj
z3
, takoder tipa
COMPLEX
.
Dakle za
z1
oblika
(x1,y1)
,
z2
oblika
(x2,y2)
, dobiva se
z3
oblika
(x3,y3)
, tako da bude
x3=x1+x2
,
y3=y1+y2
.
MULT(z1,z2,&z3)
. . .
za zadane
z1,z2
tipa
COMPLEX
raˇ
cuna se njihov umnoˇ
zak
z3
, takoder tipa
COMPLEX
. Dakle za
z1
oblika
(x1,y1)
,
z2
oblika
(x2,y2)
, dobiva se
z3
oblika
(x3,y3)
, takav da
je
x3=x1*x2-y1*y2
,
y3=x1*y2+y1*x2
.
Struktura podataka pogodna za prikaz kompleksnog broja bila bi tipa:
typedef struct
{
scalar re;
scalar im;
}
COMPLEX;
im
re
Implementacija apstraktnog tipa podataka COMPLEX se sastoji od prethodne definicije tipa,te od
funkcija oblika:
void ADD (COMPLEX z1, COMPLEX z2, COMPLEX *z3)
{
...
}
void MULT (COMPLEX z1, COMPLEX z2, COMPLEX *z3)
{
...
}
(algoritmi upotrijebljeni u potprogramima su trivijalni).
Za apstraktni tip podataka COMPLEX je vaˇ
zno da su prisutne operacije
ADD( )
i
MULT( )
. Bez
tih operacija radilo bi se o tipu, i tada kompleksne brojeve ne bismo mogli razlikovati od uredenih
parova skalara. Dodatna dimenzija “apstraktnosti” sastoji se u tome ˇ
sto nismo do kraja odredili ˇ
sto
je tip
scalar
. To je naime nebitno za prouˇ
cavanje struktura podataka i algoritama (vaˇ
zan je odnos
medu varijablama a ne njihov sadrˇ
zaj).
Na vjeˇ
zbama ´
ce biti izloˇ
zen cjelovit primjer za rjeˇ
savanje problema metodom postepenog profinja-
vanja.
6
1. UVOD
c
s
.................
....
....
.
.....
.....
................
....
....
................
..
.....
....
.................
.................
....
....
.
.................
....
....
.
c
.................
....
....
.
1
.........................
................................. ..........................................................
..........................
............................... ......................................................
.....
.....
....
....
....
...
....
....
....
..
....
....
...
....
...
...
...
...
..
...
...
..
...
....
..
...
..
...
..
.
..
..
..
..
..
..
.
..
..
...
..
...
..
...
..
...
..
...
..
...
..
...
..
....
...
..
...
...
..
...
...
....
..
....
...
....
....
....
....
....
....
.......
........
.............
...............
...............
...............
..........
.........................
.......................
..........
........
......
....
....
....
..
...
...
...
.
.................................
..............
.......
................
..................
...
....
.....
...
...
...
..
...
...
..
...
...
..
..
..
......................................
..............
..........
.........
.........
.........
.........
..
.......
.......
........
......
......
......
....
.....
....
....
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
.
..
.
.....
.....
....
..
.....
....
....
.....
...
.....
....
...
....
...
.....
....
...
.....
....
.....
....
......
.....
.....
......
.........
...........
..............
..............
.............
............
.............
.
............
...............
...............
....................
..................................
0
1
2
3
1.2
3.4
5.6
7.8
2
-1
1
0
3
Slika 1.2
Primjer strukture podataka.
1.3
Zapisivanje i analiziranje algoritma
Kao jezik za zapisivanje algoritama sluˇ
zit ´
ce nam programski jezik C. Dakle, umjesto algoritama pisat
´
cemo program (ili funkciju) u C-u koji radi po tom algoritmu. Obiˇ
cno ´
ce biti rijeˇ
c o “skiciranom”
nedovrˇ
senom) kodu, gdje su neki nizovi naredbi zamijenjeni slobodnim tekstom.
Pod
analizom algoritma
podrazumijevamo procjenu vremena izvrˇ
savanja tog algoritma. Vrijeme
poistovje´
cujemo s brojem operacija koje odgovaraju´
ci program treba obaviti, i izraˇ
zavamo kao funkciju
oblika
T
(
n
), gdje je
n
neka mjera za veliˇ
cinu skupa ulaznih podataka. Naprimjer, ako promatramo
algoritam koji sortira niz realnih brojeva, tada njegovo vrijeme izvrˇ
savanja izraˇ
zavamo u obliku
T
(
n
)
gdje je
n
duljina niza realnih brojeva. Sliˇ
cno, ako promatramo algoritam za invertiranje matrica, tada
njegovo vrijeme izvrˇ
savanja izraˇ
zavamo kao
T
(
n
), gdje je
n
red matrice.
ˇ
Cesto se deˇ
sava da
T
(
n
) ne ovisi samo o veliˇ
cini skupa ulaznih podataka
n
, nego takoder i o
vrijednostima tih podataka. Npr. algoritam za sortiranje moˇ
zda brˇ
ze sortira niz brojeva koji je “skoro
sortiran”, a sporije niz koji je “jako izmijeˇ
san”. Tada definiramo
T
(
n
) kao vrijeme u najgorem sluˇ
caju,
dakle kao maksimum za vrijeme izvrˇ
savanja po svim skupovima ulaznih podataka veliˇ
cine
n
. Takoder
se tada promatra vrijeme u prosjeˇ
cnom sluˇ
caju
T
avg
(
n
), koje se dobiva kao matematiˇ
cko oˇ
cekivanje
vremena izvrˇ
savanja. Da bi mogli govoriti o oˇ
cekivanju, moramo pretpostaviti distribuciju za razne
skupove ulaznih podataka veliˇ
cine
n
. Obiˇ
cno se pretpostavlja uniformna distribucija, dakle smatra se
da su svi skupovi ulaznih podataka jednako vjerojatni.
Funkciju
T
(
n
) nema smisla precizno odredivati, dovoljno je utvrditi njen red veliˇ
cine. Npr. vrijeme
izvrˇ
savanja Gaussovog algoritma za invertiranje matrice je
O
(
n
3
). Time smo zapravo rekli da
T
(
n
)
≤
const
·
n
3
. Nismo precizno utvrdili koliko ´
ce sekundi trajati naˇ
s program. Jedino ˇ
sto znamo je sljede´
ce:
- ako se red matrice udvostruˇ
ci, invertiranje bi moglo trajati i do 8 puta dulje;
- ako se red matrice utrostruˇ
ci, invertiranje traje 27 puta dulje, itd.
