C - 8: Zusammengesetzte Datenstrukturen

8 Zusammengesetzte Datenstrukturen

8.1 Strukturen
8.1.1 Vereinbarung von Strukturen
8.1.2 Zugriff auf Strukturelemente
8.1.3 Rekursive Strukturen
8.2 Varianten (Unions)
8.3 Bitfelder
8.4 Aufzählungen
8.5 "typedef"

8.1 Strukturen

Während Vektoren eine Zusammenfassung von Objekten gleichen Typs sind, handelt es sich bei einer Struktur um eine Zusammenfassung von Objekten möglicherweise verschiedenen Typs zu einer Einheit (vergl. record in PASCAL). Die Verwendung von Strukturen bietet Vorteile bei der Organisation komplizierter Daten. Beispiele sind Personaldaten (Name, Adresse, Gehalt, Steuerklasse, usw.) oder Studentendaten (Name, Adresse, Studienfach, Note).

8.1.1 Vereinbarung von Strukturen

Strukturen werden mit Hilfe des Schlüsselwortes struct vereinbart

struct Strukturname { Komponente(n) } Strukturvariable(n) Init. ;

Strukturname ist optional und kann nach seiner Definition für die Form (den Datentyp) dieser speziellen Struktur verwendet werden, d.h. als Abkürzung für die Angaben in den geschweiften Klammern. Strukturkomponenten werden wie normale Variable vereinbart. Struktur- und Komponentennamen können mit anderen Variablennamen identisch sein ohne daß Konflikte auftreten, da sie vom Compiler in einer separaten Tabelle geführt werden.

Durch die Angabe einer (oder mehrerer) Strukturvariablen wird diese Struktur erzeugt (d.h. Speicherplatz dafür bereitgestellt). Strukturvereinbarungen ohne Angabe einer Strukturvariablen legen nur die Form (den Prototyp) der Struktur fest.

Strukturen können wie Vektoren nur initialisiert werden, wenn sie global oder static sind.

Beispiele für Strukturvereinbarungen:

struct datum { /* legt die Form der Struktur datum fest */ int tag; int monat; int jahr; int jahrestag; char mon_name[4]; }; struct datum { /* erzeugt die Strukturen geb_dat */ int tag; /* und heute mit der Form datum */ int monat; int jahr; int jahrestag; char mon_name[4]; } geb_dat, heute; struct datum geb_dat,heute; /* erzeugt ebenfalls die */ /* Strukturen geb_dat und */ /* heute mit der Form datum */ struct datum heute = {26,9,1987,0,"jun"}; /* erzeugt */ /* die Struktur heute der */ /* Form datum mit den ange- */ /* gebenen Initialisierungen */

Strukturen können als Elemente ebenfalls wieder Strukturen enthalten (allerdings nicht sich selbst) und Strukturen können zu Vektoren zusammengefaßt werden:

struct kunde { char name[NAMLAE]; char adresse[ADRLAE]; int kund_nr; struct datum liefer_dat; struct datum rech_dat; struct datum bez_dat; }; struct kunde kunde1, kunde2, ... ; struct kunde kunden[KUNANZ];

8.1.2 Zugriff auf Strukturelemente

Mit Strukturen sind nur 2 Operationen möglich:

a) Zugriff auf Strukturelemente (direkt und indirekt)

b) (Anfangs-)Adresse bestimmen

Die Adresse wird wie gewohnt mit dem & Operator bestimmt. Für den Elementzugriff gibt es zwei eigene Operatoren. Der direkte Zugriff wird dabei mit dem Punktoperator . nach folgendem Schema durchgeführt:

Strukturvariable.Komponente

Beispiele für direkten Zugriff:

geb_dat.jahr heute.tag heute.mon_name[0] kunde1.kund_nr kunden[3].name kunde2.liefer_dat.monat

Für den indirekten Zugriff muß die Adresse der Struktur in einem dafür geeigneten Zeiger stehen. Dann kann mit Hilfe des Zeigeroperators -> (Minuszeichen Größerzeichen) auf die Strukturelemente zugegriffen werden:

