Abstrakt datatype - Abstract data type

For ikke at forveksle med algebraisk datatype .

Inden for datalogi er en abstrakt datatype ( ADT ) en matematisk model for datatyper . En abstrakt datatype defineres af dets adfærd ( semantik ) fra en brugers synspunkt , af dataene, specifikt hvad angår mulige værdier, mulige operationer på data af denne type og opførsel af disse operationer. Denne matematiske model står i kontrast til datastrukturer , som er konkrete repræsentationer af data, og er synspunktet for en implementer, ikke en bruger.

Formelt kan en ADT defineres som en "klasse af objekter, hvis logiske adfærd er defineret af et sæt værdier og et sæt operationer"; dette er analogt med en algebraisk struktur i matematik. Hvad der menes med "adfærd" varierer efter forfatter, idet de to hovedtyper af formelle specifikationer for adfærd er aksiomatiske (algebraiske) specifikationer og en abstrakt model; disse svarer til henholdsvis aksiomatisk semantik og operationel semantik i en abstrakt maskine . Nogle forfattere inkluderer også beregningskompleksiteten ("omkostninger"), både hvad angår tid (til computeroperationer) og plads (til repræsentation af værdier). I praksis er mange almindelige datatyper ikke ADT'er, da abstraktionen ikke er perfekt, og brugere skal være opmærksomme på spørgsmål som aritmetisk overløb , der skyldes repræsentationen. For eksempel lagres heltal ofte som værdier med fast bredde (32-bit eller 64-bit binære tal) og oplever dermed heltalsoverløb, hvis maksimumværdien overskrides.

ADT'er er et teoretisk koncept inden for datalogi, der bruges til design og analyse af algoritmer , datastrukturer og softwaresystemer og svarer ikke til specifikke funktioner i edb -sprog - almindelige edb -sprog understøtter ikke direkte formelt specificerede ADT'er. Imidlertid svarer forskellige sproglige funktioner til visse aspekter af ADT'er og forveksles let med ADT'er korrekt; disse omfatter abstrakte typer , uigennemsigtige datatyper , protokoller og design efter kontrakt . ADT'er blev først foreslået af Barbara Liskov og Stephen N. Zilles i 1974 som en del af udviklingen af CLU -sproget.

Eksempler

For eksempel er heltal en ADT, defineret som værdierne ..., −2, −1, 0, 1, 2, ..., og ved hjælp af addition, subtraktion, multiplikation og division, sammen med større end , mindre end osv., som opfører sig i henhold til velkendt matematik (med omhu for heltaldeling ), uafhængigt af hvordan heltalene repræsenteres af computeren. Eksplicit omfatter "adfærd" at adlyde forskellige aksiomer (associativitet og kommutativitet for addition osv.) Og forudsætninger for operationer (kan ikke dividere med nul). Typisk er heltal repræsenteret i en datastruktur som binære tal , oftest som tos komplement , men kan være binært kodet decimal eller i ens komplement , men brugeren abstraheres fra det konkrete valg af repræsentation og kan simpelthen bruge dataene som datatyper.

En ADT består ikke kun af operationer, men også af værdier for de underliggende data og af begrænsninger på operationerne. En "grænseflade" refererer typisk kun til operationerne og måske nogle af begrænsningerne for operationerne, især forudsætninger og efterbetingelser, men ikke andre begrænsninger, såsom forholdet mellem operationerne.

For eksempel kan en abstrakt stak , som er en sidst-i-først-ud-struktur, defineres af tre operationer push:, der indsætter et dataelement i stakken; pop, der fjerner et dataelement fra det; og peekeller top, der får adgang til et dataelement oven på stakken uden fjernelse. En abstrakt kø , som er en først-i-først-ud-struktur, vil også have tre operationer enqueue:, der indsætter et dataelement i køen; dequeue, der fjerner det første dataelement fra det; og front, der får adgang til og betjener det første dataelement i køen. Der ville ikke være nogen måde at differentiere disse to datatyper på, medmindre der indføres en matematisk begrænsning, der for en stak angiver, at hver pop altid returnerer det senest skubbede element, der endnu ikke er poppet. Når man analyserer effektiviteten af algoritmer, der bruger stakke, kan man også angive, at alle operationer tager samme tid, uanset hvor mange dataelementer der er blevet skubbet ind i stakken, og at stakken bruger en konstant mængde lagerplads for hvert element.

