Kurt Nørmark ©
Institut for Datalogi, Aalborg Universitet

Sammendrag Forrige lektion Næste lektion Stikord Referencer Indhold

I denne lektion ser vi først på endnu flere muligheder for dataabstraktion. Vi har tidligere studeret arrays. I denne lektion gælder det structs i C, også kendt som records i andre programmeringssprog. Vi introducerer også ideerne om dataabstraktion.

Datastrukturer betegner data som er sammensat af forskellige primitive datatyper ved brug af arrays, records og pointere mellem disse

Henvisning Oversigt over typer i C

Datastrukturer Arrays: Tabeller med elementer af samme type, og tilgang via heltallige indekser Records/structures: Tabeller med felter af forskellige typer, og tilgang via feltnavne Kædede strukturer: Sammenkædning af records og arrays, og tilgang ved brug af pointere

Datastrukturer (2) Slide Indhold Stikord Referencer Lærebog

Vi illustrerer her eksempler på de tre forskellige former for datastrukturer, som blev introduceret på forrige side

Figur. En illustration af arrays, structures og sammenkædede structures.

En record er en tabel med navngivne felter, som kan være af forskellige datatyper En record gruppérer og sammensætter en mængde variable af forskellige typer i en logisk helhed I C kaldes records for structures

Figur. En skitse af en structure

Henvisning Tilsvarende introduktion til arrays

Structures/records (2) Slide Indhold Stikord Referencer Lærebog

Der er effektiv tilgang til felterne i en record, men der er typisk meget færre felter i en record end der er elementer i et array Prisen for 'elementer af forskellige typer' er at vi ikke kan 'beregne os frem til' et felt i tabellen.

Generelle egenskaber af records Elementerne/felterne i en record kan være af forskellige typer Elementerne er individuelt navngivne med feltnavne Elementerne i en record tilgås med dot notation: record.feltnavn Når en record er skabt og allokeret i lageret kan der ikke tilføjes eller fjernes felter Felterne i en record lagres konsekutivt, med afstættelse af passende plads til hvert felt

Henvisninger Tilsvarende introduktion til arrays Operator tabel for C

Structures/records (3) Slide Indhold Stikord Referencer Lærebog

Vi ser her på simple structures i C og på motivationen for at have structures/records i et programmeringssprog

Program: Motivation for structures - logisk sammenhørende, men sideordnede variable.

#include <stdio.h> typedef unsigned long CPR; int main(void) { char *baby_name = "Paul"; CPR baby_cpr = 2304031577; CPR baby_father_cpr = 1605571233; CPR baby_mother_cpr = 2412671234; char *mother_name = "Anna"; CPR mother_cpr = 2412671234; CPR mother_father_cpr = 1605376789; CPR mother_mother_cpr = 1201402468; char *father_name = "Frank"; CPR father_cpr = 1605571233; CPR father_father_cpr = 1111331357; CPR father_mother_cpr = 1212358642; return 0; }

Program: Introduktion af structures - sammenhørende data om en person.

#include <stdio.h> typedef unsigned long CPR; struct person { char *name; CPR cpr; CPR father; CPR mother; }; int main(void) { struct person baby = {"Paul", 2304031577, 1605571233, 2412671234}, mother = {"Anna", 2412671234, 1605376789, 1201402468}, father = {"Frank", 1605571233, 1111331357, 1212358642}; printf("%s's mother and father is %s and %s\n", baby.name, mother.name, father.name); return 0; }

Ved indførelse af structures/records får vi en bedre strukturering af data Alle data om en person kan håndteres som en helhed

Structures i C (1) Slide Indhold Stikord Referencer Lærebog

Syntax: En struct type specifikation

struct structure-tag{ type1 field1; type2 field2; ... typen fieldn; };

Terminologi: Structure tag name: Navnet efter struct. Member: Variablene, som udgør bestanddelene af strukturen Tilgang til et felt via en variabel, som indeholder en struct variabel.felt Tilgang til felt via en variabel som indeholder en pointer til en struct variabel->felt (*variabel).felt

Henvisninger Operator tabel for C Enumeration types

Structures i C (2) Slide Indhold Stikord Referencer Lærebog

Lovlige operationer structures: Assignment af structures af samme type:    struct1 = struct2 Members assignes parvis til hinanden Uddragning af addressen af en struct med & operatoren Tilgang til members med dot notation og    ->    operatoren Størrelsen af en struct Brug af sizeof operatoren En struct kan fylde mere en summen af felternes størrelse