Strukturzeiger->Komponente

Beispiele für indirekten Zugriff:

struct datum *pdat; struct kunde *pkun; pdat = &heute; pkun = &kunden[4]; pdat->tag pdat->mon_name[1] pkun->adresse pkun->rech_dat.monat

Bei diesen Zugriffen muß man immer den Vorrang und die Assoziativität der Operatoren . und -> beachten (höchster Vorrang).

Beispiele für Operatorvorrang:

struct { int x; int *y; } *p; ++p->x /* x = x + 1, da implizit ++(p->x) */ (++p)->x /* p zeigt auf nächste Struktur, */ dann Zugriff auf x */ (p++)->x /* Zugriff auf x, dann p auf nächste Struktur */ p++->x /* wie eben, Warum? */

Die gerade gezeigten Beispiele für Ausdrücke würden in einem "echten" Programm allerdings zu schwerwiegenden Laufzeitfehlern führen. Warum?

Es wurde zwar ein Zeiger auf eine Struktur vereinbart, nicht aber die Struktur selbst, für die folglich auch kein Speicherplatz bereitgestellt wird. Daher ist sie natürlich auch nicht mit Werten vordefiniert.

Merke: Mit Zeigern kann man nur arbeiten, wenn sie auch auf eine "vernünftige" Stelle zeigen.

Anders als Felder kann man bei modernen C-Compilern, insbesondere ANSI-C, Structs aufeinander zuweisen. Structs sind also gütige L-Values. Beispiel:

#define N 32 struct _s { char s[N]; } s1, s2; char c1[N], c2[N]; strcpy(c1, "hallo"); /* Geht immer */ strcpy(s1.s, "hallo"); c2 = c1; /* FALSCH, Feld ist nicht L-Value */ s2 = s1; /* RICHTIG ! Struct ist L-Value */

Beispiel für Anwendung von structs: Realisierung von Tag im Jahr bestimmen mit einer Struktur (Vgl. Abschnitt 7 und Beispielprogramm p7-1.c):

/* 1. Möglichkeit mit alter Funktion day_of_year */ struct datum d; d.jahrestag = day_of_year(d.jahr, d.monat, d.tag); /* 2. Möglichkeit mit modifizierter Funktion */ struct datum rech_dat; rech_dat.jahrestag = day_of_year(&rech_dat); /* Tag im Jahr aus Monat und Tag bestimmen */ int day_of_year(struct datum *pd) { int i, leap, day; day = pd->tag; leap = pd->jahr % 4 == 0 && pd->jahr % 100 != 0 || pd->jahr % 400 == 0; for (i = 1; i < pd->monat; i++) day += day_tab[leap][i]; return (day); } /* day_of_year() */ /* Monat und Tag aus Tag im Jahr bestimmen */ void month_day(struct datum *pd) { int i, leap; leap = pd->jahr % 4 == 0 && pd->jahr % 100 != 0 || pd->jahr % 400 == 0; pd->tag = pd->jahrestag; for (i = 1; pd->tag > day_tab[leap][i]; i++) pd->tag -= day_tab[leap][i]; pd->monat = i; } /* month_day() */

Beispielprogramm p8-1.c

