8. Die Klassischen Datenstrukturen

8.1 Was sind Datenstrukturen?

Eine Datenstruktur ist ein Mittel für die Speicherung von Informationen. Daten, in einer Beziehung zueinander stehen, sollten ihrer Zusammengehörigkeit nach eingeordnet (d.h. gespeichert) werden. Da diese Datenstrukturen - im Gegensatz zu den sog. statischen Datenstrukturen, wie Reihungen oder Strukturen, die durch Datendeklarationen vom Compiler zugeordnet werden - zur Programmlaufzeit aufgebaut werden, bezeichnet man sie auch als dynamische Datenstrukturen. Etwas genauer: Im Gegensatz zu den statischen Datenstrukturen, die am Anfang eines Blocks vom Laufzeitsystem zugeteilt werden, benötigen dynamische Datenstrukturen explizite Speicherverwaltung.

8.2 Rekursive Datenstrukturen

In C ist es möglich eine Datenstruktur zu erklären, die auf denselben Datenstrukturtyp zeigt. Dadurch können beliebig viele Strukturen miteinander verkettet werden:

struct Knoten{
   int   Data1;    /*Normales Feld*/
   char *Data2;
   struct Knoten *Naechster;
   /*Verweis auf eine weitere Struktur "Knoten"*/
};

Die Zeigervariable Naechster enthält normalerweise die Adresse des nächsten Listenelements oder NULL, wie Abb.8.1 zeigt. Der allgemeine Zeigerwert NULL wird verwendet, um das Ende der Liste anzugeben und ist der einzige Wert, der mit jedem Zeiger verwendet werden darf.

**Abbildung 8.1:** Knotenelement einer Liste
$\includegraphics[width=5cm]{Drawing8_1}$

Beispiel:

Die Anweisungen

{
  struct Knoten s,t,u;
  struct Knoten *Liste;
  s.Data1 = 1; s.Data2 = "Alboin";
  t.Data1 = 2; t.Data2 = "Gisulf";
  u.Data1 = 3; u.Data3 = "Theodolinda";
}

definieren 3 alleinstehende Knoten, d.h. die keine Beziehung zueinander haben. Die Verkettung wird durch die Anweisungen

s.Naechster = &t; t.Naechster = &u; u.Naechster = NULL;
Liste = &s;

ausgeführt Die dadurch entstandene Listenstruktur wird in Abb.8.2 gezeichnet.

**Abbildung 8.2:** Eine Verkettete Liste
$\includegraphics[width=11cm]{Drawing8_2}$

Bemerkung

Statt statisch erklärter Variablen werden normalerweise Listenelemente durch malloc() zugeteilt. Der Vorteil dabei ist klar: Listen werden dynamisch, d.h. nach Bedarf, verwaltet.

Beispiel:

Man kann z.B. einen Knoten in die obige Liste (etwas umständlich) einfügen:

s.Naechster = (struct Knoten *)malloc(sizeof(struct Knoten));
s.Naechster.Data1 = 4; s.Naechster.Data2 = "Childebert";
s.Naechster.Naechster = t;

Das Ergebnis sieht man nun in Abb.8.3.

**Abbildung 8.3:** Einfügen Knoten ``Childebert''
$\includegraphics[width=12cm]{Drawing8_3}$

Die obigen Listenoperationen werden etwas übersichtlicher, wenn man eine zusätzliche Zeigervariable als Hilfsvariable heranzieht:

struct Knoten *KnotenZeiger;
KnotenZeiger = (struct Knoten*)malloc(sizeof(struct Knoten));
KnotenZeiger->Naechster = s.Naechster;
s.Naechster = KnotenZeiger;

