Структура података

Структура података, начин представљања података у рачунарској меморији, којим се омогућује њихово лако представљање и обрада.[2][3][4] Тачније, структура података је скуп вредности података, односа међу њима и функција или операција које се могу применити на податке,[5] тј. то је алгебарска структура о подацима. Најбитније структуре су: низови, уланчане листе, стекови, редови, приоритетни редови, графови, бинарни и m-арна стабла.

Структура података позната као хеш табела.[1]

Употреба уреди

Структуре података служе као основа за апстрактне типове података (ADT). ADT дефинише логичку форму типа података. Структура података имплементира физички облик типа података.[6]

Различити типови структура података су погодни за различите врсте апликација, а неке су високо специјализоване за специфичне задатке. На пример, релационе базе података обично користе индексе Б-стабла за проналажење података,[7] док имплементације компајлера обично користе хеш табеле за тражење идентификатора.[8]

Структуре података обезбеђују средства за ефикасно управљање великим количинама података за употребу као што су велике базе података и услуге индексирања интернета. Обично су ефикасне структуре података кључне за пројектовање ефикасних алгоритама. Неке формалне методе дизајна и програмски језици наглашавају структуре података, а не алгоритме, као кључни организациони фактор у дизајну софтвера. Структуре података се могу користити за организовање складиштења и проналажења информација ускладиштених у главној и у секундарној меморији.[9]

Низови уреди

Као елементарне структуре могли би се навести низови - мада, неко се можда неће сложити да су низови структуре. Низови су структуре података које се могу користити за чување великог броја истородних података. У рачунарској меморији се углавном реализују као континуални меморијски блокови. Директан приступ је веома ефикасан, као и секвенцијалан. Такође, постоји велики број ефикасних алгоритама за претраживање низова и уређивање низова по неком критеријуму. На пример: ако је адреса почетка низа А, а тражи се i-ти елемент низа, до њега се долази веома једноставно

a[i] = вредност_локације (A + i * величина_појединачног_елемента_низа)

Мане низова су веома захтевно уметање елемената између два већ постојећа, њихово брисање (потребно је померити све елементе низа од места где се умећу једно место према крају низа).

Листе уреди

И листе спадају међу једноставне структуре, са истом сврхом као и низови али различите имплементације. Сваки елемент листе, поред податка, чува и показивач на следећи елемент листе. Појединачни елементи листе могу се произвољно алоцирати и деалоцирати. Што се тиче ефикасности, ефикаснији су од низова у појединим случајевима. Секвенцијалан приступ је ефикасан, али директан није, јер је потребно да се прође кроз све елементе листе ради добављања податка. Уметање елемената у листу је такође једноставно, као и брисање.

Стекови уреди

Стек је структура података, над којом се могу извршити две операције: операција смештања на стек (push), и операција узимања са стека (pop). Ова структура је посебна по томе што се елемент који је последњи стављен на стек, први се уклања са стека. Стекови су врло чести у рачунарству - скоро сваки процесор подржава коришћење меморије као стека, јер се користе за памћење адреса при скоку у друге потпрограме, за чување података, итд.

Редови уреди

Слично стековима, и над редовима се могу вршити две операције: уметање у ред (Insert) и операција уклањања из реда (delete). Разлика у односу на стек је само у томе што се, из реда узима елемент који је најдуже провео чекајући у реду. И редови су чести у рачунарству: користе се организовање различитих активности током извршавања програма. Приоритетни редови се од обичних разликују по томе што се при уметању податка у ред, податку додељује приоритет, а при вађењу из реда, из реда се узима елемент са најмањим/највећим приоритетом.

Стабла уреди

Стабла су структуре података, које одржавају релације међу подацима. Подаци су организовани тако, да постоји један податак (корен стабла), који је у релацији са подацима који су на следећем нивоу, а ови у релацији са подацима на следећем нивоу. Сваки податак има једног родитеља (сем корена), и ниједно, једно или више деце. Назив је настао, јер цртањем овакве структуре на папиру добија се изглед наопаког стабла. Стабла се у рачунарству користе за моделирање података који су у оваквим односима, као и на пример за: ефикасно рачунање аритметичких израза, стабла одлучивања (програмирање оваквог типа игара: шах, икс-окс...). Поред овог, постоје посебне модификације стабала које служе за брзо претраживање по скупу података: висински балансирана стабла, Б стабла итд.

Графови уреди

Графови су уопштења бинарних стабала. Сваки податак може бити у релацији са произвољним бројем података. Користе се, на пример, за одређивање најкраћег пута између два града, максимизацију протока, итд.

Остале структуре уреди

Поред ових структура, које су најчешће, постоји велики број структура које су модификација ових, и које се користе за различите потребе.

Референце уреди

  1. ^ Mehlhorn, Kurt; Sanders, Peter (2008), „4 Hash Tables and Associative Arrays”, Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, стр. 81—98 
  2. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms, Third Edition (3rd изд.). The MIT Press. ISBN 978-0262033848. 
  3. ^ 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. 
  4. ^ „Data structure”. Encyclopaedia Britannica. 17. 4. 2017. Приступљено 2018-11-06. 
  5. ^ Wegner, Peter; Reilly, Edwin D. (2003-08-29). Encyclopedia of Computer Science. Chichester, UK: John Wiley and Sons. стр. 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. Архивирано из оригинала 2021-04-27. г. Приступљено 2018-06-14. 
  9. ^ „When data is too big to fit into the main memory”. homes.sice.indiana.edu. Архивирано из оригинала 27. 04. 2021. г. Приступљено 25. 12. 2022. 

Литература уреди

Спољашње везе уреди