Пређи на садржај

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

С Википедије, слободне енциклопедије
Структура података позната као хеш табела.[1]

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

Употреба

[уреди | уреди извор]

Структуре података служе као основа за апстрактне типове података (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. 

Литература

[уреди | уреди извор]

Спољашње везе

[уреди | уреди извор]