13 Dynamische Datenstrukturen
In diesem Kapitel erfahren Sie etwas über das Erstellen von dynamischen Datenstrukturen, wie z. B. verkettete Listen. Mit den Kenntnissen zur dynamischen Speicherverwaltung (Kapitel 11) und den Strukturen (Abschnitt 12.1) haben Sie die Grundlagen für dynamische Datenstrukturen wie verkettete Listen oder binäre Bäume geschaffen. Der Vorteil solcher Strukturen, wie z. B. verketteter Listen, ist, dass damit wesentlich schneller Elemente eingefügt oder nicht mehr benötigte Elemente gelöscht werden können, als z. B. mit dynamischen Arrays. Außerdem wird immer nur so viel Speicher verwendet, wie Daten in der Liste vorhanden sind und benötigt werden. Auch das Sortieren ist mit Listen wesentlich schneller realisierbar als beispielsweise mit Arrays. Muss dann auch noch die Suche extra schnell sein, greift man zu den binären Bäumen, die im Grunde nur eine andere Form von Listen darstellen.
Wir beschränken uns in diesem Grundlagenbuch darauf, die einfachste Listenart – die einfach (vorwärts) verkettete Liste – detailliert darzustellen. Die doppelt verkettete Liste werden wir nur kurz anreißen, und auf das Thema Bäume (Trees), Stapel (Stacks) und Warteschlangen (Queues) werden wir nur am Rande verweisen. Wir haben überdies in dem Werk »C von A bis Z« Listen, Bäume, Stacks und Queues ausführlich behandelt. Wer es also »wirklich wissen« möchte, besorgt sich dieses Buch. Hiervor sei aber insofern gewarnt, als dass es wirklich alles enthält, was man über das Thema dynamische Datenstrukturen wissen muss und mit seinen 1.200 Seiten nicht gerade etwas ist, was man »mal eben« durcharbeiten kann. Mit ein paar Monaten müssen Sie hier schon mindestens rechnen.
13.1 (Einfach) verkettete Listen
Verkettete Listen sind zunächst auch nichts anderes als gewöhnliche Strukturtypen mit einem zusätzlichen Zeiger als Komponente von demselben Typ wie dem Strukturtyp. Damit kann der Zeiger dieser Komponente innerhalb der Struktur die Adresse einer anderen Strukturvariablen von demselben Typ speichern. Da jede Struktur einen solchen Strukturzeiger enthält, können Sie eine Struktur nach der anderen aneinanderhängen. Ein Beispiel hierzu wäre:
struct Id3_tag {
char titel[MAX];
char kuenstler[MAX];
char album[MAX];
short jahr;
char kommentar[MAX];
char genre[MAX];
struct Id3_tag *next; // Hier muss explizit "struct" stehen
};
Das Besondere an diesem Zeiger ist, dass er eine Adresse beinhaltet, die einen Wert von demselben Typ wie die Struktur selbst referenziert (struct Id3_tag). Mit diesem Zeiger können somit einzelne Strukturvariablen miteinander verkettet werden. Der next-Zeiger verweist immer auf die Adresse des nächsten Elements, das wiederum eine Strukturvariable mit denselben Komponenten und ebenfalls einen weiteren Zeiger beinhaltet. Zudem wird noch ein Ende für die Kette benötigt. Dazu kann man dem letzten next-Zeiger beispielsweise den NULL-Zeiger zuweisen oder einen speziellen Dummy-Ende-Zeiger von demselben Strukturtyp dafür anlegen. Auf jeden Fall sollten Sie einen speziellen Zeiger verwenden, der immer auf das erste Element in der verketteten Liste verweist, um nicht den »Faden« bzw. den Anfang der Kette zu verlieren.
Sie sollten wissen, dass für jedes neue Element in der Liste, das Sie hinzufügen, auch Speicherplatz vorhanden sein muss. In der Praxis wird für jedes neue Element mittels malloc() Speicher zur Laufzeit angefordert. Beim Löschen eines Elements in der Liste müssen Sie darauf achten, dass Sie den Speicher wieder an das System zurückgeben und die Liste nicht abreißen lassen. Achten Sie ganz besonders darauf, dass die Zeiger richtig miteinander »verkettet« sind. Nichts ist schlimmer, als ein ins Nirwana verweisender Zeiger bei einer verketteten Liste mit vielen Daten. Meistens können Sie dann nicht mehr auf diese Daten zugreifen, und wenn das Programm lange läuft, sind Sicherheitslücken wie Memory Leaks vorprogrammiert.
Jedes Element in der Liste wird als Knoten (engl. node) bezeichnet. Ein solcher Knoten enthält die eigentlichen Daten und einen Zeiger auf seinen Nachfolger.
Abbildung 13.1 Ein Listenelement mit seinen Daten und einem Zeiger auf seinen Nachfolger wird als Knoten bezeichnet.
Vereinfachte Beispiele in diesem Buch
Damit der Buchumfang wegen der Listings zu den verketteten Listen nicht ins Unermessliche wächst, wurde eine sehr einfache Datenstruktur mit nur einer Ganzzahl und dem Zeiger auf das nächste Element zur Demonstration verwendet. Sie können jedoch, da malloc() ja mit void* arbeitet, beliebige Speicherobjekte in Listen anordnen und mit void* auch beliebige Speicherobjekte miteinander verknüpfen. Probieren Sie es ruhig aus, es wird genau so funktionieren wie die einfachen Beispiele.
Nachfolgend sehen Sie ein etwas umfangreicheres Beispiel, das aber zunächst auf die nötigsten Funktionen beschränkt wurde. Die einzelnen Funktionen werden anschließend noch genauer erläutert.
00 // Kapitel13/verkettete_liste.c
01 #include <stdio.h>
02 #include <stdlib.h>
03 void dump_buffer(FILE *fp) {
04 int ch;
05 while( (ch = fgetc(fp)) != EOF && ch != '\n' )
06 /* Kein Anweisungsblock nötig */ ;
07 }
08 struct knoten {
int wert;
struct knoten *next;
};
09 typedef struct knoten Knoten_t;
10 typedef struct knoten* KnotenPtr_t;
11 KnotenPtr_t anfang = NULL;
12 void einfuegenKnoten( KnotenPtr_t neu ) {
13 KnotenPtr_t hilfZeiger;
14 if( anfang == NULL ) {
15 anfang = neu;
16 neu->next = NULL;
17 }
18 else {
19 hilfZeiger = anfang;
20 while(hilfZeiger->next != NULL) {
21 hilfZeiger = hilfZeiger->next;
22 }
23 hilfZeiger->next = neu;
24 neu->next = NULL;
25 }
26 }
27 void neuerKnoten( void ) {
28 KnotenPtr_t neu = malloc(sizeof(Knoten_t));
29 if( neu == NULL ) {
30 printf("Kein Speicher vorhanden!?\n");
31 return;
32 }
33 printf("Wert neuen fuer Knoten eingeben: ");
34 if( scanf("%d", &neu->wert) != 1 ) {
35 dump_buffer(stdin);
36 printf("Fehler bei der Eingabe\n");
37 free(neu); // Speicher wieder freigeben
38 return;
39 }
40 dump_buffer(stdin);
41 einfuegenKnoten( neu );
42 }
43 void loescheKnoten( int val ) {
44 KnotenPtr_t hilfZeiger1;
45 KnotenPtr_t hilfZeiger2;
46 if( anfang != NULL ) {
47 if( anfang->wert == val ) {
48 hilfZeiger1 = anfang->next;
49 free(anfang);
50 anfang = hilfZeiger1;
51 }
52 else {
53 hilfZeiger1 = anfang;
54 while( hilfZeiger1->next != NULL ) {
55 hilfZeiger2 = hilfZeiger1->next;
56 if( hilfZeiger2->wert == val ) {
57 hilfZeiger1->next = hilfZeiger2->next;
58 free(hilfZeiger2);
59 break;
60 }
61 hilfZeiger1 = hilfZeiger2;
62 } // Ende while
63 } // Ende else
64 } // Ende if
65 }
66 void knotenAuflisten( void ) {
67 KnotenPtr_t hilfZeiger = anfang;
68 printf("Elemente in der Liste:\n");
69 while( hilfZeiger != NULL ) {
70 printf("\t -> %d\n", hilfZeiger->wert);
71 hilfZeiger = hilfZeiger->next;
72 }
73 }
74 int main(void) {
75 int wahl = 0, val = 0;
76 do {
77 printf(" -1- Neues Element hinzufuegen\n");
78 printf(" -2- Element loeschen\n");
79 printf(" -3- Alle Elemente auflisten\n");
80 printf(" -4- Programmende\n");
90 printf(" Ihre Auswahl : ");
91 if( scanf("%d", &wahl) != 1 ) {
92 printf("Fehlerhafte Auswahl\n");
93 wahl = 0;
94 dump_buffer(stdin);
95 }
96 switch( wahl ) {
97 case 1 : neuerKnoten(); break;
98 case 2 : if( anfang == NULL ) {
99 printf("Liste ist leer!\n");
100 }
101 else {
102 printf("Wert zum Loeschen : ");
103 if( scanf("%d", &val) != 1 ) {
104 printf("Fehler bei der Eingabe\n");
105 }
106 else {
107 loescheKnoten( val );
108 }
109 }
110 break;
111 case 3 : if( anfang == NULL ) {
112 printf("Liste ist leer!\n");
113 }
114 else {
115 knotenAuflisten();
116 }
117 break;
118 }
119 }while( wahl != 4 );
120 return EXIT_SUCCESS;
121 }
Listing 13.1 verkettete_liste.c stellt ein Programm mit den grundlegenden Funktionen zur Verwaltung einer verketteten Liste dar.
Das Programm gibt bei der Ausführung z. B. Folgendes aus:
–1- Neues Element hinzufügen
–2- Element löschen
–3- Alle Elemente auflisten
–4- Programmende
Ihre Auswahl : 1
Wert für Knoten eingeben: 6789
–1- Neues Element hinzufügen
–2- Element löschen
–3- Alle Elemente auflisten
–4- Programmende
Ihre Auswahl : 3
1234
2345
4567
6789
–1- Neues Element hinzufügen
–2- Element löschen
–3- Alle Elemente auflisten
–4- Programmende
Ihre Auswahl : 2
Wert zum Löschen : 2345
–1- Neues Element hinzufügen
–2- Element löschen
–3- Alle Elemente auflisten
–4- Programmende
Ihre Auswahl : 3
1234
4567
6789
13.1.1 Ein neues Element in die Liste einfügen
Die grundlegende Operation auf verketteten Listen dürfte das Hinzufügen neuer Elemente sein. In unserem Listing wird diese Operation in den Zeilen (12) bis (42) durchgeführt:
12 void einfuegenKnoten( KnotenPtr_t neu ) {
13 KnotenPtr_t hilfZeiger;
14 if( anfang == NULL ) {
15 anfang = neu;
16 neu->next = NULL;
17 }
18 else {
19 hilfZeiger = anfang;
20 while(hilfZeiger->next != NULL) {
21 hilfZeiger = hilfZeiger->next;
22 }
23 hilfZeiger->next = neu;
24 neu->next = NULL;
25 }
26 }
27 void neuerKnoten( void ) {
28 KnotenPtr_t neu = malloc(sizeof(Knoten_t));
29 if( neu == NULL ) {
30 printf("Kein Speicher vorhanden!?\n");
31 return;
32 }
33 printf("Neuen Wert fuer Knoten eingeben: ");
34 if( scanf("%d", &neu->wert) != 1 ) {
35 dump_buffer(stdin);
36 printf("Fehler bei der Eingabe\n");
37 free(neu); // Speicher wieder freigeben
38 return;
39 }
40 dump_buffer(stdin);
41 einfuegenKnoten( neu );
42 }
Listing 13.2 Die Funktion einfuegenKnoten() fügt ein neues Element in eine Verkettete Liste ein.
Zuerst legen Sie immer einen neuen Knoten dynamisch zur Laufzeit an, also mit malloc(). Den neuen Knoten legen Sie in dem letzten Beispiel in den Zeilen (27) bis (42) an. In Zeile (28) wird dafür zuerst einmal Speicher vom Heap für das neue Element angefordert, und es werden auch gleich die Werte, in unserem Fall nur ein Wert für das Strukturelement, eingelesen. In Zeile (41) soll der fertige Knoten zur Liste hinzugefügt werden. Hierbei wird die Adresse des Knotens an die Funktion einfuegenKnoten() übergeben, die in den Zeilen (12) bis (26) aufgeführt ist. Sie hätten für diese Funktion durchaus auch den Namen KnotenEinfuegen() wählen können, wir haben aber hier eine Schreibweise gewählt, die Sie in fremden Programmen oft antreffen. Diese Schreibweise nennt in Kleinschrift zuerst das, was die Funktion tut und anschließend das Objekt, mit dem etwas getan wird.
In Zeile (14) überprüft die Funktion dann zunächst, ob überhaupt ein Element in der Liste vorhanden ist, oder ob der hier übergebene Zeiger doch auf NULL zeigt. Dies ist immer der Fall, dafür haben wir ja vorher gesorgt, aber man weiß ja nie, ob nicht irgendwann doch ein Fehler auftritt. Der Strukturzeiger anfang wurde am Anfang des Programms jedoch mit dem NULL-Zeiger belegt, und dies ist in Ordnung. Ist anfang dann immer noch der NULL-Zeiger, handelt es sich um den ersten Knoten in der Liste, der hinzugefügt werden soll. Daher bekommt der Zeiger anfang zuerst die Adresse des neuen Knotens (Zeile (15)), und dem Komponentenzeiger des Knotens auf das nächste Element in der Liste wird jetzt der NULL-Zeiger zugewiesen (Zeile (16)).
Abbildung 13.2 Der erste Knoten mit dem Wert 1234 wurde hier zu dem Beispiel in der Liste hinzugefügt.
Handelt es sich jedoch nicht um das erste Element, das hinzugefügt werden soll, durchlaufen Sie in den Zeilen (18) bis (25) die komplette verkettete Liste, bis Sie am Ende angekommen sind. Genau genommen leistet dies die while-Schleife in den Zeilen (20) bis (22). In dieser Schleife wird hilfZeiger so lange auf das nächste Element gesetzt, bis dieses ein NULL-Zeiger ist. Erst dann bekommt das nächste Element, das zuvor noch den NULL-Zeiger enthielt, in Zeile (23) die Adresse des neuen Knotens. Dem next-Zeiger des neuen Knotens wird anschließend in Zeile (24) der NULL-Zeiger zugewiesen. Sie müssen also in diesem Beispiel stets die gesamte Liste durchlaufen, um ein Element an die Liste anzuhängen.
Zeiger auf den letzten Knoten
An dieser Stelle muss angemerkt werden, dass ein Zeiger auf den letzten Knoten erheblich sinnvoller wäre, wenn Sie bei einer verketteten Liste das Element immer nur hinten anhängen. Damit ersparen Sie sich das ständige Durchlaufen aller Knoten. Allerdings hilft Ihnen das Durchlaufen der einzelnen Knoten zum besseren Verständnis, wenn Sie am Ende des Kapitels bei den Aufgaben den neuen Knoten sortiert einfügen sollen. Alternativ können neue Elemente auch sofort immer am Anfang der Liste eingefügt werden. Dies minimiert den Aufwand noch mehr und steigert die Geschwindigkeit ungemein, aber auch hier können natürlich die Elemente nicht sortiert eingefügt werden. Sie erhalten dann im Endeffekt einen Stack (Stapel), und das Element, das Sie zuletzt eingefügt haben, liegt auch immer oben auf dem Stapel. Dieses Prinzip wird FIFO (First In First Out) genannt.
Abbildung 13.3 Ein weiteres Element (hier mit dem Wert 2345) wurde zur verketteten Liste hinzugefügt.
13.1.2 Ein Element suchen und ausgeben
Alle Elemente auszugeben ist für Sie wahrscheinlich bereits ein Kinderspiel. Hierbei müssen Sie lediglich alle Knoten – vom ersten bis zum letzten – durchlaufen. Diese Funktion wurde in den Zeilen (66) bis (73) definiert:
66 void knotenAuflisten( void ) {
67 KnotenPtr_t hilfZeiger = anfang;
68 printf("Elemente in der Liste:\n");
69 while( hilfZeiger != NULL ) {
70 printf("\t -> %d\n", hilfZeiger->wert);
71 hilfZeiger = hilfZeiger->next;
72 }
73 }
Wichtig ist hier, dass Sie einen Hilfszeiger verwenden und die einzelnen Knoten nicht über den anfang-Zeiger durchlaufen. In diesem Fall wäre die Liste für immer verloren, da Sie ja den Anfang an das Ende verschoben hätten. Der Hilfszeiger durchläuft also in einer Schleife Knoten für Knoten, bis er auf den NULL-Zeiger und somit auf das Ende der Liste stößt. Ähnlich wie diese Funktion ist auch die Suchfunktion aufgebaut, die Sie am Ende des Kapitels als Aufgabe erstellen sollen. Hierbei müssen Sie zusätzlich noch Knoten für Knoten überprüfen, ob das gesuchte Element gefunden wurde.
13.1.3 Ein Element aus der Liste entfernen
Das Löschen eines Knotens ist etwas schwieriger. Die Funktion wurde in den Zeilen (43) bis (65) definiert. Dort wurde der zu löschende Wert als Funktionsparameter mit übergeben:
43 void loescheKnoten( int val ) {
44 KnotenPtr_t hilfZeiger1;
45 KnotenPtr_t hilfZeiger2;
46 if( anfang != NULL ) {
47 if( anfang->wert == val ) {
48 hilfZeiger1 = anfang->next;
49 free(anfang);
50 anfang = hilfZeiger1;
51 }
52 else {
53 hilfZeiger1 = anfang;
54 while( hilfZeiger1->next != NULL ) {
55 hilfZeiger2 = hilfZeiger1->next;
56 if( hilfZeiger2->wert == val ) {
57 hilfZeiger1->next = hilfZeiger2->next;
58 free(hilfZeiger2);
59 break;
60 }
61 hilfZeiger1 = hilfZeiger2;
62 } // Ende while
63 } // Ende else
64 } // Ende if
65 }
In der Funktion loescheKnoten() überprüfen Sie zunächst in Zeile (46), ob überhaupt ein Knoten in der Liste vorhanden ist. Ist dem nicht so, macht diese Funktion nichts, weil der nachfolgende Anweisungsblock nicht ausgeführt wird. Sie können natürlich an dieser Stelle auch eine kleine Übung einschieben und eine Fehlermeldung implementieren, die anzeigt, dass ein Knoten nicht aus einer leeren Liste entfernt werden kann.
13.1.4 Das erste Element in der Liste löschen
Nun überprüfen Sie in Zeile (47), ob es der erste Knoten in der Liste ist, der das gesuchte Element enthält und der gelöscht werden soll. Dieser Fall wird in den Zeilen (48) bis (50) behandelt. hilfZeiger1 bekommt die Adresse des nächsten (!) Elements hinter dem Element, auf das anfang verweist (Zeile (48)):
Abbildung 13.4 Das erste Element ist das gesuchte, daher verweist hilfZeiger1 zunächst auf das nachfolgende Element.
Mit hilfZeiger1 haben Sie den künftigen neuen Anfang der Liste gesichert. Nun können Sie den alten anfang mit free() in Zeile (49) freigeben:
Abbildung 13.5 Der Speicher für das erste Element wurde freigegeben.
Zum Schluss müssen Sie dem Zeiger anfang die Adresse des neuen Anfangs in der Liste übergeben, den Sie zuvor in Zeile (48) gesichert haben. In Zeile (50) bekommt der Zeiger anfang die Adresse von hilfZeiger1, und die Löschung des ersten Elements ist komplett:
Abbildung 13.6 Der Zeiger anfang verweist auf das neue erste Element in der Liste.
13.1.5 Ein beliebiges Element in der Liste löschen
Sie können aber auch ein beliebiges Element in der Liste löschen, sofern es nicht das erste ist. Dies wird im letzten Listing in den Zeilen (52) bis (63) gemacht. Auch hier lassen Sie hilfZeiger1 zunächst in Zeile (53) auf den Anfang der Liste verweisen. Anschließend wird der Code zwischen den Zeilen (54) bis (62) ausgeführt. Die while-Schleife in Zeile (54) wird hierbei so lange durchlaufen, bis das nächste Element, auf das hilfZeiger1 verweist, der NULL-Zeiger und somit das Ende der Liste ist. Das bedeutet dann, dass das Element nicht in der Liste vorhanden ist. In der Schleife selbst bekommt hilfZeiger2 in Zeile (55) immer die Adresse des nächsten Elements von hilfsZeiger1. Schlägt die Überprüfung in Zeile (56) fehl, wurde der von uns gesuchte Knoten nicht gefunden, und hilfZeiger1 bekommt die Adresse von hilfZeiger2. Dann beginnt der nächste Schleifendurchlauf.
Im nächsten Beispiel wird jetzt davon ausgegangen, dass das zweite Element in der Liste das gesuchte ist – dass Zeile (56) also wahrheitsgemäß zutrifft. Grafisch würde die Liste bis zu Zeile (56) wie in Abbildung 13.7 aussehen.
Abbildung 13.7 hilfZeiger2 verweist auf den von uns gesuchten Knoten.
In Zeile (57) wird das zu löschende Element »ausgehängt«, indem der next-Zeiger von Knoten hilfsZeiger1 auf den nächsten Knoten hinter hilfsZeiger2 verweist. Grafisch dürfte dies einfacher verstehen zu sein (siehe Abbildung 13.8).
Abbildung 13.8 Das zu löschende Element wird ausgehängt.
Der Knoten ist nun aus der Liste entfernt worden. Jetzt müssen Sie nur noch den reservierten Speicherplatz für den Knoten in Zeile (58) mittels free() freigeben, damit hier keine Speicherlecks entstehen. Mit break wird dann die Schleife und damit auch die Funktion abgebrochen:
Abbildung 13.9 Um Speicherlecks (engl memory leaks) zu vermeiden, muss der nicht mehr benötigte Knoten wieder freigegeben werden.