Thema indholdsfortegnelse -- Tastaturgenvej: 'u'  Forrige tema i denne lektion -- Tastaturgenvej: 'p'  Næste slide i denne lektion -- Tastaturgenvej: 'n'Datastrukturer og Dataabstraktion
39.  Records/structures

I dette kapitel foretager vi en grundig gennemgang af records. I C taler vi om structures, eller blot structs, i stedet for records. Recordbetegnelsen anvendes eksempelvis i Pascal. Som altid ser vi på et antal eksempler når vi kommer godt igang med emnet.

39.1 Structures/records (1)39.5 Eksempel: Dato structure
39.2 Structures/records (2)39.6 Eksempel: Bog structure
39.3 Structures/records (3)39.7 Structures ved parameteroverførsel
39.4 Structures i C (1)39.8 Structures i structures
 

39.1.  Structures/records (1)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Både arrays og structures kan opfattes som tabeller. Den mest betegnende forskel er dog, at structures tillader 'elementer' af forskellige typer i tabellen. Vi husker fra afsnit 21.1 at alle elementer i et array skal være af samme type.

En record er en tabel med navngivne felter, som kan være af forskellige datatyper

En record gruppérer og sammensætter en mængde variable af forskellige typer i en logisk helhed

I C kaldes records for structures

I figur 39.1 har vi tegnet en tabel, hvor elementerne opfattes som felter. Felter har navne, og ikke indeks numre som vi kender det fra arrays.

Figur 39.1    En skitse af en structure

 

39.2.  Structures/records (2)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Herunder gengiver vi de generelle egenskaber af records.

  • Elementerne/felterne i en record kan være af forskellige typer

  • Elementerne er individuelt navngivne med feltnavne

  • Elementerne i en record tilgås med dot notation: record.feltnavn

  • Når en record er skabt og allokeret i lageret kan der ikke tilføjes eller fjernes felter

  • Felterne i en record lagres konsekutivt, med afstættelse af passende plads til hvert felt

Der er effektiv tilgang til felterne i en record, men der er typisk meget færre felter i en record end der er elementer i et array

Prisen for 'elementer af forskellige typer' er at vi ikke kan 'beregne os frem til' et felt i tabellen.

 

39.3.  Structures/records (3)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Lad os et øjeblik antage, at vi ikke har structs i vores programmeringssprog. Ligesom vi gjorde for arrays i afsnit 21.2 vil vi skrive et program, som udstiller genvordighederne ved at undvære structures.

I program 39.1 ser vi tre grupper af logisk sammenhørende variable, som beskriver egenskaber af en far, mor og en baby. Hver person beskrives ved navn, CPR nummer og forældrenes CPR numre. I alt fire egenskaber pr. person.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>

typedef unsigned long CPR;

int main(void) {

  char *baby_name = "Paul";
  CPR baby_cpr = 2304031577;
  CPR baby_father_cpr = 1605571233;
  CPR baby_mother_cpr = 2412671234;

  char *mother_name = "Anna";
  CPR mother_cpr = 2412671234;
  CPR mother_father_cpr = 1605376789;
  CPR mother_mother_cpr = 1201402468;

  char *father_name = "Frank";
  CPR father_cpr = 1605571233;
  CPR father_father_cpr = 1111331357;
  CPR father_mother_cpr = 1212358642;
  
  return 0;
}
Program 39.1    Motivation for structures - logisk sammenhørende, men sideordnede variable.

Vi fornemmer klart, at det vil være hensigtsmæssigt med en mere eksplicit grupperingsmekanisme, som f.eks. sammenknytter variablene baby_name, baby_cpr, baby_father_cpr og baby_mother_cpt til en enhed. Structures i C (og records generelt) bidrager netop med dette.

I program 39.2 vises et alternativ til program 39.1, hvor vi har introduceret grupperingen af personnavn og de tre relevante CPR numre. Grupperingen hedder blot person. struct person skal forstås som en typedefinition.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>

typedef unsigned long CPR;

struct person {
  char *name;
  CPR cpr;
  CPR father;
  CPR mother;
};

int main(void) {

  struct person 
    baby = {"Paul", 2304031577, 1605571233, 2412671234},
    mother = {"Anna", 2412671234, 1605376789, 1201402468},
    father = {"Frank", 1605571233, 1111331357, 1212358642};

  printf("%s's mother and father is %s and %s\n", 
         baby.name, mother.name, father.name);

  
  return 0;
}
Program 39.2    Introduktion af structures - sammenhørende data om en person.

