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.
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]
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).
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.
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.
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.
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.
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
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-7Book
Ellis Horowitz en Sartaj Sahni, Fundamentals of Data Structures in Pascal, Computer Science Press, 1984, ISBN 0-914894-94-3
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
