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 tilgang ved brug af pointere

Datastrukturer (2) Slide Indhold Stikord Referencer

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 structure er en tabel med navngivne felter, som kan være af forskellige datatyper En structure indkapsler og aggregerer en mængde variable af forskellige typer En structure definerer en ny type

Figur. En skitse af en structure

Structures (2) Slide Indhold Stikord Referencer

Der er effektiv tilgang til felterne i en structure, men der er typisk meget færre felter i en structure end der er elementer i et array Hvert felt i en struct skal navngives af programmøren

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

Henvisninger Tilsvarende introduktion til arrays Operator tabel for C

At 'elementer kan være af forskellige typer' medfører at vi ikke kan 'beregne os frem til' et felt i tabellen

Structures (3) Slide Indhold Stikord Referencer

Vi ser her på simple structures i C og på motivationen for at have structures 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; printf("%s's mother and father is %s and %s\n", baby_name, mother_name, father_name); return 0; }

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

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

Program: Introduktion af structures - med structure initializers.

#include <stdio.h> typedef unsigned long int CPR; struct person { char *name; CPR cpr, father_cpr, mother_cpr; }; 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; }

Med introduktionen af structures 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

Syntax: En struct type specifikation

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

Terminologi: Structure tag name: Navnet efter struct. Member: Felterne som udgør bestanddelene af strukturen Tilgang til et felt via en variabel, som indeholder en struct variabel.felt Direkte komponent selektion Tilgang til felt via en variabel som indeholder en pointer til en struct variabel->felt    der er det samme som    (*variabel).felt Indirekte komponent selektion

Henvisninger Operator tabel for C Enumeration types

Structures i C (2) Slide Indhold Stikord Referencer

Structs er data af første klasse data i C

Henvisning Tilsvarende diskussion af arrays

Første klasses egenskaberne Structs kan overføres som værdi-parameter, returneres via return, og organiseres frit i datastrukturer 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: Direkte komponent selektion: . Indirekte komponent selektion: -> Størrelsen af en struct Brug af sizeof operatoren En struct kan fylde mere en summen af felternes størrelse

Henvisning Strukturel lighed af strenge

Structures kan ikke sammenlignes strukturelt med ==

Eksempel: Dato structure Slide Indhold Stikord Referencer

En dato er en aggregering af dag, måned og år Det er også muligt - redundant - at have felter for 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 = {tuesday, 8, 11, 2011}; date tomorrow = {wednesday, 9, 11, 2011}; if (date_before(today, tomorrow)) printf("OK\n"); else printf("Problems\n"); return 0; }

Opgave 12.2. Funktionen date_compare

På den tilknyttede slide har vi programmeret funktionen date_before. Den returnerer en boolsk værdi: Hvorvidt datoen d1 kommer forud for d2. Programer på basis af date_before funktionen date_compare, som sammenligner to datoer efter de gængse konventioner i C (som vi bl.a. har studeret i forbindelse med sammenligningen af to tekststrenge). Funktionen date_compare skal altså kunne returnere enten et negativt, positivt eller nul resultat.

Eksempel: Bog structure Slide Indhold Stikord Referencer

En bog repræsenteres naturligt som en struct med felter for titel, forfatter, forlag, 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("Problem Solving and Program Design in C", "Hanly & Koffman", "Pearson", 2010, 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); printf("Sizeof(b1) = %d bytes\n", sizeof(book)); /* 20 bytes */ return 0; }

Ovenstående program illustrerer bl.a. kopiering af en structure via et assignment Tekststrenge kopieres dog via deres pointere - tegn arrayet kopieres ikke

Program: En variation der allokerer de tre tekststrenge inde i struct book.

#include <stdio.h> #include <string.h> #define TITLE_MAX 50 #define AUTHOR_MAX 40 #define PUBLISHER_MAX 20 struct book { char title[TITLE_MAX], author[AUTHOR_MAX], publisher[PUBLISHER_MAX]; 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; strcpy(result.title, title); strcpy(result.author, author); strcpy(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("Problem Solving and Program Design in C", "Hanly & Koffman", "Pearson", 2010, 1); b2 = make_book("Pelle Erobreren", "Martin Andersen Nexoe", "Gyldendal", 1910, 0); b3 = b2; strcpy(b3.title, "Ditte Menneskebarn"); b3.publishing_year = 1917; prnt_book(b1); prnt_book(b2); prnt_book(b3); printf("Sizeof(b1) = %d bytes\n", sizeof(book)); /* 120 bytes */ return 0; }

Structures ved parameteroverførsel Slide Indhold Stikord Referencer

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 (der returneres en kopi) Det er dog typisk mere effektivt at overføre og tilbageføre pointere til structures Arrays - til sammenligning: Overføres som en pointer (call by reference parameteroverførsel) Returneres som en pointer fra en funktion

På næste slide ser vi på pointers til structs

Pointers til structures Slide Indhold Stikord Referencer

Det er muligt at overføre og tilbageføre pointere til structs Men man skal - som altid - passe på, når man arbejder med pointere til lokale variable

Program: Et eksempel på overførsel og tilbageførsel af bøger via en pointer - compiler warning - virker ikke.

/* Incorrect program - compiler warning - 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){ 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("Problem Solving and Program Design in C", "Hanly & Koffman", "Pearson", 2010, 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 via en pointer - virker ikke - forkerte resultater.

/* Incorrect program - compiles, but the program gives wrong results. */ #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("Problem Solving and Program Design in C", "Hanly & Koffman", "Pearson", 2010, 1); b2 = make_book("Pelle Eroberen", "Martin Andersen Nexoe", "Gyldendal", 1911, 0); prnt_book(b1); prnt_book(b2); return 0; }

Program: Output fra programmet.

Title: Pelle Eroberen Author: Martin Andersen Nexoe Publisher: Gyldendal Year: 1911 University text book: no Title: Pelle Eroberen Author: Martin Andersen Nexoe Publisher: Gyldendal Year: 1911 University text book: no

Program: Et eksempel på overførsel og tilbageførsel af bøger via en pointer - nu OK.

#include <stdio.h> #include <stdlib.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)); if (result == NULL){ printf("Out of memory. Bye\n"); exit(EXIT_FAILURE); } 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("Problem Solving and Program Design in C", "Hanly & Koffman", "Pearson", 2010, 1); b2 = make_book("Pelle Eroberen", "Martin Andersen Nexoe", "Gyldendal", 1911, 0); prnt_book(b1); prnt_book(b2); free(b1); free (b2); return 0; }

Program: Output fra programmet.

Title: Problem Solving and Program Design in C Author: Hanly & Koffman Publisher: Pearson Year: 2010 University text book: yes Title: Pelle Eroberen Author: Martin Andersen Nexoe Publisher: Gyldendal Year: 1911 University text book: no

Structures i structures Slide Indhold Stikord Referencer

Det er muligt at indlejre structures i hinanden

