Struktura podataka

(Preusmjereno sa Strukture podataka)

Struktura podataka, način predstavljanja podataka u računarskoj memoriji, kojim se omogućuje njihovo lako predstavljanje i obrada. Najbitnije strukture su: nizovi, ulančane liste, stekovi, redovi, prioritetni redovi, grafovi, binarni i m-arna stabla.

NizoviUredi

Kao elementarne strukture mogli bi se navesti nizovi - mada, neko se možda neće složiti da su nizovi strukture. Nizovi su strukture podataka koje se mogu koristiti za čuvanje velikog broja istorodnih podataka. U računarskoj memoriji se uglavnom realizuju kao kontinualni memorijski blokovi. Direktan pristup je veoma efikasan, kao i sekvencijalan. Takođe, postoji veliki broj efikasnih algoritama za pretraživanje nizova i uređivanje nizova po nekom kriterijumu. Na primer: ako je adresa početka niza A, a traži se i-ti element niza, do njega se dolazi veoma jednostavno

a[i] = vrednost_lokacije (A + i * veličina_pojedinačnog_elementa_niza)

Mane nizova su veoma zahtevno umetanje elemenata između dva već postojeća, njihovo brisanje (potrebno je pomeriti sve elemente niza od mesta gde se umeću jedno mesto prema kraju niza).

ListeUredi

I liste spadaju među jednostavne strukture, sa istom svrhom kao i nizovi ali različite implementacije. Svaki element liste, pored podatka, čuva i pokazivač na sledeći element liste. Pojedinačni elementi liste mogu se proizvoljno alocirati i dealocirati. Što se tiče efikasnosti, efikasniji su od nizova u pojedinim slučajevima. Sekvencijalan pristup je efikasan, ali direktan nije, jer je potrebno da se prođe kroz sve elemente liste radi dobavljanja podatka. Umetanje elemenata u listu je takođe jednostavno, kao i brisanje.

StekoviUredi

Glavni članak: Stek

Stek je struktura podataka, nad kojom se mogu izvršiti dve operacije: operacija smeštanja na stek (push), i operacija uzimanja sa steka (pop). Ova struktura je posebna po tome što se element koji je poslednji stavljen na stek, prvi se uklanja sa steka. Stekovi su vrlo česti u računarstvu - skoro svaki procesor podržava korišćenje memorije kao steka, jer se koriste za pamćenje adresa pri skoku u druge potprograme, za čuvanje podataka, itd.

RedoviUredi

Slično stekovima, i nad redovima se mogu vršiti dve operacije: umetanje u red (Insert) i operacija uklanjanja iz reda (delete). Razlika u odnosu na stek je samo u tome što se, iz reda uzima element koji je najduže proveo čekajući u redu. I redovi su česti u računarstvu: koriste se organizovanje različitih aktivnosti tokom izvršavanja programa. Prioritetni redovi se od običnih razlikuju po tome što se pri umetanju podatka u red, podatku dodeljuje prioritet, a pri vađenju iz reda, iz reda se uzima element sa najmanjim/najvećim prioritetom.

StablaUredi

Stabla su strukture podataka, koje održavaju relacije među podacima. Podaci su organizovani tako, da postoji jedan podatak (koren stabla), koji je u relaciji sa podacima koji su na sledećem nivou, a ovi u relaciji sa podacima na sledećem nivou. Svaki podatak ima jednog roditelja (sem korena), i nijedno, jedno ili više dece. Naziv je nastao, jer crtanjem ovakve strukture na papiru dobija se izgled naopakog stabla. Stabla se u računarstvu koriste za modeliranje podataka koji su u ovakvim odnosima, kao i na primer za: efikasno računanje aritmetičkih izraza, stabla odlučivanja (programiranje ovakvog tipa igara: šah, iks-oks...). Pored ovog, postoje posebne modifikacije stabala koje služe za brzo pretraživanje po skupu podataka: visinski balansirana stabla, B stabla itd.

GrafoviUredi

Grafovi su uopštenja binarnih stabala. Svaki podatak može biti u relaciji sa proizvoljnim brojem podataka. Koriste se, na primer, za određivanje najkraćeg puta između dva grada, maksimizaciju protoka, itd.

Ostale struktureUredi

Pored ovih struktura, koje su najčešće, postoji veliki broj struktura koje su modifikacija ovih, i koje se koriste za različite potrebe.

Spoljašnje vezeUredi