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.
Upotreba
urediStrukture 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
urediKao 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
urediI 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
urediStek 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
urediSlič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
urediStabla 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
urediGrafovi 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
urediPored 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- ^ Mehlhorn, Kurt; Sanders, Peter (2008), „4 Hash Tables and Associative Arrays”, Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, str. 81—98
- ^ 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.
- ^ 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.
- ^ „Data structure”. Encyclopaedia Britannica. 17. 4. 2017. Pristupljeno 2018-11-06.
- ^ Wegner, Peter; Reilly, Edwin D. (2003-08-29). Encyclopedia of Computer Science. Chichester, UK: John Wiley and Sons. str. 507—512. ISBN 978-0470864128.
- ^ „Abstract Data Types”. Virginia Tech - CS3 Data Structures & Algorithms.
- ^ Gavin Powell (2006). „Chapter 8: Building Fast-Performing Database Models”. Beginning Database Design. Wrox Publishing. ISBN 978-0-7645-7490-0.
- ^ „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.
- ^ „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- Peter Brass (2008). Advanced Data Structures. Cambridge University Press. ISBN 978-0521880374.
- Donald Knuth (1997). The Art of Computer Programming. 1 (3rd izd.). Addison-Wesley. ISBN 978-0201896831.
- Dinesh Mehta; Sartaj Sahni (2004). Handbook of Data Structures and Applications. Chapman and Hall/CRC Press. ISBN 1584884355.
- Niklaus Wirth (1985). Algorithms and Data Structures. Prentice Hall. ISBN 978-0130220059.
- Alfred Aho; John Hopcroft; Jeffrey Ullman (1983). Data Structures and Algorithms. Svjetlost. ISBN 0-201-00023-7.
- G. H. Gonnet; R. Baeza-Yates (1991). Handbook of Algorithms and Data Structures - in Pascal and C (2nd izd.). Addison-Wesley. ISBN 0-201-41607-7.
- Ellis Horowitz; Sahni, Sartaj (1984). Fundamentals of Data Structures in Pascal. Computer Science Press. ISBN 0-914894-94-3.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd izd.). Massachusetts Institute of Technology. str. 253—280. ISBN 978-0-262-03384-8.
- Knuth, Donald (1998). The Art of Computer Programming. 3: Sorting and Searching (2nd izd.). Addison-Wesley. str. 513—558. ISBN 978-0-201-89685-5.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). „Chapter 11: Hash Tables”. Introduction to Algorithms (2nd izd.). MIT Press and McGraw-Hill. str. 221–252. ISBN 978-0-262-53196-2.
- Mehta, Dinesh P.; Sahni, Sartaj (28. 10. 2004). „9: Hash Tables”. Handbook of Datastructures and Applications (1 izd.). Taylor & Francis. ISBN 978-1-58488-435-4. doi:10.1201/9781420035179.
- Konheim, Alan G. (21. 6. 2010). Hashing in Computer Science: Fifty Years of Slicing and Dicing. John Wiley & Sons, Inc. ISBN 9780470630617. doi:10.1002/9780470630617.
- Lu, Yi; Prabhakar, Balaji; Bonomi, Flavio (2006), „Perfect Hashing for Network Applications”, 2006 IEEE International Symposium on Information Theory: 2774—2778, ISBN 1-4244-0505-X, S2CID 1494710, doi:10.1109/ISIT.2006.261567
- Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009), „Hash, displace, and compress” (PDF), Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009, Proceedings (PDF), Lecture Notes in Computer Science, 5757, Berlin: Springer, str. 682—693, CiteSeerX 10.1.1.568.130 , MR 2557794, doi:10.1007/978-3-642-04128-0_61
- Owolabi, Olumide (1. 2. 2003). „Empirical studies of some hashing functions”. Information and Software Technology. Department of Mathematics and Computer Science, University of Port Harcourt. 45 (2): 109—112. doi:10.1016/S0950-5849(02)00174-X — preko ScienceDirect.
- Celis, Pedro (1986). Robin Hood Hashing (PDF). Ontario, Canada: University of Waterloo, Dept. of Computer Science. ISBN 031529700X. OCLC 14083698. Arhivirano (PDF) iz originala 1. 11. 2021. g. Pristupljeno 2. 11. 2021.
- Poblete, P.V.; Viola, A. (14. 8. 2018). „Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions”. Combinatorics, Probability and Computing. Cambridge University Press. 28 (4): 600—617. ISSN 1469-2163. S2CID 125374363. doi:10.1017/S0963548318000408. Pristupljeno 1. 11. 2021 — preko Cambridge Core.
- Clarkson, Michael (2014). „Lecture 13: Hash tables”. Cornell University, Department of Computer Science. Arhivirano iz originala 7. 10. 2021. g. Pristupljeno 1. 11. 2021 — preko cs.cornell.edu.
- Gries, David (2017). „JavaHyperText and Data Structure: Robin Hood Hashing” (PDF). Cornell University, Department of Computer Science. Arhivirano (PDF) iz originala 26. 4. 2021. g. Pristupljeno 2. 11. 2021 — preko cs.cornell.edu.
- Celis, Pedro (28. 3. 1988). External Robin Hood Hashing (PDF) (Tehnički izveštaj). Bloomington, Indiana: Indiana University, Department of Computer Science. 246. Arhivirano (PDF) iz originala 2. 11. 2021. g. Pristupljeno 2. 11. 2021.
- Tamassia, Roberto; Goodrich, Michael T. (2006). „Chapter Nine: Maps and Dictionaries”. Data structures and algorithms in Java : [updated for Java 5.0] (4th izd.). Hoboken, NJ: Wiley. str. 369–418. ISBN 978-0-471-73884-8.
- McKenzie, B. J.; Harries, R.; Bell, T. (februar 1990). „Selecting a hashing algorithm”. Software: Practice and Experience. 20 (2): 209—224. S2CID 12854386. doi:10.1002/spe.4380200207. hdl:10092/9691 .