Program: Basalt eksempel på structures i structures.

#include <stdio.h> struct point { int x, y; }; struct rectangle { struct point p1, p2; }; int main(void) { struct point pt1, pt2; struct rectangle r; /* Member-wise initialization of x,y coordinates in points */ pt1.x = 5; pt1.y = 6; pt2.x = 7; pt2.y = 8; /* Member-wise initialization of points in rectangle */ r.p1 = pt1; r.p2 = pt2; /* Printing corner points of r */ printf("Corner points in r: (%d,%d) and (%d,%d)\n", r.p1.x, r.p1.y, r.p2.x, r.p2.y); return 0; }

Program: Et attraktivt alternativ.

#include <stdio.h> struct point { int x, y; }; struct rectangle { struct point p1, p2; }; int main(void) { struct point pt1 = {5,6}, pt2 = {7,8}; struct rectangle r = {pt1, pt2}, s = {{5,6}, {7,8}}; /* Printing corner points of r and s*/ printf("Corner points in r: (%d,%d) and (%d,%d)\n", r.p1.x, r.p1.y, r.p2.x, r.p2.y); printf("Corner points in s: (%d,%d) and (%d,%d)\n", s.p1.x, s.p1.y, s.p2.x, s.p2.y); return 0; }

Program: Output fra programmet.

Corner points in r: (5,6) and (7,8) Corner points in s: (5,6) and (7,8)

Program: Et udvidet eksempel på structures i structures.

#include <stdio.h> struct point { int x, y; }; struct rectangle { struct { int x, y; } p1, p2; }; int main(void) { struct rectangle r; struct point pt1, pt2; /* OK - initialization of x,y coordinates of points in rectangles */ r.p1.x = 1; r.p1.y = 2; r.p2.x = 10; r.p2.y = 12; /* Not OK - cannot assign points to the fields of rectangle */ pt1.x = 1; pt1.y = 2; pt2.x = 10; pt2.y = 12; r.p1 = pt1; /* error: incompatible types */ r.p2 = pt2; /* error: incompatible types */ return 0; }

Structs med bit felter - bit fields Slide Indhold Stikord Referencer

Det er muligt at lave kompakte pakkede structs med heltals-felter, der angives med en bit størrelse

Program: En bit field struct med RGB pixels.

#include <stdio.h> struct pixel { unsigned int red: 8; unsigned int green: 8; unsigned int blue: 8; }; typedef struct pixel pixel; pixel make_pixel(unsigned int red, unsigned int green, unsigned int blue){ pixel p; p.red = red; p. green = green; p.blue = blue; return p; } unsigned int get_red(pixel p){ return p.red; } unsigned int get_green(pixel p){ return p.green; } unsigned int get_blue(pixel p){ return p.blue; } int main(void) { pixel p; p = make_pixel(80, 90, 100); printf("Pixel info: red = %d, green = %d, blue = %d\n", get_red(p), get_green(p), get_blue(p)); printf("Size of a pixel: %d bytes\n", sizeof(pixel)); return 0; }

Program: Output fra programmet.

Pixel info: red = 80, green = 90, blue = 100 Size of a pixel: 4 bytes

Program: En tilsvarende struct - uden bit felter.

#include <stdio.h> struct pixel { unsigned int red; unsigned int green; unsigned int blue; }; typedef struct pixel pixel; pixel make_pixel(unsigned int red, unsigned int green, unsigned int blue){ pixel p; p.red = red; p. green = green; p.blue = blue; return p; } unsigned int get_red(pixel p){ return p.red; } unsigned int get_green(pixel p){ return p.green; } unsigned int get_blue(pixel p){ return p.blue; } int main(void) { pixel p; p = make_pixel(80, 90, 100); printf("Pixel info: red = %d, green = %d, blue = %d\n", get_red(p), get_green(p), get_blue(p)); printf("Size of a pixel: %d bytes\n", sizeof(pixel)); return 0; }

Program: Output fra programmet.

Pixel info: red = 80, green = 90, blue = 100 Size of a pixel: 12 bytes

Program: Et lignende program lavet med bitvise operatorer.

typedef unsigned int pixel; pixel make_pixel(unsigned int red, unsigned int green, unsigned int blue){ return (1 << 24) | (red << 16) | (green << 8) | blue; } unsigned int get_red(pixel p){ return (p >> 16) & 0xff; } unsigned int get_green(pixel p){ return (p >> 8) & 0xff; } unsigned int get_blue(pixel p){ return p & 0xff; }

Program: Et lignende program lavet med aritmetiske operatorer.

typedef unsigned int pixel; pixel make_pixel(unsigned int red, unsigned int green, unsigned int blue){ return 1 * 256 * 256 * 256 + red * 256 * 256 + green * 256 + blue; } unsigned int get_red(pixel p){ return (p / (256 * 256)) % 256; } unsigned int get_green(pixel p){ return (p / 256) % 256; } unsigned int get_blue(pixel p){ return p % 256; }

Størrelsen af en struct med bitfelter er vilkårlig Størrelsen af et bitfelt er typisk højst bitstørrelsen af den angivne heltalstype Hvis bitfelter skal anvendes til at danne bestemte bitmønstre i lageret, kræver det viden om maskinens byte ordering

Unions Slide Indhold Stikord Referencer

En union er en struct-lignende type hvor kun ét af felterne er til stede på et givet tidspunkt I en union er felterne placeret oven i hinanden - ikke ved siden af hinanden Vi ser på et eksempel hvor en geometrisk form er enten en cirkel eller et rektangel

Syntax: En union type specifikation

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

Program: En geometrisk form som enten er en cirkel eller et rektangel.

#include <stdio.h> #include <stdlib.h> #include <math.h> #define PI 3.14159 struct point { double x, y; }; struct circle { struct point center; double radius; }; struct rectangle { struct point upper_left, lower_right; }; enum geometric_kind {circle, rectangle}; struct geometric_form{ enum geometric_kind kind; union { struct circle circle; struct rectangle rectangle; } form; }; double area(struct geometric_form f){ double result; if (f.kind == circle) result = f.form.circle.radius * f.form.circle.radius * PI; else if (f.kind == rectangle) result = fabs(f.form.rectangle.upper_left.x - f.form.rectangle.lower_right.x) * fabs(f.form.rectangle.upper_left.y - f.form.rectangle.lower_right.y); else { printf("Should not happen. Bye\n"); exit(1); } return result; } int main(void) { struct geometric_form gf1, gf2; gf1.kind = circle; gf1.form.circle.radius = 5.0; gf1.form.circle.center.x = 0.0; gf1.form.circle.center.y = 0.0; printf("Area of gf1: %f\n", area(gf1)); gf2.kind = rectangle; gf2.form.rectangle.upper_left.x = 1.0; gf2.form.rectangle.upper_left.y = 1.0; gf2.form.rectangle.lower_right.x = 4.0; gf2.form.rectangle.lower_right.y = 4.0; printf("Area of gf2: %f\n", area(gf2)); return 0; }