Introduktion

Abstrakte datatyper er rent teoretiske enheder, der bruges (blandt andet) til at forenkle beskrivelsen af ​​abstrakte algoritmer, til at klassificere og evaluere datastrukturer og formelt beskrive typesystemer for programmeringssprog. En ADT kan imidlertid implementeres af specifikke datatyper eller datastrukturer på mange måder og i mange programmeringssprog; eller beskrevet i et formelt specifikationssprog . ADT'er implementeres ofte som moduler : modulets grænseflade erklærer procedurer, der svarer til ADT -operationerne, nogle gange med kommentarer, der beskriver begrænsningerne. Denne informations skjulte strategi gør det muligt at ændre implementeringen af ​​modulet uden at forstyrre klientprogrammerne .

Udtrykket abstrakt datatype kan også betragtes som en generaliseret tilgang til en række algebraiske strukturer , såsom gitter, grupper og ringe. Begrebet abstrakte datatyper er relateret til begrebet datainstraktion , der er vigtigt i objektorienteret programmering og design ved kontraktmetoder til softwareudvikling .

Definere en abstrakt datatype

En abstrakt datatype er defineret som en matematisk model af dataobjekterne, der udgør en datatype, samt de funktioner, der fungerer på disse objekter. Der er ingen standardkonventioner for at definere dem. Der kan trækkes en bred opdeling mellem "imperativ" og "funktionel" definition.

Imperativ stil definition

I filosofien om tvingende programmeringssprog opfattes en abstrakt datastruktur som en enhed, der kan ændres - hvilket betyder, at den kan være i forskellige tilstande på forskellige tidspunkter. Nogle operationer kan ændre tilstanden for ADT; derfor er rækkefølgen, hvor operationer evalueres, vigtig, og den samme operation på de samme enheder kan have forskellige effekter, hvis den udføres på forskellige tidspunkter - ligesom instruktioner fra en computer eller kommandoer og procedurer for et imperativt sprog. For at understrege denne opfattelse er det sædvanligt at sige, at operationerne udføres eller anvendes i stedet for at blive evalueret . Den tvingende stil bruges ofte, når man beskriver abstrakte algoritmer. (Se The Art of Computer Programming af Donald Knuth for flere detaljer)

Abstrakt variabel

Definitioner af imperativ stil af ADT afhænger ofte af begrebet en abstrakt variabel , som kan betragtes som den enkleste ikke-trivielle ADT. En abstrakt variabel V er en foranderlig enhed, der indrømmer to operationer:

  • store( V , x ) hvor x er en værdi af uspecificeret karakter;
  • fetch( V ), der giver en værdi,

med den begrænsning, der

  • fetch( V ) altid returnerer værdien x anvendt i den seneste store( V , x ) operation på den samme variabel V .

Som i så mange programmeringssprog skrives operationen store( V , x ) ofte V ← x (eller en lignende notation), og fetch( V ) er underforstået, når en variabel V bruges i en kontekst, hvor der kræves en værdi. Således forstås for eksempel V ← V + 1 almindeligt at være en stenografi for store( V , fetch( V ) + 1).

I denne definition, er det implicit, at lagre en værdi i en variabel U har ingen effekt på tilstanden af en distinkt variabel V . For at gøre denne antagelse eksplicit, kunne man tilføje den begrænsning, at

  • hvis U og V er forskellige variabler, sekvensen { store( U , x ); store( V , y )} svarer til { store( V , y ); store( U , x )}.

Mere generelt antager ADT -definitioner ofte, at enhver handling, der ændrer tilstanden for en ADT -forekomst, ikke har nogen effekt på tilstanden for en anden instans (herunder andre forekomster af den samme ADT) - medmindre ADT -aksiomerne indebærer, at de to instanser er forbundet ( aliased ) i den forstand. For eksempel, når en udvidelse af definitionen af en abstrakt variabel til at omfatte abstrakte optegnelser , den operation, vælger et felt fra en rekord variabel R skal give en variabel V , der er alias for den del af R .

Definitionen af en abstrakt variabel V kan også begrænse de lagrede værdier x for medlemmer af et specifikt sæt X , kaldet området eller typen af V . Som i programmeringssprog kan sådanne begrænsninger forenkle beskrivelsen og analysen af ​​algoritmer og forbedre deres læsbarhed.

