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