Um mit Listenstrukturen konsequent umzugehen, empfiehlt es sich eine Header - Datei `list.h' zu definieren und mittels der Include - Anweisung

#include "list.h"

im Programm zu verwenden:

(*) typedef ... DATA;   /*Datentyp nach Bedarf hier*/
    struct Knoten{
         DATA d;
         struct Knoten *Naechster;
    };
    typedef struct Knoten ELEMENT;
    typedef ELEMENT *LIST_POINTER;

Will man, z.B. Datenfelder wie in den obigen Beispielen, so setze man statt (*):

typedef struct {
    int   Data1;
    char *Data2;
   } DATA;

und im Verwendungsprogramm:

LISTPOINTER Header,p;
{
  Header = (LISTPOINTER)malloc(sizeof(ELEMENT));
  Header->d.Data1 = 1;
  Header->d.Data2 = "Alboin";
  Header->Naechster = NULL;
  ...
}

Diese Art Operation will man allerdings nicht im Anwendungsprogramm definieren, sondern im Header - Datei list.h schreiben, um dem Anwender diese Art Details zu ersparen.

8.3 Listenstrukturen

8.3.1 Verkettete Listen

Man will folgende Operationen mit verketteten Listen implementieren:

Liste erzeugen
Suchen eines Elements der Liste
Einfügen eines Elements in die Liste
Löschen eines Elements aus der Liste

Einfügen

In Abb.8.4 wird die Listenstruktur vor and nach der Einfügungsoperation des Knotens ``Grasulf'' nach ``Ansfrit'', aber vor ``Grimoald'' gezeigt.

**Abbildung 8.4:** Einfügen des Knoten ``Grasulf'' in die verkettete List
$\includegraphics[width=12cm]{Drawing8_4}$

Wenn q auf den einzufügenden Knoten zeigt und tt p auf den Knoten in der Liste, wonach der erste der beiden eingefügt werden sollte, zeigt, schreibt man die Funktion folgendermaßen:

void einfuegen( LISTPOINTER p, LISTPOINTER q)
{
  q->Naechster = p->Naechster;
  p->Naechster = q;
}

Problem:

Diese Funktion funktioniert nicht, wenn die Liste leer ist, d.h. p = NULL;. Der Zugriff auf das Naechster - Feld des nicht existierenden Knotens führt sogar zum Programmabsturz!

void einfuegen( LISTPOINTER *p, LISTPOINTER *q)
{
  if (*p == NULL) *p = *q;
  else {
        (*q)->Naechster = (*p)->Naechster;
        (*p)->Naechster = *q;
        }
}

8.3.2 Queues (Schlangen)

Wie Abb.8.5 zeigt, ist eine Schlange (oder engl. Queue) eine verkettete Liste mit zwei Zeigern: VORN zeigt auf den ersten Knoten und HINTEN auf den letzten. Einfügen wird hinten, Löschen vorne ausgeführt. Aus diesem Grund wird eine Schlange FIFO - Struktur (First In First Out) genannt.

**Abbildung 8.5:** Struktur einer Schlange
$\includegraphics[width=8cm]{Drawing8_5}$

Wie bei allgemeinen Listen wird hier eine Header - Datei mit Namen `queue.h' erstellt, die die relevanten Schlangendefinitionen enthält:

#include "list.h"
  typedef QUEUEELEMENT ELEMENT;
  typedef LISTPOINTER QUEUEPOINTER;
  QUEUEPOINTER VORN;
  QUEUEPOINTER HINTEN;

Dann werden folgende Operationen für eine Schlangenstruktur erlaubt:

Schlange initialisieren:
$\begin{boxedminipage}[t]{5cm} {\tt VORN = HINTEN = NULL;} \end{boxedminipage}$
Schlange mit 1 Knoten initialisieren. Wenn dataPtr auf eine Variable vom Typ DATA zeigt, wird die Schlange durch nachfolgenden Code mit einem Knoten initialisiert:

$\begin{boxedminipage}[t]{12.5cm} \begin{verbatim}VORN = HINTEN = (QUEUEPOINTER... ...)); VORN->d = *dataPtr; VORN->Naechster = NULL;\end{verbatim}\end{boxedminipage}$
Element aus einer Schlange entfernen. Diese Funktion gibt eine Struktur des Typs DATA zurück:

