Gegevensstructuur: definitie, voorbeelden en toepassingen in informatica

Basis gegevensstructuren

Array

Het eenvoudigste type gegevensstructuur is een lineaire array. Ook bekend als een één-dimensionale array. Een array bevat verschillende waarden van hetzelfde type (Integer, Floats, String, enz.). De toegang tot elementen binnen de array is zeer snel. Een array heeft normaal gesproken een vaste grootte. Nadat de grootte van de array aan het begin is gedefinieerd, kan het niet mogelijk zijn de grootte van de array te vergroten zonder een nieuwe grotere array te maken en alle waarden naar de nieuwe array te kopiëren. In de informatica is een array-gegevensstructuur of kortweg een array een gegevensstructuur die bestaat uit een verzameling elementen (waarden of variabelen), elk geïdentificeerd door ten minste één array-index of -sleutel. Een array wordt zo opgeslagen dat de positie van elk element kan worden berekend uit zijn index tuple door een wiskundige formule.

Bijvoorbeeld, een array van 10 integer variabelen, met de indices 0 tot en met 9, kan worden opgeslagen als 10 woorden op de geheugenadressen 2000, 2004, 2008, 2036, zodat het element met index i het adres 2000 + 4 × i heeft.

Aangezien het wiskundige concept van een matrix kan worden voorgesteld als een tweedimensionaal raster, worden tweedimensionale arrays soms ook matrices genoemd. In sommige gevallen wordt in de informatica de term "vector" gebruikt om te verwijzen naar een array, hoewel tupels in plaats van vectoren het correctere wiskundige equivalent zijn. Arrays worden vaak gebruikt om tabellen te implementeren, vooral opzoektabellen; het woord tabel wordt soms gebruikt als synoniem van array.

Arrays behoren tot de oudste en belangrijkste datastructuren, en worden door bijna elk programma gebruikt. Zij kunnen ook worden gebruikt om vele andere gegevensstructuren te implementeren, zoals lijsten en strings. Zij maken effectief gebruik van de adresseringslogica van computers. In de meeste moderne computers en veel externe opslagapparaten is het geheugen een ééndimensionale array van woorden, waarvan de indices de adressen zijn. Processoren, vooral vectorprocessoren, zijn vaak geoptimaliseerd voor array-bewerkingen.

Arrays zijn nuttig omdat de element indexen kunnen worden berekend tijdens de run time. Deze eigenschap maakt het onder andere mogelijk dat een enkele iteratieve instructie willekeurig veel elementen van een array kan verwerken. Om die reden moeten de elementen van een array datastructuur dezelfde grootte hebben en dezelfde datarepresentatie gebruiken. De verzameling geldige index-tupels en de adressen van de elementen (en dus de element-adresseringsformule) liggen gewoonlijk, maar niet altijd, vast terwijl de array in gebruik is.

De term array wordt vaak gebruikt om array-gegevenstype aan te duiden, een soort gegevenstype dat door de meeste programmeertalen op hoog niveau wordt aangeboden en dat bestaat uit een verzameling waarden of variabelen die kunnen worden geselecteerd door één of meer indexen die tijdens de run-time worden berekend. Array-types worden vaak geïmplementeerd door array-structuren; in sommige talen kunnen ze echter worden geïmplementeerd door hash-tabellen, gekoppelde lijsten, zoekbomen, of andere gegevensstructuren.

Gekoppelde lijst

Een gekoppelde gegevensstructuur is een verzameling informatie/gegevens die door referenties aan elkaar zijn gekoppeld. De gegevens worden vaak nodes genoemd. De verwijzingen worden vaak links of pointers genoemd. Vanaf hier zullen de woorden node en pointer worden gebruikt voor deze begrippen.

In gelinkte datastructuren worden pointers alleen gederefereerd of vergeleken op gelijkheid. Gelinkte gegevensstructuren zijn dus anders dan arrays, waarvoor pointers moeten worden opgeteld en afgetrokken.

Gekoppelde lijsten, zoekbomen, en expressiebomen zijn allemaal gekoppelde gegevensstructuren. Zij zijn ook belangrijk in algoritmen zoals topological sort en set union-find.

Stack

