| Information des Listenelements(hier: Zeichenkette, z. B. ein Name) | Zeiger auf nachfolgendes Element |
Die Deklaration der entsprechenden Struktur sieht folgendermaßen aus: struct LinListe { char inhalt[80]; struct LinListe *next;};Beim Aufbau der verketteten Liste können die einzelnen Listenelemente gleich nach einem bestimmten Ordnungskriterium (hier: Stringvergleich) hintereinander gehängt werden:
Das Symbol für elektrische Masse am Ende des letzten Elements deutet dabei
den NULL-Zeiger an, der das Ende der Liste anzeigt.
Da jedes Element auf seinen Nachfolger zeigt, kann die ganze Liste an einem
einzigen Zeiger hängen. Dieser Zeiger ist der Ursprung der Liste, oder
auf englisch "root". root ist in den folgenden Beispielen eine globale
Variable. Zeiger auf Listenelemente sind Zeiger auf Strukturvariable.
Wenn die Liste aufgebaut ist, so können in einer Schleife alle Elemente
durchgegangen und der Inhalt ausgegeben oder geändert werden, wie das
folgende Programmfragment, die Ausgabe der Liste, zeigt:
void DruckeListe(struct LinListe *root)
{
struct LinListe *Tail = root;
while (Tail != NULL)
{
printf("%s\n", Tail->inhalt);
Tail = Tail->next;
}
}
Der Zeiger Tail (Schwanz) wird benötigt, um an der Liste entlang zu gehen.
Tail kann so lange auf das jeweils nächste Element gesetzt werden, bis das
Listenende erreicht ist. Den NULL-Zeiger zu dereferenzieren, würde zu
einem Laufzeitfehler führen.
Man kann die Ausgabe auch rekursiv formulieren:
void DruckeListeRecursiv(struct LinListe *root)
{
if (root != NULL)
{
printf("%s\n", root->inhalt);
DruckeListeRecursiv(root->next);
}
}
Als nächstes wollen wir ansehen, wie ein neuer Auftrag in die Liste eingefügt
wird. Wir nehmen jetzt an, daß die Liste so aufgebaut wird, daß die
Elemente der lexikalischen Ordnung nach geordnet sind. Man nennt diesen Vorgang auch
"Sortieren durch Einfügen".
Für ein neues Listenlelement wird zuerst eine neue Datenstruktur angelegt. Wenn
kein Speicherbereich ausreichender Größe zur Verfügung steht, dann
ist der Rückgabewert der NULL-Zeiger.
struct LinListe *Erzeuge(char *String)
/* erzeugt und initialisiert neues Element in der Liste */
{
struct LinListe *Neu;
Neu = (struct LinListe *) malloc(sizeof(struct LinListe));
if (Neu == NULL)
{
printf("Speicher voll, Abbruch...\n");
exit(1);
}
Neu->next = NULL;
strcpy(Neu->inhalt,String);
return(Neu);
}
Um das neue Element einzufügen, wird ein weiterer Zeiger verwendet, der so lange
von einem Element zum Nächsten bewegt wird, bis die Stelle gefunden ist, an der
das neue Element einzufügen ist. Der Zeiger heißt im Beispiel "Tail",
als Abkürzung für Rest der Liste ("Schwanz").
Ist die passende Stelle gefunden, so wird das neue Element durch Ändern von
zwei Zeigern eingefügt. Dabei sind drei Fälle zu unterscheiden.
Die Liste ist noch leer:
root zeigt auf den Nullpointer. In diesem Fall muß root
auf das erste neu erzeugte Element zeigen:
Es wird am Anfang der nichtleeren Liste eingefügt:
In diesem Fall ändert sich der Wert von root.
Einfügen innerhalb der Liste:
Hier ist es egal, ob irgendwo zwischen zwei Elementen eingefügt wird oder
ob das am Listenende geschieht.
Für alle drei Einfügevarianten schreiben wir eine einzige Funktion:
struct LinListe *ElementEinfuegen(struct LinListe *root, struct LinListe *Neu)
{
struct LinListe *Tail;
/* Wenn Neu das erste Listenelement werden muss, */
/*dann ist die globale Variable root zu aendern */
if (root == NULL)
/*Liste noch leer, erstes Element, root wird neues Element */
root = Neu;
else if (strcmp(Neu->inhalt, root->inhalt) < 0)
/* Einfuegen vor dem ersten Element, root aendert sich */
{
Tail = root;
root = Neu;
Neu->next = Tail;
}
else
{
Tail = root;
/* Element suchen, nach dem Neu einzuhaengen ist */
while ((Tail->next != NULL) && (strcmp(Tail->next->inhalt, Neu->inhalt) < 0))
/*Reihenfolge beachten: erst auf NULL testen */
Tail = Tail->next;
/* Neu nach Tail einhaengen */
Neu->next = Tail->next;
Tail->next = Neu;
}
return(root);
}
Wird kein Sortierkriterium benötigt, wird immer am Ende ein neues Listenelement
angehängt. Die Funktion vereinfacht sich dann entsprechend:
struct LinListe *ElementAnhaengen(struct LinListe *root, struct LinListe *Neu)
{
struct LinListe *Tail;
/* Wenn Neu das erste Listenelement werden muss, */
/*dann ist die globale Variable root zu aendern */
if (root == NULL)
/*Liste noch leer, erstes Element, root wird neues Element */
root = Neu;
else
{
Tail = root;
/* Element suchen, nach dem Neu einzuhaengen ist */
while (Tail->next != NULL)
Tail = Tail->next;
/* Neu nach Tail einhaengen */
Neu->next = Tail->next;
Tail->next = Neu;
}
return(root);
}
Zum Schluß noch das Testprogramm (ohne Funktionsdefinitionen):
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct LinListe
{
char inhalt[80];
struct LinListe *next;
};
struct LinListe *root = NULL;
/* Hier Funktionen einfuegen, siehe oben */
int main(void)
{
char str[80];
struct LinListe *Neu;
while(1)
{
if (gets(str) != NULL)
{
Neu = Erzeuge(str);
root = ElementEinfuegen(root, Neu);
}
else break;
}
printf("\n");
DruckeListe(root);
return(0);
}
Bei linearen Listen ist das Löschen von Einträgen auch noch recht einfach.
Es muß lediglich der Zeiger des Vorgängers auf den Nachfolger gesetzt
werden.
Da jedoch bei einer einfach verketteten Liste kein Verweis auf den Vorgänger
existiert (da bräuchte man doppelt verkettete Listen), wir ein Trick verwendet.
Beim durch die Liste laufende Zeiger Tailwird nicht der Inhalt des durch
den Zeiger referierten Objektes untersucht, sondern der Inhalt des Nachfolgers. Dadurch
zeigt Tail immer auf den Vorgänger des zu löschenden Elements
und das "Ausklinken" ist ganz einfach.
Da nun erst ab dem zweiten Element der Liste nach dem zu l&öuml;schenden Element
gesucht wird, muß das erste Element getrennt untersucht werden. Das ist
aber sowieso notwendig, da sich dann der Wert von root ändert.
Die Funktion sieht dann so aus:
struct LinListe *ElementLoeschen(struct LinListe *root, char *key)
{
struct LinListe *Tail, *Hilf;
if (strcmp(key, root->inhalt) == 0)
/* Erstes Element loeschen, root aendert sich */
{
Hilf = root;
root = root->next;
free(Hilf);
}
else
{
Tail = root;
while ((Tail->next != NULL) && (strcmp(Tail->next->inhalt, key) != 0))
/*Reihenfolge beachten: erst auf NULL testen */
Tail = Tail->next;
if (Tail->next != NULL)
{
Hilf = Tail->next;
Tail->next = Tail->next->next;
free(Hilf);
}
else
{
printf("%s not found!\n",key);
}
}
return(root);
}
Beispiel: Keller, realisiert mit linearer Liste
Ein Keller, auch Stapel oder Stack genannt, ist eine besondere lineare Liste, bei
der die Daten eine Folge bilden, die nur durch die Ein- und Ausfügeoperationen
bestimmt wird. Das Prinzip eines Kellers besteht darin, daß stets das
zuletzt eingefügte Element eines Kellers als erstes wieder entfernt werden
muß. Die Kellerverwaltung arbeitet nach dem LIFO-Prinzip: Last In First Out.
Was zuletzt in den Keller kam, kommt zuerst aus dem Keller auch wieder raus.
Man kann sich einen Keller als eine Bücherkiste vorstellen, in die man einzeln
Bücher legen und wieder herausnehmen kann. Üblicherweise stehen folgende
fünf Kelleroperationen zur Verfügung:
Init
Push
Pop
Top
Empty |
Initialisiert einen neuen Keller.
Legt ein Element auf dem Keller ab.
Holt ein Element aus dem Keller.
Liest das oberste Element im Keller.
Prüft, ob ein Keller leer ist. |
 |
