Kapitel 12
Datastrukturer og Dataabstraktion

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

Datastrukturer (1)
Slide Indhold Stikord
Referencer 

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

Henvisning

  • 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.


Structures

Structures (1)
Slide Indhold Stikord
Referencer 

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

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

Structures i C (2)
Slide Indhold Stikord
Referencer 

Structs er data af første klasse data i C

Henvisning

  • 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

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å til 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.


Arrays af structures

Array af bøger
Slide Indhold Stikord
Referencer 

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){
  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 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: 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 side. 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

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

den omkringliggende side 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.

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).

Definier en struct i C (med felter kuloer og vaerdi) som repræsenterer et spillekort. Beslut selv typen af felterne. 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 sort_kort anbefales det at benytte qsort med en passende sammenligningsfunktion.


Structures med arrays

Structs med felter af array typer
Slide Indhold Stikord
Referencer 

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

Sammenkædede datastrukturer (1)
Slide Indhold Stikord
Referencer 

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

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


Abstrakte datatyper

Abstrakte datatyper
Slide Indhold Stikord
Referencer 

Begrebet abstrakt datatype: En abstrakt datatype er en mængde af værdier og en tilhørende mængde af operationer på disse værdierVæ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#


Samlede referencer
Indhold Stikord
Oversigt over typer i C
Operator tabel for C
Tilsvarende introduktion til arrays
Enumeration types
Tilsvarende diskussion af arrays
Strukturel lighed af strenge
Siden med date_before
Dynamisk allokering af lager

 

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: 20. november 2017, 10:52:26