Datastruktuur

In rekenaarwetenskap is 'n datastruktuur 'n formaat vir die organisering, bestuur en stoor van data wat effektiewe toegang en wysiging moontlik maak. Meer konkreet is 'n datastruktuur 'n versameling datawaardes, die verhoudings tussen hulle, en die funksies of bewerkings wat toegepas kan word op die data.

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."

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, terwyl programvertalers gewoonlik hutstabelle gebruik om identifiseerders op te soek.

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.

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:

 '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.

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

Verwysings

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

Verdere leeswerk 
 Alfred Aho, John Hopcroft, en Jeffrey Ullman, Data Structures and Algorithms, Addison-Wesley, 1983, 
 G. H. Gonnet and R. Baeza-Yates, Handbook of Algorithms and Data Structures - in Pascal and C, tweede uitgawe, Addison-Wesley, 1991,  Book
 Ellis Horowitz en Sartaj Sahni, Fundamentals of Data Structures in Pascal, Computer Science Press, 1984,