Program: Output fra programmet.

Area of gf1: 78.539750 Area of gf2: 9.000000

Resultater via parametre eller med struct return Slide Indhold Stikord Referencer

Vi ser her på brug af pointere til returværdier fra en funktion i forhold til brug af return af en struct

Brug af pointere Mulighed for to eller flere resultater Svært at skelne input fra output fra input/output (særligt for arrays) Brug af return Kun mulighed for ét resultat Kan kræve at adskillige resultater indkapsles i et objekt (typisk en struct i C)

Program: Løsning af andengradsligning - resultater via parametre af pointertyper.

#include <stdio.h> #include <math.h> void solveQuadraticEquation(double a, double b, double c, int *numberOfRoots, double *root1, double *root2); void printRoots(int numberOfRoots, double firstRoot, double secondRoot); int main(void) { double a, b, c, r1, r2, s1, s2; int nr1, nr2; printf("Enter coeficients a, b, and c: "); scanf("%lf %lf %lf", &a, &b, &c); if (a != 0){ solveQuadraticEquation(a, b, c, &nr1, &r1, &r2); printRoots(nr1, r1, r2); } else printf("The coeficient a must be non-zero"); solveQuadraticEquation(1.0, 1.0, -30.0, &nr2, &s1, &s2); printRoots(nr2, s1, s2); return 0; } /* Find roots in the quadratic equation a * x*x + b * x + c = 0. Assume as a precondition that a is not zero */ void solveQuadraticEquation(double a, double b, double c, int *numberOfRoots, double *root1, double *root2){ double discriminant; discriminant = b * b - 4 * a * c; if (discriminant < 0){ *numberOfRoots = 0; } else if (discriminant == 0){ *numberOfRoots = 1; *root1 = -b/(2*a); } else{ *numberOfRoots = 2; *root1 = (-b + sqrt(discriminant))/(2*a); *root2 = (-b - sqrt(discriminant))/(2*a); } } void printRoots(int numberOfRoots, double firstRoot, double secondRoot){ if (numberOfRoots == 0) printf("No roots\n"); else if (numberOfRoots == 1) printf("One root: %f\n", firstRoot); else printf("Two roots: %f and %f\n", firstRoot, secondRoot); }

Program: Løsning af andengradsligning - resultater via returneret objekt af struct type.

#include <stdio.h> #include <math.h> struct rootPack{ int numberOfRoots; double firstRoot; double secondRoot; }; typedef struct rootPack rootPack; rootPack solveQuadraticEquation(double a, double b, double c); void printRoots(rootPack rp); int main(void) { double a, b, c; rootPack rp1, rp2; printf("Enter coeficients a, b, and c: "); scanf("%lf %lf %lf", &a, &b, &c); if (a != 0){ rp1 = solveQuadraticEquation(a, b, c); printRoots(rp1); } else printf("The coeficient a must be non-zero"); /* Solve another quadractic Equation */ rp2 = solveQuadraticEquation(1.0, 1.0, -30.0); printRoots(rp2); return 0; } /* Find roots in the quadratic equation a * x*x + b * x + c = 0. Assume as a precondition that a is not zero */ rootPack solveQuadraticEquation(double a, double b, double c){ rootPack result; double discriminant; discriminant = b * b - 4 * a * c; if (discriminant < 0){ result.numberOfRoots = 0; /* result.firstRoot and result.secondRoot undefined */ } else if (discriminant == 0){ result.numberOfRoots = 1; result.firstRoot = -b/(2*a); /* result.secondRoot undefined */ } else{ result.numberOfRoots = 2; result.firstRoot = (-b + sqrt(discriminant))/(2*a); result.secondRoot = (-b - sqrt(discriminant))/(2*a); } return result; } void printRoots(rootPack rp){ if (rp.numberOfRoots == 0) printf("No roots\n"); else if (rp.numberOfRoots == 1) printf("One root: %f\n", rp.firstRoot); else printf("Two roots: %f and %f\n", rp.firstRoot, rp.secondRoot); }

Hvis der kun er ét resultat fra en funktion, brug så return. Hvis der er flere resultater så overvej at samle disse til én værdi og brug af return.

Structs kan være elementtyper i arrays

Figur. En skitse af en et array med elementer der er structs

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

int main(void) { book shelf[MAX_BOOKS]; int i; shelf[0] = make_book("Problem Solving and Program Design in C", "Hanly and Koffman", "Pearson", 2010, 1); shelf[1] = make_book("C by Disssection", "Kelley and Pohl", "Addison Wesley", 2001, 1); shelf[2] = make_book("The C Programming Language", "Kernighan og Ritchie", "Prentice Hall", 1988, 1); shelf[3] = make_book("Pelle Erobreren", "Martin Andersen Nexoe", "Gyldendal", 1910, 0); shelf[4] = shelf[3]; strcpy(shelf[4].title, "Ditte Menneskebarn"); shelf[4].publishing_year = 1917; for(i = 0; i <=4; i++) prnt_book(shelf[i]); return 0; }

Program: Hele programmet.

#include <stdio.h> #include <string.h> #define MAX_BOOKS 10 #define TITLE_MAX 50 #define AUTHOR_MAX 40 #define PUBLISHER_MAX 20 struct book { char title[TITLE_MAX], author[AUTHOR_MAX], publisher[PUBLISHER_MAX]; 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); void prnt_book(book b); int main(void) { book shelf[MAX_BOOKS]; int i; shelf[0] = make_book("Problem Solving and Program Design in C", "Hanly and Koffman", "Pearson", 2010, 1); shelf[1] = make_book("C by Disssection", "Kelley and Pohl", "Addison Wesley", 2001, 1); shelf[2] = make_book("The C Programming Language", "Kernighan og Ritchie", "Prentice Hall", 1988, 1); shelf[3] = make_book("Pelle Erobreren", "Martin Andersen Nexoe", "Gyldendal", 1910, 0); shelf[4] = shelf[3]; strcpy(shelf[4].title, "Ditte Menneskebarn"); shelf[4].publishing_year = 1917; for(i = 0; i <=4; i++) prnt_book(shelf[i]); return 0; } book make_book(char *title, char *author, char *publisher, int year, int text_book){ book result; strcpy(result.title, title); strcpy(result.author, author); strcpy(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); }

Program: Program output.

Title: Problem Solving and Program Design in C Author: Hanly and Koffman Publisher: Pearson Year: 2010 University text book: yes Title: C by Disssection Author: Kelley and Pohl Publisher: Addison Wesley Year: 2001 University text book: yes Title: The C Programming Language Author: Kernighan og Ritchie Publisher: Prentice Hall Year: 1988 University text book: yes Title: Pelle Erobreren Author: Martin Andersen Nexoe Publisher: Gyldendal Year: 1910 University text book: no Title: Ditte Menneskebarn Author: Martin Andersen Nexoe Publisher: Gyldendal Year: 1917 University text book: no

