Структура података
Структура података, начин представљања података у рачунарској меморији, којим се омогућује њихово лако представљање и обрада.[2][3][4] Тачније, структура података је скуп вредности података, односа међу њима и функција или операција које се могу применити на податке,[5] тј. то је алгебарска структура о подацима. Најбитније структуре су: низови, уланчане листе, стекови, редови, приоритетни редови, графови, бинарни и m-арна стабла.
Употреба
[уреди | уреди извор]Структуре података служе као основа за апстрактне типове података (ADT). ADT дефинише логичку форму типа података. Структура података имплементира физички облик типа података.[6]
Различити типови структура података су погодни за различите врсте апликација, а неке су високо специјализоване за специфичне задатке. На пример, релационе базе података обично користе индексе Б-стабла за проналажење података,[7] док имплементације компајлера обично користе хеш табеле за тражење идентификатора.[8]
Структуре података обезбеђују средства за ефикасно управљање великим количинама података за употребу као што су велике базе података и услуге индексирања интернета. Обично су ефикасне структуре података кључне за пројектовање ефикасних алгоритама. Неке формалне методе дизајна и програмски језици наглашавају структуре података, а не алгоритме, као кључни организациони фактор у дизајну софтвера. Структуре података се могу користити за организовање складиштења и проналажења информација ускладиштених у главној и у секундарној меморији.[9]
Низови
[уреди | уреди извор]Као елементарне структуре могли би се навести низови - мада, неко се можда неће сложити да су низови структуре. Низови су структуре података које се могу користити за чување великог броја истородних података. У рачунарској меморији се углавном реализују као континуални меморијски блокови. Директан приступ је веома ефикасан, као и секвенцијалан. Такође, постоји велики број ефикасних алгоритама за претраживање низова и уређивање низова по неком критеријуму. На пример: ако је адреса почетка низа А, а тражи се i-ти елемент низа, до њега се долази веома једноставно
a[i] = вредност_локације (A + i * величина_појединачног_елемента_низа)
Мане низова су веома захтевно уметање елемената између два већ постојећа, њихово брисање (потребно је померити све елементе низа од места где се умећу једно место према крају низа).
Листе
[уреди | уреди извор]И листе спадају међу једноставне структуре, са истом сврхом као и низови али различите имплементације. Сваки елемент листе, поред податка, чува и показивач на следећи елемент листе. Појединачни елементи листе могу се произвољно алоцирати и деалоцирати. Што се тиче ефикасности, ефикаснији су од низова у појединим случајевима. Секвенцијалан приступ је ефикасан, али директан није, јер је потребно да се прође кроз све елементе листе ради добављања податка. Уметање елемената у листу је такође једноставно, као и брисање.
Стекови
[уреди | уреди извор]Стек је структура података, над којом се могу извршити две операције: операција смештања на стек (push), и операција узимања са стека (pop). Ова структура је посебна по томе што се елемент који је последњи стављен на стек, први се уклања са стека. Стекови су врло чести у рачунарству - скоро сваки процесор подржава коришћење меморије као стека, јер се користе за памћење адреса при скоку у друге потпрограме, за чување података, итд.
Редови
[уреди | уреди извор]Слично стековима, и над редовима се могу вршити две операције: уметање у ред (Insert) и операција уклањања из реда (delete). Разлика у односу на стек је само у томе што се, из реда узима елемент који је најдуже провео чекајући у реду. И редови су чести у рачунарству: користе се организовање различитих активности током извршавања програма. Приоритетни редови се од обичних разликују по томе што се при уметању податка у ред, податку додељује приоритет, а при вађењу из реда, из реда се узима елемент са најмањим/највећим приоритетом.
Стабла
[уреди | уреди извор]Стабла су структуре података, које одржавају релације међу подацима. Подаци су организовани тако, да постоји један податак (корен стабла), који је у релацији са подацима који су на следећем нивоу, а ови у релацији са подацима на следећем нивоу. Сваки податак има једног родитеља (сем корена), и ниједно, једно или више деце. Назив је настао, јер цртањем овакве структуре на папиру добија се изглед наопаког стабла. Стабла се у рачунарству користе за моделирање података који су у оваквим односима, као и на пример за: ефикасно рачунање аритметичких израза, стабла одлучивања (програмирање оваквог типа игара: шах, икс-окс...). Поред овог, постоје посебне модификације стабала које служе за брзо претраживање по скупу података: висински балансирана стабла, Б стабла итд.
Графови
[уреди | уреди извор]Графови су уопштења бинарних стабала. Сваки податак може бити у релацији са произвољним бројем података. Користе се, на пример, за одређивање најкраћег пута између два града, максимизацију протока, итд.
Остале структуре
[уреди | уреди извор]Поред ових структура, које су најчешће, постоји велики број структура које су модификација ових, и које се користе за различите потребе.
Референце
[уреди | уреди извор]- ^ Mehlhorn, Kurt; Sanders, Peter (2008), „4 Hash Tables and Associative Arrays”, Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, стр. 81—98
- ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms, Third Edition (3rd изд.). The MIT Press. ISBN 978-0262033848.
- ^ Black, Paul E. (15. 12. 2004). „data structure”. Ур.: Pieterse, Vreda; Black, Paul E. Dictionary of Algorithms and Data Structures [online]. National Institute of Standards and Technology. Приступљено 2018-11-06.
- ^ „Data structure”. Encyclopaedia Britannica. 17. 4. 2017. Приступљено 2018-11-06.
- ^ Wegner, Peter; Reilly, Edwin D. (2003-08-29). Encyclopedia of Computer Science. Chichester, UK: John Wiley and Sons. стр. 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. Архивирано из оригинала 2021-04-27. г. Приступљено 2018-06-14.
- ^ „When data is too big to fit into the main memory”. homes.sice.indiana.edu. Архивирано из оригинала 27. 04. 2021. г. Приступљено 25. 12. 2022.
Литература
[уреди | уреди извор]- Peter Brass (2008). Advanced Data Structures. Cambridge University Press. ISBN 978-0521880374.
- Donald Knuth (1997). The Art of Computer Programming. 1 (3rd изд.). 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. Свјетлост. ISBN 0-201-00023-7.
- G. H. Gonnet; R. Baeza-Yates (1991). Handbook of Algorithms and Data Structures - in Pascal and C (2nd изд.). 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 изд.). Massachusetts Institute of Technology. стр. 253—280. ISBN 978-0-262-03384-8.
- Knuth, Donald (1998). The Art of Computer Programming. 3: Sorting and Searching (2nd изд.). Addison-Wesley. стр. 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 изд.). MIT Press and McGraw-Hill. стр. 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 изд.). 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, стр. 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 — преко ScienceDirect.
- Celis, Pedro (1986). Robin Hood Hashing (PDF). Ontario, Canada: University of Waterloo, Dept. of Computer Science. ISBN 031529700X. OCLC 14083698. Архивирано (PDF) из оригинала 1. 11. 2021. г. Приступљено 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. Приступљено 1. 11. 2021 — преко Cambridge Core.
- Clarkson, Michael (2014). „Lecture 13: Hash tables”. Cornell University, Department of Computer Science. Архивирано из оригинала 7. 10. 2021. г. Приступљено 1. 11. 2021 — преко cs.cornell.edu.
- Gries, David (2017). „JavaHyperText and Data Structure: Robin Hood Hashing” (PDF). Cornell University, Department of Computer Science. Архивирано (PDF) из оригинала 26. 4. 2021. г. Приступљено 2. 11. 2021 — преко cs.cornell.edu.
- Celis, Pedro (28. 3. 1988). External Robin Hood Hashing (PDF) (Технички извештај). Bloomington, Indiana: Indiana University, Department of Computer Science. 246. Архивирано (PDF) из оригинала 2. 11. 2021. г. Приступљено 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 изд.). Hoboken, NJ: Wiley. стр. 369–418. ISBN 978-0-471-73884-8. - McKenzie, B. J.; Harries, R.; Bell, T. (фебруар 1990). „Selecting a hashing algorithm”. Software: Practice and Experience. 20 (2): 209—224. S2CID 12854386. doi:10.1002/spe.4380200207. hdl:10092/9691 .
