Kapitel 23 Dynamische Datenstrukturen

In diesem Kapitel werden die Themen Strukturen, Zeiger und dynamische Speicherverwaltung vermischt. Was auf den ersten Blick ein wenig kompliziert aussieht, und es auch manches Mal ist, erweist sich, sobald Sie es beherrschen, als eine enorme Erleichterung.

23.1 Lineare Listen (einfach verkettete Listen) 

In Kapitel 16, Dynamische Speicherverwaltung, wurde der Umgang mit dynamisch zugeordnetem Speicher näher erläutert. Dynamisch heißt, dass zur Laufzeit des Programms Speicher vom Heap alloziiert wird.

Der Hauptsinn von dynamischen Datenstrukturen liegt darin, dass eine Struktur mit einem Zeiger vom Typ der Struktur selbst definiert wird. Folgende Struktur einer Angestelltenliste sei gegeben:

struct datum {
   int tag;
   int monat;
   int jahr;
};
struct angestellt{
   char name[20];
   char vorname[20];
   struct datum alter;
   struct datum eingest;
   long gehalt;
};

Eine solche Struktur wurde ja bereits behandelt und stellt somit nichts Neues mehr dar. Jetzt soll diese Struktur erweitert werden:

struct datum {
   int tag;
   int monat;
   int jahr;
};
struct angestellt {
   char name[20];
   char vorname[20];
   struct datum alter;
   struct datum eingest;
   long gehalt;
   struct angestellt *next;
};

Folgende Zeile dürfte Ihnen am Ende der Struktur angestellt aufgefallen sein:

struct angestellt *next;

Das Besondere an diesem Zeiger ist, dass es ein Zeiger auf eine Adresse ist, die denselben Typ wie die Struktur selbst (struct angestellt) beinhaltet. Mit diesem Zeiger können somit einzelne Strukturen miteinander verkettet werden. Der next-Zeiger verweist immer auf die Adresse des nächsten Elements, welches wiederum eine Struktur mit denselben Elementen und ebenfalls wieder einen weiteren Zeiger beinhaltet. Sie können dabei eine gewisse Ähnlichkeit mit den Arrays von Strukturen erkennen. Wobei hier das nächste Element mithilfe eines Zeigers statt mit dem Indizierungsoperator angesprochen wird, und Sie zuvor noch für das nächste Element einen Speicherplatz reservieren müssen. Außerdem wird noch ein Ende für die Kette benötigt. Dazu verwenden Sie einfach den next-Zeiger und übergeben diesem einen NULL-Zeiger:

struct angestellt *next = NULL;

Somit würde die Struktur angestellt folgendermaßen aussehen:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.1   Eine Struktur für eine einfach verkettete Liste

Nochmals: Der Zeiger struct angestellt *next zeigt nicht auf sich selbst, sondern auf eine Adresse des nächsten Elements vom selben Typ (Flashback: Zeiger dereferenzieren eine Adresse und keinen Wert). In diesem Beispiel wird erst noch auf NULL verwiesen, da noch keine Daten eingegeben wurden.

In Kapitel 17, Strukturen, wurde bereits gezeigt, wie Sie auf die einzelnen Elemente einer Struktur zugreifen können. Als Beispiel:

struct angestellt a;

Anschließend wurde mit a.name, a.vorname oder a.alter usw. auf die einzelnen Strukturelemente zugegriffen. Ähnlich funktionierte dies, wenn nicht mit einer Strukturvariablen, sondern mit Zeigern auf eine Struktur gearbeitet wird:

struct angestellt *structzeiger;

Der Zugriff auf die einzelnen Elemente der Struktur sieht dann so aus:

(*structzeiger).name
(*structzeiger).vorname
(*structzeiger).alter

Diese Schreibweise ist allerdings nicht allzu lesefreundlich und birgt die Gefahr, Fehler zu machen. Zum Glück haben die Compilerbauer einen extra Operator geschaffen, der eine Kombination aus Dereferenzierung und Elementzugriff ist:

->

Da der ->-Operator die Form eines Zeigers hat, ist dieser auch noch einfacher zu lesen. Somit ergibt sich folgende Schreibweise für den Zugriff auf die einzelnen Strukturelemente:

structzeiger->name
structzeiger->vorname
structzeiger->alter

Theoretisch könnten Sie jetzt einen Datensatz nach dem anderen anhängen. Aber irgendwann wollen Sie den Datensatz auch wieder ausgeben oder sortieren. Deshalb benötigt die Kette einen Anfang, d.h. eine Anfangsadresse, mit der die Liste beginnt. Also ist ein weiterer Zeiger der Struktur angestellt erforderlich, in dem sich die Anfangsadresse befindet:

