Struktura podataka

Struktura podataka, način predstavljanja podataka u računarskoj memoriji, kojim se omogućuje njihovo lako predstavljanje i obrada.[2][3][4] Tačnije, struktura podataka je skup vrednosti podataka, odnosa među njima i funkcija ili operacija koje se mogu primeniti na podatke,[5] tj. to je algebarska struktura o podacima. Najbitnije strukture su: nizovi, ulančane liste, stekovi, redovi, prioritetni redovi, grafovi, binarni i m-arna stabla.

Struktura podataka poznata kao heš tabela.[1]

Upotreba uredi

Strukture podataka služe kao osnova za apstraktne tipove podataka (ADT). ADT definiše logičku formu tipa podataka. Struktura podataka implementira fizički oblik tipa podataka.[6]

Različiti tipovi struktura podataka su pogodni za različite vrste aplikacija, a neke su visoko specijalizovane za specifične zadatke. Na primer, relacione baze podataka obično koriste indekse B-stabla za pronalaženje podataka,[7] dok implementacije kompajlera obično koriste heš tabele za traženje identifikatora.[8]

Strukture podataka obezbeđuju sredstva za efikasno upravljanje velikim količinama podataka za upotrebu kao što su velike baze podataka i usluge indeksiranja interneta. Obično su efikasne strukture podataka ključne za projektovanje efikasnih algoritama. Neke formalne metode dizajna i programski jezici naglašavaju strukture podataka, a ne algoritme, kao ključni organizacioni faktor u dizajnu softvera. Strukture podataka se mogu koristiti za organizovanje skladištenja i pronalaženja informacija uskladištenih u glavnoj i u sekundarnoj memoriji.[9]

Nizovi uredi

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

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

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

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

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

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

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

Reference uredi

  1. ^ Mehlhorn, Kurt; Sanders, Peter (2008), „4 Hash Tables and Associative Arrays”, Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, str. 81—98 
  2. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms, Third Edition (3rd izd.). The MIT Press. ISBN 978-0262033848. 
  3. ^ Black, Paul E. (15. 12. 2004). „data structure”. Ur.: Pieterse, Vreda; Black, Paul E. Dictionary of Algorithms and Data Structures [online]. National Institute of Standards and Technology. Pristupljeno 2018-11-06. 
  4. ^ „Data structure”. Encyclopaedia Britannica. 17. 4. 2017. Pristupljeno 2018-11-06. 
  5. ^ Wegner, Peter; Reilly, Edwin D. (2003-08-29). Encyclopedia of Computer Science. Chichester, UK: John Wiley and Sons. str. 507—512. ISBN 978-0470864128. 
  6. ^ „Abstract Data Types”. Virginia Tech - CS3 Data Structures & Algorithms. 
  7. ^ Gavin Powell (2006). „Chapter 8: Building Fast-Performing Database Models”. Beginning Database Design. Wrox Publishing. ISBN 978-0-7645-7490-0. 
  8. ^ „1.5 Applications of a Hash Table”. University of Regina - CS210 Lab: Hash Table. Arhivirano iz originala 2021-04-27. g. Pristupljeno 2018-06-14. 
  9. ^ „When data is too big to fit into the main memory”. homes.sice.indiana.edu. Arhivirano iz originala 27. 04. 2021. g. Pristupljeno 25. 12. 2022. 

Literatura uredi

Spoljašnje veze uredi