Opgave 12.3. Sortering af et array af bøger

Programmer en funktion, sort_books_by_title, som kan kaldes på variablen shelf fra programmet på den tilhørende slide. Tag udgangspunkt i dette program. Overfør også indekset af den sidste bog som en parameter til sort_books_by_title, således at sorteringsfunktionen ved hvor mange bøger, der skal sorteres: void sort_books_by_title(book shelf[], int last){ qsort(shelf, last+1, ..., ...); } Som antydet af funktionsnavnet, skal funktionen ordne bøgerne således at titlerne kommer i alfabetisk orden. Efter sorteringen er den første bog således 'C by Dissection', og den sidste bog er 'The C Programming Language'. Sorteringen skal foregå ved at bytte om på bøgerne i arrayet (ikke ved at danne en ny, sorteret kopi af arrayet). Ved løsningen af denne opgave skal du anvende funktionen qsort fra stdlib.h, som tidligere har været beskrevet i dette undervisningsmateriale. Programmer dernæst en funktion sort_books_by_kind_and_year. Denne funktion skal primært sortere bøgerne således at alle skønliterære bøger kommer før lærebøgerne (university text books). Inden for begge disse grupper skal funktionen sekundært sortere bøgerne efter udgivelsesår. Relativt til eksemplet på den tilknytede side i undervisningsmaterialet skal det give følgende ordning på bøgerne: Title: Pelle Erobreren Year: 1910 University text book: no Title: Ditte Menneskebarn Year: 1917 University text book: no Title: The C Programming Language Year: 1988 University text book: yes Title: C by Disssection Year: 2001 University text book: yes Title: Problem Solving and Program Design in C Year: 2010 University text book: yes Afprøv begge sorterings-funktionerne på de fem bøger i variablen shelf.

Arrays af datoer: Kalender Slide Indhold Stikord Referencer

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[DATE_MAX]; char ignore; date first_date = {tuesday, 17, 11, 2015}, last_date = {thursday, 17, 11, 2016}, 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++){ if (j % 20 == 0) { printf("More? - touch the enter key: "); scanf("%c", &ignore); } prnt_date(calendar[j]); } }

Henvisning Siden med date_before

Program: Hele kalenderprogrammet - bortset fra funktionen tomorrow.

#include <stdio.h> #include <stdlib.h> #define DATE_MAX 1000 /* 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[DATE_MAX]; char ignore; date first_date = {tuesday, 17, 11, 2015}, last_date = {thursday, 17, 11, 2016}, 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++){ if (j % 20 == 0) { printf("More? - touch the enter key: "); scanf("%c", &ignore); } prnt_date(calendar[j]); } } /* 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); } /* 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; } 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; }

Program: Output fra kalenderprogrammet.