struct angestellt *anfang;

Da zu Beginn des Programms noch kein Datensatz eingegeben wurde, verweist dieser Zeiger zunächst auch auf NULL. Bisher sieht die Struktur demnach so aus:

struct datum {
   int tag;
   int monat;
   int jahr;
};
struct angestellt {
    char name[20];
    char vorname[20];
    struct datum alter;
    struct datum eingest;
    long gehalt;
    struct angestellt *next;
};
struct angestellt *next   = NULL;
struct angestellt *anfang = NULL;

Jetzt folgt eine Funktion, mit der Sie Adresssätze aneinander hängen können. Die Funktion anhaengen() ist sehr ausführlich kommentiert:

/* linear_list1.c */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 20
struct datum {
   int tag;
   int monat;
   int jahr;
};
struct angestellt {
   char name[MAX];
   char vorname[MAX];
   struct datum alter;
   struct datum eingest;
   long gehalt;
   struct angestellt *next;
};
struct angestellt *next = NULL;
struct angestellt *anfang=NULL;
/* Wir hängen einen Datensatz an oder geben einen neuen ein
 * n=name,v=vornam,at=alter.tage,am=alter.monat,aj=alter.jahr
 * eint=eigestellt tag,einm=eingestellt monat,einj=eingest.
 * Jahr  g=gehalt */
void anhaengen(char *n, char *v, int at, int am, int aj,
                int eint, int einm, int einj, long g) {
   /* Zeiger zum Zugriff auf die einzelnen Elemente
    * der Struktur*/
   struct angestellt *zeiger;
  /* Wir fragen ab, ob es schon ein Element in der Liste
   * gibt. Wir suchen das Element, auf das unser Zeiger
   *  *anfang zeigt. Falls *anfang immer noch auf NULL zeigt,
   *  bekommt *anfang die Adresse unseres 1. Elements und ist
   *  somit der Kopf (Anfang) unserer Liste */
   if(anfang == NULL) {
      /* Wir reservieren Speicherplatz für unsere Struktur
       * für das erste Element der Liste*/
      if((anfang = (struct angestellt *)
       malloc(sizeof(struct angestellt))) == NULL) {
         fprintf(stderr, "Kein Speicherplatz vorhanden "
                         "für anfang\n");
         return;
      }
      strcpy(anfang->name, n);
      strcpy(anfang->vorname, v);
      anfang->alter.tag = at;
      anfang->alter.monat = am;
      anfang->alter.jahr = aj;
      anfang->eingest.tag = eint;
      anfang->eingest.monat = einm;
      anfang->eingest.jahr = einj;
      anfang->gehalt = g;
      /* Somit haben wir unseren Anfang der Liste. Von nun an
       * zeigt der Zeiger anfang immer auf das Element vor ihm.
       * Da dies aber jetzt das 1. Element der Liste war, zeigt
       * der Zeiger anfang auf den Zeiger next. next zeigt am
       * Ende immer wieder  NULL */
      anfang->next=NULL;
   }
   /* Es scheint schon mindestens ein Element in der Liste
    * vorhanden zu sein, da der Anfang nicht == NULL ist.
    * Jetzt suchen wir so lange nach dem nächsten Element,
    * bis der *next-Zeiger auf NULL zeigt. Somit haben wir
    * das Ende der Liste gefunden und können einen neuen
    * Datensatz anhängen */
   else {
      zeiger=anfang; /* Wir zeigen auf das 1. Element */
      while(zeiger->next != NULL)
         zeiger=zeiger->next;
      /* Wir reservieren einen Speicherplatz für das letzte
       * Element der Liste und hängen es an. */
      if((zeiger->next =(struct angestellt *)
       malloc(sizeof(struct angestellt))) == NULL) {
          fprintf(stderr,"Kein Speicherplatz für das "
                         "letzte Element\n");
          return;
      }
      zeiger=zeiger->next; /* zeiger auf neuen Speicherplatz */
      strcpy(zeiger->name,n);
      strcpy(zeiger->vorname,v);
      zeiger->alter.tag=at;
      zeiger->alter.monat=am;
      zeiger->alter.jahr=aj;
      zeiger->eingest.tag=eint;
      zeiger->eingest.monat=einm;
      zeiger->eingest.jahr=einj;
      /* Wir terminieren wieder unsere Datenstruktur */
      zeiger->gehalt=g;
      zeiger->next=NULL;
   }
}
/* Funktion zur Eingabe der Daten */
void eingabe(void) {
   char nam[MAX],vorn[MAX];
   int atag,amon,ajahr,eintag,einmon,einjahr;
   long gehalt;
   printf("Name........................: ");
   fgets(nam, MAX, stdin);
   printf("Vorname.....................: ");
   fgets(vorn, MAX, stdin);
   printf("Alter...........(tt.mm.jjjj): ");
   scanf("%2d.%2d.%4d",&atag,&amon,&ajahr);
   printf("Eingestellt am..(tt.mm.jjjj): ");
   scanf("%2d.%2d.%4d",&eintag,&einmon,&einjahr);
   printf("Monatsgehalt................: ");
   scanf("%ld",&gehalt);
   getchar();
   /* Eingegebenen Datensatz hinten anhängen */
   anhaengen(nam, vorn, atag, amon, ajahr, eintag,
    einmon, einjahr, gehalt);
}
int main(void) {
   while(1)
      eingabe();
   return EXIT_SUCCESS;
}