Records kan ikke sammenlignes strukturelt med ==

Henvisning Strukturel lighed af strenge

Eksempel: Dato structure Slide Indhold Stikord Referencer Lærebog

En dato er en aggregering af dag, måned og år Det er muligt - redundant - at angive ugedag, ugenummer, mv.

Program: En struct for en dato.

struct date { weekday day_of_week; int day; int month; int year; }; typedef struct date date;

Program: Et dato program med en funktion, date-before, der vurderer om en dato kommer før en anden dato.

#include <stdio.h> enum weekday {sunday, monday, tuesday, wednesday, thursday, friday, saturday}; typedef enum weekday weekday; struct date { weekday day_of_week; int day; int month; int year; }; typedef struct date date; /* Is date d1 less than date d2 */ int date_before(date d1, date d2){ return (d1.year < d2.year) || (d1.year == d2.year && d1.month < d2.month) || (d1.year == d2.year && d1.month == d2.month && d1.day < d2.day); } int main(void) { date today = {thursday, 14, 4, 2005}; date tomorrow = {friday, 15, 4, 2005}; if (date_before(today, tomorrow)) printf("OK\n"); else printf("Problems\n"); return 0; }

Eksempel: Bog structure Slide Indhold Stikord Referencer Lærebog

En bog repræsenteres naturligt som en struct med titel felt, forfatter felt, forlags felt mv.

Program: Et eksempel på en struct for en bog.

struct book { char *title, *author, *publisher; int publishing_year; int university_text_book; }; typedef struct book book;

Program: Et program som kan lave og udskrive en bog.

#include <stdio.h> struct book { char *title, *author, *publisher; int publishing_year; int university_text_book; }; typedef struct book book; book make_book(char *title, char *author, char *publisher, int year, int text_book){ book result; result.title = title; result.author = author; result.publisher = publisher; result.publishing_year = year; result.university_text_book = text_book; return result; } void prnt_book(book b){ char *yes_or_no; yes_or_no = (b.university_text_book ? "yes" : "no"); printf("Title: %s\n" "Author: %s\n" "Publisher: %s\n" "Year: %4i\n" "University text book: %s\n\n", b.title, b.author, b.publisher, b.publishing_year, yes_or_no); } int main(void) { book b1, b2, b3; b1 = make_book("C by Disssection", "Kelley & Pohl", "Addison Wesley", 2001, 1); b2 = make_book("Pelle Erobreren", "Martin Andersen Nexoe", "Gyldendal", 1910, 0); b3 = b2; b3.title = "Ditte Menneskebarn"; b3.publishing_year = 1917; prnt_book(b1); prnt_book(b2); prnt_book(b3); return 0; }

Ovenstående program illustrerer bl.a. kopiering af en structure via et assignment

Structures ved parameteroverførsel Slide Indhold Stikord Referencer Lærebog

Structures behandles anderledes end arrays ved parameteroverførsel og værdireturnering fra en funktion

Structures: Kan overføres som en værdiparameter (call by value parameteroverførsel) Kan returneres fra en funktion Det er mere effektivt at overføre og tilbageføre pointere til structures Arrays: Overføres som en reference (call by reference parameteroverførsel) Returneres som en reference fra en funktion

Program: Et eksempel på overførsel og tilbageførsel af bøger per refererence - virker ikke.

/* Incorrect program - see books-ptr.c for a better version */ #include <stdio.h> struct book { char *title, *author, *publisher; int publishing_year; int university_text_book; }; typedef struct book book; book *make_book(char *title, char *author, char *publisher, int year, int text_book){ static book result; result.title = title; result.author = author; result.publisher = publisher; result.publishing_year = year; result.university_text_book = text_book; return &result; } void prnt_book(book *b){ char *yes_or_no; yes_or_no = (b->university_text_book ? "yes" : "no"); printf("Title: %s\n" "Author: %s\n" "Publisher: %s\n" "Year: %4i\n" "University text book: %s\n\n", b->title, b->author, b->publisher, b->publishing_year, yes_or_no); } int main(void) { book *b1, *b2; b1 = make_book("C by Disssection", "Kelley & Pohl", "Addison Wesley", 2001, 1); b2 = make_book("Pelle Eroberen", "Martin Andersen Nexoe", "Gyldendal", 1911, 0); prnt_book(b1); prnt_book(b2); return 0; }

