C-Programmierung: Verkette Listen

Aus Wikibooks

Wechseln zu: Navigation, Suche

Beim Programmieren in C kommt man immer wieder zu Punkten, an denen man feststellt, dass man mit einem Array nicht auskommt. Diese treten zum Beispiel dann ein, wenn man eine unbekannte Anzahl von Elementen verwalten muss. Mit den Mitteln, die wir jetzt kennen, könnte man beispielsweise für eine Anzahl an Elementen Speicher dynamisch anfordern und wenn dieser aufgebraucht ist, einen neuen größeren Speicher anfordern, den alten Inhalt in den neuen Speicher schreiben und dann den alten wieder löschen. Klingt beim ersten Hinsehen ziemlich ineffizient, Speicher allokieren, füllen, neu allokieren, kopieren und freigeben. Also lassen Sie uns überlegen, wie wir das Verfahren optimieren können.

[Bearbeiten] 1. Überlegung:

Wir fordern vom System immer nur Platz für ein Element an. Vorteil: Jedes Element hat einen eigenen Speicher und wir können jetzt für neue Elemente einfach einen malloc ausführen. Weiterhin sparen wir uns das Kopieren, da jedes Element von unserem Programm eigenständig behandelt wird. Nachteil: Wir haben viele Zeiger, die jeweils auf ein Element zeigen und wir können immer noch nicht beliebig viele Elemente verwalten.

[Bearbeiten] 2. Überlegung:

Jedes Element ist ein komplexer Datentyp, welcher einen Zeiger enthält, der auf ein Element gleichen Typs zeigen kann. Vorteil: wir können jedes Element einzeln allokieren und so die Vorteile der ersten Überlegung nutzen, weiterhin können wir nun in jedem Element den Zeiger auf das nächste Element zeigen lassen, und brauchen in unserem Programm nur einen Zeiger auf das erste Element. Somit ist es möglich, beliebig viele Elemente zur Laufzeit zu verwalten. Nachteil: Wir können nicht einfach ein Element aus der Kette löschen, da sonst kein Zeiger mehr auf die nachfolgenden existiert.

[Bearbeiten] Die einfach verkettete Liste

Die Liste ist das Resultat der beiden Überlegungen, die wir angestellt haben. Die einfachste Art, eine verkettete Liste zu erzeugen, sieht man im folgenden Beispielquelltext (welcher nicht funktioniert):

  1. #include <stdio.h>

  2. #include <stdlib.h>

  3.  

  4. struct element {

  5.        int value; // der Wert des Elements

  6.        struct element *next; // das nächste Element

  7. };

  8.  

  9. void append(struct element ***lst, struct element *new)

  10. {

  11.   struct element *lst_iter = *lst;

  12.  

  13.   if ( lst_iter!= NULL ) { // sind Elemente vorhanden

  14.       while (lst_iter->next != NULL ) // suche das letzte Element

  15.           lst_iter=lst_iter->next;

  16.       lst_iter->next=new; // Hänge das Element hinten an

  17.   }

  18.   else // wenn die liste leer ist, bin ich das erste Element

  19.       *lst=new;

  20. }

  21.  

  22. int main(int argc, char *argv[])

  23. {

  24.     struct element *first;

  25.     struct element *einE;

  26.  

  27.     if (argc > 1) {

  28.             printf("Zu viele Parameter fuer %s \n", argv[0]);

  29.             return EXIT_FAILURE;

  30.     }

  31.       first = NULL; // init. die Liste mit NULL = leere liste

  32.       einE = malloc(sizeof(*einE)); // erzeuge ein neues Element

  33.       einE->value = 1;			     

  34.       einE->next = NULL; // Wichtig für das Erkennen des Listenendes

  35.  

  36.       append(&first, einE); // füge das Element in die Liste ein

  37.  

  38.       return EXIT_SUCCESS;

  39. }

<< Speicherverwaltung | Inhaltsverzeichnis | Fehlerbehandlung >>

Von „http://de.wikibooks.org/wiki/C-Programmierung:_Verkette_Listen“
Persönliche Werkzeuge