$\begin{boxedminipage}[t]{12cm} \begin{verbatim}if (VORN == NULL) { fprintf(std... ...ORN->Naechster; free(where); return temp; }\end{verbatim}\end{boxedminipage}$
Element in eine Schlange einfügen. Als Parameter hat diese Funktion einen Zeiger dataPtr auf Speicherzellen des Typs DATA.

$\begin{boxedminipage}[t]{13cm} \begin{verbatim}if (VORN == NULL) { VORN = (Q... ...EN->d = *dataPtr; HINTEN->Naechster = NULL; }\end{verbatim}\end{boxedminipage}$

Unter der Annahme, daß der Grunddatentyp wie oben ist, kann man im Anwenderprogramm z.B. schreiben

#include "queue.h"
int main()
{
  DATA GothenKnoten;
  SchlangeInit();
  GothenKnoten.Data1 = 25;
  GothenKnoten.Data2 = "Theodohad";
  SchlangeInsert(GothenKnoten);
  ...
}

8.3.3 Stacks

**Abbildung 8.6:** Arbeitsweise einer Stackstruktur
$\includegraphics[width=8cm]{Drawing8_6}$

Im Gegensatz zu Schlangen haben Stacks nur einen internen Zeiger SP (für ,, Stackpointer``). Siehe Abb.8.6 für die Darstellung der Stackstruktur. Einfügen und Entfernen finden dort statt. Die Einfügungsoperation heißt bei Stacks ,,push`` und Entfernung heißt ,,pop``. Auch hier gibt es vier Grundoperationen:

Stack initialisieren: void initStack()
Test, ob Stack leer ist: int istLeer()
Element vom Typ DATA im Stack einfügen: void push(DATA)
Element vom Typ DATA vom Stack eintfernen: DATA pop()

Die Implementierung des Stacktyps ist im nachfolgenden Programmteil angegeben. Auch dieser Programmabschnitt ist in eine Header - Datei `stack.h' zu schreiben:

#include <stdlib.h>
#ifndef NULL
#define NULL 0
#endif

typedef ...  DATA;

struct StackElement {
   DATA       d;
   struct StackElement *next;
};

typedef struct StackElement STACKELEMENT;
typedef STACKELEMENT *STACK_POINTER;              
STACK_POINTER SP;                   /*good for one stack*/
/* Now some typical stack operations */

int istLeer()
{
   return (SP == NULL);
}

DATA pop()
{
  DATA temp;
  STACK_POINTER where;
  if (!istLeer())
  {
     temp = SP->d;
     where = SP;
     SP = SP->next;
     free(where);
     return temp;
  }
  else{
     printf("Stack is empty!");
     exit(1);
     }
}

void push (DATA x)
{
  STACK_POINTER temp;
  temp = (STACK_POINTER)malloc(sizeof(STACKELEMENT));
  temp->d = x;
  temp->next = SP;
  SP = temp;
}

void init_stack()
{
  SP = NULL;
}

Anwendung: Umgekehrte Polnische Notation

Eine interessante und nicht ganz triviale Anwendung einer Stackstruktur ist das Herstellen eines Programms, das wie ein Taschenrechner, die umgekehrte polnische Notation für numerische Ausdrücke verwendet. Dies bedeutet vor allem, daß eine arithmetische Operation als erstes durch ihre (2) Operanden und dann durch die eigentliche Operation bezeichnet wird. Zum Beispiel, statt 5 + 4 zu schreiben, schreibt man 54 +. Da jeder Operand das Ergebnis einer Auswertung eines anderen polnischen Ausdrucks sein kann, wird der Ausdruck von links nach rechts ausgewertet und braucht daher keine Klammern. Z. B. der (infix) Ausdruck

(5 + 4)*20 - 6

wird

5 4 + 20 * 6 -

geschrieben. Während auf diese Weise verfahren wird, füge man einen Operand auf den Stack und falls einem Operator begegnet wird, wird dieser auf die beiden obersten Elemente des Stacks angewandt, dann entfernt und schließlich das Ergebnis der Operation in den Stack eingefügt. Hier wird eine Struktur vom Typ DATA folgendermaßen dargestellt:

typedef struct{
   enum {operator, value} type;
   union {
     int val;
     char op;
   } field;
} DATA;

Also wird jede Komponente eines Ausdrucks entweder eine ganze Zahl oder ein Operand `+', `-', `*' oder `/'. Der Eingabewert `0' bedeutet: `Ein Operand folgt' und `1' heißt: 'Eine Operation folgt'.

#include <stdio.h>
#include "stack.h"

const int max = 25;
DATA polish_exp[25];
int count = 0;

void read_polish()
{
  char str[max];
  int intvalue = 0,i;
  printf("Bitte Zeichenkette in umgekehreten Polnisch eintippen und
          '$' am Ende\n");
 scanf("%[0-9+ -*/$]", str);
 for (i = 0; str[i] != '\0'; i++){ 
    switch (str[i]){
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':
         intvalue = str[i] - '0';
         while (str[i+1] == '0'||
                str[i+1] == '1'||
                str[i+1] == '2'||
                str[i+1] == '3'||
                str[i+1] == '4'||
                str[i+1] == '5'||
                str[i+1] == '6'||
                str[i+1] == '7'||
                str[i+1] == '8'||
                str[i+1] == '9'){
           intvalue = (str[i+1]-'0') + intvalue*10;
           i++;
           }
           polish_exp[count].type = value;
           polish_exp[count].field.val = intvalue;  
           count++;
         break;
    case '+':
    case '-':
    case '*':
    case '/':
         polish_exp[count].type = operator;
         polish_exp[count].field.op = str[i];
         count++;
         break;
    case ' ':
   }
 }
}

int evaluate_polish()
{
  char binop;
  int i, operand1, operand2;
  DATA buffer, temp;

  for (i = 0; i < count; i++){
     if (polish_exp[i].type == operator){  /*calculate operator on 2 topmost
                                            stack elements, i.e. values */
          binop = polish_exp[i].field.op;  /*get the operator*/
          buffer = pop();                  /*get second operand*/
          operand2 = buffer.field.val;
          buffer = pop();                  /*get first operand*/
          operand1 = buffer.field.val;
          temp.type = value;
          switch(binop) {
               case '+' : temp.field.val = operand1 + operand2;
                          break;
               case '-' : temp.field.val = operand1 - operand2;
                          break;
               case '*' : temp.field.val = operand1 * operand2;
                          break;
               case '/' : temp.field.val = operand1/operand2;
               }
           push(temp);                     /*put result on stack*/
       }
       else                                /*type is val--just push*/
          push(polish_exp[i]);
   } /*for*/
  return pop().field.val;
}



void print_polish()
{
  int i;
  printf("count = %d\n", count);
  for(i=0; i <count;i++)
  if (polish_exp[i].type ==  value) printf("%d",polish_exp[i].field.val);
  else if (polish_exp[i].type == operator) printf("%c",polish_exp[i].field.op);
  else printf("Operand/Operator unknown");
  printf("\n");
}

int main(void)
{
 read_polish();
 printf("Value of reverse polish string is %d\n", evaluate_polish());
 print_polish();
 return 0;
}

8.3.4 Doppelverkettete Listen

Wie Abb.8.7 darstellt, will man in einer doppelverketteten List von jeden Knoten aus sowohl nach hinten als auch nach vorne durchlaufen können. Dies bedeutet auch: zu jedem Zeitpunkt kann man den Vorgänger und Nachfolger erkennen.

**Abbildung 8.7:** Struktur einer doppelverketteten Liste
$\includegraphics[width=12cm]{Drawing8_7}$

Die Header - Datei `Dllistei.h' wird wie folgt definiert:

typedef ...  DATA;

struct Dlliste_knoten {
   DATA       d;
   struct Dlliste_knoten  *Naechster;
   struct Dlliste_knoten  *Vorheriger;
};

typedef struct Dlliste_knoten DLISTEKNOTEN;
typedef DLISTEKNOTEN *ZDLISTEKNOTEN;
ZDLISTEKNOTEN HEADER;

Für den Datentyp vier Grundoperationen:

Doppelverkettete Liste initialisieren: void initDllist()
Test, ob die Liste leer ist: int istLeer()
Einfügen eines Knotens in eine doppelverkettete Liste:
```
void einfuegen(ZDLISTENKNOTEN p, DATA *q);
```
wobei p ein Zeiger auf einen Knoten ist, wonach der Knoten mit Datenfeld *q eingefügt wird.
Knoten, durch den Zeiger p gegeben, aus der doppelverketteten Liste entfernen:
```
DATA loeschen(ZDLISTENKNOTEN p);
```

Doppelverkettete Liste initialisieren:

$\begin{boxedminipage}[t]{5cm} \begin{verbatim}{ HEADER = NULL; }\end{verbatim}\end{boxedminipage}$

`
Doppelverkettete Liste mit 1 Knoten initialisieren. Wenn dataPtr auf eine Variable vom Typ DATA zeigt, dann wird die Liste durch nachfolgenden Code mit einem Knoten initialisiert:

$\begin{boxedminipage}[t]{12.5cm} \begin{verbatim}{ HEADER = (ZDLISTEKNOTEN)mal... ...>Vorheriger = NULL; HEADER->NAECHSTER = NULL; }\end{verbatim}\end{boxedminipage}$
Element aus einer doppelverketteten Liste entfernen. Diese Funktion gibt eine Struktur des Typs DATA zurück:

$\begin{boxedminipage}[t]{10.5cm} \begin{verbatim}{ DATA temp = p->d; if (p->... ...ger = p->Vorheriger; free(p); return temp; }\end{verbatim}\end{boxedminipage}$
Element in eine doppelverkettete Liste einfügen. Parameter p und q sind wie oben beschrieben:

$\begin{boxedminipage}[t]{12.5cm} \begin{verbatim}{ if ((!istLeer())&&(p)) { ... ...ADER->Vorheriger = NULL; } else error(); } }\end{verbatim}\end{boxedminipage}$

8.4 Bäume

8.4.1 Definitionen

Definition

Ein Baum ist eine endliche Menge B eines oder mehrerer Knoten derart, daß

Es ein ausgezeichnetes Element, Wurzel genannt, gibt.
Die übrigen Knoten (oder Elemente) in m $\geq$ 0 disjunkte Mengen aufgeteilt sind und jeder davon ein Baum ist. Diese Mengen heißen Unterbäume von B.

Bemerkungen:

Die Definition ist rekursiv
Jeder Knoten eines Baums ist die Wurzel eines Unterbaums

Definitionen

Die Anzahl der Unterbäume eines Knotens wird Grad des Knotens genannt. Ein Knoten mit dem Grad 0 heißt Blattknoten. Die Zweigebene eines Baums ist wie folgt definiert: Für die Wurzel ist sie 0 und für eine Nicht - Wurzel ist sie die Zweigebene des Unterbaums der enthaltenden Wurzel +1. Abb. 8.8 zeigt eine Klassifizierung der indo - europäischen Sprachen als Baum. Dieser Baum wird auch abstrakt mit 3 Zweigebenen gezeichnet.

**Abbildung 8.8:** Klassifizierung von Sprachen als Baum
$\includegraphics[width=12cm]{Drawing8_8}$

Wenn die Reihenfolge aller Unterbäume von B wichtig ist, dann spricht man von einem geordneten Baum. Alle Bäume sind geordnete Bäume, es sei denn sie werden anders bezeichnet. Ein Wald ist eine Menge von 0 oder mehr disjunkten Bäumen. Also bilden die Nicht - Wurzel - Knoten eines Baums einen Wald.

Es gibt zwei Arten von Abstammungsbäume:

Ahnentafel. Sie zeigt von einer Person alle Vorfahren in die Vergangenheit zurück.
Stammtafel. Sie zeigt die genealogische Abfolge einer Familie über mehrere Generationen von einem Urahnen ausgehend.

Für Datenstrukturen orientert man sich an der zweiten Art: Jede Wurzel ist der Vater ihrer Unterbäume. Die Unterbäume sind die Söhne des Vaters und untereinander Brüder. Die Wurzel eines Baums hat keinen Vater.

Definition

Ein Binärbaum ist eine endliche Menge von Knoten, die entweder leer ist oder aus einer Wurzel und 2 disjunkten Binärbäumen besteht.

Bemerkungen

Die Definition eines Binärbaums ist rekursiv.
Ein Binärbaum ist kein Sonderfall eines Baums

8.4.2 Programmdarstellung von Bäumen

Die Knoten von Bäumen werden ähnlich wie Knoten von Listen definiert. Statt auf den nächsten Knoten zu zeigen, zeigt ein Baumknoten auf seine Unterbäume. Alle Bäume sind von jetzt an Binärbäume.

typedef ..., DATA;
typedef struct Bknoten{
   DATA d;
   struct Bknoten *links;
   struct Bknoten *rechts;
   } BKNOTEN;
typedef BKNOTEN *BAUMZEIGER;
BAUMZEIGER Wurzel;

Wie üblich werden diese Typ- und Datendeklarationen in eine Header - Datei `baum.h' geschrieben. Es gibt sehr viele Programm Operationen mit Binärbäumen. Nur einige davon werden hier ohne Implementationsdetails aufgezählt:

Baum initialisieren:
BAUMZEIGER initBAUM();
Baum mit 1 Knoten initialisieren:
BAUMZEIGER knotenKreieren(DATA *daten);
Abfrage, ob der Baum leer ist:
int istLeer();
Linker Baum anheften:
BAUMZEIGER linksSetzen(BAUMZEIGER ZKnoten, DATA *daten);
Rechter Baum anheften:
BAUMZEIGER rechtsSetzen(BAUMZEIGER ZKnoten, DATA *daten);
Daten holen:
DATA getDATA(BAUMZEIGER ZKnoten);

Ein geordneter Binärbaum wird nun gebaut. Für jeden Knoten sind alle Daten

Links kleiner als die Daten des Knotens
Rechts größer als die Daten des Knotens

**Abbildung 8.9:** Ein geordneter Baum
$\includegraphics[width=12cm]{Drawing8_9}$

Abb8.9 zeigt den Baum, der aus der Eingabereihenfolge

10, 5, 15, 3, 8, 12, 18, 1, 4, 9, 14

entsteht.

void einfuegen(BAUMZEIGER *wurzelptr, int n)
{
  if ((*wurzelptr) == NULL){
     *wurzelptr = (BAUMZEIGER)malloc(sizeof(BKNOTEN));
     (*wurzelptr)->d = n;
     (*wurzelptr)->links = NULL;
     (*wurzelptr)->rechts = NULL;
     }
  else if (n < (*wurzelptr)->d) 
            einfuegen(&((*wurzelptr)->links),n);
  else if (n > (*wurzelptr)->d) 
            einfuegen(&((*wurzelptr)->rechts),n);
  else fprintf(stderr, "Element %d ist bereits vorhanden\n",n);
}

Bemerkungen

Die Funktion ist rekursiv.
Knoten werden immer am Rande des Baums (d.h. bei Nullzeiger) eingefügt.
Damit der links oder rechts Zeiger des Knotens mit einer gültigen Adresse versehen wird, muss die Adresse des Knotenzeigers übergeben werden.

8.4.3 Durchlauf eines Binärbaums

Es gibt 3 Hauptmöglichkeiten, einen Baum so zu durchlaufen, daß jeder Knoten genau einmal besucht wird:

Preorder:

Wurzel

linker Teilbaum

rechter Teilbaum
Inorder:

linker Teilbaum

Wurzel

rechter Teilbaum
Postorder:

linker Teilbaum

rechter Teilbaum

Wurzel

Beispiel:

Man betrachte den sog. Ausdruckbaum in Abb.8.10 für den arithmetischen Ausdruck (A - B*C)*(D + E/F).

**Abbildung 8.10:** Ausdruckbaum für (A - B*C)*(D + E/F)
$\includegraphics[width=12cm]{Drawing8_10}$

Dann lautet das Ergebnis von allen 3 Durchlaufarten:

Preorder:	* - A*BC + D/EF
Inorder:	A - BCD + E/F
Postorder:	ABC* - DEF/ + *

Beispiel 1

Dieser Abschnitt zeigt zunächst ein Beispielprogramm, das alle bisher beschriebenen Punkte implementiert. Der Baum aus Abb.8.9 wird aufgebaut und durchläuft unter Anwendung der 3 Durchlaufmethoden. Zusätzlich wird eine rekursive Funktion drucken(), um einen Baum seitlichliegend auszudrucken, angeboten.

#include <stdio.h>
#include <stdlib.h>

typedef int DATA;
typedef struct Bknoten{
	DATA d;
	struct Bknoten *links;
	struct Bknoten *rechts;
	}BKNOTEN;
typedef BKNOTEN *BAUMZEIGER;

void einfuegen(BAUMZEIGER *wurzelptr, int n)
{
  if ((*wurzelptr) == NULL){
     *wurzelptr = (BAUMZEIGER)malloc(sizeof(BKNOTEN));
     (*wurzelptr)->d = n;
     (*wurzelptr)->links = NULL;
     (*wurzelptr)->rechts = NULL;
     }
  else if (n < (*wurzelptr)->d) 
          einfuegen(&((*wurzelptr)->links),n);
  else if (n > (*wurzelptr)->d) 
          einfuegen(&((*wurzelptr)->rechts),n);
  else fprintf(stderr, "Element %d ist bereits vorhanden\n",n);
}

void drucken(BAUMZEIGER knoten, int sp)
{
  int i;
  if (knoten != NULL){
   drucken(knoten->rechts, sp+3);
   for(i = 1; i <= sp;i++) putchar(' ');
   printf("%d\n", knoten->d);
   drucken(knoten->links, sp+3);
  }
}

void preorder(BAUMZEIGER ptr)
{
 if(ptr != NULL){
                 printf("%d ", ptr->d);
                 preorder(ptr->links);
                 preorder(ptr->rechts);
                 }
}

void inorder(BAUMZEIGER ptr)
{
  if (ptr != NULL){
                   inorder(ptr->links);
                   printf("%d ",ptr->d);
                   inorder(ptr->rechts);
                  }
}

void postorder(BAUMZEIGER ptr)
{
  if (ptr != NULL){
                   postorder(ptr->links);
                   postorder(ptr->rechts);
                   printf("%d ",ptr->d);
                  }
}




int main()
{
 BAUMZEIGER wurzel;
 int intval;
 wurzel = NULL;
 scanf("%d", &intval);
 while (intval != -1){
   einfuegen(&wurzel, intval);
   scanf("%d", &intval);
 }
 drucken(wurzel,0);
 printf("Preorder:  ");
 preorder(wurzel);
 putchar('\n');
 printf("Inorder:   ");
 inorder(wurzel);
 putchar('\n');
 printf("Postorder: ");
 postorder(wurzel);
 putchar('\n');
 return 0;
}

Eingabe: 10 5 15 3 8 12 18 1 4 9 14
Ausgabe:
      18
   15
         14
      12
10
         9
      8
   5
         4
      3
         1
Preorder:  10 5 3 1 4 8 9 15 12 14 18 
Inorder:   1 3 4 5 8 9 10 12 14 15 18 
Postorder: 1 4 3 9 8 5 14 12 18 15 10

Beispiel 2

Hier wird der Scanner und Parser für eine Grammatik für Ausdrücke systematisch gebaut. Ziel ist es, arithmetische Ausdrücke, die von infix Zeichenketten im Programm vorkommen, in Ausdrucksbäume umzuwandeln und damit für die Codegenerierung vorzubereiten. Der Student gewinnt dabei einen Einblick in die interne Arbeitsweise eines Compilers. In der Tat sind Ausdrücke, auch wenn hier etwas einfach dargestellt, der wahre Kern einer Programmiersprache.

Schritt1: Der Scanner. Der Scanner führt lexikalische Analyse durch, d.h. zerlegt Quellcode in Form einer Eingabezeichenkette in sprachliche atomare Elemente. Diese Elemente heißen Tokens. Etwas genauer: Die Aufgabe des Scanners besteht darin, das nächste lexikalische Symbol oder Token aus dem Quelltext zu holen. Der Scanner hat außerden folgende Aufgaben:

Leerräume zu übergehen
Reservierte Wörter, z.B. for, main usw. zu erkennen
Nicht-reservierte Buchstabenfolgen, wie z.B. 'a' oder 'x' als Konstanten oder Variablen zu erkennen
Folgen von Kommastellen als Konstanten, oder besser, Literalen zu erkennen.
Spezielle Zeichen, wie z.B. -> oder { zu erkennen.
Numerische Literalen in numerische Werte umzuwandeln

Die Tokens werden durch eine einfache Grammatik beschrieben. Zum Beispiel sieht eine Grammatik für die Tokens aus einer Ausdruckgrammatik wie folgt aus:

<Zahlenstelle>	::=	0 \| 1 \|^...\| 9
<Integer>	::=	<Zahlenstelle> \| <Zahlenstelle> <Integer>
<Konst>	::=	a \| b \|^...\| w
<Var>	::=	x
<PlusOp>	::=	+
<MinusOp>	::=	-
<MalOp>	::=	*
<TeilOp>	::=	/
<LKlammer>	::=	(
<RKlammer>	::=	)

Vorgehensweise:

Bis zu 80 Zeichen sind in einer Zeile erlaubt und werden in einem Puffer ohne Trennzeichen ablelegt. Am Ende der Zeichenkette wird ein Haltsymbol ($) plaziert. Leerräume werden übersprungen. Das Ergebnis: Eine globale Variable Symbol wird der aktuellen gescannten Symbolart besetzt, d.h. PlusOp, MinusOp usw. Erlaubt am Ende ist das Terminal-Symbol TermSym, um den Vorgang zu stoppen. Ist Symbol gleich IntWert, dann enthält die globale Variable Wert ihren Wert. Es ist wichtig hier zu merken, daß der Scanner nach Bedarf immer das nächste Token aus der Eingabe liefert. Beziehungen zwischen den Tokens, oder Syntax werden vom Scanner nicht geprüft. Die Struktur eines Knotens im Ausdruckbaum ist in der Datei tree.h zu finden und ist hier gegeben:

#define MaxStellen 6
typedef enum{PlusOp, MinusOp, MalOp, TeilOp, LKlammer, RKlammer,
             ConstOp, VarOp, TermSym} SymArt;

typedef struct{
  enum{operator, value} type;
  union{
    struct {
      char Inhalt[MaxStellen];
      int Laenge;
      int Wert;
    } Blatt;
    SymArt Op;
  } KnotenTyp;
} DATA;


struct Knoten{
    DATA d;
    struct Knoten *links, *rechts;
};
 
typedef struct Knoten *KnotenZeiger;

Der Scanner selbst kann dann mit Hilfe dieser Struktur geschrieben werden. Man achte besonders auf die Funktion holeSym, die beim Aufruf immer das nächste Token aus der Eingabe liefert:

#include "tree.h"
#include <stdio.h>
#define SIZE 80

extern SymArt Symbol;
char intPuffer[MaxStellen];
char RgabePuffer[MaxStellen];
int Laenge; 
int Aktuell = 0;
char Sym;
char puffer[SIZE];
int anzZeich = 0;
int tempVal;

void reInit()
{
  Aktuell = 0;
}

void liesCharString()
{
  int i;
  scanf("%[0-9+ #*/()a-x$-]", puffer);
  for (i=0;puffer[i]!='\0';i++) anzZeich++;
}
  
SymArt holeSym()
/* Liest naechster Symbol aus der Eingabe--ist entweder eine Konstante,
   die Variable x oder ein Operator +,-,*,/,(,).  Eine Konstante ist
   entweder ein Buchstabe 'a' bis 'w' oder eine int Zahl mit max 6 Stellen*/
{
   int i, temp;
   Sym = puffer[Aktuell];
   while (Sym == ' '){Aktuell++; Sym = puffer[Aktuell];}
   switch (Sym){
     case '0':
     case '1':
     case '2':
     case '3':
     case '4':
     case '5':
     case '6':
     case '7':
     case '8':
     case '9':
        if (Aktuell < anzZeich){
          i = 0;
          do{
            intPuffer[i] = Sym;
            Aktuell++; i++;
            Sym = puffer[Aktuell];
          } while ((Aktuell < anzZeich) && (Sym == '0' ||
                                            Sym == '1' ||
                                            Sym == '2' ||
                                            Sym == '3' ||
                                            Sym == '4' ||
                                            Sym == '5' ||
                                            Sym == '6' ||
                                            Sym == '7' ||
                                            Sym == '8' ||
                                            Sym == '9') &&
                                            (i < MaxStellen));
           if (Aktuell <= anzZeich) Aktuell--;
         }
        Laenge = i;
        tempVal = 0;
        for (i = 0; i < Laenge; i++){
            RgabePuffer[i] = intPuffer[i];
            tempVal = 10*tempVal + (intPuffer[i] - '0');
            }
        Aktuell++;
        return ConstOp;
        break;
     case 'a':
     case 'b':
     case 'c':
     case 'd':
     case 'e':
     case 'f':
     case 'g':
     case 'h':
     case 'i':
     case 'j':
     case 'k':
     case 'l':
     case 'm':
     case 'n':
     case 'o':
     case 'p':
     case 'q':
     case 's':
     case 't':
     case 'u':
     case 'v':
     case 'w':
        Laenge = 1;
        RgabePuffer[0] = Sym;
        Aktuell++;
        return ConstOp;
        break;
     case 'x':
        RgabePuffer[0] = 'x';
        Laenge = 1;
        Aktuell++;
        return VarOp;
     case '+': Aktuell++; return PlusOp;
     case '-': Aktuell++; return MinusOp;
     case '*': Aktuell++; return MalOp;
     case '/': Aktuell++; return TeilOp;
     case '(': Aktuell++; return LKlammer;
     case ')': Aktuell++; return RKlammer;
     case ' ': Aktuell++; break;
     case '$': return TermSym;
  }
}

void printSym()
{
    switch (Symbol){
      case ConstOp: printf("ConstOp ");
                    break;
      case VarOp: printf("VarOp ");
                    break;
      case  PlusOp: printf("PlusOp ");
                    break;
      case  MinusOp:printf("MinusOp ");
                    break;
      case MalOp:printf("MalOp ");
                    break;
      case  TeilOp: printf("TeilOp ");
                    break;
      case LKlammer: printf("LinkeKlammer ");
                     break;
      case RKlammer: printf("RechteKlammer ");
                     break;
      case TermSym :printf("Terminal Symbol ");
                    break;

    }
 }

Schritt 2: Der Parser Man konstruiere nun den Ausdrucksbaum seiner BNF entsprechend, d.h. entsprechend einer Grammatik, die bestimmt wie zulässige Ausdrücke geformt werden müssen. Es sei bemerkt, daß ein legaler Ausdruck nur eine Ableitung in dieser Grammatk ist (diese Ableitung ist i.A. nicht eindeutig bestimmt). Die Methode der syntaktischen Prüfung (Parsing) heißt rekursiver Abstieg. Nach unserer Ausdrucksgrammatik, nämlich

<Expression>	::=	<Term> \| <Term>+ <Term> \| < Term > - <Term >
<Term>	::=	<Factor> \| <Factor>*``** <Factor> \| < Factor > `/` <Factor>
<Factor>	::=	<Integer> \| ( <Expression>)

wird nun der Parser geschrieben. Die Methode des rekursiven Abstiegs lautet nun wie folgt: Zu jedem Nicht-Terminal-Symbol (oder Ausdruck in eckigen Klammern) wird eine C-Funktion zugeordnet. Die rechte Seite der entsprechenden Produktion wird von links nach rechts abgearbeitet. Dabei sind folgende zwei Punkte zu beachten:

Terminal-Symbole werden in der Eingabe zusammengepasst
Nicht-Terminal-Symbole verursachen einen Aufruf der entsprechenden Funktion

Die Methode ist rekursiv, da die Grammatik rekursiv ist. Das Programm, das nach der Grammatik Syntaxbäume systematisch baut wird nun gegeben:

#include "tree.h"
#include <stdio.h>
#include <stdlib.h>

SymArt Symbol;
KnotenZeiger ExpBaum;
extern int Laenge;
extern char RgabePuffer[MaxStellen];
extern int tempVal;
KnotenZeiger term(); //foreward declarations
KnotenZeiger factor();

extern void printSym();
void Fehler(int which)
{
 switch(which){
  case 1: printf("Malformed expression\n");
          break;
  case 2: printf("No right paren\n");
  }
}

void Baumdrucken(KnotenZeiger B, int margin)
{
  int i;
  if (B){
    Baumdrucken(B->links, margin+8);
    if (B->d.type == value){
        for(i = 0; i < margin; i++) putchar(' ');
        for(i = 0; i < B->d.KnotenTyp.Blatt.Laenge;i++) 
          putchar(B->d.KnotenTyp.Blatt.Inhalt[i]);
        putchar('\n');
      }
   else switch(B->d.KnotenTyp.Op){
     case PlusOp:
                 for (i = 0; i < margin; i++) putchar(' ');
                 putchar('+'); putchar('\n');
                 break;
     case MinusOp:

                 for (i = 0; i < margin; i++) putchar(' ');
                 putchar('-'); putchar('\n');
                 break;

     case MalOp:

                 for (i = 0; i < margin; i++) putchar(' ');
                 putchar('*'); putchar('\n');
                 break;

     case TeilOp:

                 for (i = 0; i < margin; i++) putchar(' ');
                 putchar('/'); putchar('\n');
                 break;
 
    }
  Baumdrucken(B->rechts, margin+8);
  }
}

void postorder(KnotenZeiger B)
{
  int i;
  if (B != NULL){
      postorder(B->links);
      postorder(B->rechts);
      if (B->d.type == value){
        putchar('(');
        for(i = 0; i < B->d.KnotenTyp.Blatt.Laenge;i++)
            printf("%c",B->d.KnotenTyp.Blatt.Inhalt[i]);
        putchar(')');
       }
      else
        switch(B->d.KnotenTyp.Op){
         case PlusOp: printf("+");break;
         case MinusOp: printf("-"); break;
         case MalOp: printf("*"); break;
         case TeilOp:printf("/");
        }
  }
}

KnotenZeiger expression()
{
 KnotenZeiger p,q;
 q = term();
 while ((Symbol == PlusOp) || (Symbol == MinusOp)){
  p = (KnotenZeiger)malloc(sizeof(struct Knoten));
  p->links = q;
  p->d.KnotenTyp.Op = Symbol;
  Symbol = holeSym();
  p->d.type = operator;
  p->rechts = term();
  q = p;
  }
 return q;
}

KnotenZeiger term()
{
 KnotenZeiger p,q;
 q = factor();
 while((Symbol == MalOp) || (Symbol == TeilOp)){
   p = (KnotenZeiger)malloc(sizeof(struct Knoten));
   p->links = q;
   p->d.KnotenTyp.Op = Symbol;
   Symbol = holeSym();
   p->rechts = factor();
   p->d.type = operator;
   q = p;
   }
   return q;
}

KnotenZeiger factor()
{
 KnotenZeiger p;
 int i;
 if (Symbol == LKlammer){
   Symbol = holeSym();
   p = expression();
   if (Symbol != RKlammer) Fehler(2);  //Missing right paren
   else Symbol = holeSym();
  }
 else if ((Symbol == ConstOp) || (Symbol == VarOp)){
   p = (KnotenZeiger)malloc(sizeof(struct Knoten));
   for (i = 0; i < Laenge; i++) 
     p->d.KnotenTyp.Blatt.Inhalt[i] = RgabePuffer[i];
   p->d.KnotenTyp.Blatt.Laenge = Laenge;
   p->d.KnotenTyp.Blatt.Wert = tempVal;
   p->links = NULL;
   p->rechts = NULL;
   p->d.type = value;
   Symbol = holeSym();
 }
   return p;

}


int main()
{
 printf("Bitte Infix Ausdruck eingeben und mit $ beenden: ");
 liesCharString();
 Symbol = holeSym();
 ExpBaum = expression();
 printf("Now the tree in postorder:\n");
 postorder(ExpBaum);
 putchar('\n');
 printf("Wert des Ausdruckbaeums ist %d\n", evaluateExpression(ExpBaum));
 putchar('\n');
 printf("Nun wird der Baum gedruckt\n");
 Baumdrucken(ExpBaum, 0);
 if (Symbol != TermSym) Fehler(1);
 return 0;
}

Das Programm verursacht folgende Ausgabe:

Bitte Infix Ausdruck eingeben und mit $ beenden: 
(1 + 2) * (3 + 4)$
Now the tree in postorder:
(1)(2)+(3)(4)+*
Nun wird der Baum gedruckt
                1
        +
                2
*
                3
        +
                4

Prof. Raymond Zavodnik, 17.01.2003

	Wurzel
	linker Teilbaum
	rechter Teilbaum

	linker Teilbaum
	Wurzel
	rechter Teilbaum

	linker Teilbaum
	rechter Teilbaum
	Wurzel