Strukture podataka i algoritmi – Drugo izdanje

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 podataka,
algoritam zavrˇsava nakon konaˇcnog broja ponavljanja.