Program: Et eksempel på overførsel og tilbageførsel af bøger per reference - OK.

#include <stdio.h> struct book { char *title, *author, *publisher; int publishing_year; int university_text_book; }; typedef struct book book; book *make_book(char *title, char *author, char *publisher, int year, int text_book){ book *result; result = (book*)malloc(sizeof(book)); result->title = title; result->author = author; result->publisher = publisher; result->publishing_year = year; result->university_text_book = text_book; return result; } void prnt_book(book *b){ char *yes_or_no; yes_or_no = (b->university_text_book ? "yes" : "no"); printf("Title: %s\n" "Author: %s\n" "Publisher: %s\n" "Year: %4i\n" "University text book: %s\n\n", b->title, b->author, b->publisher, b->publishing_year, yes_or_no); } int main(void) { book *b1, *b2; b1 = make_book("C by Disssection", "Kelley & Pohl", "Addison Wesley", 2001, 1); b2 = make_book("Pelle Eroberen", "Martin Andersen Nexoe", "Gyldendal", 1911, 0); prnt_book(b1); prnt_book(b2); return 0; }

Structures i structures Slide Indhold Stikord Referencer Lærebog

Det er muligt at indlejre structures i hinanden

Program: Basalt eksempel på structures i structures.

#include <stdio.h> struct point { int x; int y; }; struct rect { struct point p1; struct point p2; }; int main(void) { struct point pt1, pt2; struct rect r; pt1.x = 5; pt1.y = 6; pt2.x = 17; pt2.y = 18; r.p1 = pt1; r.p2 = pt2; return 0; }

Program: Et udvidet eksempel på structures i structures.

#include <stdio.h> struct point { int x; int y; }; struct rect { struct point p1; struct point p2; }; struct another_rect { struct { int x; int y; } p1; struct { int x; int y; } p2; }; int main(void) { struct point pt1, pt2; struct rect r; struct another_rect ar; pt1.x = 5; pt1.y = 6; pt2.x = 17; pt2.y = 18; r.p1 = pt1; r.p2 = pt2; ar.p1.x = 1; ar.p1.y = 2; ar.p2.x = 10; ar.p2.y = 12; ar.p1 = pt1; /* error: incompatible types */ ar.p2 = pt2; /* error: incompatible types */ return 0; }

Vi viser hvordan man kan lave et array af bøger

Program: Et array af bøger i funktionen main.

int main(void) { book shelf[MAX_BOOKS]; int i; shelf[0] = make_book("C by Disssection", "Kelley & Pohl", "Addison Wesley", 2001, 1); shelf[1] = make_book("Pelle Erobreren", "Martin Andersen Nexoe", "Gyldendal", 1910, 0); shelf[2] = shelf[1]; shelf[2].title = "Ditte Menneskebarn"; shelf[2].publishing_year = 1917; for(i = 0; i <=2; i++) prnt_book(shelf[i]); return 0; }

Program: Hele programmet.

#include <stdio.h> #define MAX_BOOKS 10 struct book { char *title, *author, *publisher; int publishing_year; int university_text_book; }; typedef struct book book; book make_book(char *title, char *author, char *publisher, int year, int text_book){ book result; result.title = title; result.author = author; result.publisher = publisher; result.publishing_year = year; result.university_text_book = text_book; return result; } void prnt_book(book b){ char *yes_or_no; yes_or_no = (b.university_text_book ? "yes" : "no"); printf("Title: %s\n" "Author: %s\n" "Publisher: %s\n" "Year: %4i\n" "University text book: %s\n\n", b.title, b.author, b.publisher, b.publishing_year, yes_or_no); } int main(void) { book shelf[MAX_BOOKS]; int i; shelf[0] = make_book("C by Disssection", "Kelley & Pohl", "Addison Wesley", 2001, 1); shelf[1] = make_book("Pelle Erobreren", "Martin Andersen Nexoe", "Gyldendal", 1910, 0); shelf[2] = shelf[1]; shelf[2].title = "Ditte Menneskebarn"; shelf[2].publishing_year = 1917; for(i = 0; i <=2; i++) prnt_book(shelf[i]); return 0; }

Arrays af datoer: Kalender Slide Indhold Stikord Referencer Lærebog

En kalender kan repræsenteres som en array af datoer

Program: Et program der laver en kalender - kun main funktionen.