Bemærk, at denne definition ikke indebærer noget om resultatet af evalueringen af fetch( V ), når V er un-initialiseret , der er, før der foretages storeoperation på V . En algoritme, der gør det, betragtes normalt som ugyldig, fordi dens virkning ikke er defineret. (Der er dog nogle vigtige algoritmer, hvis effektivitet stærkt afhænger af antagelsen om, at en sådan fetcher lovlig, og returnerer en vilkårlig værdi i variabelens område.)

Oprettelse af forekomst

Nogle algoritmer skal oprette nye forekomster af nogle ADT (f.eks. Nye variabler eller nye stakke). For at beskrive sådanne algoritmer inkluderer man normalt i ADT -definitionen en create() operation, der giver en forekomst af ADT, normalt med aksiomer svarende til

  • resultatet af create() adskiller sig fra enhver instans, der bruges af algoritmen.

Dette aksiom kan styrkes til også at udelukke delvis aliasing med andre tilfælde. På den anden side tillader dette aksiom stadig implementeringer af create() at give en tidligere oprettet instans, der er blevet utilgængelig for programmet.

Eksempel: abstrakt stak (tvingende)

Som et andet eksempel kunne en imperativ-stil definition af en abstrakt stak angive, at tilstanden af ​​en stak S kun kan ændres af operationerne

  • push( S , x ), hvor x er en værdi af uspecificeret karakter;
  • pop( S ), der giver en værdi som følge heraf,

med den begrænsning, der

  • For enhver værdi x og enhver abstrakt variabel V , operationssekvensen { push( S , x ); V ← pop( S )} svarer til V ← x .

Da opgaven V ← x per definition ikke kan ændre tilstanden S , indebærer denne betingelse, at V ← pop( S ) gendanner S til den tilstand, den havde før push( S , x ). Af denne betingelse og af egenskaberne af abstrakte variabler følger det f.eks., At sekvensen

{ push( S , x ); push( S , y ); U ← pop( S ); push( S , z ); V ← pop( S ); W ← pop( S )}

hvor x , y og z er alle værdier, og U , V , W er parvise forskellige variabler, svarer til

{ U ← y ; V ← z ; W ← x }

Her antages det implicit, at operationer på en stakforekomst ikke ændrer tilstanden for nogen anden ADT -forekomst, herunder andre stakke; det er,

  • For alle værdier x , y og eventuelle forskellige stakke S og T er sekvensen { push( S , x ); push( T , y )} svarer til { push( T , y ); push( S , x )}.

En abstrakt stakdefinition indeholder normalt også en boolsk -værdiansat funktion empty( S ) og en create() operation, der returnerer en stakforekomst , med aksiomer svarende til

  • create() ≠ S for enhver tidligere stak S (en nyoprettet stak adskiller sig fra alle tidligere stakke);
  • empty( create()) (en nyoprettet stak er tom);
  • not empty( push( S , x )) (skubber noget ind i en stak gør det ikke tomt).

Enkeltinstansstil

Nogle gange defineres en ADT som om, at der kun eksisterede én forekomst af den under udførelsen af ​​algoritmen, og alle operationer blev anvendt på den forekomst, som ikke eksplicit er noteret. For eksempel kunne den abstrakte stak ovenfor være blevet defineret med operationer push( x ) og pop(), der fungerer på den eneste eksisterende stak. ADT -definitioner i denne stil kan let omskrives til at indrømme flere sameksisterende forekomster af ADT ved at tilføje en eksplicit forekomstparameter (som S i det foregående eksempel) til hver operation, der bruger eller ændrer den implicitte forekomst.

På den anden side kan nogle ADT'er ikke defineres meningsfuldt uden at antage flere instanser. Dette er tilfældet, når en enkelt operation tager to forskellige forekomster af ADT som parametre. For eksempel kan du overveje at forstørre definitionen af ​​den abstrakte stak med en operation compare( S , T ), der kontrollerer, om stablerne S og T indeholder de samme emner i den samme rækkefølge.

Funktionel stil definition

En anden måde at definere en ADT, tættere på ånden i funktionel programmering , er at betragte hver tilstand i strukturen som en separat enhed. I denne opfattelse modelleres enhver handling, der ændrer ADT, som en matematisk funktion, der tager den gamle tilstand som et argument og returnerer den nye tilstand som en del af resultatet. I modsætning til de tvingende operationer har disse funktioner ingen bivirkninger . Derfor er rækkefølgen, hvor de evalueres, uvæsentlig, og den samme operation, der anvendes på de samme argumenter (inklusive de samme inputtilstande), vil altid returnere de samme resultater (og outputtilstande).

