In diesem Kapitel sollen einige Funktionen aus Standardheaderdateien näher erläutert werden. Alle Headerdateien sind vom ANSI C Komitee vorgeschrieben und somit auf allen Systemen einsetzbar. C C++ C/C++ Standardfunktionen Headerdateien ANSI C assert.h ctype.h math.h stdlib.h signal.h setjmp.h Standardfunktionen - Headerdateien ANSI C assert.h ctype.h math.h stdlib.h signal.h setjmp.h Kapitel 24: Dynamische Datenstrukturen)

24.2. Doppelt verkettete Listen            zurück  zum Inhaltsverzeichnis

Im Gegensatz zu den einfach verketteten Listen haben doppelt verkettete zusätzlich noch einen Zeiger auf den Vorgänger. Soll z.B. erst ein Element in der Liste gelöscht werden, und gleich darauf wird auf den Vorgänger des gelöschten Elements zugegriffen, müsste bei der einfach verketteten Liste der vollständige Satz von neuem durchlaufen werden. Mit der doppelt verketteten Liste kann hingegen sofort auf den Vorgänger zugegriffen werden. Zur Realisierung doppelt verketteter Listen muss nur der Struktur bei der Deklaration ein weiterer Zeiger hinzugefügt werden:

struct angestellt{
            char name[20];
            char vorname[20];
            struct datum alter;
            struct datum eingest;
            long gehalt;
            struct angestellt *next;       /*Nachfolger*/
            struct angestellt *previous;   /*Vorgänger*/
                  };

Außerdem sollten Sie noch einen Zeiger auf das letzte Element definieren. Wird z.B. nach einem Namen mit dem Anfangsbuchstaben "Z" gesucht, wäre es doch reine Zeitverschwendung, die Liste von vorn zu durchlaufen. Also gäbe es noch folgende Angaben:

struct angestellt *anfang;
struct angestellt *ende;

Die Initialisierung mit NULL soll gleich in eine Funktion verpackt werden:

void start(void)
{
   anfang=ende=NULL;
}

So sieht die Struktur jetzt mit dem Extra-Zeiger auf seinen Vorgänger aus:

Abbildung 24.22: Struktur einer doppelt verketteten Liste

Abbildung 24.22: Struktur einer doppelt verketteten Liste

Bevor all dies in die Praxis umgesetzt wird, noch schnell ein Bild dazu, wie Sie sich eine doppelt verkettete Liste vorstellen können:

Abbildung 24.23: Doppelt verkettete Liste

Abbildung 24.23: Doppelt verkettete Liste

Auf den kommenden Seiten werden die Funktionen, die im Abschnitt über die einfach verketteten Listen verwendet wurden, umgeschrieben, damit diese mit doppelt verketteten Listen eingesetzt werden können. Es muss dabei immer darauf geachtet werden, dass jetzt jedes Element in der Liste auch einen Vorgänger besitzt.

Es soll mit der Funktion anhaengen() angefangen werden:

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, *zeiger1;

   /* Wurde schon Speicher für den ende-Zeiger bereitgestellt?*/
   if(ende == NULL)
      {
         if((ende=(struct angestellt *)
                      malloc(sizeof(struct angestellt))) == NULL)
            {
               printf("Konnte keinen Speicherplatz für ende "
                      "reservieren\n");
               exit(0);
            }
      }

   /*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");
         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=eint;
         anfang->eingest.monat=einm;
         anfang->eingest.jahr=einj;
         anfang->gehalt=g;

Bis hierhin stellt diese Funktion nichts Neues dar. Es wird davon ausgegangen, dass sich noch kein Element in der Liste befindet, und Sie fügen nun das erste Element ein:

         anfang->next=NULL;
         ende=anfang;
         ende->previous=NULL;
      }

Der next-Zeiger vom ersten Element zeigt zunächst auf gar nichts (NULL). Der ende-Zeiger, der auf das letzte Element verweist, zeigt am Anfang zunächst auf das erste Element, das gleichzeitig ja auch das letzte der Liste ist. Der previous-Zeiger, der auf den Vorgänger zeigen soll, verweist ebenso auf NULL. Genauso gut hätten Sie anstatt ende->previous=NULL auch anfang->previous=NULL schreiben können. Beides hätte denselben Effekt gehabt.

Jetzt zur zweiten Möglichkeit - das neue Element wird hinten angehängt:

   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 "
                            "letztes Element\n");
         zeiger1=zeiger;
         zeiger=zeiger->next; /*zeiger auf neuen Speicherplatz*/
         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=eint;
         zeiger->eingest.monat=einm;
         zeiger->eingest.jahr=einj;
         zeiger->gehalt=g;