int main(void) { date calendar[1000]; date first_date = {thursday, 14, 4, 2005}, last_date = {thursday, 13, 4, 2006}, current_date; int i = 0, j = 0; current_date = first_date; while (date_before(current_date, last_date)){ calendar[i] = current_date; current_date = tomorrow(current_date); i++; } for (j = 0; j < i; j++) prnt_date(calendar[j]); }

Henvisning Siden med date_before

Program: Hele kalenderprogrammet - bortset fra funktionen tomorrow.

#include <stdio.h> /* Date related types */ enum weekday {sunday, monday, tuesday, wednesday, thursday, friday, saturday}; typedef enum weekday weekday; struct date { weekday day_of_week; int day; int month; int year; }; typedef struct date date; /* Funktion prototypes */ int leapYear(int); int date_before(date, date); weekday next_day_of(weekday); void prnt_date(date); char *name_of_weekday(date); date tomorrow(date); int main(void) { date calendar[1000]; date first_date = {thursday, 14, 4, 2005}, last_date = {thursday, 13, 4, 2006}, current_date; int i = 0, j = 0; current_date = first_date; while (date_before(current_date, last_date)){ calendar[i] = current_date; current_date = tomorrow(current_date); i++; } for (j = 0; j < i; j++) prnt_date(calendar[j]); } /* Return the date after d */ date tomorrow(date d){ /* Implementation left as an exercise */ } /* Is y a leapyear */ int leapYear(int y){ int result; if (y % 400 == 0) result = 1; else if (y % 100 == 0) result = 0; else if (y % 4 == 0) result = 1; else result = 0; return result; } /* Is date d1 less than date d2 */ int date_before(date d1, date d2){ return (d1.year < d2.year) || (d1.year == d2.year && d1.month < d2.month) || (d1.year == d2.year && d1.month == d2.month && d1.day < d2.day); } weekday next_day_of(weekday d){ return (weekday) (((int) d + 1) % 7); } /* Print date d */ void prnt_date(date d){ printf("%9s %2i.%2i.%4i\n", name_of_weekday(d), d.day, d.month, d.year); } /* Return the name of the weekday of the date d */ char *name_of_weekday(date d){ char *result; switch (d.day_of_week) { case sunday: result = "Sunday"; break; case monday: result = "Monday"; break; case tuesday: result = "Tuesday"; break; case wednesday: result = "Wednesday"; break; case thursday: result = "Thursday"; break; case friday: result = "Friday"; break; case saturday: result = "Saturday"; break; } return result; }

Opgave 9.2. Funktionen tomorrow

Implementer funktionen tomorrow, som er illustreret på den omkringliggende side. Funktionen tager en dato som parameter, og den returnerer datoen på den efterfølgende dag. Hint: Lad i udgangspunktet resultatet være den overførte parameter, og gennemfør (pr. assignment til enkelte felter) de nødvendige ændringer.

Sammenkædede datastrukturer benytter typisk, som byggeklodser, dynamisk allokerede structures der sammenbindes af pointere

Begrebet self-referential structure: En 'self-referential structure' er en pointer repræsentation af en rekursiv datatype

Figur. En rekursiv struktur i forhold til en self-referential structure med pointere

I denne lektion vil vi begrænse os til at studere kædede lister (linked lists)

Henvisning Dynamisk allokering af lager

Sammenkædede datastrukturer (2) Slide Indhold Stikord Referencer Lærebog

Program: Structures for recursive and self referential structures.

/* Illegal recursive data structure */ struct first_list { int data; struct first_list next; }; /* Legal self-referential data structure */ struct second_list { int data; struct second_list *next; };

Kædede lister ala Lisp Slide Indhold Stikord Referencer Lærebog

Vi vil nu implementere kædede lister som de findes i Lisp og tilsvarende programmeringssprog

Program: Typen cons_cell.

struct cons_cell { void *data; struct cons_cell *next; }; typedef struct cons_cell cons_cell;

Program: Funktionerne cons, head og tail.

/* Returns a pointer to a new cons cell, which refers data and next via pointers*/ cons_cell *cons(void *data, cons_cell *next){ cons_cell *result; result = malloc(sizeof(cons_cell)); result->data = data; result->next = next; return result; } /* Return the head reference of the cons cell */ void *head(cons_cell *cell){ return cell->data; } /* Return the tail refererence f the cons cell */ cons_cell *tail(cons_cell *cell){ return cell->next; }

Program: Et eksempel på en liste af punkter håndteret i funktionen main.

