Vad är en datastruktur? Definition, typer, algoritmer och exempel

Array

Den enklaste typen av datastruktur är en linjär matris. Även känd som en endimensionell matris. En matris innehåller flera värden av samma typ (heltal, flertalet, flertalet, strängar osv.). Det går mycket snabbt att komma åt element i matrisen. En array har normalt en fast storlek. När arrayens storlek har definierats från början kan det inte vara möjligt att öka arrayens storlek utan att skapa en ny större array och kopiera alla värden till den nya arrayen. Inom datavetenskap är en array-datastruktur eller helt enkelt en array en datastruktur som består av en samling element (värden eller variabler), var och en identifierad av minst ett array-index eller en nyckel. En array lagras så att varje elements position kan beräknas från dess indextupel med hjälp av en matematisk formel.

Till exempel kan en matris med 10 heltalsvariabler, med index 0-9, lagras som 10 ord på minnesadresserna 2000, 2004, 2008, 2036, så att elementet med index i har adressen 2000 + 4 × i.

Eftersom det matematiska begreppet matris kan representeras som ett tvådimensionellt rutnät, kallas tvådimensionella matriser ibland också för matriser. I vissa fall används termen "vektor" inom datateknik för att hänvisa till en matris, även om tupler snarare än vektorer är den mer korrekta matematiska motsvarigheten. Arrayer används ofta för att implementera tabeller, särskilt uppslagstabeller; ordet tabell används ibland som en synonym till array.

Arrayer är bland de äldsta och viktigaste datastrukturerna och används i nästan alla program. De kan också användas för att implementera många andra datastrukturer, t.ex. listor och strängar. De utnyttjar effektivt datorernas adresseringslogik. I de flesta moderna datorer och många externa lagringsenheter är minnet en endimensionell matris av ord, vars index är deras adresser. Processorer, särskilt vektorprocessorer, är ofta optimerade för arrayoperationer.

Arrayer är användbara eftersom elementindexen kan beräknas vid körning. Denna funktion gör det bland annat möjligt att med ett enda iterativt uttalande bearbeta godtyckligt många element i en array. Av den anledningen måste elementen i en array-datastruktur ha samma storlek och bör använda samma datarepresentation. Mängden giltiga indextupler och elementens adresser (och därmed formeln för elementadressering) är vanligtvis, men inte alltid, fastställda medan matrisen används.

Termen array används ofta för att beteckna array-datatyp, en typ av datatyp som tillhandahålls av de flesta programmeringsspråk på hög nivå och som består av en samling värden eller variabler som kan väljas med hjälp av ett eller flera index som beräknas vid körning. Array-typer implementeras ofta genom array-strukturer, men i vissa språk kan de också implementeras genom hashtabeller, länkade listor, sökträd eller andra datastrukturer.

Länkad lista

En länkad datastruktur är en uppsättning information/data som länkas samman med hjälp av referenser. Uppgifterna kallas ofta noder. Referenserna kallas ofta länkar eller pekare. Hädanefter kommer orden nod och pekare att användas för dessa begrepp.

I länkade datastrukturer avpubliceras eller jämförs pekare endast för att kontrollera jämlikhet. Länkade datastrukturer skiljer sig alltså från matriser, som kräver att pekare adderas och subtraheras.

Länkade listor, sökträd och uttrycksträd är alla länkade datastrukturer. De är också viktiga i algoritmer som topologisk sortering och set union-find.

Stack

En stapel är en grundläggande datastruktur som logiskt sett kan betraktas som en linjär struktur som representeras av en verklig fysisk stapel eller hög, en struktur där insättning och borttagning av objekt sker i ena änden som kallas stackens topp. Det grundläggande konceptet kan illustreras genom att tänka på din datamängd som en stapel tallrikar eller böcker där du bara kan ta bort det översta objektet från stapeln för att ta bort saker från den. Denna struktur används i hela programmeringen.

Den grundläggande implementeringen av en stapel kallas också för en "Last In First Out"-struktur, men det finns olika varianter av stapelimplementeringar.

Det finns i princip tre operationer som kan utföras på staplar. De är:

• infoga ("skjuta") ett objekt i en stapel.
• ta bort ("poppa") ett objekt från stapeln
• visa innehållet i det översta objektet i stapeln ("peeking")

Kö

En kö är en abstrakt datatyp eller en linjär datastruktur där det första elementet läggs in från ena änden (svansen) och borttagandet av befintliga element sker från den andra änden (huvudet). En kö är en struktur som bygger på principen "först in först ut". "First In First Out" innebär att de element som sätts in först i kön kommer att komma ut först, och de element som sätts in sist i kön kommer att komma ut sist. Ett exempel på en kö är köer med väntande människor. Den första personen i kön går först och den sista personen i kön går sist.

Processen att lägga till ett element i en kö kallas "enqueuing" och processen att ta bort ett element från en kö kallas "dequeuing".

Graf

En graf är en abstrakt datatyp som är tänkt att implementera begreppen graf och hypergraf från matematiken.

En grafisk datastruktur består av en ändlig (och eventuellt föränderlig) uppsättning ordnade par, som kallas kanter eller bågar, av vissa enheter som kallas noder eller hörn. Som i matematik sägs en kant (x,y) peka eller gå från x till y. Noderna kan vara en del av grafstrukturen eller kan vara externa enheter som representeras av heltalsindex eller referenser. En datastruktur för grafer kan också förknippa varje kant med ett kantvärde, t.ex. en symbolisk etikett eller ett numeriskt attribut.

Träd

Trädet är en av de mest kraftfulla avancerade datastrukturerna. Den förekommer ofta i avancerade ämnen som artificiell intelligens (AI) och design. Överraskande nog är trädet viktigt i en mycket enklare tillämpning - att hålla ett effektivt index.

När ett träd används är det stor chans att ett index används. Den enklaste typen av index är en sorterad lista med nyckelfält. Ett träd har normalt en definierad struktur. När det gäller ett binärt träd kan du använda en binär sökning för att hitta ett objekt utan att behöva titta på varje objekt.

Träddatatypen är en typ av graf, vilket innebär att många algoritmer för att gå igenom en graf också fungerar med ett träd. Algoritmerna kan dock vara mycket lika och måste ha en särskild startnod, dvs. en nod utan andra noder som länkar till den.

Problemet med en enkel ordnad lista uppstår när du börjar lägga till nya objekt och måste hålla listan sorterad - det kan göras ganska effektivt men kräver vissa ändringar. Dessutom är det inte lätt att dela ett linjärt index eftersom hela indexet måste "låsas" när en användare redigerar det, medan en "gren" av ett träd kan låsas och de andra grenarna kan redigeras av andra användare (eftersom de inte kan påverkas).

Hashtabell

En hashtabell är en matris där varje index pekar på en länkad lista baserad på ett hashvärde. Ett hashvärde är ett värde som bestäms av en hashfunktion. En hashfunktion bestämmer ett unikt värde baserat på de data den lagrar. Detta gör det möjligt att få tillgång till data i konstant tid eftersom datorn alltid vet var den ska leta.