I den funktionelle opfattelse er der især ingen måde (eller behov) at definere en "abstrakt variabel" med semantikken i tvingende variabler (nemlig med fetchog storeoperationer). I stedet for at gemme værdier i variabler, sender man dem som argumenter til funktioner.

Eksempel: abstrakt stak (funktionel)

For eksempel kan en komplet definition i funktionel stil af en abstrakt stak bruge de tre operationer:

  • push: tager en stakstilstand og en vilkårlig værdi, returnerer en staktilstand;
  • top: tager en stakstilstand, returnerer en værdi;
  • pop: tager en stakstilstand, returnerer en stakstilstand.

I en definition i funktionel stil er der ikke behov for en createoperation. Der er faktisk ingen forestilling om "stack -instans". Stacktilstandene kan betragtes som værende potentielle tilstande i en enkelt stakstruktur, og to-stakstilstande, der indeholder de samme værdier i samme rækkefølge, betragtes som identiske tilstande. Denne opfattelse afspejler faktisk adfærden for nogle konkrete implementeringer, såsom sammenkædede lister med hash -ulemper .

I stedet for create() kan en funktionel stildefinition af en abstrakt stak antage eksistensen af ​​en særlig stakstilstand, den tomme stak , betegnet med et specielt symbol som Λ eller "()"; eller definer en bottom() operation, der ikke tager argumenter og returnerer denne særlige stakstilstand. Bemærk, at aksiomerne indebærer det

  • push(Λ, x ) ≠ Λ.

I en funktionel stildefinition af en stak behøver man ikke et emptyprædikat: i stedet kan man teste, om en stak er tom ved at teste, om den er lig med Λ.

Bemærk, at disse aksiomer ikke definerer effekten af top( r ) eller pop( r ), medmindre s er en stakstilstand, der returneres af a push. Da pushstakken ikke er tom, er disse to operationer udefinerede (derfor ugyldige), når s = Λ. På den anden side indebærer aksiomerne (og manglen på bivirkninger) at push( s , x ) = push( t , y ) hvis og kun hvis x = y og s = t .

Som i nogle andre grene af matematik er det sædvanligt også at antage, at stabelstaterne kun er dem, hvis eksistens kan bevises ud fra aksiomerne i et begrænset antal trin. I eksemplet ovenfor med abstrakt stak betyder denne regel, at hver stak er en endelig værdisekvens, der bliver den tomme stak (Λ) efter et begrænset antal pops. I sig selv udelukker aksiomerne ovenfor ikke eksistensen af ​​uendelige stakke (der kan popredigeres for altid, hver gang der giver en anden tilstand) eller cirkulære stakke (der vender tilbage til den samme tilstand efter et begrænset antal pops). Især udelukker de ikke tilstande s sådan at pop( s ) = s eller push( s , x ) = s for nogle x . Da man imidlertid ikke kan opnå sådanne staktilstande med de givne operationer, antages de "ikke at eksistere".

Om man skal inkludere kompleksitet

Bortset fra adfærden med hensyn til aksiomer er det også muligt at inkludere deres algoritmiske kompleksitet i definitionen af ​​en ADT -operation . Alexander Stepanov , designer af C ++ Standard Template Library , inkluderede kompleksitetsgarantier i STL -specifikationen og argumenterede:

Grunden til at indføre begrebet abstrakte datatyper var at tillade udskiftelige softwaremoduler. Du kan ikke have udskiftelige moduler, medmindre disse moduler har samme kompleksitetsadfærd. Hvis jeg erstatter et modul med et andet modul med den samme funktionelle adfærd, men med forskellige kompromiser, vil brugeren af ​​denne kode blive ubehageligt overrasket. Jeg kunne fortælle ham alt, hvad jeg kan lide om dataabstraktion, og han ville stadig ikke bruge koden. Kompleksitetskrav skal være en del af grænsefladen.

-  Alexander Stepanov

Fordele ved abstrakt datatypning

Indkapsling

Abstraktion giver et løfte om, at enhver implementering af ADT har visse egenskaber og evner; at kende disse er alt, hvad der kræves for at gøre brug af et ADT -objekt.