Zuerst wird die Funktion eingabe() zur Eingabe der einzelnen Daten aufgerufen. Diese eingegebenen Variablen werden anschließend als Argument an die Parameter der Funktion anhaengen() übergeben. Sehr wichtig ist bei der Funktion die Zeile

zeiger=zeiger->next;

Es wird davon ausgegangen, dass bereits ein Element eingegeben wurde und das nächste somit das zweite Element in der Liste ist. Wenn jetzt zeiger nicht auf die Adresse von zeiger->next verweisen würde, wäre dies zwar kein syntaktischer Fehler, aber es würde immer wieder die erste Struktur überschrieben werden.

Mit der folgenden Zeile wird es überhaupt erst möglich, dass die while-Schleife funktioniert, um wieder neue Daten einzugeben:

zeiger->next=NULL;

Sonst würde die while-Schleife mit der Abfrage, ob zeiger auf next zeigt, niemals korrekt abbrechen, da niemals auf NULL verwiesen würde:

while(zeiger->next != NULL)
   zeiger=zeiger->next;

Dies soll jetzt bildlich dargestellt werden. Es wurden bereits zwei Personen eingegeben. Somit sind folgende zwei Datensätze vorhanden:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.2   Eine verkettete Liste mit zwei Datensätzen

Hier erkennen Sie auch, dass der Strukturzeiger anfang immer auf das erste Element der Liste zeigt. Der Strukturzeiger next im letzten Element zeigt immer auf NULL und somit immer das Ende der Kette an.

Als Nächstes soll eine Funktion erstellt werden, mit der Sie einzelne Elemente in der Liste löschen können. Der Speicherplatz wird dabei wie üblich mit der Funktion free() freigegeben.

23.1.1 Erstes Element der Liste löschen 

Falls das erste Element in der Liste gelöscht werden soll, ist dies nicht allzu schwierig. Dabei muss nur ein Zeiger vom Typ struct angestellt auf die Adresse von anfang->next zeigen (zweites Element). Anschließend kann mit free(anfang) der Speicher freigegeben werden. Zum Schluss bekommt der Zeiger anfang die Adresse des Zeigers anfang->next. So werden Sie in der Praxis das erste Element in der Liste los:

/* Funktion zum Löschen */
void loesche(char *wen) {
   struct angestellt *zeiger;
   /* Ist überhaupt ein Element vorhanden? */
   if(anfang != NULL) {
      /* Ist unser 1. Element das von uns gesuchte (wen[])? */
      if(strcmp(anfang->name,wen) == 0) {
         zeiger=anfang->next;

Es sei jetzt der Fall gegeben, dass das erste Element in der Liste das momentan gesuchte ist, welches gelöscht werden soll. Somit ergibt sich im Augenblick folgender Zustand:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.3   Ein Zeiger auf das nächste Element vom Anfang

Jetzt folgt der Aufruf:

free(anfang);

Damit wird der Speicherplatz freigegeben, auf den der Zeiger anfang verweist:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.4   Speicherplatz des ersten Elements wird freigegeben

Belassen Sie es jetzt hiermit, sind die restlichen Daten der Kette wohl verloren, da es keinen Anfang mehr gibt. Es muss noch die Adresse des Zeigers zeiger an den Zeiger anfang übergeben werden:

anfang=zeiger;

Damit ergibt sich folgendes finale Bild:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.5   Zeiger des ersten Elements bekommt eine neue Adresse

23.1.2 Beliebiges Element in der Liste löschen 

Das erste Element in der Liste zu löschen war nicht schwer. Anders sieht es aus, wenn ein Element irgendwo in der Liste entfernt werden muss. Dafür wird ein Zeiger mehr benötigt: einer, der auf die Adresse verweist, welche sich vor dem zu löschenden Element befindet, und ein weiterer Zeiger, der auf das nächste Element nach dem zu löschenden Element zeigt. Dazu eine kurze Zusammenfassung der bisherigen Funktion loesche():

/* Funktion zum Löschen */
void loesche(char *wen) {
   struct angestellt *zeiger, *zeiger1;
   /* Ist überhaupt ein Element vorhanden? */
   if(anfang != NULL) {
      /* Ist unser 1. Element das von uns gesuchte (wen[])? */
      if(strcmp(anfang->name,wen) == 0) {
         zeiger=anfang->next;
         free(anfang);
         anfang=zeiger;
      }
      else {
         /* Es ist nicht das 1. Element zu löschen. Wir suchen in
          * der weiteren Kette, ob das zu löschende Element vor-
          * handen ist */
         zeiger=anfang;

Daraus ergibt sich momentan folgende »Grundstellung«:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.6   Auf der Suche nach dem zu löschenden Element

Es wird der Einfachheit halber davon ausgegangen, dass das gesuchte Element das zweite in der Liste sei (siehe Abbildung). Das Stückchen Quellcode, welches nach einem bestimmten Namen in der Liste sucht, sieht folgendermaßen aus:

         while(zeiger->next != NULL) {
            zeiger1=zeiger->next;
            /* Ist die Adresse von zeiger1 der gesuchte Name? */
            if(strcmp(zeiger1->name,wen) == 0) {
               /* Falls ja, dann ... */

Bildlich ergibt sich daraus folgender Stand:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.7   Element zum Löschen gefunden

Die Adresse, auf die zeiger1 zeigt, ist das gesuchte Element in der Liste, welches gelöscht werden soll. Bevor Sie jetzt den Speicherplatz freigeben können, benötigt das Element in der Liste, auf das zeiger verweist, eine Adresse für den next-Zeiger, damit die Kette nicht abreißt:

               zeiger->next=zeiger1->next;
               free(zeiger1);
               break;
            }
            zeiger=zeiger1;
         }  /* Ende while */
      }     /* Ende else */
   }        /* Ende if(anfang != NULL) */
   else
      printf("Es sind keine Daten zum Löschen vorhanden!!!\n");
}

Dies etwas genauer:

zeiger->next=zeiger1->next;

In Worten: Der Zeiger zeiger, der auf die Adresse der nächsten (next) Datenstruktur zeigt (zum jetzigen Zeitpunkt zeigt zeiger->next ja noch auf das zu löschende Element, auf das der Zeiger zeiger1 zeigt), bekommt jetzt die Adresse, auf die der next-Zeiger des zu löschenden Elements (zeiger1) verweist. Bildlich ist das einfacher zu verstehen:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.8   Das zu löschende Element wird ausgehängt

So wird das zu löschende Element ausgehängt. Jetzt kann der Speicherplatz freigegeben werden:

free(zeiger1);

Somit ergibt sich folgendes Bild:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.9   Speicherplatz des zu löschenden Elements wurde freigegeben

23.1.3 Elemente der Liste ausgeben 

Die Funktion zur Ausgabe der einzelnen Elemente in der Liste lässt sich recht einfach erstellen. Zuerst übergeben Sie einem Zeiger die Anfangsadresse der Liste und durchlaufen mit

while(zeiger != NULL)

die Liste so lange, bis der Zeiger zeiger auf NULL verweist – was das Ende der Liste darstellt. Hier die komplette Funktion zur Ausgabe der verketteten Liste:

void ausgabe(void) {
   struct angestellt *zeiger = anfang;
   printf("||====================================="
          "==================||\n");
   printf("|%10cName%10c |Geburtsdatum|"
   "Eingestellt|Gehalt|\n",' ',' ');
   printf("||====================================="
   "==================||\n");
   while(zeiger != NULL) {
      printf("|%12s,%-12s| %02d.%02d.%04d|"
             "%02d.%02d.%04d|%06ld|\n",
         zeiger->name,zeiger->vorname,zeiger->alter.tag,
         zeiger->alter.monat,zeiger->alter.jahr,
         zeiger->eingest.tag,zeiger->eingest.monat,
         zeiger->eingest.jahr,zeiger->gehalt);
         printf("|-----------------------------------"
                "----------------------|\n");
         zeiger=zeiger->next;
   }
}

Und jetzt das gesamte Programm inklusive der main()-Funktion:

/* linear_list2.c */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 20
struct datum{
   int tag;
   int monat;
   int jahr;
};
struct angestellt{
   char name[MAX];
   char vorname[MAX];
   struct datum alter;
   struct datum eingest;
   long gehalt;
   struct angestellt *next;
};
struct angestellt *next   = NULL;
struct angestellt *anfang = NULL;
/* Wir hängen einen Datensatz an oder geben einen neuen ein
 * n=name,v=vornam,at=alter.tage,am=alter.monat,aj=alter.jahr
 * eint=eigestellt tag,einm=eingestellt monat,
 * einj=eingest. Jahr g=gehalt */
void anhaengen(char *n, char *v, int at, int am, int aj,
                int eint, int einm, int einj, long g) {
   /* Zeiger zum Zugriff auf die einzelnen Elemente
    * der Struktur */
   struct angestellt *zeiger;
  /* Wir fragen ab, ob es schon ein Element in der Liste
   * gibt. Wir suchen das Element, auf das unser Zeiger
   *  *anfang zeigt. Falls *anfang immer noch auf NULL zeigt,
   *  bekommt *anfang die Adresse unseres 1. Elements und ist
   *  somit der Kopf (Anfang) unserer Liste */
   if(anfang == NULL) {
      /* Wir reservieren Speicherplatz für unsere Struktur
       * für das erste Element der Liste*/
      if((anfang = (struct angestellt *)
       malloc(sizeof(struct angestellt))) == NULL) {
         fprintf(stderr, "Kein Speicherplatz vorhanden "
                         "für anfang\n");
         return;
      }
      strcpy(anfang->name, n);
      strcpy(anfang->vorname, v);
      anfang->alter.tag = at;
      anfang->alter.monat = am;
      anfang->alter.jahr = aj;
      anfang->eingest.tag = eint;
      anfang->eingest.monat = einm;
      anfang->eingest.jahr = einj;
      anfang->gehalt = g;
      /* Somit haben wir unseren Anfang der Liste. Von nun an
       * zeigt der Zeiger anfang immer auf das Element vor ihm.
       * Da dies aber jetzt das 1. Element der Liste war, zeigt
       * der Zeiger anfang auf den Zeiger next. next zeigt am
       * Ende immer wieder  NULL */
      anfang->next=NULL;
   }
   /* Es scheint schon mindestens ein Element in der Liste
    * vorhanden zu sein, da der Anfang nicht == NULL ist.
    * Jetzt suchen wir so lange nach dem nächsten Element,
    * bis der *next-Zeiger auf NULL zeigt. Somit haben wir
    * das Ende der Liste gefunden und können einen neuen
    * Datensatz anhängen */
   else {
      zeiger=anfang; /* Wir zeigen auf das 1. Element */
      while(zeiger->next != NULL)
         zeiger=zeiger->next;
      /* Wir reservieren einen Speicherplatz für das letzte
       * Element der Liste und hängen es an. */
      if((zeiger->next =(struct angestellt *)
       malloc(sizeof(struct angestellt))) == NULL) {
          fprintf(stderr,"Kein Speicherplatz für das "
                         "letzte Element\n");
          return;
      }
      zeiger=zeiger->next; /* zeiger auf neuen Speicherplatz */
      strcpy(zeiger->name,n);
      strcpy(zeiger->vorname,v);
      zeiger->alter.tag=at;
      zeiger->alter.monat=am;
      zeiger->alter.jahr=aj;
      zeiger->eingest.tag=eint;
      zeiger->eingest.monat=einm;
      zeiger->eingest.jahr=einj;
      /* Wir terminieren wieder unsere Datenstruktur */
      zeiger->gehalt=g;
      zeiger->next=NULL;
   }
}
/* Funktion zum Löschen einer Datei */
void loesche(char *wen) {
   struct angestellt *zeiger, *zeiger1;
   /* Ist überhaupt ein Element vorhanden? */
   if(anfang != NULL) {
      /* Ist unser 1. Element das von uns gesuchte (wen[])? */
      if(strcmp(anfang->name,wen) == 0) {
         zeiger=anfang->next;
         free(anfang);
         anfang=zeiger;
      }
      else {
         /* Es ist nicht das 1. Element zu löschen.
          * Wir suchen in der weiteren Kette, ob das zu
          * löschende Element vorhanden ist*/
         zeiger=anfang;
         while(zeiger->next != NULL) {
            zeiger1=zeiger->next;
            /* Ist die Adresse von zeiger1
             * der gesuchte Name? */
            if(strcmp(zeiger1->name,wen) == 0) {
               /* Falls ja dann ... */
               zeiger->next=zeiger1->next;
               free(zeiger1);
               break;
            }
            zeiger=zeiger1;
         } /* Ende while */
      }    /* Ende else */
   }       /* Ende if(anfang != NULL) */
   else
      printf("Es sind keine Daten zum Löschen vorhanden!!!\n");
}
/* Funktion zum Ausgeben der Dateien */
void ausgabe(void) {
   struct angestellt *zeiger = anfang;
   printf("||====================================="
          "==================||\n");
   printf("|%10cName%10c |Geburtsdatum|"
   "Eingestellt|Gehalt|\n",' ',' ');
   printf("||====================================="
   "==================||\n");
   while(zeiger != NULL) {
      printf("|%12s,%-12s| %02d.%02d.%04d|"
             "%02d.%02d.%04d|%06ld|\n",
         zeiger->name,zeiger->vorname,zeiger->alter.tag,
         zeiger->alter.monat,zeiger->alter.jahr,
         zeiger->eingest.tag,zeiger->eingest.monat,
         zeiger->eingest.jahr,zeiger->gehalt);
         printf("|-----------------------------------"
                "----------------------|\n");
         zeiger=zeiger->next;
   }
}
/* Funktion zur Eingabe der Daten */
void eingabe(void) {
   char nam[MAX],vorn[MAX];
   int atag,amon,ajahr,eintag,einmon,einjahr;
   long gehalt;
   char *ptr;
   printf("Name........................: ");
   fgets(nam, MAX, stdin);
   ptr = strrchr(nam, '\n');
   *ptr = '\0';
   printf("Vorname.....................: ");
   fgets(vorn, MAX, stdin);
   ptr = strrchr(vorn, '\n');
   *ptr = '\0';
   printf("Alter...........(tt.mm.jjjj): ");
   scanf("%2d.%2d.%4d",&atag,&amon,&ajahr);
   printf("Eingestellt am..(tt.mm.jjjj): ");
   scanf("%2d.%2d.%4d",&eintag,&einmon,&einjahr);
   printf("Monatsgehalt................: ");
   scanf("%ld",&gehalt);
   getchar();
   anhaengen(nam, vorn, atag, amon, ajahr, eintag,
      einmon, einjahr, gehalt);
}
int main(void) {
   int wahl;
   char dname[MAX];
   do {
      printf("\n1 : Eingabe\n");
      printf("2 : Ausgabe\n");
      printf("3 : Namen löschen\n");
      printf("9 : Ende\n");
      printf("Ihre Wahl : ");
      scanf("%d",&wahl);
      getchar();
      switch(wahl) {
         case 1 : eingabe();
                  break;
         case 2 : ausgabe();
                  break;
         case 3 : printf("Der Name zum Löschen: ");
                  fgets(dname, MAX, stdin);
                  loesche(strtok(dname, "\n"));
                  break;
         case 9 : break;
         default: printf("Falsche Eingabe!!!\n");
      }
   } while(wahl != 9);
   return EXIT_SUCCESS;
}

Dem Programm fehlen noch einige Optionen, und die Optik lässt auch sehr zu wünschen übrig. Auf den nächsten Seiten wird dieses Programm noch erheblich ausgebaut.

23.1.4 Eine vollständige Liste auf einmal löschen 

Auch die Funktion, mit der alle Elemente einer Liste auf einmal gelöscht werden können, ist nicht schwierig zu implementieren. Hier der Quellcode:

void loesche_alles(void) {
   struct angestellt *zeiger, *zeiger1;
   /* Ist überhaupt eine Liste zum Löschen vorhanden? */
   if(anfang != NULL) {
      /*Es ist eine vorhanden....*/
      zeiger=anfang->next;
      while(zeiger != NULL) {
         zeiger1=anfang->next->next;
         anfang->next=zeiger1;
         free(zeiger->next);
         free(zeiger);
         zeiger=zeiger1;
      }
      /* Jetzt löschen wir erst den Anfang der Liste */
      free(anfang->next);
      free(anfang);
      anfang=NULL;
      printf("Liste erfolgreich gelöscht!!\n");
   }
   else
      fprintf(stderr,"Keine Liste zum Löschen vorhanden!!\n");
}

Zuerst wird überprüft, ob überhaupt eine Liste zum Löschen vorhanden ist. Anschließend bekommt der Zeiger zeiger die Adresse des zweiten Elements:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.10   Zeiger auf das nächste Element vom Anfang

Jetzt wird mit

anfang->next=zeiger1;

dem next-Zeiger des ersten Elements die Adresse übergeben, auf die zeiger1 verweist:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.11   Zu löschendes Element aushängen

Hiermit wurde das Element mit der Adresse, auf die der Zeiger zeiger zeigt, ausgehängt. Jetzt kann der Speicher freigegeben werden:

free(zeiger->next);
free(zeiger);

Zuerst wird der next-Zeiger vom Element, auf das zeiger1 verweist, ausgehängt (müsste nicht sein). Mit free(zeiger) gibt das Element die Liste endgültig frei. Jetzt bekommt noch der Zeiger zeiger die Adresse von zeiger1. Somit sieht es nun folgendermaßen aus:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.12   Speicherplatz freigegeben

Es geht wieder von neuem in der while-Schleife los, wie im Folgenden bildlich ohne weitere Kommentare dargestellt (siehe Abbildung 23.13).

Die Abbruchbedingung für die while-Schleife wäre nun erreicht. Der Zeiger zeiger verweist jetzt auf NULL. Am Ende muss nur noch der Anfang gelöscht werden:

free(anfang->next);
free(anfang);
anfang=NULL;

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.13   Wieder Zeiger auf das nächste Element vom Anfang, dann aushängen und Speicherplatz freigeben

Zur Sicherheit wird dem Zeiger auf das erste Element noch der NULL-Zeiger übergeben, da selbst dann, wenn der Speicher freigegeben ist, der Zeiger anfang immer noch auf die ursprüngliche Speicherstelle zeigt. Dabei kann es leicht zu Programmierfehlern kommen.

23.1.5 Element in die Liste einfügen 

Nun folgt eine Funktion zum sortierten Einfügen eines neuen Elements in die Liste. Die Elemente (Nachnamen) sollen alphabetisch eingefügt werden. Dazu gibt es folgende vier Möglichkeiten, die beim Einfügen eines neuen Elements auftreten können:

Die folgende Funktion überprüft, welche der Möglichkeiten zutrifft, und führt dann entsprechende Arbeiten aus. Zuerst der Funktionskopf:

void sortiert_eingeben(char *n, char *v, int at, int am,
                      int aj, int et, int em, int ej, long geh) {
   struct angestellt *zeiger, *zeiger1;

Jetzt muss überprüft werden, ob überhaupt ein Element in der Liste vorhanden ist:

   if(anfang == NULL)
      anhaengen(n,v,at,am,aj,et,em,ej,geh);

Falls noch kein Element in der Liste vorhanden ist, wird die Funktion anhaengen() mit entsprechenden Argumenten aufgerufen.

Es befindet sich bereits mindestens ein Element in der Liste. Somit beginnt die Suche danach mit:

   zeiger=anfang;
   while(zeiger != NULL && (strcmp(zeiger->name,n) < 0))
      zeiger=zeiger->next;

Die einzelnen Elemente in der Liste werden so lange durchlaufen, bis entweder das Ende erreicht ist (zeiger == NULL) oder bis das neue Element größer oder gleich dem Namen ist, auf den der zeiger verweist. Auf jeden Fall wird die Schleife unterbrochen. Jetzt muss überprüft werden, warum die Schleife abgebrochen wurde. Zuerst wird nachgesehen, ob keine Übereinstimmung stattgefunden hat, und das neue Element somit ganz hinten angehängt wird:

   if(zeiger == NULL)
      anhaengen(n,v,at,am,aj,et,em,ej,geh);

In diesem Fall ist das neue Element das größte und wird mit der Funktion anhaengen() am Ende angefügt.

Die nächste Möglichkeit: Das neue Element ist das kleinste und muss ganz an den Anfang der Liste platziert werden:

   else if(zeiger == anfang) {
      anfang=(struct angestellt *)
        malloc(sizeof(struct angestellt));
      strcpy(anfang->name,n);
      strcpy(anfang->vorname,v);
      anfang->alter.tag=at;
      anfang->alter.monat=am;
      anfang->alter.jahr=aj;
      anfang->eingest.tag=et;
      anfang->eingest.monat=em;
      anfang->eingest.jahr=ej;
      anfang->gehalt=geh;
      anfang->next=zeiger;
   }

Dies sieht bildlich folgendermaßen aus:

else if(zeiger == anfang)

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.14   Neues Element wird am Anfang eingefügt

anfang=(struct angestellt *)malloc(sizeof(struct angestellt));

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.15   Speicherplatz für das neue Element reserviert

anfang->next=zeiger;

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.16   Neues Element am Anfang eingefügt

Jetzt fehlt noch die schwierigste Möglichkeit: Das Element muss irgendwo in der Mitte eingefügt werden:

   else {
      zeiger1=anfang;
      /* Wir suchen das Element, das vor dem Zeiger
       * zeiger steht */
      while(zeiger1->next != zeiger)
         zeiger1=zeiger1->next;
      zeiger=(struct angestellt *)
        malloc(sizeof(struct angestellt));
      strcpy(zeiger->name,n);
      strcpy(zeiger->vorname,v);
      zeiger->alter.tag=at;
      zeiger->alter.monat=am;
      zeiger->alter.jahr=aj;
      zeiger->eingest.tag=et;
      zeiger->eingest.monat=em;
      zeiger->eingest.jahr=ej;
      zeiger->gehalt=geh;
      /* Wir fügen das neue Element ein */
      zeiger->next=zeiger1->next;
      zeiger1->next=zeiger;
   }

Als Beispiel wird ein neues Element zwischen dem zweiten und dem dritten Element eingefügt. Bildlich ergibt sich dadurch folgender Stand:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.17   Ein Zeiger befindet sich eine Position hinter dem neuen Element, welches eingefügt werden soll

Der Zeiger zeiger verweist somit auf das dritte Element. Jetzt wird mit

      while(zeiger1->next != zeiger)
         zeiger1=zeiger1->next;

die Adresse des Elements, welches vor dem Zeiger zeiger steht, ermittelt:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.18   Ein Zeiger befindet sich jetzt vor dem einzufügenden Element

Für das neue Element wird jetzt zunächst Speicherplatz benötigt:

zeiger=(struct angestellt *)malloc(sizeof(struct angestellt));

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.19   Speicherplatz für das neu einzufügende Element reservieren

Nun muss das neue Element in die Liste eingehängt werden. Dies geschieht in zwei Schritten: Der next-Zeiger des neuen Elements bekommt die Adresse, auf die auch der next-Zeiger von zeiger1 verweist:

zeiger->next=zeiger1->next;

Es ergibt sich folgendes Bild:

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.20   next-Zeiger des neuen Elements auf die Adresse des next-Zeigers vom Vorgänger verweisen

Jetzt muss noch der next-Zeiger von zeiger1 auf die Adresse des neuen Elements zeigen:

zeiger1->next=zeiger

Hier klicken, um das Bild zu Vergrößern

Abbildung 23.21   next-Zeiger des Vorgängers auf das neue Element verweisen

Hier die vollständige Funktion sortiert_eingeben():

void sortiert_eingeben(char *n, char *v, int at, int am, int aj,
                        int et, int em, int ej, long geh) {
   struct angestellt *zeiger, *zeiger1;
   /* Ist es das 1. Element der Liste? */
   if(anfang==NULL)
      anhaengen(n,v,at,am,aj,et,em,ej,geh);
   /* Es ist nicht das 1. Element. Wir suchen so lange, bis das
    * gesuchte Element gefunden wird oder wir auf NULL stoßen */
   else {
      zeiger=anfang;
      while(zeiger != NULL && (strcmp(zeiger->name,n) < 0))
         zeiger=zeiger->next;
      /* Falls der Zeiger auf NULL zeigt, können wir unser
       * Element hinten anhängen, da unser neues Element das
       * "grösste" zu sein scheint */
      if(zeiger==NULL)
         anhaengen(n,v,at,am,aj,et,em,ej,geh);
      /* Ist unser neues Element das kleinste und somit
       * kleiner als das 1. Element, so müssen wir es an
       * den Anfang hängen */
      else if(zeiger==anfang) {
         anfang=(struct angestellt *)
           malloc(sizeof(struct angestellt));
         if(NULL == anfang) {
            fprintf(stderr, "Kein Speicher\n");
            return;
         }
         strcpy(anfang->name,strtok(n, "\n"));
         strcpy(anfang->vorname,strtok(v, "\n"));
         anfang->alter.tag=at;
         anfang->alter.monat=am;
         anfang->alter.jahr=aj;
         anfang->eingest.tag=et;
         anfang->eingest.monat=em;
         anfang->eingest.jahr=ej;
         anfang->gehalt=geh;
         anfang->next=zeiger;
            }
         /* Die letzte Möglichkeit ist, dass wir das Element
          * irgendwo in der Mitte einfügen müssen */
         else {
            zeiger1=anfang;
            /* Wir suchen das Element, das vor dem
             * Zeiger zeiger steht */
            while(zeiger1->next != zeiger)
               zeiger1=zeiger1->next;
            zeiger=(struct angestellt *)
              malloc(sizeof(struct angestellt));
            if(NULL == zeiger) {
               fprintf(stderr, "Kein Speicher");
               return;
            }
            strcpy(zeiger->name,strtok(n, "\n"));
            strcpy(zeiger->vorname,strtok(v, "\n"));
            zeiger->alter.tag=at;
            zeiger->alter.monat=am;
            zeiger->alter.jahr=aj;
            zeiger->eingest.tag=et;
            zeiger->eingest.monat=em;
            zeiger->eingest.jahr=ej;
            zeiger->gehalt=geh;
            /* Wir fügen das neue Element ein */
            zeiger->next=zeiger1->next;
            zeiger1->next=zeiger;
         } //Ende else
      } //Ende else
}

Das Programm wird in den nächsten Abschnitten noch verwendet und erweitert. Den kompletten Quellcode des Programms bis hierher (linear_list3.c) können Sie unter: http://www.pronix.de/ downloaden oder, noch besser, Sie versuchen diese Funktion selbst einzubauen.