Datastrukturer i datalogi: Definition, typer og implementering

Array

Den enkleste type datastruktur er et lineært array. Også kendt som et endimensionelt array. Et array indeholder flere værdier af samme type (hele tal, flydende tal, streng osv.). Adgang til elementer i arrayet er meget hurtig. Et array har normalt en fast størrelse. Når arrayets størrelse er defineret i starten, er det muligvis ikke muligt at øge arrayets størrelse uden at oprette et nyt større array og kopiere alle værdierne til det nye array. Inden for datalogi er en array-datastruktur eller blot et array en datastruktur, der består af en samling elementer (værdier eller variabler), som hver især identificeres af mindst ét array-indeks eller én nøgle. Et array lagres således, at hvert enkelt elements position kan beregnes ud fra dets indeks-tupel ved hjælp af en matematisk formel.

F.eks. kan et array med 10 hele talvariabler med indeks 0 til 9 lagres som 10 ord på hukommelsesadresserne 2000, 2004, 2008 og 2036, således at elementet med indeks i har adressen 2000 + 4 × i.

Da det matematiske begreb matrix kan repræsenteres som et todimensionalt gitter, kaldes todimensionale arrays også nogle gange for matricer. I nogle tilfælde anvendes udtrykket "vektor" i databehandlinger til at betegne et array, selv om tupler snarere end vektorer er den mere korrekte matematiske ækvivalent. Arrays bruges ofte til at implementere tabeller, især opslagstabeller; ordet tabel bruges undertiden som synonym for array.

Arrays er blandt de ældste og vigtigste datastrukturer og bruges i næsten alle programmer. De kan også bruges til at implementere mange andre datastrukturer, f.eks. lister og strenge. De udnytter effektivt computernes adresseringslogik. I de fleste moderne computere og mange eksterne lagerenheder er hukommelsen et endimensionalt array af ord, hvis indeks er deres adresser. Processorer, især vektorprocessorer, er ofte optimeret til array-operationer.

Arrays er nyttige, fordi elementindeksene kan beregnes på køretid. Denne egenskab gør det bl.a. muligt at behandle vilkårligt mange elementer i et array med en enkelt iterativ erklæring. Derfor skal elementerne i en array-datastruktur have samme størrelse og bør anvende samme datarepræsentation. Sættet af gyldige indeks-tupler og elementernes adresser (og dermed elementadresseringsformlen) er normalt, men ikke altid, fast, mens arrayet er i brug.

Udtrykket array bruges ofte om array-datatypen, en datatype, der leveres af de fleste programmeringssprog på højt niveau, som består af en samling værdier eller variabler, der kan vælges ved hjælp af et eller flere indekser, der beregnes på køretid. Array-typer implementeres ofte ved hjælp af array-strukturer; i nogle sprog kan de dog også implementeres ved hjælp af hash-tabeller, linkede lister, søgetræer eller andre datastrukturer.

Sammenkoblet liste

En linket datastruktur er et sæt af oplysninger/data, der er forbundet med hinanden ved hjælp af referencer. Dataene kaldes ofte knuder. Referencerne kaldes ofte links eller pointers. Fra nu af vil ordene node og pointer blive brugt om disse begreber.

I linkede datastrukturer bliver pointere kun derefereret eller sammenlignet med henblik på lighed. Således er linkede datastrukturer anderledes end arrays, som kræver tilføjelse og subtraktion af pointere.

Sammenkædede lister, søgetræer og udtrykstræer er alle sammenkædede datastrukturer. De er også vigtige i algoritmer som f.eks. topologisk sortering og sæt union-find.

Stack

En stak er en grundlæggende datastruktur, der logisk set kan opfattes som en lineær struktur, der er repræsenteret af en fysisk stak eller bunke, en struktur, hvor indsættelse og sletning af elementer finder sted i den ene ende, der kaldes toppen af stakken. Det grundlæggende koncept kan illustreres ved at tænke på dit datasæt som en stak plader eller bøger, hvor man kun kan tage det øverste element af stakken for at fjerne ting fra den. Denne struktur anvendes i hele programmeringsprocessen.

Den grundlæggende implementering af en stak kaldes også en "Last In First Out"-struktur; der findes dog forskellige variationer af stakimplementeringer.

Der er grundlæggende tre operationer, der kan udføres på stakke. De er:

• indsættelse ("pushing") af et emne i en stak
• sletning ("popping") af et element fra stakken
• visning af indholdet af det øverste element i stakken ("peeking")

Kø

En kø er en abstrakt datatype eller en lineær datastruktur, hvor det første element indsættes fra den ene ende ("halen"), og sletningen af eksisterende elementer sker fra den anden ende ("hovedet"). En kø er en "First In First Out"-struktur. "First In First Out" betyder, at de elementer, der sættes først i køen, kommer først ud først, og de elementer, der sættes sidst i køen, kommer sidst ud sidst. Et eksempel på en kø er køer af ventende mennesker. Den første person i køen kommer først, og den sidste person i køen kommer sidst.

Processen med at tilføje et element til en kø kaldes "enqueuing", og processen med at fjerne et element fra en kø kaldes "dequeuing".

Graf

En graf er en abstrakt datatype, der er beregnet til at implementere graf- og hypergrafkoncepter fra matematikken.

En grafdatastruktur består af et endeligt (og muligvis foranderligt) sæt af ordnede par, kaldet kanter eller buer, af visse enheder kaldet knuder eller hjørner. Som i matematik siges en kant (x,y) at pege eller gå fra x til y. Knudepunkterne kan være en del af grafstrukturen eller være eksterne enheder, der repræsenteres af hele tal indekser eller referencer. En grafdatastruktur kan også tilknytte en kantværdi til hver kant, f.eks. en symbolsk etiket eller en numerisk egenskab.

Træ

Træet er en af de mest kraftfulde avancerede datastrukturer. Det optræder ofte i avancerede emner som f.eks. kunstig intelligens (AI) og design. Overraskende nok er træet vigtigt i en meget mere grundlæggende anvendelse - nemlig at føre et effektivt indeks.

Når der anvendes et træ, er der stor sandsynlighed for, at der anvendes et indeks. Den enkleste type indeks er en sorteret liste over nøglefelter. Et træ har normalt en defineret struktur. I tilfælde af et binært træ kan man bruge en binær søgning til at finde et element uden at skulle kigge på hvert enkelt element.

Trædatatypen er en type graf, hvilket betyder, at mange algoritmer, der er lavet til at gennemløbe en graf, også fungerer med et træ, men algoritmerne kan være meget ens og skal have en dedikeret startknude, dvs. en knude uden andre knuder, der er forbundet til den.

Problemet med en simpel ordnet liste opstår, når du begynder at tilføje nye elementer og skal holde listen sorteret - det kan gøres rimeligt effektivt, men kræver nogle ændringer. Desuden er et lineært indeks ikke let at dele, fordi hele indekset skal "låses", når en bruger redigerer det, hvorimod en "gren" af et træ kan låses, så de andre grene kan redigeres af andre brugere (da de ikke kan påvirkes).

Hashtabel

En hashtabel er et array, hvor hvert indeks peger på en linket liste baseret på en hashværdi. En hash-værdi er en værdi, der bestemmes af en hash-funktion. En hashfunktion bestemmer en unik værdi på grundlag af de data, den lagrer. Dette giver mulighed for adgang til data på konstant tid, fordi computeren altid ved, hvor den skal lede.