Prijeđi na sadržaj

Struktura podataka

Izvor: Wikipedija

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.

Nizovi

[uredi | uredi kod]

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).

Liste

[uredi | uredi kod]

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.

Stekovi

[uredi | uredi kod]
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.

Redovi

[uredi | uredi kod]

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.

Stabla

[uredi | uredi kod]

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.

Grafovi

[uredi | uredi kod]

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 strukture

[uredi | uredi kod]

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 veze

[uredi | uredi kod]