Tuesday 17.11.2015 Wednesday 18.11.2015 Thursday 19.11.2015 Friday 20.11.2015 Saturday 21.11.2015 Sunday 22.11.2015 Monday 23.11.2015 Tuesday 24.11.2015 Wednesday 25.11.2015 Thursday 26.11.2015 Friday 27.11.2015 Saturday 28.11.2015 Sunday 29.11.2015 Monday 30.11.2015 Tuesday 1.12.2015 Wednesday 2.12.2015 Thursday 3.12.2015 Friday 4.12.2015 Saturday 5.12.2015 Sunday 6.12.2015 Monday 7.12.2015 Tuesday 8.12.2015 Wednesday 9.12.2015 Thursday 10.12.2015 Friday 11.12.2015 Saturday 12.12.2015 Sunday 13.12.2015 Monday 14.12.2015 Tuesday 15.12.2015 Wednesday 16.12.2015 Thursday 17.12.2015 Friday 18.12.2015 Saturday 19.12.2015 Sunday 20.12.2015 Monday 21.12.2015 Tuesday 22.12.2015 Wednesday 23.12.2015 Thursday 24.12.2015 Friday 25.12.2015 Saturday 26.12.2015 Sunday 27.12.2015 Monday 28.12.2015 Tuesday 29.12.2015 Wednesday 30.12.2015 Thursday 31.12.2015 Friday 1. 1.2016 Saturday 2. 1.2016 Sunday 3. 1.2016 Monday 4. 1.2016 Tuesday 5. 1.2016 Wednesday 6. 1.2016 Thursday 7. 1.2016 Friday 8. 1.2016 Saturday 9. 1.2016 Sunday 10. 1.2016 Monday 11. 1.2016 Tuesday 12. 1.2016 Wednesday 13. 1.2016 Thursday 14. 1.2016 Friday 15. 1.2016 Saturday 16. 1.2016 Sunday 17. 1.2016 Monday 18. 1.2016 Tuesday 19. 1.2016 Wednesday 20. 1.2016 Thursday 21. 1.2016 Friday 22. 1.2016 Saturday 23. 1.2016 Sunday 24. 1.2016 Monday 25. 1.2016 Tuesday 26. 1.2016 Wednesday 27. 1.2016 Thursday 28. 1.2016 Friday 29. 1.2016 Saturday 30. 1.2016 Sunday 31. 1.2016 Monday 1. 2.2016 Tuesday 2. 2.2016 Wednesday 3. 2.2016 Thursday 4. 2.2016 Friday 5. 2.2016 Saturday 6. 2.2016 Sunday 7. 2.2016 Monday 8. 2.2016 Tuesday 9. 2.2016 Wednesday 10. 2.2016 Thursday 11. 2.2016 Friday 12. 2.2016 Saturday 13. 2.2016 Sunday 14. 2.2016 Monday 15. 2.2016 Tuesday 16. 2.2016 Wednesday 17. 2.2016 Thursday 18. 2.2016 Friday 19. 2.2016 Saturday 20. 2.2016 Sunday 21. 2.2016 Monday 22. 2.2016 Tuesday 23. 2.2016 Wednesday 24. 2.2016 Thursday 25. 2.2016 Friday 26. 2.2016 Saturday 27. 2.2016 Sunday 28. 2.2016 Monday 29. 2.2016 Tuesday 1. 3.2016 Wednesday 2. 3.2016 Thursday 3. 3.2016 Friday 4. 3.2016 Saturday 5. 3.2016 Sunday 6. 3.2016 Monday 7. 3.2016 Tuesday 8. 3.2016 Wednesday 9. 3.2016 Thursday 10. 3.2016 Friday 11. 3.2016 Saturday 12. 3.2016 Sunday 13. 3.2016 Monday 14. 3.2016 Tuesday 15. 3.2016 Wednesday 16. 3.2016 Thursday 17. 3.2016 Friday 18. 3.2016 Saturday 19. 3.2016 Sunday 20. 3.2016 Monday 21. 3.2016 Tuesday 22. 3.2016 Wednesday 23. 3.2016 Thursday 24. 3.2016 Friday 25. 3.2016 Saturday 26. 3.2016 Sunday 27. 3.2016 Monday 28. 3.2016 Tuesday 29. 3.2016 Wednesday 30. 3.2016 Thursday 31. 3.2016 Friday 1. 4.2016 Saturday 2. 4.2016 Sunday 3. 4.2016 Monday 4. 4.2016 Tuesday 5. 4.2016 Wednesday 6. 4.2016 Thursday 7. 4.2016 Friday 8. 4.2016 Saturday 9. 4.2016 Sunday 10. 4.2016 Monday 11. 4.2016 Tuesday 12. 4.2016 Wednesday 13. 4.2016 Thursday 14. 4.2016 Friday 15. 4.2016 Saturday 16. 4.2016 Sunday 17. 4.2016 Monday 18. 4.2016 Tuesday 19. 4.2016 Wednesday 20. 4.2016 Thursday 21. 4.2016 Friday 22. 4.2016 Saturday 23. 4.2016 Sunday 24. 4.2016 Monday 25. 4.2016 Tuesday 26. 4.2016 Wednesday 27. 4.2016 Thursday 28. 4.2016 Friday 29. 4.2016 Saturday 30. 4.2016 Sunday 1. 5.2016 Monday 2. 5.2016 Tuesday 3. 5.2016 Wednesday 4. 5.2016 Thursday 5. 5.2016 Friday 6. 5.2016 Saturday 7. 5.2016 Sunday 8. 5.2016 Monday 9. 5.2016 Tuesday 10. 5.2016 Wednesday 11. 5.2016 Thursday 12. 5.2016 Friday 13. 5.2016 Saturday 14. 5.2016 Sunday 15. 5.2016 Monday 16. 5.2016 Tuesday 17. 5.2016 Wednesday 18. 5.2016 Thursday 19. 5.2016 Friday 20. 5.2016 Saturday 21. 5.2016 Sunday 22. 5.2016 Monday 23. 5.2016 Tuesday 24. 5.2016 Wednesday 25. 5.2016 Thursday 26. 5.2016 Friday 27. 5.2016 Saturday 28. 5.2016 Sunday 29. 5.2016 Monday 30. 5.2016 Tuesday 31. 5.2016 Wednesday 1. 6.2016 Thursday 2. 6.2016 Friday 3. 6.2016 Saturday 4. 6.2016 Sunday 5. 6.2016 Monday 6. 6.2016 Tuesday 7. 6.2016 Wednesday 8. 6.2016 Thursday 9. 6.2016 Friday 10. 6.2016 Saturday 11. 6.2016 Sunday 12. 6.2016 Monday 13. 6.2016 Tuesday 14. 6.2016 Wednesday 15. 6.2016 Thursday 16. 6.2016 Friday 17. 6.2016 Saturday 18. 6.2016 Sunday 19. 6.2016 Monday 20. 6.2016 Tuesday 21. 6.2016 Wednesday 22. 6.2016 Thursday 23. 6.2016 Friday 24. 6.2016 Saturday 25. 6.2016 Sunday 26. 6.2016 Monday 27. 6.2016 Tuesday 28. 6.2016 Wednesday 29. 6.2016 Thursday 30. 6.2016 Friday 1. 7.2016 Saturday 2. 7.2016 Sunday 3. 7.2016 Monday 4. 7.2016 Tuesday 5. 7.2016 Wednesday 6. 7.2016 Thursday 7. 7.2016 Friday 8. 7.2016 Saturday 9. 7.2016 Sunday 10. 7.2016 Monday 11. 7.2016 Tuesday 12. 7.2016 Wednesday 13. 7.2016 Thursday 14. 7.2016 Friday 15. 7.2016 Saturday 16. 7.2016 Sunday 17. 7.2016 Monday 18. 7.2016 Tuesday 19. 7.2016 Wednesday 20. 7.2016 Thursday 21. 7.2016 Friday 22. 7.2016 Saturday 23. 7.2016 Sunday 24. 7.2016 Monday 25. 7.2016 Tuesday 26. 7.2016 Wednesday 27. 7.2016 Thursday 28. 7.2016 Friday 29. 7.2016 Saturday 30. 7.2016 Sunday 31. 7.2016 Monday 1. 8.2016 Tuesday 2. 8.2016 Wednesday 3. 8.2016 Thursday 4. 8.2016 Friday 5. 8.2016 Saturday 6. 8.2016 Sunday 7. 8.2016 Monday 8. 8.2016 Tuesday 9. 8.2016 Wednesday 10. 8.2016 Thursday 11. 8.2016 Friday 12. 8.2016 Saturday 13. 8.2016 Sunday 14. 8.2016 Monday 15. 8.2016 Tuesday 16. 8.2016 Wednesday 17. 8.2016 Thursday 18. 8.2016 Friday 19. 8.2016 Saturday 20. 8.2016 Sunday 21. 8.2016 Monday 22. 8.2016 Tuesday 23. 8.2016 Wednesday 24. 8.2016 Thursday 25. 8.2016 Friday 26. 8.2016 Saturday 27. 8.2016 Sunday 28. 8.2016 Monday 29. 8.2016 Tuesday 30. 8.2016 Wednesday 31. 8.2016 Thursday 1. 9.2016 Friday 2. 9.2016 Saturday 3. 9.2016 Sunday 4. 9.2016 Monday 5. 9.2016 Tuesday 6. 9.2016 Wednesday 7. 9.2016 Thursday 8. 9.2016 Friday 9. 9.2016 Saturday 10. 9.2016 Sunday 11. 9.2016 Monday 12. 9.2016 Tuesday 13. 9.2016 Wednesday 14. 9.2016 Thursday 15. 9.2016 Friday 16. 9.2016 Saturday 17. 9.2016 Sunday 18. 9.2016 Monday 19. 9.2016 Tuesday 20. 9.2016 Wednesday 21. 9.2016 Thursday 22. 9.2016 Friday 23. 9.2016 Saturday 24. 9.2016 Sunday 25. 9.2016 Monday 26. 9.2016 Tuesday 27. 9.2016 Wednesday 28. 9.2016 Thursday 29. 9.2016 Friday 30. 9.2016 Saturday 1.10.2016 Sunday 2.10.2016 Monday 3.10.2016 Tuesday 4.10.2016 Wednesday 5.10.2016 Thursday 6.10.2016 Friday 7.10.2016 Saturday 8.10.2016 Sunday 9.10.2016 Monday 10.10.2016 Tuesday 11.10.2016 Wednesday 12.10.2016 Thursday 13.10.2016 Friday 14.10.2016 Saturday 15.10.2016 Sunday 16.10.2016 Monday 17.10.2016 Tuesday 18.10.2016 Wednesday 19.10.2016 Thursday 20.10.2016 Friday 21.10.2016 Saturday 22.10.2016 Sunday 23.10.2016 Monday 24.10.2016 Tuesday 25.10.2016 Wednesday 26.10.2016 Thursday 27.10.2016 Friday 28.10.2016 Saturday 29.10.2016 Sunday 30.10.2016 Monday 31.10.2016 Tuesday 1.11.2016 Wednesday 2.11.2016 Thursday 3.11.2016 Friday 4.11.2016 Saturday 5.11.2016 Sunday 6.11.2016 Monday 7.11.2016 Tuesday 8.11.2016 Wednesday 9.11.2016 Thursday 10.11.2016 Friday 11.11.2016 Saturday 12.11.2016 Sunday 13.11.2016 Monday 14.11.2016 Tuesday 15.11.2016 Wednesday 16.11.2016

