Algoritmi i strukture podataka

Knjiga je nastala kao rezultat potrebe za odgovarajućim udžbenikom iz predmeta Strukture podataka i u njenom pisanju učinjen je napor da ona može da bude korisna za čitaoce sa različitim nivoom predznanja. Posle prvog poglavlja koje predstavlja uvod u oblast, knjiga je podeljena na četiri dela: linearne strukture podataka, nelinearne strukture podataka, pretraživanja i sortiranje. Naglasak se stavljen na strukture podataka koje se nalaze u operativnoj memoriji, a knjiga takođe sadrži i pitanja i zadatke za samostalno rešavanje.


Sadržaj
PREDGOVOR, I

1 UVOD, 1
1.1 O ALGORITMIMA, 1
1.1.1 Kunvencije pseudojezika, 2
1.1.2 Analiza algoritama, 4
1.1.3 Implementaciju algoritama, 7
1.2 O STRUKTURAMA PODATAKA, 8
1.2.1 Klasifikacija struktura podataka, 11
1.2.2 Memorijska reprezentacija, 12
1.2.3 Operacije sa strukturama podataka, 14

DEO I LINEARNE STRUKTURE PODATAKA, l7
2 NIZOVI, 19
2.1 VRSTE NIZOVA, 19
2.2 OPERACIJE SA NIZOVIMA, 20
2.3 PREDSTAVLJANJE NIZOVA U MEMORIJI, 21
2.3.1 Smeštanje vektora, 22
2.3.2 Smeštanje matrica, 24
2.3.3 Smeštanje višedimenzionalnih nizova, 26
2.4 OPTIMIZAClJE PRI SMEŠTANJU NIZOVA, 28
2.4.1 Trougaone matrice, 29
2.4.2 Retki nizovi, 31

3 ULANČANE LISTE, 35
3.1 OSNOVNI POJMOVI I OSOBINE, 35
3.2 OPERACIJE SA JEDNOSTRUKO ULANČANIM LISTAMA, 38
3.3 OPERACIJE SA KRUŽNIM ULANČANIM LISTAMA, 43
3.4 OPERACIJE SA DVOSTRUKO ULANČANIM LISTAMA, 46
3.5 POREĐENJE ULANČANE I SEKVENCIJALNE REPREZENTACIJE LINEARNIH LISTA, 49
3.6 PRlMENE ULANČANIH LISTA, 52
3.6.1 Predstavljanje retkih nizova, 52
3.6.2 Predstavljanje skupova, 54
3.6.3 Predstavljanje polinoma, 57

4 STEKOVI, 61
4.1 DEFINICIJA STEKA, 61
4.2. IMPLEMENTACIJA STEKA I OPERAClJE SA NJIM, 62
4.2.1 Sekvencijalna reprezentacija steka, 63
4.2.2 Sekvencijalna implementacija više stekova, 66
4.2.3 Ulančana reprezentacija steka, 69
4.3 PRIMENE STEKOVA, 71
4.3.1 Obrada aritmetičkih izraza, 71
4.3.2 Rad sa potprogramima, 81

5 REDOVI, 91
5.1 DEFINICIJA REDA, 91
5.2 IMPLEMENTACIJA REDA I OPERACIJE SA NJIM, 93
5.2.1 Sekvencijalna reprezentacija reda, 93
5.2.2 Ulančana reprezentacija reda, 101
5.3 PRIORITETNI RED, 103
531 Vektorska implementacija prioritetnog reda, 103
5.3.2 Ulančana implementacija prioritetnog reda, 105
5.4 PRIMENE I PERFORMANSE REDOVA, 106

DEO II NELINEARNE STRUKTURE PODATAKA, 109
6 STABLA, 111
6.1 DEFINIClJE STABLA I TERMINOLOGIJA, 111
6.2 PREDSTAVLJANJE STABLA, 115
6.2.1 Grafičko predstavljanje, 115
6.2.2 Memorijska reprezentacija, 115
6.3 BINARNA STABLA 118
6.3.1 Osobine i vrste binarnih stabala, 118
6.3.2 Memorijska reprezentacija binarnih stabala, 121
6.3.3 Minimizacija dužine puta u binarnom stablu, 122
6.3.4 Operacije sa binarnim stablima, 128
6.3.5 Povezana binarna stabla, 136
6.4 PREDSTAVLJANJE STABLA VIŠEG STEPENA BINARNIM STABLOM, 139
6.5 PRIMENE STABALA, 145
6.5.1 Predstavljanje arilmeličkih izraza, 145
6.5.2 Predstavljanje ulančanih lista, 147
6.5.3 Stabla odlučivanja, 149
6.5.4 Stabla igara, 151