I main i program 39.2 erklærer vi variablene baby, mother og father af typen struct person. Vi ser også en direkte record-notation i tuborg klammer, helt analogt til den tilsvarende array-notation introduceret i program 21.3.

Ved indførelse af structures/records får vi en bedre strukturering af data

Alle data om en person kan håndteres som en helhed

 

39.4.  Structures i C (1)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

I dette afsnit viser vi den syntaktiske opbygning, og vi opregner et antal yderligere egenskaber af structures.


struct structure-tag{
 type1 field1;
 type2 field2;
 ...
 typen fieldn;
};
Syntaks 39.1    En struct type specifikation

  • Terminologi:

    • Structure tag name: Navnet efter struct.

    • Member: Variablene, som udgør bestanddelene af strukturen

  • Tilgang til et felt via en variabel, som indeholder en struct

    • variabel.felt

  • Tilgang til felt via en variabel som indeholder en pointer til en struct

    • variabel->felt

    • (*variabel).felt

Det er værd at bemærke tilgangen til et felt via en pointer til en struct. Operatoren -> befinder sig i den øverste prioritetsgruppe i operatortabellen i tabel 2.3.

Herunder giver vi en oversigt over de lovlige operationer, som kan udføres på structures.

  • Lovlige operationer structures:

    • Assignment af structures af samme type:    struct1 = struct2

      • Members assignes parvis til hinanden

    • Uddragning af addressen af en struct med & operatoren

    • Tilgang til members med dot notation og    ->    operatoren

  • Størrelsen af en struct

    • Brug af sizeof operatoren

    • En struct kan fylde mere en summen af felternes størrelse

Det er bemærkelsesværdigt, at man ikke i C kan sammenligne to structures strukturelt og feltvis, ala strukturel strengsammenligning i figur 28.1.

 

39.5.  Eksempel: Dato structure
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

I det første eksempel på en struct viser vi en dato, date, som primært er karakteriseret af egenskaberne (felterne) day, month, og year. Sekundært medtager vi også en ugedag, weekday. Vi siger undertiden af dette felt er redundant, da den kan afledes entydigt af day, month og year.

1
2
3
4
5
6
7
8
struct date {
  weekday day_of_week;
  int day;
  int month;
  int year;
};

typedef struct date date;
Program 39.3    En struct for en dato.

Vi viser struct date i en praktisk sammenhæng i program 39.4. Med rødt ser vi en funktion, date_before, som afgør om en dato d1 kommer før en dato d2. Bemærk at kroppen af funktionen date_before er ét stort logisk udtryk sammensat af en logisk or operator, jf. tabel 6.2. Alternativt kunne vi have programmeret kroppen af date_before med en if-else kæde. (jf. afsnit 8.5)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>

enum weekday {sunday, monday, tuesday, wednesday, thursday, 
              friday, saturday};
typedef enum weekday weekday;

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

typedef struct date date;

/* Is date d1 less than date d2 */
int date_before(date d1, date d2){
 return
  (d1.year < d2.year) ||
  (d1.year == d2.year && d1.month < d2.month) ||
  (d1.year == d2.year && d1.month == d2.month && d1.day < d2.day);
}  

int main(void) {

  date today = {thursday, 14, 4, 2005};
  date tomorrow = {friday, 15, 4, 2005};

  if (date_before(today, tomorrow))
    printf("OK\n");
  else printf("Problems\n");

  return 0;
}
Program 39.4    Et dato program med en funktion, date-before, der vurderer om en dato kommer før en anden dato.

I main funktionen kalder vi date_before med to konstruerede datoer. Vi forventer naturligvis at programmet udskriver OK.

 

39.6.  Eksempel: Bog structure
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

I program 39.5 ser vi en structure, der beskriver forskellige egenskaber af en bog. Ud over title, forfatter og publiseringsår repræsenterer vi hvorvidt bogen er en universitetslærebog. Vi har også en typedef, som navngiver struct book til book. Dette er helt analogt til de navngivninger, vi introducerede for enumeration typer i afsnit 19.3.

1
2
3
4
5
6
7
struct book {
  char *title, *author, *publisher;
  int publishing_year;
  int university_text_book;
};

typedef struct book book;
Program 39.5    Et eksempel på en struct for en bog.

Med blåt i program 39.6 ser vi igen struct book. Med brunt under denne viser vi en funktion, make_book, som laver og returnerer en bog på baggrund af parametre, der modsvarer de enkelte felter. Funktionen overfører og assigner altså blot informationerne til felterne i struct book. Læg mærke til, at den returnerede bog ikke er en pointer. Der er helt reelt tale om returnering af en lokal variabel, som er af typen struct book. Enkelt og lige til.