Opgave 12.5. Funktionen tomorrow

På den omkringliggende slide er der vist et program, der genererer en kalender på et helt år. Vi har på en tidligere slide programmeret struct date. I denne opgave skal du programmere den manglende funktion tomorrow. Funktionen tomorrow tager en dato som parameter, og den returnerer datoen på den efterfølgende dag. Du kan taget udgangspunkt i dette program. Hint: Lad i udgangspunktet resultatet være den overførte parameter, og gennemfør (pr. assignment til enkelte felter) de nødvendige ændringer.

Opgave 12.5. Spillekort

Et spillekort er karakteriseret af en kulør (klør, ruder, hjerter og spar) og en værdi (es, 2, .., 10, knægt, dame, og konge). Alternativt kan et spillekort være en joker (som hverken har kulør eller værdi). Definer en struct i C (med felter kuloer og vaerdi) som repræsenterer et spillekort. Beslut selv typen af felterne. Enumerationtyper kan være attraktive. Overvej hvordan du ønsker at håndtere jokeren! Lav et spil kort bestående af de 52 "normale" spillekort og 3 jokere, altså ialt 55 kort. Organiser disse i et array af structs. Programmer en funktion sorter_kort som sorterer kortene således: Klør kommer før ruder kommer før hjerter kommer før spar Inden for hver kulør benyttes ordningen 2, ..., 10, knægt, dame, konge og es. Jokerne kommer efter de normale spillekort I programmeringen af sorter_kort forventes at du benytter qsort med en passende sammenligningsfunktion. Da kortene typisk er ordnet per konstruktion kan det anbefales du også programmerer en funktion, som blander kortene tilfældigt. Med en sådan funktion kan du blande kortene inden de sorteres. Blanding af kortene kan gøres på mange forskellige måder. Det kan f.eks. ske ved at gennemløbe alle kort, og at bytte det aktuelle kort om med et tilfældigt valgt andet kort. Målet med opgaven er at opnå viden og færdigheder i programmering med structs og array af structs. Det er endvidere målet at opnå viden og færdigheder om sortering af et array af structs.

Arrays kan være felter i en struct

Figur. En skitse af en struct med et array felt

Program: En struct med et array af hjørne-punkter i en firkant.

#include <stdio.h> struct point { double x, y; }; typedef struct point point; struct quadrangle { int rank; struct point points[4]; }; typedef struct quadrangle quadrangle; quadrangle make_quadrangle(point corners[]){ int i; struct quadrangle result; result.rank = 4; for(i = 0; i < 4; i++) result.points[i] = corners[i]; return result; } int main(void) { quadrangle q1 = {4, {{1.0, 1.0}, {7.0, 7.0}, {-5.0, 0.0}, {-15.0, 16.0}}}, q2; point corner_points[] = { {1.0, 1.0}, {7.0, 7.0}, {-5.0, -5.0}, {5.0, -16.0} }; q2 = make_quadrangle(corner_points); // ... printf("Size of quadrangle: %d bytes\n", sizeof(quadrangle)); return 0; }

Program: Output fra programmet - afslører størrelsen af struct quadrangle.

Size of quadrangle: 72 bytes

Program: En struct med en pointer til et array af hjørne-punkter i en polygon.

#include <stdio.h> #include <stdlib.h> struct point { double x, y; }; typedef struct point point; struct polygon { int rank; point *points; }; typedef struct polygon polygon; polygon make_polygon(int rank, point corners[]){ int i; struct polygon result; result.rank = rank; result.points = (point*)malloc(rank * sizeof(struct point)); // Check if malloc returns NULL - not included here... for(i = 0; i < rank; i++) result.points[i] = corners[i]; return result; } int main(void) { polygon a_pentagon; point five_points[] = { {0.0, 0.0}, {3.0, 7.0}, {10.0, 5.0}, {10.0, -5.0}, {2.0, -16.0} }; a_pentagon = make_polygon(5, five_points); // ... // Free memory allocated for a_pentagon.points ... printf("Size of polygon: %d bytes\n", sizeof(polygon)); printf("Size of int: %d bytes\n", sizeof(int)); printf("Size of point*: %d bytes\n", sizeof(point * )); return 0; }

Program: Output fra programmet - afslører størrelsen af struct polygon.

Size of polygon: 8 bytes Size of int: 4 bytes Size of point*: 4 bytes

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) Sammenkædede datastrukturer er også vigtige i forbindelse med træer (forgrenede strukturer)

Henvisning Dynamisk allokering af lager

Sammenkædede datastrukturer (2) Slide Indhold Stikord Referencer

Program: Structures for recursive and self referential structures.

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

Figur. En tilsvarende kædet liste - med og uden pointers til elementerne

Kædede lister ala Lisp Slide Indhold Stikord Referencer

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 = (cons_cell *)malloc(sizeof(cons_cell)); if (result == NULL){ printf("Out of memory. Bye."); exit(EXIT_FAILURE); } 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); }

Program: Hele programmet.

#include <stdio.h> #include <stdlib.h> struct point {int x; int y;}; typedef struct point point; void prnt_point(point p){ printf("Point: %i, %i\n", p.x, p.y); } struct cons_cell { void *data; struct cons_cell *next; }; typedef struct cons_cell cons_cell; /* 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 = (cons_cell *)malloc(sizeof(cons_cell)); if (result == NULL){ printf("Out of memory. Bye."); exit(EXIT_FAILURE); } 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; } /* 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; } 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; }

En datastruktur opbygget af cons celler er i realiteten et binært træ

Mutation af cons celler Slide Indhold Stikord Referencer

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; }

Program: Output fra programmet.

Point: 5, 6 Point: 6, 7 Point: 5, 6

Funktioner på lister Slide Indhold Stikord Referencer

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; }

Program: Output fra programmet.

Number of points in the list points: 4 Point: 1, 2 Point: 3, 4 Point: 5, 6 Point: 6, 7 Point: 8, 9 Point: 10, 11 Point: 12, 13 Point: 14, 15 p6 is NOT member of points p6 is member of more_points p6 is member of point_list Point: 6, 7 Point: 5, 6 Point: 3, 4 Point: 1, 2

