Memorijsko predstavljanje nelinearnih struktura

Uvod

U računarstvu se susrećemo s dva osnovna pojma:

• strukture podataka – “statički” aspekt nekog programa. Ono sa čime se radi.
• algoritmi – “dinamički” aspekt programa. Ono što radi.

Strukture podataka i algoritmi su u nerazdvojivoj vezi: nemoguće je govoriti o jednom a da se ne spomene drugo.
Osnovni pojmovi:

• tip podatka – skup vrednosti koje neki podatak može primiti (npr. podatak tipa int može imati samo vrednosti iz skupa celih brojeva).
• apstraktni tip podataka (a.t.p.) – zadaje se navodenjem jednog ili više tipova podataka, te jedne ili više operacija (funkcija). Operacije i rezultati navedenih operacija su podaci navedenih tipova.
• struktura podataka – skupina varijabli u nekom programu i veza među tim varijablama.
• algoritam – konačni niz instrukcija, od kojih svaka ima jasno značenje i može biti izvršena u konačnom vremenu. Iste instrukcije mogu se izvršiti više puta, pod pretpostavkom da same instrukcije ukazuju na ponavljanje. Ipak, zahtevamo da, za bilo koje vrednosti ulaznih podataka, algoritam završava nakon konačnog broja ponavljanja.

Elementi od kojih se grade strukture podataka

Struktura podataka se sastoji od manjih celina koje se udružuju u veće i međusobno povezuju vezama.
Uvodimo posebne nazive za celine, načine udruživanja i načine povezivanja. Takođe, uvodimo pravila
kako se strukture prikazuju dijagramima.
Celija – varijabla koju posmatramo kao zasebnu celinu. To je relativan pojam (nešto se u jednom trenutku može smatrati ćelijom, a kasnije se može gledati unutrašnja građa iste celine). Svaka ćelija ima svoj tip i adresu.

Polje (array u C-u). Mehanizam udruživanja manjih delova strukture u veće. Polje čini više ćelija istog tipa sa uzastopnim adresama. Broj ćelija je unapred zadat i nepromenljiv.
Jedna ćelija se zove element polja i jednoznačno je određena vrednošću indeksa.

Zapis (slog, structure u C-u). Takođe mehanizam udruživanja manjih delova strukture u veće. Zapis čini više ćelija, koje ne moraju biti istog tipa, ali koje imaju uzastopne adrese. Broj, redosled i tip ćelija je unapred zadat i nepromenljiv. Sama ćelija se zove komponenta zapisa. Polja i zapisi se mogu kombinovati. Na primer, možemo imati polje zapisa, zapis čije pojedine komponente su polja, polje od polja, zapis čija komponenta je zapis, i slično.

Pointer – služi za uspostavljanje veze između deelova strukture. Pointer je ćelija koja pokazuje neku drugu ćeliju. Sadržaj pointera je adresa ćelije koju treba pokazati.

Kursor – takođe služi za uspostavljanje veze između delova strukture. Kursor je ćelija tipa integer koja pokazuje na element nekog polja. Sadržaj kursora je indeks elementa na kog treba pokazati.

Slika pokazuje primer strukture podataka koja se sastoji od niza zapisa povezanih pomoću pointera, te od jednog polja zapisa. Zapisi su još međusobno povezani kursorima.