Datastruktuur

In rekenaarwetenskap is 'n datastruktuur 'n formaat vir die organisering, bestuur en stoor van data wat effektiewe toegang en wysiging moontlik maak.^{[1][2][3][4][5]} Meer konkreet is 'n datastruktuur 'n versameling datawaardes, die verhoudings tussen hulle, en die funksies of bewerkings wat toegepas kan word op die data.^[6]

'n Datastruktuur bekend as 'n hutstabel.

Gebruik

Datastrukture dien as die basis vir abstrakte datatipes (ADT). "Die ADT definieer die logiese vorm van die datatipe. Die datastruktuur implementeer die fisiese vorm van die datatipe."^[7]

Verskillende tipe datastrukture is geskik vir verskillende toepassings, en party is hoogs gespesialiseerd vir spesifieke take. So byvoorbeeld gebruik relasionele databasisse tipies B-boomindekse vir dataherwinning,^[8] terwyl programvertalers gewoonlik hutstabelle gebruik om identifiseerders op te soek.^[9]

Datastrukture verskaf 'n manier om groot hoeveelhede data doeltreffend te bestuur vir gebruike soos groot databasisse en internetindekseringsdienste. Doeltreffende datastrukture is gewoonlik die sleutel tot die ontwerp van doeltreffende algoritmes. Sommige formele ontwerpsmetodes en programmeertale beklemtoon datastrukture eerder as algoritmes as die sleutelfaktor vir organisering by sagtewareontwerp. Datastrukture kan gebruik word vir die stoor en herwinning van inligting wat in beide die hoofgeheue en sekondêre geheue gestoor word.^[10]

Implementering

Datastrukture word oor die algemeen gebaseer op die vermoë van 'n rekenaar om data op enige plek in sy geheue te kry en te stoor. Dié toegang geskied deur 'n wyser—'n bisstring wat 'n geheueadres voorstel, wat ook in die geheue gestoor kan word en deur die program gemanipuleer kan word. So bv. is die datastrukture skikking en rekord gebaseer op die berekening van data-items se adresse met wiskundige bewerkings, terwyl geskakelde datastrukture gebaseer is op die direkte stoor van data-items se adresse in die struktuur. Heelwat datastrukture gebruik altwee beginsels, soms gekombineer op nietriviale maniere (soos by XOR-skakeling).

Die implementering van 'n datastruktuur vereis tipies die skryf van 'n stel prosedures wat instansiërings van die datastruktuur skep en manipuleer. Die doeltreffendheid van 'n datastruktuur kan nie afsonderlik van hierdie bewerkings ontleed word nie. Hierdie waarneming motiveer die teoretiese konsep van 'n abstrakte datatipe, 'n datastruktuur wat indirek gedefinieer word deur die bewerkings wat uitgevoer word daarop, en deur die wiskundige eienskappe van daardie bewerkings (insluitend hul koste in ruimte en tyd).

Voorbeelde

Daar is verskeie tipe datastrukture, meestal gebou op eenvoudiger primitiewe datatipes:^[11]

• 'n Skikking is 'n aantal elemente in 'n spesifieke volgorde, tipies almal van die dieselfde tipe (afhangende van die taal kan die individuele elemente óf almal gedwing word om die dieselfde tipe te wees, óf kan van feitlik enige tipe wees). Elemente word verkry deur middel van 'n heelgetal indeks om te spesifiseer watter element benodig word. Tipiese implementering ken aaneenlopende geheuewoorde vir die elemente van skikkings toe (maar dit is nie altyd noodsaaklik nie). Skikkings kan 'n vaste lengte hê of aanpasbare lengte hê.
• 'n Geskakelde lys (ook net 'n lys genoem) is 'n lineêre versameling data-elemente van enige soort, die sogenaamde nodusse, waar elke nodus self 'n waarde het en wys na die volgende nodus in die geskakelde lys. Die belangrikste voordeel van 'n geskakelde lys bo 'n skikking is dat waardes altyd doeltreffend ingevoeg en verwyder kan word sonder die verskuiwing van die res van die lys. Sekere ander bewerkings, soos ewekansige toegang tot 'n sekere element is egter stadiger op lyste as op skikkings.
• 'n Rekord (ook 'n tuple of struct genoem) is 'n saamgestelde datastruktuur. 'n Rekord is 'n waarde wat ander waardes bevat, tipies 'n vaste aantal en volgorde, en tipies geïndekseer volgens naam. Die elemente van rekords word gewoonlik velde of lede genoem.
• 'n Vereniging is 'n datastruktuur wat bepaal watter uit 'n aantal toegelate primitiewe tipes gestoor kan word in sy instansiërings, bv. float (dryfpuntgetal) of long integer (lang heelgetal). In teenstelling met 'n rekord wat gedefinieer kan word om 'n dryfpuntgetal en 'n heelgetal te bevat; is daar in 'n vereniging net een waarde op 'n slag. Voldoende ruimte word toegeken om die wydste veldtipe te bevat.
• 'n Geëtiketteerde vereniging (tagged union) (ook 'n variant, variantrekord, gediskrimineerde vereniging, of disjunkte vereniging) bevat 'n addisionele veld wat die huidige tipe aandui vir beter tipeveiligheid.
• 'n Objek is 'n datastruktuur wat datavelde bevat soos 'n rekord, asook verskeie metodes wat werk op die data-inhoud. 'n Objek is 'n instansiëring in die geheue van 'n klas uit 'n taksonomie. In die konteks van objek-georiënteerde programmering staan rekords bekend as gewone ou datastrukture om hulle te onderskei van objekte.^[12]

