Abstrakt datatype

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

I datalogi er en abstrakt datatype, eller abstrakt datastruktur en matematisk model for en bestemt klasse af strukturer som har indbyrdes lignende adfærd. I programmering kan begrebet bruges til at beskrive datastrukturer som grundlæggende modellerer det samme.

En abstrakt datatype kan indirekte defineres ud fra hvilke operationer man kan udføre på den og hvilke restriktioner disse operationer er underlagt. For eksempel kan en abstrakt datastruktur defineres ud fra to operationer: skub, som indsætter noget data i strukturen, og fjern, som udtager noget data i den. Med restriktionen at fjern altid udtager det stykke data som senest blev indsat, kan man sige at den abstrakte datatype svarer til en stak. Yderligere kunne man tilføje restriktionen at begge operationer skal tage den samme mængde tid uanset hvor stor stakken er.

Abstrakte datatyper er rent teoretiske modeller som bruges til at forsimple beskrivelsen af algoritmer, til at klassificere og evaluere datastrukturer og til formelt at beskrive typesystemer i programmeringssprog.

Abstrakte datatyper kan dog implementeres ved hjælp af specifikke datatyper eller datastrukturer eller beskrives i et formelt specifikationssprog. Abstrakte datatyper er ofte implementeret som moduler hvor modulets grænseflade deklarerer procedurer som svarer til den abstrakte datatypes operationer og med dokumentation som beskriver restriktioner.

Begrebet abstrakte datatyper er også relateret til begrebet dataabstraktion, som er vigtigt i objektorienteret og kontraktbaseret programmering inden for udvikling af software.

Definition[redigér | redigér wikikode]

Der findes ingen standardiseret måde at definere abstrakte datatyper, men en populær måde at inddele definitioner er mellem imperativ og funktionel definitionsstilart (se Programmeringsparadigme).

Imperative definitioner[redigér | redigér wikikode]

I imperative definitioner, som i større grad lægger sig op ad det imperative programmeringsparadigme, betragtes datastrukturer som mutérbare, hvilket vil sige at den samme mængde data kan have forskellige tilstande på forskellige tidspunkter. Nogle operationer kan ændre på datastrukturens tilstand mens andre blot aflæser den. For at understrege denne pointe kan man sige at instruktionerne udføres eller anvendes på strukturen, snarere end at de blot evalueres.

Abstrakte variable[redigér | redigér wikikode]

Imperative definitioner for abstrakte datatyper afhænger ofte af abstrakte variable, der kan betragtes som de simpleste abstrakte datatyper idet de har to operationer: gem, som tilskriver en værdi til en given abstrakt variabel, og hent, som svarer til værdien for en given abstrakt variabel, med den begrænsning at værdien for en abstrakt variabel altid er den seneste værdi den er tilskrevet.

I beskrivelser af algoritmer benyttes ofte syntaksen V ← x eller V := x når en værdi x gemmes i en abstrakt variabel V, og når værdien for en abstrakt variabel hentes nøjes man med at skrive V.

I beskrivelsen af nogle algoritmer benyttes kun en enkelt abstrakt datastruktur af en given type, for eksempel ved sortering, hvor operationsnavne som gem og hent således implicit altid refererer til denne ene struktur.

Funktionelle definitioner[redigér | redigér wikikode]

En anden måde at definere abstrakte datatyper, som i større grad lægger sig op ad det funktionelle programmeringsparadigme, er ved at betragte hver tilstand af sin abstrakte datastruktur som separate enheder, altså som immutérbare.

Her betragtes altså ikke instanser af data, men kun værdier som returneres af funktioner. Det funktionelle paradigme kan være nyttigt i beskrivelser af algoritmer som afhænger af rekursion, eller hvis man ønsker at bevise korrektheden af en algoritme ved matematisk induktion.