|
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
Zur platzsparenden Abspeicherung von Daten werden in bestimmten
Fällen mehrere Objekte in einem Maschinenwort zusammengefaßt.
Ein Objekt ist dann durch ein oder mehrere Bits diese Maschinenwortes
repräsentiert (Beispiele: Initialisierungwerte für peripere
Bausteine, Tabelle der ASCII-Zeichen mit ihren Eigenschaften (alpha,
digit, hexdigit, print, usw.))
Für die Verarbeitung solcher Daten stehen die Operatoren
für die bitweisen logischen Verknüpfungen zur Verfügung.
Bestimmte Ausdrücke werden dabei häufig verwendet:
#define ALPHA 01
#define DIGIT 02
#define HEX 04
int attr;
attr |= ALPHA | HEX; /* setzt Bits ALPHA und HEX */
attr &= ~(ALPHA | HEX); /* löscht Bits ALPHA und HEX */
if ((attr & (ALPHA|HEX)) == 0) /* genau dann wahr, wenn */
/* ALPHA und HEX gleich 0 sind */
|
Alternativ dazu bietet C die Möglichkeit, Bitwerte in Maschinenworten
direkt zu definieren. Dazu wird die struct-Anweisung in
abgewandelter Form verwendet:
struct {
unsigned int is_alpha: 1; /* Bit 0 */
unsigned int is_digit: 1; /* Bit 1 */
unsigned int is_hex: 1; /* Bit 2 */
: 3; /* 3 Bit freilassen */
unsigned int zei_satz: 2; /* Bits 6 und 7 */
} attr;
|
Die Bitfeldvariable ist vom Typ int. Passen nicht alle
Bitfelder in ein int Objekt, so wird dieses bis zur nächsten
int Grenze erweitert. Die Zahl hinter dem Doppelpunkt ist
die Anzahl der Bits dieser Komponente. Die Angabe nur eines Doppelpunktes
ohne Komponentennamen ist erlaubt (namenlose Komponente) und kann
als Platzhalter verwendet werden. Eine Bitbreite von 0 erzwingt
die Fortsetzung des Bitfeldes auf der nächsten int
Grenze.
Der Zugriff erfolgt wie bei Strukturen, die Komponenten sind hier
kleine ganze Zahlen ohne Vorzeichen. Die 3 Bitmanipulationen mit
bitweisen logischen Operatoren von oben kann man mit Bitfeldern
so formulieren:
attr.is_alpha = attr.is_hex = 1;
attr.is_alpha = attr.is_hex = 0;
if ((attr.is_alpha == 0) && (attr.is_hex == 0))
...
|
Achtung: Bitfelder haben keine Adressen und es gibt
keine Vektoren von Bitfeldern!
8.4 Aufzählungen
In neueren Implementationen von C, insbesondere ANSI-C
ist auch der Datentyp Aufzählung
realisiert. Eine Aufzählungsvereinbarung wird durch das Schlüsselwort
enum eingeleitet, es folgt der Aufzählungstypname,
die in geschweiften Klammern eingeschlossen Aufzählungsliste
und schließlich die Aufzählungsvariable, die eine der
in der Aufzählungliste genannten Konstanten als Wert haben
kann.
enum Aufzählungstyp { Aufzählungsliste } Aufzählungsvar.;
|
Beispiele:
enum farben { gelb, gruen, blau, rot} farbe;
enum farben col, *pcol;
|
Die Werte der Konstanten beginnen links bei 0 und erhöhen
sich nach rechts jeweils um 1 (gelb=0, gruen=1, blau=2, usw.).
Einer Aufzählungskonstanten kann aber auch direkt eine int
Konstante zugewiesen werden, die Werte der weiter rechts stehenden
Konstanten werden dann wieder je um 1 von diesem Wert erhöht.
enum farben { gelb, gruen = 3, blau, rot, schwarz = 8, braun};
|
braun hat damit den Wert 9.
8.5 "typedef"
Mit typedef kann man neue Datentypnamen definieren
(Nicht aber neue Datentypen!). typedef ist #define ähnlich,
aber weitergehender, da erst vom Compiler verarbeitet und nicht
nur einfacher Textersatz. Die Anwendungen von typedef liegen darin,
ein Programm gegen Portabilitätsprobleme abzuschirmen und
für eine bessere interne Dokumentation
Beispiel für Portabilitätsprobleme (int):
typedef int LENGTH;
typedef char *STRING;
LENGTH len, maxlen;
LENGTH *lengths[];
STRING p, alloc();
|
Beispiel für interne Dokumentation:
typedef struct tnode {
char *word;
int count;
struct tnode left*;
struct tnode *right;
} TREENODE, *TREEPTR;
typedef int (*PFI)(); /* das kann der Präprozessor nicht */
/* auswerten, Verwandschaft mit */
/* Prototyping bei Funktionen */
/* PFI ist der Datentyp für einen */
/* Zeiger auf eine Funktion, die */
/* ein int Resultat liefert */
|
zurück zum Inhaltsverzeichnis
|
|