Abstrakte datatyper er helt naturligt en kontrast til det vi kunne kalde "konkrete eller simple datatyper". Som diskuteret i afsnit 17.1 er en type en mængde af værdier med fælles egenskaber. Eksempelvis er heltal, int i C, en type. Værdierne er 0, 1, -1, 2, -2, etc. De fælles egenskaber er først og fremmest alle de velkendte operatorer, som virker på tallene.

Vi vil nu set på et udvidet typebegreb, hvor de operationelle egenskaber - funktionerne som virker på værdierne - er i fokus.

42.1 Abstrakte datatyper 42.4 En liste som en ADT 42.2 Tal som en abstrakt datatype 42.5 Fra structures til classes 42.3 En cons celle som en ADT

 

42.1.  Abstrakte datatyper
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Ud over at være en mængde af værdier er en abstrakt datatype også karakteriseret af af de operationer, som kan anvendes på værdierne.

Abstrakte datatyper er centrale og velunderstøttede i objekt-orienterede programmeringssprog. I mere enkle sprog, herunder C, håndterer vi udelukkende abstrakte datatype med brug af programmeringsdisciplin. Med dette mener vi, at vi skal programmere på en bestemt måde, med brug af bestemte mønstre og bestemte fremgangsmåder. Ofte er structures et centralt element i en sådan disciplin. Vi opsummerer her i punktform programmering med abstrakte datatyper i C.

Sammenhørende data indkapsles i en struct Der defineres en samling af funktioner der 'arbejder på' strukturen Disse funktioner udgør grænsefladen Funktioner uden for den abstrakte datatype må ikke have kendskab til detaljer om data i strukturen Dette kendskab må kun udnyttes internt i funktionerne, som udgør typens grænseflade Der laves en funktion der skaber og initialiserer et objekt af typen Dette er en konstruktør

Vi vil nu se nærmere på abstrakte datatyper i C. Specielt vil vi se hvorledes nogle af liste eksemplerne fra kapitel 41 kan fortolkes som abstrakte datatyper.

42.2.  Tal som en abstrakt datatype
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Vi vil i dette afsnit argumentere for heltal, som vi omgås disse værdier i programmeringssammenhæng, kan opfattes som en abstrakt datatype. I introduktionen til kapitel 42 argumenterede for at heltal er en type. Vores centrale observation i dette afsnit er, at vi næsten udelukkende arbejder med heltal gennem en (abstrakt) notation og en mængde af aritmetiske funktioner. Vi er kun sjældent bevidste om den konkrete binære repræsentation af heltal, som diskuteret i afsnit 16.5.

I illustrationen herunder viser vi til venstre den konkrete binære repræsentation af heltal. Til højre skitserer vi heltal i decimal notation og mængden af operationer, noteret som f.eks. +, - og *. Bemærk at den decimale notation i sig selv er forholdsvis abstrakt i forhold til den binære notation.

Figur 42.1    En konkret og en abstrakt forståelse af heltal

Pointen er således at vi ofte ønsker at eftergøre observationerne om heltal i vore egne datatyper. I en nødeskal ønsker vi altså at introducere værdier, som bearbejdes af et antal funktioner, som vi programmerer, og som vi anvender når en type skal nyttiggøres. Kendskabet til detaljerne i værdierne skal dog begrænses så meget som muligt.

I de næste afsnit vil vi give eksempler på den tankegang, som blev udtrykt for heltal i dette afsnit.

42.3.  En cons celle som en ADT
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Vi introducerede cons celler som byggeklodser for kædede lister i afsnit 41.3.

En cons celle er en relativ simpel struktur, der er repræsenteret som en struct i C. En cons celle er repræsenteret som sammensætningen (aggregeringen) af to pointere, data pointeren og next pointeren. En værdi i typen er altså en sådan to-komponent struktur. Vi ønsker nu at indkapsle denne viden i en abstrakt datatype. Vi konstruerer en cons celle med funktionen cons. Vi kan tænke på denne funktion som en konstruktør. Vi kan aflæse hver af to to pointere med en funktion. Her kalder vi disse funktioner for hhv. head og tail. Vi kan endvidere ændre data og next værdierne af en cons cellen med set_head og set_tail.

Vi opsummerer her operationerne på cons celler.

cons, der spiller rollen som konstruktør head og tail som tilgår bestanddelene set_head og set_tail som muterer bestanddelene

I næste afsnit tager vi et trin opad abstraktionsstigen. I stedet for at se på cons celler ser vi nu på typen bestående af listeværdier og de naturlige operationer på lister.

42.4.  En liste som en ADT
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Vi opfatter nu hele lister som værdier i en abstrakt datatype. Operationerne på lister kan f.eks. være følgende:

En funktion/konstruktør der laver en tom liste Funktioner der indsætter og sletter et element Udvidede versioner af insert_after og delete_after, som også håndterer tomme lister fornuftigt Funktioner ala list_length, append, member og reverse Mange andre...

Det kan måske være vanskeligt helt at forstå essensen af ovenstående observation. Som det fremgår af afsnit 41.6 er det forbundet med specielle udfordringer at indsætte og slette elementer i begyndelsen (forenden) af en liste. Dette skyldes i bund og grund at der kan være flere referencer til det første element i en liste. Hvis vi derimod har sikkerhed for, at der kun er én reference til det første element i en liste, nemlig fra et særligt listeobjekt (som repræsenterer listen som helhed) er problemet løst.

42.5.  Fra structures til classes
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Diskussionen om abstrakte datatyper, og eksemplerne vi har studeret i de forrige afsnit, leder frem mod de programmeringssproglige grundbegreber i objekt-orienteret programmering. Mest håndfast glider structure begrebet (C structs) over i klassebegrebet. Vi vil ganske kort gøre nogle få observationer om overgangen fra structures til klasser.

Følgende punkter karakteriser dataabstraktion på en lidt mere fyldig måde end i afsnit 42.1.

Logisk sammenhørende værdier grupperes og indkapsles på passende vis Sådanne værdier kaldes ofte for objekter Operationer på objekterne knyttes tæt til disse Om muligt flytter operationerne ind i datatypen, hvilket bringer os fra records til klasser Synlighed af objektets egenskaber (data og operationer) afklares Det er attraktivt at flest mulige egenskaber holdes private Objektets grænseflade til andre objekter udarbejdes omhyggeligt Grænsefladen udgøres af en udvalgt mængde af operationer

Der er mange måder er lære om objekt-orienteret programmering. Lad mig nævne at jeg har skrevet et undervisningsmateriale om objekt-orienteret programmering i Java - i samme stil som indeværende materiale.