Bemærk at alle fire funktioner er rekursive

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

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 en garbage collector eller af et kald af free

 

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

 

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; }

Program: Output fra programmet.

Point: 1, 2 Point: 3, 4 Point: 11, 12 Point: 5, 6 Point: 1, 2 Point: 11, 12 Point: 5, 6

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

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

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

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

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

Dataabstration Der abstraheres fra detaljer i datarepræsentation Repræsentationsuafhængighed Data tilgås via udvalgte funktioner (operationer). Mange typer i C kan opfattes som abstrakte datatyper

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

Opgaver Slide Indhold Stikord Referencer

Opgave 12.9. Brøker og structs

Lav en struct, som repræsenterer en brøk (engelsk: fraction). Den nye type skal naturligvis have to felter, for hhv. tæller og nævner (engelsk: numerator og denominator). I denne opgave ønsker vi at disse skal være af typen unsigned int. Vi arbejder således udelukkende med positive brøker. Programmer nu følgende funktioner på brøker: En funktion der forkorter brøken mest muligt (ved at dividere igennem med den største fælles divisor)) En funktion (procedure) der udskriver en brøk på skærmen. En funktion der multiplicerer (ganger) en brøk med et heltal, og som returnerer produktet (en brøk). Forkort den resulterende brøk mest muligt. En funktion der multiplicerer (ganger) to brøker sammen, og som returnerer produktet. Forkort den resulterende brøk mest muligt. En funktion adderer to brøker (lægger dem sammen) og som returnerer summen. Forkort den resulterende brøk mest muligt. Det kan også anbefales at lave en funktion der laver en brøk ud fra en tæller og en nævner. Altså en funktion der returnerer en brøk konstrueret ud fra tæller og nævner input. Vi har tidligere i kurset arbejdet med en funktion, der finder den største fælles divisor af to positive heltal. For ikke at bruge for meget tid på dette aspekt, er der en mulig implementation af denne funktion her (Euclids algoritme): unsigned int gcd(unsigned int large, unsigned int small){ unsigned int remainder; while (small > 0){ remainder = large % small; large = small; small = remainder; } return large; } Når man skal addere to brøkker skal man først finde en fælles nævner. Dette kan gøres ved at multiplicere begge brøker med den anden brøks nævner. Hvis du har brug for mere matematisk viden om brøker henviser vi til Wikipedias side om brøker. Skriv også en main funktion som giver eksempler på hvordan givne brøker kan konstrueres, adderes og multipliceres.

Opgave 12.9. Funktioner på cirkulære lister

I denne opgave skal du tage udgangspunkt i diskussionen af cirkulære lister i videoen, som hører til denne lektion. Jeg foreslår at du laver en cirkulær liste med punkter. Start med at programmere en funktion der beregner listens længde: length_of_circular_list Programmer dernæst de fire funktioner der hhv. indsætter og sletter det første og det sidste element i en liste: insert_head insert_tail delete_head delete_tail Det forventes at alle pånær én af disse kan køres i konstant tid (altså uafhængig af listens længde). Hvilken funktion er markant mindre effektiv end i de andre? Her et udgangspunkt, som gør det lidt lettere at komme i gang: #include <stdio.h> #include <stdlib.h> struct point {int x; int y;}; typedef struct point point; struct list_node { void *data; struct list_node *next; }; typedef struct list_node list_node; void print_point(point *p); void print_circular_point_list(list_node *cl); list_node *insert_head(list_node *cl, void *el); list_node *insert_tail(list_node *cl, void *el); list_node *delete_head(list_node *cl); list_node *delete_tail(list_node *cl); int length_of_circular_list(list_node *cl); list_node *find_previous_node(list_node *cl); int main(void) { point p1 = {1,2}, p2 = {3,4}, p3 = {5,6}, p4 = {7,8}; list_node *circular_list = NULL; printf("Length of circular list: %d\n", length_of_circular_list(circular_list)); return EXIT_SUCCESS; } void print_point(point *p){ printf("(%1d, %1d)\n", p->x, p->y); } void print_circular_point_list(list_node *cl){ list_node *cur, *prev; if (cl != NULL){ cur = cl->next; do{ prev = cur; print_point(cur->data); cur = cur->next; } while(prev != cl); } } /* An exercise */ int length_of_circular_list(list_node *cl){ return 0; }

Opgave 12.9. Højde-funktion af binært træ

Højden af et binært træ defineres som højden af træets rod. Højden af en knude K i træet er den længste sti fra K til et blad. Med dette bliver højden af et blad altså 0. Skriv en funktion i C der beregner højden af et træ. Udgangspunktet (parameteren) skal være en pointer til en knude i træet. Afprøv funktionen på forskellige træer. Her er et godt udgangspunkt for denne opgave - dog givet i kontekst af binære søgetræer - og svarende til de programmer der er diskuteret i lektionsvideoen. #include <stdio.h> #include <stdlib.h> #include <limits.h> struct tree_node{ int key; struct tree_node *leftp, *rightp; }; typedef struct tree_node tree_node; tree_node *make_tree(int key, tree_node *left, tree_node *right); void assert_allocation_success(void *alloc_pointer); tree_node *insert_in_binary_search_tree(tree_node *tree_ptr, int e); void print_tree(tree_node *tree_ptr); void print_tree_helper(tree_node *tree_ptr, int level); int tree_height(tree_node *tree_ptr); int main(void) { tree_node *tree4 = NULL; tree4 = insert_in_binary_search_tree(tree4, 6); tree4 = insert_in_binary_search_tree(tree4, 2); tree4 = insert_in_binary_search_tree(tree4, 1); tree4 = insert_in_binary_search_tree(tree4, 4); tree4 = insert_in_binary_search_tree(tree4, 3); tree4 = insert_in_binary_search_tree(tree4, 5); tree4 = insert_in_binary_search_tree(tree4, 7); tree4 = insert_in_binary_search_tree(tree4, 9); tree4 = insert_in_binary_search_tree(tree4, 8); printf("tree4:\n"); print_tree(tree4); exit(EXIT_FAILURE); } tree_node *make_tree(int key, tree_node *left, tree_node *right){ tree_node *the_tree = malloc(sizeof(tree_node)); assert_allocation_success(the_tree); the_tree->key = key; the_tree->leftp = left; the_tree->rightp = right; return the_tree; } void assert_allocation_success(void *alloc_pointer){ if (alloc_pointer == NULL){ printf("Allocation problems. Your program stops."); exit(EXIT_FAILURE); } } /* Insert the element e i the binary search tree, designated by tree_ptr. Drop the insertion if e is already in the tree. Return the tree in terms of a pointer to its root node. */ tree_node *insert_in_binary_search_tree(tree_node *tree_ptr, int e){ if (tree_ptr == NULL){ /* Make a small tree rooted with e and empty subtrees */ /* This branch is never reached via recursion */ tree_node *the_tree = make_tree(e, NULL, NULL); return the_tree; } else if (e == tree_ptr->key){ /* Do nothing */ return tree_ptr; } else if (e < tree_ptr->key && tree_ptr->leftp == NULL){ tree_node *the_tree = make_tree(e, NULL, NULL); tree_ptr->leftp = the_tree; return tree_ptr; } else if (e < tree_ptr->key){ insert_in_binary_search_tree(tree_ptr->leftp, e); return tree_ptr; } else if (e > tree_ptr->key && tree_ptr->rightp == NULL){ tree_node *the_tree = make_tree(e, NULL, NULL); tree_ptr->rightp = the_tree; return tree_ptr; } else { /* e > tree_ptr->key) */ insert_in_binary_search_tree(tree_ptr->rightp, e); return tree_ptr; } } void print_tree(tree_node *tree_ptr){ print_tree_helper(tree_ptr, 0); } /* print the tree designated by tree_ptr as horizotally, as an indented text, on standard output. Empty subtrees are printed as "." if tree_ptr is passsed as NULL */ void print_tree_helper(tree_node *tree_ptr, int level){ int i; /* print indented root */ for(i = 0; i < level; ++i) printf(" "); if (tree_ptr == NULL) printf(".\n"); /* Missing part */ else printf("%d\n", tree_ptr->key); if(tree_ptr != NULL){ /* print branches */ if (tree_ptr->leftp == NULL && tree_ptr->rightp == NULL){ /* print nothing */ } else if (tree_ptr->leftp != NULL && tree_ptr->rightp == NULL){ print_tree_helper(tree_ptr->leftp, level+1); print_tree_helper(NULL, level+1); } else if (tree_ptr->leftp == NULL && tree_ptr->rightp != NULL){ print_tree_helper(NULL, level+1); print_tree_helper(tree_ptr->rightp, level+1); } else { print_tree_helper(tree_ptr->leftp, level+1); print_tree_helper(tree_ptr->rightp, level+1); } } } /* Opgave */ int tree_height(tree_node *tree_ptr){ return 0; }