Lokalisering af forandringer

Kode, der bruger et ADT -objekt, behøver ikke at redigeres, hvis implementeringen af ​​ADT ændres. Da eventuelle ændringer i implementeringen stadig skal være i overensstemmelse med grænsefladen, og da kode ved hjælp af et ADT -objekt kun kan referere til egenskaber og evner, der er angivet i grænsefladen, kan der foretages ændringer i implementeringen uden at kræve ændringer i kode, hvor ADT bruges .

Fleksibilitet

Forskellige implementeringer af ADT, der har alle de samme egenskaber og evner, er ækvivalente og kan bruges noget ombytteligt i kode, der bruger ADT. Dette giver en stor fleksibilitet ved brug af ADT -objekter i forskellige situationer. F.eks. Kan forskellige implementeringer af ADT være mere effektive i forskellige situationer; det er muligt at bruge hver i den situation, hvor de foretrækkes, hvilket øger den samlede effektivitet.

Typiske operationer

Nogle operationer, der ofte er angivet for ADT'er (muligvis under andre navne) er

  • compare( s , t ), der tester, om to instansers tilstande er ækvivalente i en eller anden forstand;
  • hash( s ), der beregner en eller anden standard hash -funktion ud fra instansens tilstand;
  • print( s ) eller show( s ), der frembringer en menneskelæselig fremstilling af instansens tilstand.

I ADT-definitioner i imperativ stil finder man ofte også

  • create(), der giver en ny forekomst af ADT;
  • initialize( S ), som forbereder en nyoprettet instans s for yderligere operationer, eller nulstiller det til nogle "oprindelige tilstand";
  • copy( s , t ), der sætter instans s i en tilstand, der svarer til t ;
  • clone( t ), der udfører s ← create(), copy( s , t ) og returnerer s ;
  • free( s ) eller destroy( s ), der genvinder hukommelsen og andre ressourcer, der bruges af s .

Den freeoperation er normalt ikke relevant eller meningsfuld, da ADT'er er teoretiske enheder, der ikke "brug hukommelse". Det kan dog være nødvendigt, når man skal analysere lageret, der bruges af en algoritme, der bruger ADT. I så fald har man brug for yderligere aksiomer, der angiver, hvor meget hukommelse hver ADT -forekomst bruger, som en funktion af dens tilstand, og hvor meget af den, der returneres til puljen af free.

Eksempler

Nogle almindelige ADT'er, som har vist sig nyttige i en lang række applikationer, er

Hver af disse ADT'er kan defineres på mange måder og varianter, ikke nødvendigvis ækvivalente. For eksempel kan en abstrakt stak muligvis have en countoperation, der fortæller, hvor mange elementer der er blevet skubbet og endnu ikke er sprunget. Dette valg gør en forskel ikke kun for sine kunder, men også for implementeringen.

Abstrakt grafisk datatype

En udvidelse af ADT til computergrafik blev foreslået i 1979: en abstrakt grafisk datatype (AGDT). Det blev introduceret af Nadia Magnenat Thalmann og Daniel Thalmann . AGDT'er giver fordelene ved ADT'er med faciliteter til at bygge grafiske objekter på en struktureret måde.

Implementering

Yderligere oplysninger: Uigennemsigtig datatype

Implementering af en ADT betyder, at der tilvejebringes en procedure eller funktion for hver abstrakt operation. ADT -instanserne repræsenteres af en konkret datastruktur, der manipuleres med disse procedurer i henhold til ADT's specifikationer.

Normalt er der mange måder at implementere den samme ADT ved hjælp af flere forskellige konkrete datastrukturer. Således kan for eksempel en abstrakt stak implementeres af en sammenkædet liste eller af en matrix .

For at forhindre klienter i at afhænge af implementeringen pakkes en ADT ofte som en uigennemsigtig datatype i et eller flere moduler , hvis grænseflade kun indeholder signaturen (antal og typer af parametre og resultater) af operationerne. Implementeringen af ​​modulet - nemlig procedurernes legemer og den anvendte konkrete datastruktur - kan derefter skjules for de fleste klienter i modulet. Dette gør det muligt at ændre implementeringen uden at påvirke klienterne. Hvis implementeringen afsløres, er den i stedet kendt som en gennemsigtig datatype.