int main(void) { cons_cell *points; point p1 = {1,2}, p2 = {3,4}, p3 = {5,6}; points = cons(&p1, cons(&p2, cons(&p3, NULL))); while (points != NULL) { prnt_point(*((point*)(head(points)))); points = tail(points); } return 0; }

Program: Typen point og funktionen prnt_point(p).

struct point {int x; int y;}; typedef struct point point; void prnt_point(point p){ printf("Point: %i, %i\n", p.x, p.y); }

I realiteten er en datastruktur, bygget af cons celler, et binært træ

Mutation af cons celler Slide Indhold Stikord Referencer Lærebog

Foruden funktionerne cons, head og tail laver vi nu også set_head og set_tail, som ændrer pladserne i en cons celle

Program: Funktionerne set_head og set_tail.

/* Change the data position of cell to new_head */ void set_head(cons_cell *cell, void *new_head){ cell->data = new_head; } /* Change the next position of cell to new_tail */ void set_tail(cons_cell *cell, cons_cell *new_tail){ cell->next = new_tail; }

Program: Et eksempel på mutationer i en liste af punkter.

int main(void) { cons_cell *points; point p1 = {1,2}, p2 = {3,4}, p3 = {5,6}, p4 = {6,7}; points = cons(&p1, cons(&p2, cons(&p3, NULL))); set_head(points,&p3); set_head(tail(points), &p4); while (points != NULL) { prnt_point(*((point*)(head(points)))); points = tail(points); } return 0; }

Funktioner på lister Slide Indhold Stikord Referencer Lærebog

Vi programmerer her et antal simple liste funktioner, som de findes Lisp

Program: Funktionen list_length.

/* Return the number of elements in list */ int list_length(cons_cell *list){ if (list == NULL) return 0; else return 1 + list_length(tail(list)); }

Program: Funktionen append.

/* Append list1 and list2. The elements in list2 are shared between the appended list and list2 */ cons_cell *append(cons_cell *list1, cons_cell *list2){ if (list1 == NULL) return list2; else return cons(head(list1), append(tail(list1),list2)); }

Program: Funktionen member.

/* Is el member of list as a data element? Comparisons are done by reference equality */ int member(void *el, cons_cell *list){ if (list == NULL) return 0; else if (head(list) == el) return 1; else return member(el, tail(list)); }

Program: Funktionen reverse.

/* Returned list in reverse order */ cons_cell *reverse(cons_cell *list){ if (list == NULL) return NULL; else return append(reverse(tail(list)), cons(head(list), NULL)); }

Program: Eksempler på anvendelse af ovenstående funktioner i en main funktion.

int main(void) { cons_cell *points, *more_points, *point_list, *pl; point p1 = {1,2}, p2 = {3,4}, p3 = {5,6}, p4 = {6,7}, p5 = {8,9}, p6 = {10,11}, p7 = {12,13}, p8 = {14,15}; points = cons(&p1, cons(&p2, cons(&p3, cons(&p4,NULL)))); more_points = cons(&p5, cons(&p6, cons(&p7, cons(&p8,NULL)))); printf("Number of points in the list points: %i\n", list_length(points)); point_list = append(points, more_points); pl = point_list; while (pl != NULL) { prnt_point(*((point*)(head(pl)))); pl = tail(pl); } if (member(&p6, points)) printf("p6 is member of points\n"); else printf("p6 is NOT member of points\n"); if (member(&p6, more_points)) printf("p6 is member of more_points\n"); else printf("p6 is NOT member of more_points\n"); if (member(&p6, point_list)) printf("p6 is member of point_list\n"); else printf("p6 is NOT member of point_list\n"); pl = reverse(points); while (pl != NULL) { prnt_point(*((point*)(head(pl)))); pl = tail(pl); } return 0; }

Bemærk at alle fire funktioner er rekursive

Indsættelse og sletning af elementer i en liste Slide Indhold Stikord Referencer Lærebog

Indsættelse og sletning af elementer i et array involverer flytning af mange elementer, og er derfor kostbar Indsættelse og sletning af elementer i en kædet liste er meget mere effektiv

Billedserie: Skridt i indsættelse af et element i en kædet liste.

Skridt i indsættelse af et element i en kædet liste.

Billed nr. 1. Et nyt element ønskes indsat på pilens plads

 

Billed nr. 2. Der er lavet et nyt kæde-objekt som skal kædes ind i listen efter den blå pil

 

Billed nr. 3. Vi fastholder en reference til elementet efter det nye element

 