Een stapel is een basisgegevensstructuur die logisch kan worden gedacht als een lineaire structuur voorgesteld door een echte fysieke stapel of stapel, een structuur waar het invoegen en verwijderen van items plaatsvindt aan één uiteinde, de top van de stapel genoemd. Het basisconcept kan worden geïllustreerd door uw gegevensverzameling te beschouwen als een stapel borden of boeken waarbij u alleen het bovenste item van de stapel kunt nemen om er dingen uit te verwijderen. Deze structuur wordt overal in het programmeren gebruikt.

De basisimplementatie van een stack wordt ook wel een "Last In First Out"-structuur genoemd; er zijn echter verschillende variaties van stackimplementaties.

Er zijn in principe drie bewerkingen die op stapels kunnen worden uitgevoerd. Dat zijn:

• een item in een stapel plaatsen ("pushing")
• een item van de stapel verwijderen ("popping")
• weergave van de inhoud van het bovenste item van de stapel ("gluren")

Wachtrij

Een wachtrij is een abstract gegevenstype of een lineaire gegevensstructuur, waarin het eerste element wordt ingevoegd vanaf het ene uiteinde (de "tail"), en het verwijderen van een bestaand element plaatsvindt vanaf het andere uiteinde (de "head"). Een wachtrij is een "First In First Out"-structuur. "First In First Out" betekent dat elementen die eerst in de wachtrij worden gezet er eerst uitkomen, en dat elementen die als laatste in de wachtrij worden gezet er als laatste uitkomen. Een voorbeeld van een wachtrij zijn rijen wachtende mensen. De eerste persoon in de rij gaat eerst, en de laatste persoon in de rij gaat als laatste.

Het toevoegen van een element aan een wachtrij wordt "enqueuing" genoemd en het verwijderen van een element uit een wachtrij wordt "dequeuing" genoemd.

Grafiek

Een grafiek is een abstract gegevenstype dat bedoeld is om de grafiek- en hypergrafiekconcepten uit de wiskunde te implementeren.

Een grafische gegevensstructuur bestaat uit een eindige (en mogelijk muteerbare) verzameling geordende paren, randen of bogen genoemd, van bepaalde entiteiten, knopen of hoekpunten genoemd. Zoals in de wiskunde wordt van een edge (x,y) gezegd dat hij van x naar y wijst of gaat. De nodes kunnen deel uitmaken van de grafiekstructuur, of externe entiteiten zijn die worden voorgesteld door gehele getallen of referenties. Een grafische gegevensstructuur kan aan elke rand ook een randwaarde toekennen, zoals een symbolisch label of een numeriek attribuut.

Boom

De boom is een van de krachtigste geavanceerde gegevensstructuren. Hij komt vaak voor in geavanceerde onderwerpen zoals Kunstmatige Intelligentie (AI) en design. Verrassend genoeg is de boom belangrijk in een veel basalere toepassing - het bijhouden van een efficiënte index.

Wanneer een boom wordt gebruikt, is de kans groot dat een index wordt gebruikt. Het eenvoudigste type index is een gesorteerde lijst van sleutelvelden. Een boom heeft normaliter een gedefinieerde structuur. In het geval van een binaire boom kan een binaire zoekopdracht worden gebruikt om een willekeurig item te vinden zonder dat naar elk item hoeft te worden gekeken.

Het gegevenstype boom is een soort grafiek, wat betekent dat veel algoritmen die zijn gemaakt om een grafiek te doorkruisen ook met een boom werken, maar de algoritmen kunnen veel op elkaar lijken en moeten een specifiek startknooppunt hebben, dat wil zeggen het knooppunt dat geen andere knooppunten heeft die er naar verwijzen.

Het probleem met een eenvoudige geordende lijst ontstaat wanneer je nieuwe items begint toe te voegen en de lijst gesorteerd moet houden - dit kan redelijk efficiënt, maar vereist enige aanpassingen. Bovendien is een lineaire index niet gemakkelijk te delen omdat de hele index "gelocked" moet worden als een gebruiker hem bewerkt, terwijl een "tak" van een boom gelocked kan worden, waarbij de andere takken bewerkbaar blijven voor andere gebruikers (omdat ze niet beïnvloed kunnen worden).

Hash tabel

Een hashtabel is een matrix waarbij elke index wijst naar een gekoppelde lijst op basis van een hashwaarde. Een hashwaarde is een waarde bepaald door een hashfunctie. Een hashfunctie bepaalt een unieke waarde op basis van de gegevens die worden opgeslagen. Dit maakt toegang tot gegevens in constante tijd mogelijk, omdat de computer altijd weet waar hij moet zoeken.