Ved implementering af en ADT repræsenteres hver forekomst (i definitioner i imperativ stil) eller hver tilstand (i definitioner i funktionel stil) normalt med et håndtag af en eller anden art.

Moderne objektorienterede sprog, såsom C ++ og Java , understøtter en form for abstrakte datatyper. Når en klasse bruges som en type, er det en abstrakt type, der refererer til en skjult repræsentation. I denne model implementeres en ADT typisk som en klasse , og hver forekomst af ADT er normalt et objekt i denne klasse. Modulets grænseflade erklærer typisk konstruktørerne som almindelige procedurer og de fleste andre ADT -operationer som metoder i denne klasse. En sådan tilgang indkapsler imidlertid ikke let flere repræsentationsvarianter, der findes i en ADT. Det kan også undergrave udvidelsen af ​​objektorienterede programmer. I et rent objektorienteret program, der bruger grænseflader som typer, refererer typer til adfærd, ikke repræsentationer.

Eksempel: implementering af den abstrakte stak

Som et eksempel er her en implementering af den abstrakte stak ovenfor i C -programmeringssproget .

Grænseflade i imperativ stil

En grænseflade i tvingende stil kan være: 

typedef struct stack_Rep stack_Rep;       // type: stack instance representation (opaque record)
typedef stack_Rep* stack_T;               // type: handle to a stack instance (opaque pointer)
typedef void* stack_Item;                 // type: value stored in stack instance (arbitrary address)

stack_T stack_create(void);               // creates a new empty stack instance
void stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack
stack_Item stack_pop(stack_T s);          // removes the top item from the stack and returns it
bool stack_empty(stack_T s);              // checks whether stack is empty

Denne grænseflade kan bruges på følgende måde: 

#include <stack.h>          // includes the stack interface

stack_T s = stack_create(); // creates a new empty stack instance
int x = 17;
stack_push(s, &x);          // adds the address of x at the top of the stack
void* y = stack_pop(s);     // removes the address of x from the stack and returns it
if (stack_empty(s)) { }     // does something if stack is empty

Denne grænseflade kan implementeres på mange måder. Implementeringen kan være vilkårligt ineffektiv, da den formelle definition af ADT ovenfor ikke angiver, hvor meget plads stakken må bruge, og heller ikke hvor lang tid hver operation skal tage. Det angiver heller ikke, om stakstatus s fortsat eksisterer efter et opkald x ← pop( s ).

I praksis bør den formelle definition angive, at rummet er proportionelt med antallet af elementer, der skubbes og endnu ikke er poppet; og at hver af ovenstående operationer skal afslutte på en konstant tid uafhængigt af dette nummer. For at overholde disse yderligere specifikationer kan implementeringen bruge en sammenkædet liste eller en matrix (med dynamisk størrelse) sammen med to heltal (et varetælling og matrixstørrelse).

Interface i funktionel stil

Funktionelle ADT-definitioner er mere passende til funktionelle programmeringssprog og omvendt. Imidlertid kan man tilbyde en grænseflade i funktionel stil, selv i et bydende sprog som C.For eksempel: 

typedef struct stack_Rep stack_Rep;          // type: stack state representation (opaque record)
typedef stack_Rep* stack_T;                  // type: handle to a stack state (opaque pointer)
typedef void* stack_Item;                    // type: value of a stack state (arbitrary address)

stack_T stack_empty(void);                   // returns the empty stack state
stack_T stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack state and returns the resulting stack state
stack_T stack_pop(stack_T s);                // removes the top item from the stack state and returns the resulting stack state
stack_Item stack_top(stack_T s);             // returns the top item of the stack state

ADT -biblioteker

Mange moderne programmeringssprog, såsom C ++ og Java, leveres med standardbiblioteker, der implementerer flere almindelige ADT'er, f.eks. Dem, der er anført ovenfor.

Indbyggede abstrakte datatyper

Specifikationen af ​​nogle programmeringssprog er bevidst vag om repræsentationen af ​​visse indbyggede datatyper og definerer kun de operationer, der kan udføres på dem. Derfor kan disse typer ses som "indbyggede ADT'er". Eksempler er arrays på mange scriptsprog, såsom Awk , Lua og Perl , som kan betragtes som en implementering af den abstrakte liste.

Se også

Noter

Citater

Referencer

Yderligere læsning

eksterne links