7 GRAFOVI, 155
7.1 DEFINICIJE GRAFA I TERMINOLOG1JA, 155
7.2 PREDSTAVLJANJE GRAFOVA, 158
7.2.1 Matrična reprezentacija, 158
7.2.2 Ulančana reprezentacija, 159
7.3 Poređenje matrične i ulančane reprezentacije, 161
7.3. OBILAZAK GRAFA, 162
7.3.1 Obilazak grafa po širini, 163
7.3.2 Obilazak grafa po dubini, 165
7.3.3 Primene algoritama obilaska, 161
7.4 OBUHVATNA STABLA, 172
7.5 ODREĐIVANJE DOSTIŽNOSTI ČVOROVA U GRAFU, 179
7.5.1 Određivanje matrice puta, 179
7.5.2 Primena matrice puta - odredivanje rekurzivnosti potprograma, 82
7.6 ODREĐlVANJE NAJKRAĆIH RASTOJANJA U GRAFU, 182
7.6.1 Određivanje najkraćih putevu između svih parova čvorova, 184
7.6.2 Određivanje najkraićih puteva od jednog čvora do svih ostalih, 188
7.7 PROTOK U GRAFOVIMA, 192
7. 7.1 Maksimizacija protoka u grafu, 193
7.7.2 Uparivanje grafa, 198
7.8 ODREĐIVANJE TOPOLOŠKOG PORETKA I KRITIČNOG PUTA, 200
7.8.1 Topološko sortiranje, 201
7.8.2 Određivanje kritičnog puta, 203

DEO III PRETRAŽIVANJE, 209
8 OSNOVNI METODI PRETRAŽIVANJA, 211
8.1 SEKVENCIJALNO PRETRAŽIVANJE, 211
8.1.1 Optimizacije sekvencijalnog pretraživanja, 213
8.1.2 Sekvencijalno pretraživanje u uređenim tabelama, 214
8.2 BINARNO PRETRAŽIVANJE, 216
8.2.1 Binarno pretraživanje u povećanoj tabeli, 218
8.2.2 Binarno pretraživanje u tabeli nepoznate veličine, 219
8.2.3 Interpolaciono pretraživanje, 220
8.2.4 Fibonacci-jevo pretraživanje, 221

9 STABLA BINARNOG PRETRAŽIVANJA, 223
9.1 DEFINICIJA STABLA BlNARNOG PRETRAŽIVANJA, 223
9.2 OSNOVNE OPERACIJE, 225
9.2.1 Ispitivanje stabla, 225
9.1.2 Umetanje, 228
9.2.3 Brisanje, 230
9.1.4 Analiza efikasnosti osnovnih operacija, 232
9.3 BALANSIRANJE STABLA, 236
9.3.1 Visinski balansirana (AVL) slabla, 237
9 3.2 Ostale vrste balansiranih stabala, 245
9.4 OPTIMALNO STABLO BINARNOG PRETRAŽIVANJA, 248
9.5 PRIMENE STABLA BINARNOG PRETRAŽIVANJA, 252
9.5.1 Tabela simbola, 252
9.5.2 Predstavljanje prioritetnog reda, 255

10 STABLA OPŠTEG PRETRAŽIVANJA, 257
10.1 PRIMENA STABALA OPŠTEG PRETRAŽIVANJA, 257
10.2 STABLA M-ARNOG PRETRAŽIVANJA, 261
10.2.1 Operacije, 262
1012 Osobine i performanse stabla m-arnog pretraživanja, 264
10.2.3 Implementacija, 266
10.3 B-STABLA, 266
10.4 B*-STABLA , 274
10.5 B+-STABLA, 276
10.6 STABLA DIGITALNOG PRETRAŽIVANJA, 280

11 HEŠIRANJE, 289
11.1 DEFINIClJE, 289
11.2 HEŠ FUNKClJE, 291
11.2.1 Heš funkcije nezavisne od raspodele ključeva, 292
11.2.2 Heš funkcije zavisne od raspodele ključeva, 298
11.3 RAZREŠAVANJE KOLIZIJA, 301
11.3.1 Otvorena adresiranje, 301
11.3.2 Ulančavanje, 311
11.4 EVALUACIJA PERFORMANSI UNUTRAŠNJEG HEŠIRANJA, 315
11.4.1 Performanse otvorenog adresiranja, 315
11.4.2 Performanse ulančavanja, 317
11.4.3 Komparativno poređenje tehnika unutrašnjeg heširanja, 317
11.5 SPOLJAŠNJE HEŠIRANJE, 319
11.5.1 Standardne tehnike spoljašnjeg heširanja, 320
11.5.2 Fleksibilne tehnike spoljašnjeg heširanja, 323

DEO IV SORTIRANJE, 331
12 UNUTRAŠNJE SORTIRANJE, 333
12.1 SORTIRANJE POREĐENJEM, 335
12.1.1 Metodi umetanja, 335
12.1.2 Metodi selekcije, 339
12.1.3 Metodi zamene, 351
12.1.4 Opšta procena performansi metoda sortiranja poređenjem, 360
12.2 METODI SORTIRANJA LINEARNE SLOŽENOSTI, 363
12.2.1 Sortiranje brojanjem, 363
12.2.2 Adresno sortiranje, 365
12.2.3 Radix sortiranje, 366
12.3 POREĐENJE EFIKASNOSTI METODA UNUTRAŠNJEG SORTIRANJA, 368
12.4 PRIMENA PRINCIPA SORTIRANJA-STATISTIKA PORETKA, 369
12.4.1 Određivanje minimuma i maksimuma, 369
12.4.2 Određivanje k-tog najmanjeg elementa, 370

13 SPOLJAŠNJE SORTIRANJE, 373
13.1 DIREKTNO SPAJANJE, 376
13.2 PRIRODNO SPAJANJE, 382
13.3 VIŠESTRUKO SPAJANJE, 384
13.4 POLIFAZNO SPAJANJE, 392
13.5 KASKADNO SPAJANJE, 398
13.6 ORGANIZACIJA BAFERA KOD SPOLJAŠNJEG SORTlRANJA, 400

14 LITERATURA, 405