ein Kapitel zurück                                           ein Kapitel weiter

Im Gegensatz zu einfach verkettete Listen haben doppelt verkettete noch zusätzlich einen Zeiger auf den Vorgänger. Nehmen wir an sie wollen aus einer Liste einen Namen löschen und anschließend auf den Vorgänger des gelöschten Namen zugreifen. Nun müssten sie wieder die ganze Liste von vorne durchlaufen. Mit einer doppelt verketteten Liste haben wir nun Zugriff auf den Vorgänger und den Nachfolger. Wir müssen zu unserer Struktur nur einen Zeiger mehr hinzufügen....

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 wollen wir noch einen Zeiger auf das letzte Element zufügen. Denn nehmen wir mal an wir suchen nach einem Namen der mit dem Buchstaben 'Z' beginnt, wozu also die ganze Liste von vorne durchlaufen lassen wenn wir jetzt da wir einen Zeiger auf den Vorgänger haben von hinten anfangen könnten. Somit hätten wir noch folgende Initialisierungen... 

struct angestellt *next;
struct angestellt *anfang;
struct angestellt *ende;

Dies wollen wir jetzt in eine Funktion umschreiben.... 

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

Wollen wir mal schauen wie unser Struktur nun bildlich aussieht...


Doppelt verkettete Listen


Und nun bevor wir loslegen das ganze ins Programm umzusetzen wollen wir uns auch noch ansehen wie wir uns das mit den doppelt verketteten Liste vorstellen können...


doppelt verkettete Listen


Jetzt haben wir zusätzlich zu dem Zeiger anfang, der immer auf das 1. Element der Liste zeigt, den Zeiger ende der jetzt immer auf das letzte Element der Liste zeigt. Fangen wir also an unsere Funktionen die wir im Kapitel zuvor kennengelernt haben umzuschreiben damit wir sie als doppelt verkettete Liste verwenden können. Was sich auch nicht als allzu schwer heraus stellen wird, da wir ja nur darauf achten müssen das jedes Element jetzt auch einen Vorgänger hat und wir auch die Liste von Hinten lesen könnten, da jetzt noch ein Zeiger für das letzte Element hinzukommt. Fangen wir mit der Funktion anhaengen() an ....

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;

/*Wir fragen ab ob es schon ein Element in der List gibt. Wir
suchen das Element auf dem unser Zeiger *anfang zeigt.
Falls *anfang immer noch auf NULL zeigt bekommt *anfang die
Adresse unseres 1.Elementes und ist somit der Kopf (Anfang)
unserer Liste*/
 if(anfang == NULL)
  {
/*Wir reservieren Speicherplatzt für unser Struktur für das
erste Element der Liste*/
   if((anfang =(struct angestellt *)malloc(sizeof(struct angestellt))) == NULL)
      fprintf(stderr,"Kein Speicherplatzt vorhanden für anfang\n");
   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;

Bis hierhin ist unsere Funktion nichts neues. Wir nehmen an das noch kein Element in der Liste vorhanden ist und geben das erste ein. 

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

Der next - Zeiger unserem ersten Elementes zeigt erst mal auf gar nicht (NULL). Der ende - Zeiger der auf das letzte Element zeigt, zeigt am Anfang natürlich ebenfalls auf das 1. Element, das gleichzeitig ja auch das letzte ist, der Liste. Der previous - Zeiger der auf den Vorgänger zeigen soll zeigt jetzt auch erst mal auf NULL. Genauso gut hätten wir anstatt ende->previous=NULL auch schreiben können anfang->previous=NULL. Beides hätte den selben Effekt gehabt. Ich glaube eine Bild kann ich mir hier sparen. Kommen wir zur 2. Möglichkeit. Wir hängen das Element hinten an....

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,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;
   zeiger->gehalt=g;

Auch am Anfang bleibt beim "hinten Anhängen" alles beim alten bis auf dem zeiger1 der auf das momentan "noch" letzte Element zeigt wie zeiger. Anschließend lassen wir unseren Zeiger zeiger auf den neuen Speicherplatz zeigen, denn wir zuvor mit malloc reserviert haben....


doppelt verkettete Listen


Nun geht es weiter unser neues Element einzufügen.... 

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

Wir übergeben dem next - Zeiger unseres neuem Elementes den NULL - Zeiger. Unseren ende - Zeiger lassen wir auch auf das neue Element zeigen, da es ja das letzte Element der Liste entspricht. Zusätzlich geben wir unserem neuen Element auch die Adresse des Vorgängers auf die zeiger1 zeigt. Somit ergibt sich folgendes Bild.....


doppelt verkettete Listen


Schwieriger wird jetzt schon unsere nächste Funktion, nämlich das löschen eines Elementes 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 1. Element ist das von uns gesuchte und soll gelöscht werden. Als erstes lassen wir eine Zeiger auf unsere zukünftige Anfangsdatei zeigen. Natürlich vorrausgesetzt es ist mehr wie eine Datei vorhanden. Falls nicht (if(zeiger == NULL)) wir die Anweisung der if() - Abfrage aktiv.


doppelt verkettete Listen


Wir gehen mal davon aus das mehrere Elemente in der Liste vorhanden sind. Nun folgen zeiger->previous=NULL; free(anfang); anfang=zeiger; und somit hätten wir das 1. Element gelöscht...


doppelt verkettete Listen


Die 2. Möglichkeit wäre unser zu löschendes Element ist das letzte der Liste... 

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

Ich überlasse die 2. Möglichkeit Ihnen den Vorgang auf ein Blatt Papier zu zeichnen. Da er ähnlich ist wie beim 1. Element spar ich mir die Arbeit.

Kommen wir zur 3.Möglichkeit : Die zu löschende Datei ist irgendwo zwischendrin oder am Ende... 

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

Nehmen wir mal an wir haben die zu löschende Datei gefunden. Nun haben wir folgende Situation....

doppelt verkettete Listen


Unser zeiger1 zeigt auf die zu löschende Datei. Jetzt wollen wir die Datei "aushängen" auf die zeiger1 zeigt... 

zeiger->next=zeiger1->next;



doppelt verkettete Listen




zeiger2=zeiger1->next;



doppelt verkettete Listen




zeiger2->previous=zeiger;



doppelt verkettete Listen




free(zeiger1);



doppelt verkettete Listen


Somit hätten wir unser Funktion löschen besprochen. Hier nochmals die ganze 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 vor-
handen ist*/
     zeiger=anfang;
     while(zeiger->next != NULL)
       {
        zeiger1=zeiger->next;
/*Ist die Adresse von zeiger1 der gesuchte Namen?*/
       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 Funktion eingabe() und ausgabe() brauchen wir nicht zu verändern. Für die beiden Funktionen loesche_alles() und sortiert_eingeben() will ich das nächste Kapitel verwenden damit diese Seite nicht zu umfangreich wird.

ein Kapitel zurück          nach oben           ein Kapitel weiter


© 2001,2002 Jürgen Wolf