Med lilla vises en funktion, der via printf kan printe en bog på standard output (typisk skærmen). Med sort, og forneden i program 39.6 assignes b1 og b2 til resultaterne returneret fra kald af make_book. Variablen b3 assignes til en kopi af b2. Bid lige mærke i, at structure assignment involverer en feltvis kopiering af indholdet i en structure.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>

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

typedef struct book book;

book make_book(char *title, char *author, char *publisher, 
               int year, int text_book){
  book result;
  result.title = title; result.author = author;
  result.publisher = publisher; result.publishing_year = year;
  result.university_text_book = text_book;
 
  return result;
}

void prnt_book(book b){
  char *yes_or_no;

  yes_or_no = (b.university_text_book ? "yes" : "no"); 
  printf("Title: %s\n"
         "Author: %s\n"
         "Publisher: %s\n"
         "Year: %4i\n"
         "University text book: %s\n\n",
         b.title, b.author, b.publisher, 
         b.publishing_year, yes_or_no);
}

int main(void) {

  book b1, b2, b3;

  b1 = make_book("C by Disssection", "Kelley & Pohl", 
                 "Addison Wesley", 2001, 1);
  b2 = make_book("Pelle Erobreren", "Martin Andersen Nexoe",
                 "Gyldendal", 1910, 0);

  b3 = b2;
  b3.title = "Ditte Menneskebarn"; b3.publishing_year = 1917;

  prnt_book(b1);  prnt_book(b2);   prnt_book(b3);
  
  return 0;
}
Program 39.6    Et program som kan lave og udskrive en bog.

I den lilla del af program 39.6 bemærker vi, at kontrolstrengen af printf er brudt op i flere delstrenge (uden komma imellem). Disse bliver implicit sammensat til én streng. Generelt gælder i C at sådanne nabostrenge sammensættes implicit til én streng. Brug af denne konvention gør ofte vore programmer mere læselige.

 

39.7.  Structures ved parameteroverførsel
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Vi har allerede i program 39.6 set hvordan vi helt enkelt kan overføre og tilbageføre structures til/fra funktioner i C. Vi vil her understrege hvordan dette foregår, og vi vil observere hvordan det adskiller sig fra overførsel og tilbageførsel af arrays.

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

  • Structures:

    • Kan overføres som en værdiparameter (call by value parameteroverførsel)

    • Kan returneres fra en funktion

    • Det er mere effektivt at overføre og tilbageføre pointere til structures

  • Arrays:

    • Overføres som en reference (call by reference parameteroverførsel)

    • Returneres som en reference fra en funktion

C tilbyder udelukkende parameteroverførsel 'by value' (værdiparametre), jf. afsnit 12.7. Når vi overfører et array overfører vi altid en pointer til første element. Når vi overfører en structure kan vi overføre strukturen som helhed. Det indebærer en kopiering felt for felt både i parameteroverførsel, og ved returneringen (som f.eks. foretaget i program 39.6).

Som det illustreres i program 39.7 kan vi også overføre og tilbageføre structures som pointere. I program 39.7 overføres parameteren b til prnt_book pr. reference (som en pointer). Se afsnit 23.1. Funktionen make_book (på det blå sted) forsøger på at tilbageføre den konstruerede bog som en pointer. Versionen i program 39.7 virker dog ikke. Det gør derimod den tilsvarende funktion i program 39.8.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/* Incorrect program - see books-ptr.c for a better version */

#include <stdio.h>

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

typedef struct book book;

book *make_book(char *title, char *author, char *publisher, 
               int year, int text_book){
  static book result;
  result.title = title; result.author = author;
  result.publisher = publisher; result.publishing_year = year;
  result.university_text_book = text_book;
 
  return &result;
}

void prnt_book(book *b){
  char *yes_or_no;

  yes_or_no = (b->university_text_book ? "yes" : "no"); 
  printf("Title: %s\n"
         "Author: %s\n"
         "Publisher: %s\n"
         "Year: %4i\n"
         "University text book: %s\n\n",
         b->title, b->author, b->publisher, 
         b->publishing_year, yes_or_no);
}

int main(void) {

  book *b1, *b2;

  b1 = make_book("C by Disssection", "Kelley & Pohl", 
                 "Addison Wesley", 2001, 1);
  b2 = make_book("Pelle Eroberen", "Martin Andersen Nexoe",
                 "Gyldendal", 1911, 0);

  prnt_book(b1);
  prnt_book(b2);
  
  return 0;
}
Program 39.7    Et eksempel på overførsel og tilbageførsel af bøger per refererence - virker ikke.