Auch am Anfang bleibt beim hinten Anhängen alles beim Alten bis auf den zeiger1, der wie zeiger auf das momentan (noch) letzte Element zeigt. Anschließend verweist man den Zeiger zeiger auf den neuen Speicherplatz, der zuvor mit malloc() reserviert wurde:

Abbildung 24.24: Neues Element wurde hinten angefügt mit einfacher Verkettung

Abbildung 24.24: Neues Element wurde hinten angefügt mit einfacher Verkettung

Die weiteren Schritte zum Einfügen des neuen Elements sind:

         zeiger->next=NULL;
         ende=zeiger;
         zeiger->previous=zeiger1;
         zeiger1->next=zeiger;
       }

Der next-Zeiger des neuen Elements bekommt den NULL-Zeiger. Der ende-Zeiger verweist auf das neue Element, da es das letzte Element in der Liste ist. Zusätzlich bekommt das neue Element auch die Adresse des Vorgängers, auf die zeiger1 verweist. Und zeiger1->next bekommt noch die Adresse des neuen Elements zeiger übergeben. Somit ergibt sich folgendes Bild:

Abbildung 24.25: Neues Element wurde hinten angefügt mit doppelter Verkettung

Abbildung 24.25: Neues Element wurde hinten angefügt mit doppelter Verkettung

Schwieriger wird die nächste Funktion, nämlich das Löschen eines Elements in der Liste:

void loesche(char wen[])
{
   struct angestellt *zeiger ,*zeiger1, *zeiger2;

   /*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;
               if(zeiger == NULL)
                  {
                     free(anfang);
                     anfang=NULL;
                     ende=NULL;
                     return;
                  }
               zeiger->previous=NULL;
               free(anfang);
               anfang=zeiger;
            }

Die erste Möglichkeit: Das erste Element ist das gesuchte und soll gelöscht werden. Als Erstes lassen Sie einen Zeiger auf die zukünftige Anfangsdatei zeigen. Natürlich vorausgesetzt, es ist mehr als ein Element vorhanden. Falls nicht (if(zeiger == NULL)), wird die Anweisung der if-Bedingung aktiv. Der momentane Stand:

Abbildung 24.26: Erstes Element in der Liste (anfang) soll gelöscht werden

Abbildung 24.26: Erstes Element in der Liste (anfang) soll gelöscht werden

Es wird davon ausgegangen, dass bereits mehrere Elemente in der Liste vorhanden sind. Also folgt nur noch:

zeiger->previous=NULL;
free(anfang);
anfang=zeiger;

und schon ist das erste Element in der Liste gelöscht:

Abbildung 24.27: Erstes Element in der Liste wurde gelöscht

Abbildung 24.27: Erstes Element in der Liste wurde gelöscht

Die zweite Möglichkeit ist, dass das zu löschende Element das letzte in der Liste ist:

else if(strcmp(ende->name,wen) == 0)
   {
      zeiger=ende->previous;
      zeiger->next=NULL;
      zeiger1=ende;
      ende=zeiger;
      free(zeiger1);
   }

Da der Vorgang ähnlich wie beim ersten Element abläuft, kann dieser auf einem Blatt Papier zur Übung selbst aufgezeichnet werden.

Weiter geht es mit der dritten Möglichkeit: Das zu löschende Element ist irgendwo zwischendrin:

   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;
               zeiger2=zeiger1->next;
               zeiger2->previous=zeiger;
               free(zeiger1);
               break;
            }
         zeiger=zeiger1;
      }

Es sei hier wieder angenommen, das zu löschende Element wurde gefunden, und es ist das zweite Element (im Bild mit del gekennzeichnet):

Abbildung 24.28: Element auf das zeiger1 verweist soll gelöscht werden

Abbildung 24.28: Element auf das zeiger1 verweist soll gelöscht werden

zeiger1 verweist auf das zu löschende Element. Dieses Element muss jetzt ausgehängt werden. Die weiteren Schritte sind somit:

zeiger->next=zeiger1->next; 

Abbildung 24.29: Zu löschendes Element zum Teil aushängen

Abbildung 24.29: Zu löschendes Element zum Teil aushängen

zeiger2=zeiger1->next; 

Abbildung 24.30: Ein Zeiger auf den Vorgänger des zu löschenden Elements

Abbildung 24.30: Ein Zeiger auf den Vorgänger des zu löschenden Elements

zeiger2->previous=zeiger;        

Abbildung 24.31: Zu löschendes Element komplett ausgehängt

Abbildung 24.31: Zu löschendes Element komplett ausgehängt

free(zeiger1);

Abbildung 24.32: Speicherplatz freigegeben

Abbildung 24.32: Speicherplatz freigegeben

Der Vorgang lässt sich anhand der Grafiken recht einfach nachvollziehen. Hier nochmals die vollständige Funktion zur Übersicht:

/*Funktion zum Löschen einer Datei*/
void loesche(char wen[])
{
   struct angestellt *zeiger ,*zeiger1, *zeiger2;

   /*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;
               if(zeiger == NULL)
                  {
                     free(anfang);
                     anfang=NULL;
                     ende=NULL;
                     return;
                  }
               zeiger->previous=NULL;
               free(anfang);
               anfang=zeiger;
            }
         /*Ist das letzte Element das von uns gesuchte? */
         else if(strcmp(ende->name,wen) == 0)
            {
               zeiger=ende->previous;
               zeiger->next=NULL;
               zeiger1=ende;
               ende=zeiger;
               free(zeiger1);
            }
         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;
                           zeiger2=zeiger1->next;
                           zeiger2->previous=zeiger;
                           free(zeiger1);
                           break;
                        }
                     zeiger=zeiger1;
                  }
            }
      }
   else
      printf("Es sind keine Daten zum Löschen vorhanden!!!\n");
}

Die Funktionen eingabe() und ausgabe() müssen nicht verändert werden.

Die Funktion loesche_alles() ist ebenfalls relativ einfach umzuschreiben. Es muss lediglich die ganze Liste durchlaufen werden, und dabei müssen alle bis auf das erste und letzte Element gelöscht werden:

void loesche_alles()
{
   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;
               if(zeiger1 == NULL)
                  break;
               anfang->next=zeiger1;
               zeiger1->previous=anfang;
               free(zeiger);
               zeiger=zeiger1;
            }

Abbildung 24.33: Momentane Zeigerstellung der Funktion loesche_alles()

Abbildung 24.33: Momentane Zeigerstellung der Funktion loesche_alles()

Die if-Abrage, ob der Zeiger zeiger1 auf NULL zeigt, wird als Abbruchbedingung benutzt, da - falls das wahr sein sollte - nur noch zwei Elemente in der Liste vorhanden sind. Genauso gut hätten Sie dies mit der while-Abfrage vornehmen können: while(zeiger->next != NULL) Zu dieser Funktion noch ein kleiner bildlicher Ablauf. Zuerst wird das Element, auf das zeiger verweist, ausgehängt:

anfang->next=zeiger1;
zeiger1->previous=anfang;