/* * p8-1.c * Beispielprogramm 1, Abschnitt 8 * Vorkommen reservierter Woerter zaehlen */ #include <stdio.h> #include <string.h> #define MAXWORD 20 #define NKEYS (sizeof(keytab) / sizeof(struct key)) #define LETTER 'a' #define DIGIT '0' struct key { /* global, daher initialisierbar */ char *keyword; int keycount; } keytab[] = { "auto", 0, "break", 0, "case", 0, "char", 0, "const", 0, "continue", 0, "default", 0, "do", 0, "double", 0, "else", 0, "enum", 0, "extern", 0, "float", 0, "for", 0, "goto", 0, "if", 0, "int", 0, "long", 0, "register", 0, "return", 0, "short", 0, "signed", 0, "sizeof", 0, "static", 0, "struct", 0, "switch", 0, "typedef", 0, "union", 0, "unsigned", 0, "void", 0, "volatile", 0, "while", 0, }; int binary(char *, struct key[], int); int getword(char *, int); int type(int); void main(void) { int n, t; char word[MAXWORD]; while ((t = getword(word, MAXWORD)) != EOF) if (t == LETTER) if ((n = binary(word, keytab, NKEYS)) >= 0) keytab[n].keycount++; for (n = 0; n < NKEYS; n++) if (keytab[n].keycount > 0) printf("%4d %s\n", keytab[n].keycount, keytab[n].keyword); } /* main() */ /* word in tab[0],...,tab[n-1] finden */ int binary(char *word, struct key tab[], int n) { int low, high, mid, cond; low = 0; high = n - 1; while (low <= high) { mid = (low + high) / 2; if ((cond = strcmp(word, tab[mid].keyword)) < 0) high = mid - 1; else if (cond > 0) low = mid + 1; else return(mid); } return(-1); } /* binary() */ #define getch() getc(stdin) #define ungetch(c) ungetc(c, stdin) /* naechstes Wort aus der Eingabe holen */ int getword(char *w, int lim) { int c, t; if (type(c = *w++ = getch()) != LETTER) { *w = '\0'; return(c); } while (--lim > 0) { t = type(c= *w++ = getch()); if (t != LETTER && t != DIGIT) { ungetch(c); break; } } *(w-1) = '\0'; return(LETTER); } /* getword() */ /* Typ eines ASCII Zeichens liefern */ int type(int c) { if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') return(LETTER); else if (c >= '0' && c <= '9') return(DIGIT); else return(c); } /* type() */

8.1.3 Rekursive Strukturen

Rekursive Strukturen sind Strukturen, die zumindest ein Element enthalten, das auf eine andere Struktur gleichen Typs verweist. Sie werden sehr oft benötigt (z.B. verkettete Listen, Datenbäume). Eine Struktur kann sich zwar nicht selbst enthalten, wohl aber einen Zeiger auf eine Struktur gleichen Typs.

struct datum { int tag; int monat; int jahr; int jahrestag; char mon_name[4]; struct datum heute; /* FALSCH */ }; struct datum { int tag; int monat; int jahr; int jahrestag; char mon_name[4]; struct datum *heute; /* RICHTIG */ };

Zur Illustration soll das folgende Beispielprogramm für einen Binärbaum dienen.

Beispielprogramm p8-2.c

/* * p8-2.c * Beispielprogramm 2, Abschnitt 8 * Haeufigkeit von Woertern zaehlen */ #include <stdio.h> #include <string.h> #include <stdlib.h> #define MAXWORD 32 #define LETTER 'a' #define DIGIT '0' /* binaerer Baum */ struct tnode { char *word; /* zeigt auf den Text */ int count; /* Haeufigkeit */ struct tnode *left; /* linker Nachfolger */ struct tnode *right; /* rechter Nachfolger */ }; struct tnode *tree(struct tnode *, char *); void treeprint(struct tnode *p); struct tnode *talloc(void); char *strsave(char *); int getword(char *, int); int type(int); void main(void) { struct tnode *root; char word[MAXWORD]; int t; root = NULL; while ((t = getword(word, MAXWORD)) != EOF) if (t == LETTER) root = tree(root, word); treeprint(root); } /* main() */ /* w bei oder nach p einfuegen */ struct tnode *tree(struct tnode *p, char *w) { int cond; if (p == NULL) { /* ein neues Wort */ p = talloc(); /* einen neuen Knoten anlegen */ p->word = strsave(w); p->count = 1; p->left = p->right = NULL; } else if ((cond = strcmp(w, p->word)) == 0) p->count++; /* Wort wird wiederholt */ else if (cond < 0) /* kleiner, links darunter */ p->left = tree(p->left, w); else /* groesser, rechts darunter */ p->right = tree(p->right, w); return(p); } /* tree() */ /* Baum p rekursiv ausgeben */ void treeprint(struct tnode *p) { if (p != NULL) { treeprint(p->left); printf("%4d %s\n",p->count, p->word); treeprint(p->right); } } /* treeprint() */ /* Platz für eine Struktur besorgen */ struct tnode *talloc(void) { return((struct tnode *) calloc(1, sizeof(struct tnode))); } /* talloc() */ /* Zeichenkette s in Sicherheit bringen */ char *strsave(char *s) { char *p; if ((p = (char *) malloc(strlen(s) + 1)) != NULL) strcpy(p, s); return (p); } /* strsave() */ #define getch() getc(stdin) #define ungetch(c) ungetc(c, stdin) /* naechstes Wort aus der Eingabe holen */ int getword(char *w, int lim) { int c, t; if (type(c = *w++ = getch()) != LETTER) { *w = '\0'; return(c); } while (--lim > 0) { t = type(c= *w++ = getch()); if (t != LETTER && t != DIGIT) { ungetch(c); break; } } *(w-1) = '\0'; return(LETTER); } /* getword() */ /* Typ eines ASCII Zeichens liefern */ int type(int c) { if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') return(LETTER); else if (c >= '0' && c <= '9') return(DIGIT); else return(c); } /* type() */