Lad os indse, hvorfor make_book (det blå sted) i program 39.7 ikke virker tilfredsstillende. Den lokale book variabel er markeret som static (se afsnit 20.3.) Static markeringen bruges for at undgå, at result bogen udraderes når funktionen returnerer. Alle kald af make_book deler således result variablen, som overlever fra kald til kald. Når make_book kaldes gentagne gange vil der blive tilskrevet indhold til denne ene result variabel flere gange. Anden gang make_book kaldes (med 'Pelle Eroberen') overskrives egenskaberne af den først konstruerede bog ('C by Dissection').

I program 39.8 reparerer vi make_book problemet. På det røde sted ser vi forskellen. I stedet for at gøre brug af en lokal variabel allokerer vi dynamisk lager til bogen ved brug af malloc, jf. afsnit 26.2. Dermed afsættes lageret på heapen, og ikke på stakken af activation records. Endnu vigtigere i vores sammenhæng, for hvert kald af make_book allokeres der plads til bogen. Dette er - i en nødeskal - forskellen mellem denne version af make_book og versionen i program 39.7.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>

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

typedef struct book book;

book *make_book(char *title, char *author, char *publisher, 
               int year, int text_book){
  book *result;
  result = (book*)malloc(sizeof(book));
  result->title = title; result->author = author;
  result->publisher = publisher; result->publishing_year = year;
  result->university_text_book = text_book;
 
  return result;
}

void prnt_book(book *b){
  char *yes_or_no;

  yes_or_no = (b->university_text_book ? "yes" : "no"); 
  printf("Title: %s\n"
         "Author: %s\n"
         "Publisher: %s\n"
         "Year: %4i\n"
         "University text book: %s\n\n",
         b->title, b->author, b->publisher, 
         b->publishing_year, yes_or_no);
}

int main(void) {

  book *b1, *b2;

  b1 = make_book("C by Disssection", "Kelley & Pohl", 
                 "Addison Wesley", 2001, 1);
  b2 = make_book("Pelle Eroberen", "Martin Andersen Nexoe",
                 "Gyldendal", 1911, 0);

  prnt_book(b1);
  prnt_book(b2);
  
  return 0;
}
Program 39.8    Et eksempel på overførsel og tilbageførsel af bøger per reference - OK.

 

39.8.  Structures i structures
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Structures kan indlejres i hinanden. Dette betyder at et felt i en structure kan være en anden structure.

I program 39.9 viser vi eksempler på, hvordan structures kan indlejres i hinanden. Med rødt ser vi en point structure, der repræsenterer et punkt i planen, karakteriseret af x og y koordinater.

Med blåt ser vi først en rektangel structure, struct rect. Et rektangel repræsenteres i vores udgave ved to modstående hjørnepunkter p1 og p2. Vi viser også en alternativ rektangel structure, struct another_rect. I denne rektangel structure har vi indlejret to anonyme punkt structures, i stedet for at gøre brug af struct point. På alle måder er struct rect 'smartere' end struct another_rect.

Med sort, forneden i program 39.9 viser vi en main funktion, der statisk allokerer to punkter pt1 og pt2, og to rektangler r og ar. Dernæst viser vi, hvordan egenskaberne af de indlejrede structures kan tilgås via dot notation (se afsnit 39.2). Læg mærke til, at dot operatoren associerer fra venstre mod højre, jf. tabel 2.3. Det betyder at ar.p1.x betyder (ar.p1).x og ikke ar.(p1.x).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>

struct point {
  int x;
  int y;
};

struct rect {
  struct point p1;
  struct point p2;
};

struct another_rect {
  struct {
    int x;
    int y;
  }  p1;
  struct {
    int x;
    int y;
  }  p2;
};

int main(void) {

  struct point pt1, pt2;
  struct rect r;
  struct another_rect ar;

  pt1.x = 5; pt1.y = 6;
  pt2.x = 17; pt2.y = 18;

  r.p1 = pt1; r.p2 = pt2;

  ar.p1.x = 1;   ar.p1.y = 2;
  ar.p2.x = 10;  ar.p2.y = 12;

  ar.p1 = pt1;  /* error: incompatible types */
  ar.p2 = pt2;  /* error: incompatible types */

  return 0;
}
Program 39.9    Et udvidet eksempel på structures i structures.

Genereret: Onsdag 7. Juli 2010, 15:13:02
Thema indholdsfortegnelse -- Tastaturgenvej: 'u'  Forrige tema i denne lektion -- Tastaturgenvej: 'p'  Næste slide i denne lektion -- Tastaturgenvej: 'n'