Billed nr. 4. Der laves en reference til det nye element

 

Billed nr. 5. ... og videre fra det nye element til resten af listen, via det huskede element

 

Billedserie: Skridt i sletning af et element i fra kædet liste.

Skridt i sletning af et element i fra kædet liste.

Billed nr. 1. Data-objektet som er markeret med et kryds ønskes slettet

 

Billed nr. 2. Kæde-objektet markeret med den blå pil skal ændres for at udføre sletningen

 

Billed nr. 3. Data-objektet som er markeret med et kryds er fjernet fra den kædede liste. Kæde-objektet såvel som data-objektet kan nu fjernes af garbage collectoren

 

Billed nr. 4. Situationen efter at kæde- og data-objekt er fjernet af funktionen free

 

Program: Funktionen insert_after.

/* Insert new_element after the cons-cell ptr_list */ void insert_after(void *new_element, cons_cell *ptr_list){ cons_cell *new_cons_cell, *ptr_after; /* Make a new cons-cell around new_element */ new_cons_cell= cons(new_element,NULL); /* Remember pointer to cons-cell after ptr_list */ ptr_after = tail(ptr_list); /* Chain in the new_cons_cell */ set_tail(ptr_list, new_cons_cell); /* ... and connect to rest of list */ set_tail(new_cons_cell, ptr_after); }

Program: Funktionen delete_after.

/* Delete the element after ptr_list. Assume as a precondition that there exists an element after ptr_list */ void delete_after(cons_cell *ptr_list){ cons_cell *ptr_after, *ptr_dispose; /* cons-cell to delete later */ ptr_dispose = tail(ptr_list); /* The element to follow ptr_list */ ptr_after = tail(ptr_dispose); /* Mutate the tail of ptr_list */ set_tail(ptr_list, ptr_after); /* Free storage - only one cons-cell */ free(ptr_dispose); }

Program: Eksempler på anvendelse af insert_after og delete_after.

int main(void) { cons_cell *points, *pl; point p1 = {1,2}, p2 = {3,4}, p3 = {5,6}, p_new = {11,12}; points = cons(&p1, cons(&p2, cons(&p3, NULL))); insert_after(&p_new, tail(points)); pl = points; while (pl != NULL) { prnt_point(*((point*)(head(pl)))); pl = tail(pl); } printf("\n\n"); delete_after(points); pl = points; while (pl != NULL) { prnt_point(*((point*)(head(pl)))); pl = tail(pl); } return 0; }

Tilgang til elementerne i et array er meget effektiv Tilgang til elementerne i en kædet liste kræver gennemløb af kæden, og er derfor mere kostbar

Begrebet abstrakt datatype: En abstrakt datatype er en mængde af værdier og en tilhørende mængde af operationer på disse værdier

Værdierne i en abstrakt datatype kaldes ofte objekter. Dette er specielt tilfældet i det objekt-orienterede programmeringsparadigme, hvor ideen om abstrakte datatyper er helt central.

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

Tal som en abstrakt datatype Slide Indhold Stikord Referencer Lærebog

Vores normale omgang med tal afspejler en abstrakt forståelse

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

Når vi programmerer med abstrakte datatyper vil vi tilstræbe en tilsvarende forståelse for alle andre datatyper

En cons celle som en ADT Slide Indhold Stikord Referencer Lærebog

En cons celle kan opfattes som en abstrakt datatype

Operationer 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

Objekter af typen cons_cell benyttes som 'byggeklodser' i nye typer på et højere abstraktionsniveau

En liste som en ADT Slide Indhold Stikord Referencer Lærebog

Også en liste kan opfattes som en abstrakt datatype

Operationer på lister: 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...

En liste er mere end samlingen af elementerne Listen som så bør repræsenteres af en structure

Fra structures til classes Slide Indhold Stikord Referencer Lærebog

En klasse i et objekt-orienteret programmeringssprog er en structure ala C, hvor grænsefladens operationer er flyttet ind i strukturen

Dataabstraktion: 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

På vej fra imperativ programmering ala C til objekt-orienteret programmering ala Java

Kapitel 9: Datastrukturer og Dataabstraktion
Kursets hjemmeside     Forfatteren's hjemmeside     Om frembringelsen af disse sider     Forrige lektion (top)     Næste lektion (top)     Forrige lektion (bund)     Næste lektion (bund)     
Genereret: 7. Juli 2010, 15:12:45