8.2 Varianten (Unions)

Während eine Struktur mehrere Variablen (verschiedenen Typs) enthält, ist eine Variante eine Variable, die (aber natürlich nicht gleichzeitig) Objekte verschiedenen Typs speichern kann. Verschiedene Arten von Datenobjekten können so in einem einzigen Speicherbereich maschinenunabhängig manipuliert werden. (Eine solche Eigenschaften ist zum Beispiel sehr nützlich beim Aufbau von Symboltabellen in Übersetzern.)

Eine Variante wird durch das Schlüsselwort union vereinbart. Die weitere Syntax ist wie bei struct.

union u_tag { /* Uniontyp u_tag */ int ival; float fval; char *pval; } uval; /* Unionvariable uval */

Im Falle einer Variante (Union) muß man sich natürlich im Programm in einer anderen Variablen merken, welcher Datentyp in der Variante gerade abgelegt ist.

Beispiel:

#define INT 1 #define FLOAT 2 #define STRING 3 if (utype == INT) printf("%d\n", uval.ival); else if (utype == FLOAT) printf("%f\n", uval.fval); else if (utype == STRING) printf("%s\n", uval.pval); else printf("bad type %d in utype\n", utype);

Eine Struktur kann innerhalb einer Varianten vorkommen und umgekehrt:

struct { char *name; int flags; int utype; union { int ival; float fval; char *pval; } uval; } symtab[NSYM]; #define INT 1 #define FLOAT 2 #define STRING 3 if (symtab[i].utype == INT) printf("%d\n", symtab[i].uval.ival); else if (symtab[i].utype == FLOAT) printf("%f\n", symtab[i].uval.fval); else if (symtab[i].utype == STRING) printf("%s\n", symtab[i].uval.pval); else printf("bad type %d in utype\n", symtab[i].utype);

Ein wichtiges Beispiel für Struktur- und Variantenvereinbarung ist die Definition der Strukturen WORDREGS und BYTEREGS sowie der Varianten REGS für MS-DOS Funktionsaufrufe:

struct WORDREGS { unsigned int ax; unsigned int bx; unsigned int cx; unsigned int dx; unsigned int si; unsigned int di; unsigned int cflag; }; struct BYTEREGS { unsigned char al,ah; unsigned char bl,bh; unsigned char cl,ch; unsigned char dl,dh; }; union REGS { struct WORDREGS x; struct BYTEREGS h; }; union REGS inregs, outregs; inregs.x.bx = 0x12; /* BX Register auf Hex 12 stellen */ inregs.h.ah = 0x10 /* AH Register auf Hex 10 stellen */ c = outregs.x.cx /* CX Register nach c kopieren */

8.3 Bitfelder