Opgave 12.9. En funktion der genkender et binært søgetræ

Programmer en funktion, is_binary_search_tree, der tager et binært træ som input, og som returnerer hvorvidt dette træ er et (binært) søgetræ. Afprøv funktionen på forskellige binære træer. Herunder er der et godt udgangspunkt for denne opgave. Det vil også være en god ide at konsultere denne del af lektionsvidoen, hvor et binært søgetræ defineres. #include <stdio.h> #include <stdlib.h> #include <limits.h> struct tree_node{ int key; struct tree_node *leftp, *rightp; }; typedef struct tree_node tree_node; tree_node *make_tree(int key, tree_node *left, tree_node *right); void assert_allocation_success(void *alloc_pointer); void print_tree(tree_node *tree_ptr); void print_tree_helper(tree_node *tree_ptr, int level); tree_node *insert_in_binary_search_tree(tree_node *tree_ptr, int e); int is_binary_search_tree(tree_node *tree_ptr); int main(void) { tree_node *tree4 = NULL; tree4 = insert_in_binary_search_tree(tree4, 6); tree4 = insert_in_binary_search_tree(tree4, 2); tree4 = insert_in_binary_search_tree(tree4, 1); tree4 = insert_in_binary_search_tree(tree4, 4); tree4 = insert_in_binary_search_tree(tree4, 3); tree4 = insert_in_binary_search_tree(tree4, 5); tree4 = insert_in_binary_search_tree(tree4, 7); tree4 = insert_in_binary_search_tree(tree4, 9); tree4 = insert_in_binary_search_tree(tree4, 8); /* Per construction, tree4 should be a binary search tree */ /* You can use make_tree to construct other trees which are not binary search trees */ printf("tree4:\n"); print_tree(tree4); exit(EXIT_FAILURE); } tree_node *make_tree(int key, tree_node *left, tree_node *right){ tree_node *the_tree = malloc(sizeof(tree_node)); assert_allocation_success(the_tree); the_tree->key = key; the_tree->leftp = left; the_tree->rightp = right; return the_tree; } void assert_allocation_success(void *alloc_pointer){ if (alloc_pointer == NULL){ printf("Allocation problems. Your program stops."); exit(EXIT_FAILURE); } } /* Insert the element e i the binary search tree, designated by tree_ptr. Drop the insertion if e is already in the tree. Return the tree in terms of a pointer to its root node. */ tree_node *insert_in_binary_search_tree(tree_node *tree_ptr, int e){ if (tree_ptr == NULL){ /* Make a small tree rooted with e and empty subtrees */ /* This branch is never reached via recursion */ tree_node *the_tree = make_tree(e, NULL, NULL); return the_tree; } else if (e == tree_ptr->key){ /* Do nothing */ return tree_ptr; } else if (e < tree_ptr->key && tree_ptr->leftp == NULL){ tree_node *the_tree = make_tree(e, NULL, NULL); tree_ptr->leftp = the_tree; return tree_ptr; } else if (e < tree_ptr->key){ insert_in_binary_search_tree(tree_ptr->leftp, e); return tree_ptr; } else if (e > tree_ptr->key && tree_ptr->rightp == NULL){ tree_node *the_tree = make_tree(e, NULL, NULL); tree_ptr->rightp = the_tree; return tree_ptr; } else { /* e > tree_ptr->key) */ insert_in_binary_search_tree(tree_ptr->rightp, e); return tree_ptr; } } /* void delete_tree(tree_node *tree_ptr) Rather difficult to program because it requires access to parents */ void print_tree(tree_node *tree_ptr){ print_tree_helper(tree_ptr, 0); } /* print the tree designated by tree_ptr as horizotally, as an indented text, on standard output. Empty subtrees are printed as "." if tree_ptr is passsed as NULL */ void print_tree_helper(tree_node *tree_ptr, int level){ int i; /* print indented root */ for(i = 0; i < level; ++i) printf(" "); if (tree_ptr == NULL) printf(".\n"); /* Missing part */ else printf("%d\n", tree_ptr->key); if(tree_ptr != NULL){ /* print branches */ if (tree_ptr->leftp == NULL && tree_ptr->rightp == NULL){ /* print nothing */ } else if (tree_ptr->leftp != NULL && tree_ptr->rightp == NULL){ print_tree_helper(tree_ptr->leftp, level+1); print_tree_helper(NULL, level+1); } else if (tree_ptr->leftp == NULL && tree_ptr->rightp != NULL){ print_tree_helper(NULL, level+1); print_tree_helper(tree_ptr->rightp, level+1); } else { print_tree_helper(tree_ptr->leftp, level+1); print_tree_helper(tree_ptr->rightp, level+1); } } } int int_max(int a, int b){ return a > b ? a : b; } /* Opgaven */ int is_binary_search_tree(tree_node *tree_ptr){ return 0; }

Kapitel 12: 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: 9. maj 2022, 14:00:28