Структура података
Структура података, начин представљања података у рачунарској меморији, којим се омогућује њихово лако представљање и обрада.[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 .