Datenstruktur für einen Keller
Man nutzt auch hier dynamisch verkettete lineare Listen. Die Elemente einer
solchen Liste müssen außer der Nutzinformation noch einen Zeiger
auf das nachfolgende Kellerelement speichern.
struct TStack
{
char Daten[100];
struct TStack *Next;
};
Implementierung der Kelleroperationen
Die Implementierung der Kelleroperationen beginnen wir mit den einfachen Funktionen
Init und Empty.
Init erledigt sich durch die Definition der Kellervariablen:
struct TStack *Keller = NULL;
Empty degeneriert zur Abfrage Keller == NULL. Interessanter sind
Push und Pop:
Etwas schwieriger ist die Implementierung der Push-Operation.
Bevor die Daten im Keller abgelegt werden können, müssen Sie in einen
Element-Verbund verpackt werden. Dazu erzeugen wir mittels New ein neues
Element und legen in ihm die Daten ab. Im Bild liegen die beiden Werte 'X' und
'Y' auf dem Keller. Das 'Z' soll als nächstes auf den Keller gelegt
werden. Das neue Element muß das oberste Kellerelement werden. Dies
gelingt durch zwei Zeigeroperationen:
- Durch Setzen des bislang undefinierten Zeigers auf das bislang
oberste Kellerelement werden die alten Kellerelemente Nachfolger des
neuen Elements.
- Durch Umsetzen des Kellerzeigers vom alten Kelleranfang auf den neuen
Kelleranfang wird das neue Element in den Keller aufgenommen.
void Push(char *Daten)
{
struct TStack *Element;
Element = (struct TStack *) malloc(sizeof(struct TStack));
strcpy(Element->Daten, Daten);
Element->Next = Keller;
Keller = Element;
}
Pop muß das oberste Kellerelement vom Keller wegnehmen und dessen
Daten zurückliefern. Wenn der Keller leer ist, geben wir eine Fehlermeldung aus.
Bei Bedarf kann der Programmierer mit Empty Auskunft über den Keller
erhalten. Wenn er dennoch durch falsche Programmierung eine Pop-Operation
auf einem leeren Keller ausführt, wird er auf seinen Programmierfehler
durch eine Fehlermeldung hingewiesen.
Das Abhängen des obersten Kellerelements erfolgt durch drei
Zeigeroperationen:
- Kellerelement an Hilfsvariable Element binden.
- Keller-Zeiger auf nächstes Kellerelement verbiegen.
- Speicher des alten Kellerelements freigeben.
void Pop(char *Resultat)
{
struct TStack *Element;
if (Keller == NULL)
printf("Der Keller ist leer!\n");
else
{
strcpy(Resultat, Keller->Daten);
Element = Keller;
Keller = Keller->Next;
free(Element);
}
}
Ein Testprogramm sieht dann z. B. so aus:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct TStack
{
char Daten[100];
struct TStack *Next;
};
struct TStack *Keller = NULL;
void Push(char *Daten);
void Pop(char *Resultat);
int main(void)
{
char str[100];
Push("Hallo");
Push("Sie da!");
Push("Ja, Sie!");
while (Keller != NULL)
{
Pop(str);
printf("%s\n",str);
}
return(0);
}
Das Ergebnis ist dann:
Ja, Sie!
Sie da!
Hallo
| 
DIENSTE