Verder is grafieke en binêre bome ander datastrukture wat algemeen gebruik word.

Verwysings

1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms, Third Edition (3rd uitg.). The MIT Press. ISBN 978-0262033848.
2. Black, Paul E. (15 Desember 2004). "data structure". In Pieterse, Vreda; Black, Paul E. (reds.). Dictionary of Algorithms and Data Structures [online]. National Institute of Standards and Technology. Besoek op 6 November 2018.
3. "Data structure". Encyclopaedia Britannica. (17 April 2017).
4. Swart (ed.), Paul E. (2004-12-15). Inskrywing vir data struktuur in die Dictionary of Algorithms and Data Structures. Aanlynweergawe. Die Amerikaanse Nasionale Instituut van Standaarde en Tegnologie, 15 desember 2004. Url besoek op 2009-05-21 van http://xlinux.nist.gov/dads/HTML/datastructur.html.
5. Encyclopædia Britannica (2009). Inskrywing data struktuur in die Encyclopædia Britannica (2009). Url besoek op 2009-05-21 van http://www.britannica.com/EBchecked/topic/152190/data-structure.
6. Wegner, Peter; Reilly, Edwin D. (29 Augustus 2003). Encyclopedia of Computer Science. Chichester, UK: John Wiley and Sons. pp. 507–512. ISBN 978-0470864128.
7. "Abstract Data Types". Virginia Tech - CS3 Data Structures & Algorithms.
8. Gavin Powell (2006). "Chapter 8: Building Fast-Performing Database Models". Beginning Database Design. Wrox Publishing. ISBN 978-0-7645-7490-0.
9. "1.5 Applications of a Hash Table". University of Regina - CS210 Lab: Hash Table. Geargiveer vanaf die oorspronklike op 27 April 2021. Besoek op 14 Junie 2018.
10. "When data is too big to fit into the main memory". homes.sice.indiana.edu. Geargiveer vanaf die oorspronklike op 27 April 2021. Besoek op 11 Oktober 2022.
11. Seymour, Lipschutz (2014). Data structures (Revised first uitg.). New Delhi, India: McGraw Hill Education. ISBN 9781259029967. OCLC 927793728.
12. Walter E. Brown (29 September 1999). "C++ Language Note: POD Types". Fermi National Accelerator Laboratory. Geargiveer vanaf die oorspronklike op 3 Desember 2016. Besoek op 6 Desember 2016.

Bronne

• Peter Brass, Advanced Data Structures, Cambridge University Press, 2008, ISBN 978-0521880374
• Donald Knuth, The Art of Computer Programming, vol. 1. Addison-Wesley, 3de uitgawe, 1997, ISBN 978-0201896831
• Dinesh Mehta en Sartaj Sahni, Handbook of Data Structures and Applications, Chapman and Hall/CRC Press, 2004, ISBN 1584884355
• Niklaus Wirth, Algorithms and Data Structures, Prentice Hall, 1985, ISBN 978-0130220059

Verdere leeswerk

• Alfred Aho, John Hopcroft, en Jeffrey Ullman, Data Structures and Algorithms, Addison-Wesley, 1983, ISBN 0-201-00023-7
• G. H. Gonnet and R. Baeza-Yates, Handbook of Algorithms and Data Structures - in Pascal and C, tweede uitgawe, Addison-Wesley, 1991, ISBN 0-201-41607-7 Book
• Ellis Horowitz en Sartaj Sahni, Fundamentals of Data Structures in Pascal, Computer Science Press, 1984, ISBN 0-914894-94-3