Datastrukturer i datalogi: Definition, typer og implementering
Få en klar introduktion til datastrukturer i datalogi: definition, typer og implementering med algoritmer, optimering og eksempler på lister, træer, grafer og hash-tabeller.
Inden for datalogi er en datastruktur en organiseret måde at lagre og organisere værdier og information på, så man kan udføre operationer effektivt. Med enkle ord er en datastruktur en metode til at organisere data for at optimere ydeevne, hukommelsesforbrug eller enkelhed i koden. Datastrukturer adskiller sig fra abstrakte datatyper ved, at de er konkrete implementeringer: abstrakte datatyper beskriver hvilke operationer der kan udføres (fx en liste), mens datastrukturer beskriver, hvordan disse operationer realiseres i hukommelsen. Implementeringen af en datastruktur foretages typisk vha. algoritmer, f.eks. relationen mellem en abstrakt liste og en sammenkædet liste (linked list), hvor hver node indeholder en værdi og en reference (pointer) til det næste — eventuelt også til det forrige — element.
Hvad karakteriserer en datastruktur?
En datastruktur karakteriseres bl.a. ved:
- Støttede operationer: indsæt, slet, søg, opdater, iteration mv.
- Tidskompleksitet: hvor hurtigt operationerne kan udføres (ofte angivet i Big O-notation).
- Pladsforbrug: hvor meget hukommelse datastrukturen kræver, inkl. metadata som pointere eller indeks.
- Stabilitet og concurrency-egenskaber: hvordan datastrukturen opfører sig ved samtidig adgang i multithreadede miljøer.
Typiske typer af datastrukturer
Her er en oversigt over almindelige datastrukturer og deres typiske anvendelser:
- Array (vektor): kontinuerlig blok af elementer med konstant tid for adgang via indeks. God til tilfældig adgang, mindre god til indsættelse/sletning midt i strukturen.
- Sammenkædede lister (linked lists): fleksibel ved indsættelse/sletning, men langsommere tilfældig adgang pga. sekventiel traversal.
- Stack og kø (stack/queue): specialiserede lister til LIFO- og FIFO-adfærd; bruges i bl.a. rekursion, parsing og job-planlægning.
- Træer (fx binære søgetræer, AVL, rød-sorte træer): organiserer data hierarkisk, gør søgning, indsættelse og sletning effektive (logaritmisk tid) når træet er balanceret.
- Heap (prioritetskø): effektiv til at finde og fjerne elementet med højeste eller laveste prioritet (fx prioriterede job, Dijkstras algoritme).
- Hashtabeller: giver gennemsnitlig konstant tid for indsætning, søgning og sletning ved hjælp af en hashfunktion; bruges til opslagstabeller og caches.
- Grafer: bruges til at modellere netværk (fx sociale netværk, veje, kommunikationssystemer); repræsenteres ofte vha. adjacency-lists eller adjacency-matrices.
- Trie (præfiks-træ): optimeret til opslag af strenge og præfikssøgninger (fx autokomplettering).
Implementering og algoritmer
Når man implementerer datastrukturer, vælger man mellem forskellige teknikker afhængigt af sprog og krav:
- Kontinuerlig hukommelse: arrays og dynamiske arrays (fx std::vector i C++ eller ArrayList i Java) bruger sammenhængende hukommelsesblokke, hvilket giver god cache-udnyttelse.
- Dynamisk allokering og pointere/referencer: sammenkædede strukturer og træer bruger pointere eller referencer til at forbinde noder, hvilket gør dem fleksible mht. vækst men kan medføre ekstra hukommelsesoverhead.
- Hashing: kræver en god hashfunktion og håndtering af kollisioner (åben adressering eller kædning).
- Balancering: selvbalancerende træer (AVL, rød-sorte) anvender rotationer og andre operationer for at sikre, at dybden forbliver logaritmisk.
Valg af datastruktur
At vælge den rigtige datastruktur er ofte en af de vigtigste designbeslutninger i udviklingen af en løsning. Overvej:
- Hvilke operationer er mest hyppige? Hvis søgning er hyppig, kan hashtabel eller balanceret træ være bedst. Hvis hyppige indsættelser/sletninger i midten er vigtige, kan en sammenkædet liste være passende.
- Begrænsninger i hukommelse og realtid: i indlejrede systemer eller realtidsprogrammer kan plads- og tidsgarantier bestemme valget.
- Enkelhed vs. ydeevne: nogle gange er en simpel løsning (fx array eller liste) tilstrækkelig og lettere at vedligeholde end en kompleks, optimeret datastruktur.
- Sprog og bibliotekstilbud: moderne sprog leverer ofte robuste standarddatastrukturer (fx Collections i Java, STL i C++ eller dict/list i Python) som bør genbruges, medmindre der er særlige krav.
Tids- og pladscomplexitet (Big O)
For hver datastruktur vurderes operationernes kompleksitet. Eksempler (typisk tilfælde):
- Array: adgang O(1), indsæt/slet i midten O(n)
- Sammenkædet liste: adgang O(n), indsæt/slet ved node O(1)
- Hashtabel: søg/indsæt/slet O(1) gennemsnitligt, værre tilfælde O(n)
- Binært søgetræ: søg/indsæt/slet O(h) hvor h er træhøjden (i gennemsnit O(log n) for balancerede træer)
- Heap: indsættelse O(log n), fjern den højeste prioritet O(log n)
Praktiske eksempler og anvendelser
- Web- og databaser: hashtabeller til caches og indeks; B-træer i databaser for effektiv diskbaseret opslag.
- Søgning og ruteplanlægning: grafer og prioritetskøer (heap) i algoritmer som Dijkstra og A*.
- Tekstbehandling: tries og suffix-arrays til mønstergenkendelse og autokomplettering.
- Systemprogrammering: arrays og linked lists i kernen, heaps til planlægning af processer.
Konklusion
Datastrukturer er grundstenen i effektiv programmering: de definerer hvordan data opbevares og hvordan algoritmer kan operere på dem. Valget af datastruktur påvirker både ydeevne og kompleksiteten af en løsning. Derfor er forståelsen af de mest almindelige datastrukturer, deres fordele, ulemper og implementeringer et centralt element i programmeringen.
Grundlæggende datastrukturer
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.
Hvert knudepunkt peger på et andet knudepunkt.
Spørgsmål og svar
Spørgsmål: Hvad er en datastruktur?
A: En datastruktur er organiseringen og implementeringen af værdier og oplysninger i en computer, så de let kan forstås og bearbejdes.
Spørgsmål: Hvordan adskiller datastrukturer sig fra abstrakte datatyper?
Svar: Datastrukturer er implementeringer af abstrakte datatyper i en konkret og fysisk sammenhæng.
Spørgsmål: Hvordan bruger datastrukturer algoritmer?
Svar: Datastrukturer anvender algoritmer til at implementere abstrakte datatyper i en konkret sammenhæng.
Spørgsmål: Kan du give et eksempel på en datastruktur?
A: En linket liste er et eksempel på en datastruktur, som indeholder en "pointer" eller "reference" mellem hver enkelt informationsknude.
Spørgsmål: Hvad er formålet med, at datastrukturer optimeres til visse operationer?
Svar: Datastrukturer optimeres ofte til visse operationer for at forbedre kodens effektivitet og hastighed.
Spørgsmål: Hvorfor er det vigtigt at finde den bedste datastruktur i programmering?
Svar: Det er vigtigt at finde den bedste datastruktur inden for programmering, da det kan få stor betydning for kodens effektivitet og hastighed ved løsningen af et problem.
Spørgsmål: Hvad er definitionen af datastruktur i enkle vendinger?
A: Datastruktur er en systematisk måde at lagre data på i en computer, så det bliver lettere at forstå og arbejde med dem.
Søge