8.1.1 Vereinbarung von Strukturen
8.1.2 Zugriff auf Strukturelemente
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.
Beispielprogramm P8-1.C
/* Realisierung von Tag im Jahr bestimmen mit
einer Struktur */
/* 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);
day_of_year(struct datum *pd)
/* Tag im Jahr aus Monat und Tag bestimmen */
{
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);
}
/* Dasselbe für month_day */
month_day(struct datum *pd)
/* Monat und Tag aus Tag im Jahr */
{
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;
}
Beispielprogramm P8-2.C
/* Vorkommen reservierter Woerter zaehlen */
#include <stdio.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[] = {
"break",0,
"case",0,
"char",0,
"continue",0,
/* ... */
"unsigned",0,
"while",0
};
main() /* reservierte Worte in C zaehlen */
{
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;
}
/* word in tab[0],...,tab[n-1] finden */
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);
}
/* naechstes Wort aus der Eingabe holen */
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);
}
/* Typ eines ASCII Zeichens liefern */
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);
}
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-3.C
/* binaerer Baum */
struct tnode {
char *word; /* zeigt auf den Text */
int count; /* Haeufigkeit */
struct tnode *left; /* linker Nachfolger */
struct tnode *right; /* rechter Nachfolger */
};
#define MAXWORD 20
main() /* Haeufigkeit von Worten zaehlen */
{
struct tnode *root, *tree();
char word[MAXWORD];
int t;
root = NULL;
while ((t = getword(word,MAXWORD)) != EOF)
if (t == LETTER)
root = tree(root,word);
treeprint(root);
}
/* w bei oder nach p einfuegen */
struct tnode *tree(struct tnode *p,char *w)
{
struct tnode *talloc();
char *strsave();
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);
}
/* Baum p rekursiv ausgeben */
treeprint(struct tnode *p)
{
if (p != NULL) {
treeprint(p->left);
printf("%4d %s\n",p->count,p->word);
treeprint(p->right);
}
}
/* Platz für eine Struktur besorgen */
struct tnode *talloc()
{
char *alloc();
return((struct tnode *) alloc(sizeof(struct tnode)));
}
/* Zeichenkette s in Sicherheit bringen */
char *strsave(char *s)
{
char *p, *alloc();
if (p=alloc(strlen(s)+1)) != NULL)
strcpy(p,s);
return (p);
}
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:
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];
symtab[i].uval.ival /* ival */
*symtab[i].uval.pval /* 1. Zeichen von pval */
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 */
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!
In neueren Implementationen von 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 also den Wert 9.
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 Protabilitä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 */