Abbildung 24.34: Zu löschendes Element aushängen

Abbildung 24.34: Zu löschendes Element aushängen

Danach kann der Speicherplatz, auf den zeiger zeigt, mit free() freigegeben werden. Es ergibt sich folgendes Bild:

Abbildung 24.35: Speicherplatz freigegeben

Abbildung 24.35: Speicherplatz freigegeben

Hier endet die while-Schleife, da zeiger1=anfang->next->next jetzt auf NULL zeigt. Jetzt müssen nur noch die letzten beiden Elemente in der Liste gelöscht werden:

free(anfang);
free(ende);
anfang=NULL;
ende=NULL;

Dazu müssen Sie den Speicherplatz, auf den anfang und ende zeigen, freigeben. Anschließend bekommen die Zeiger anfang und ende den NULL-Zeiger. Die Funktion loesche_alles() komplett:

void loesche_alles()
{
   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;
               if(zeiger1 == NULL)
                  break;
               anfang->next=zeiger1;
               zeiger1->previous=anfang;
               free(zeiger);
               zeiger=zeiger1;
            }

         /*Jetzt löschen wir erst den Anfang der Liste und
           das Ende der Liste*/
         free(anfang);
         free(ende);
         anfang=NULL;
         ende=NULL;
         printf("Liste erfolgreich gelöscht!!\n");
      }
   else
      fprintf(stderr,"Keine Liste zum Löschen vorhanden!!\n");
}

Als Nächstes soll die Funktion sortiert_eingeben() umgeschrieben werden, damit diese für doppelt verkettete Listen verwendet werden kann:

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 nun 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;
               anfang->previous=NULL;
            }

Die Erklärung, ob es sich hier um das einzige, das erste oder das letzte Element der Liste handelt, kann bei der Funktion anhaengen() in Abschnitt 24.1, Lineare Listen (einfach verkettete Listen), nachgelesen werden. Viel interessanter ist es, wie ein Element irgendwo dazwischen eingefügt wird. Hierzu zunächst der weitere Codeverlauf:

         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!!!\n");
                     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;
               zeiger->previous=zeiger1;
               zeiger1->next=zeiger;
               zeiger1->next->previous=zeiger;
         } /*Ende else*/

Es wird davon ausgegangen, dass die Position für das neue Element bereits ermittelt wurde, und sich zeiger1 vor diesem Element befindet. Somit ergibt sich folgender Zustand:

Abbildung 24.36: Neues Element einfügen

Abbildung 24.36: Neues Element einfügen

Jetzt soll das neue Element, auf welches zeiger verweist, zwischen dem zweiten und dem dritten Element eingefügt werden. Hierzu die weiteren Schritte:

zeiger->next=zeiger1->next;

Abbildung 24.37: Zeiger auf den Nachfolger des neuen Elements

Abbildung 24.37: Zeiger auf den Nachfolger des neuen Elements

zeiger->previous=zeiger1;

Abbildung 24.38: Zeiger auf den Vorgänger des neuen Elements

Abbildung 24.38: Zeiger auf den Vorgänger des neuen Elements

zeiger1->next=zeiger;
zeiger1->next->previous=zeiger;

Abbildung 24.39: Zeiger vom Vorgänger und Nachfolger zum neuen Element

Abbildung 24.39: Zeiger vom Vorgänger und Nachfolger zum neuen Element

Das soll es vorerst mit dem Kapitel "Doppelt verkettete Listen" gewesen sein. Wenn folgende Ratschläge zu diesem Thema beherzigt werden, dürften keine Probleme zu erwarten sein:

Das vollständige Listing kann unter der Adresse http://www.pronix.de/Einstieg/ heruntergeladen werden. Dem Listing wurden noch einige Funktionen, u.a. das Laden oder Speichern von Daten auf der Festplatte, hinzugefügt.

Weiter mit 24.3. Stacks nach dem LIFO (Last-in-First-out)-Prinzip            zum Inhaltsverzeichnis