Lösungsbeispiel: So könnte es aussehen

Hier gibts den Quellcode zum einsehen.

Verschiedene Zeilen des Codes bedürfen möglicherweiße der genaueren Klärung. Zunächst ist grundsätzlich zu klären, welche Fälle den überhaupt beim einfügen in eine solche Liste zu behandeln sind. Zunächst könnte die Liste leer sein, ein Fall, den wir gleich zu Anfang abfangen wollen. Als nächstes könnte das einzufügende Zeichen noch vor das erste Listenelement gehören. Auch dies wird speziell am Anfang abgefragt. Beiden Fällen ist gemeinsam, das wir den Anker selbst (den Zeiger auf das erste Element) verbiegen müssen, das heißt, die Adresse auf die er zeigt (seinen Wert) zu ändern. Beachte: Wenn wir einen Parameter eines Programmes ändern wollen, müssen wir einen Zeiger auf den Parameter an die Funktion übergeben. Daran ändert auch die Tatsache nichts, das "anker" schon ein Zeiger auf das erste Listenelement ist! Wir haben dann eben einen Zeiger auf einen Zeiger.

Ist das Element nun noch nicht eingehängt, so müssen wir die Liste durchsuchen. Dazu setzen wir einen Suchzeiger auf den Listenanfang, vergleichen dessen Zeichenkomponente mit dem neuen Zeichen und setzten den Suchzeiger solange auf das nächste Listenelement, bis wir die gewünschte Stelle gefunden haben oder am Listenende angekommen sind. Ist unser Zeichen am Ende immer noch nicht eingetragen, so müssen wir es eben ans Ende der Liste stellen.

Ganz so einfach ist die Suche in der Praxis allerdings nicht. Wenn wir den Suchzeiger auf das auszuwertende Element setzten, so verlieren wir die Information über das vorhergehende Element. Wir wissen dann nicht mehr, welchen Zeiger wir auf unser neues Element setzen müssen, um dieses in die Liste zu hängen. Deshalb führen wir einen Nachlaufzeiger ein, der sich die Speicherstelle merkt, die wir auf das neue Element setzen müssen, wenn in diesem Durchgang das Einfügen erfolgen soll.

Um zu prüfen, wann die Suche beendet ist, führen wir eine Statusvariable ein, die den Wert 1 erhält, sobalt die Stelle in der Liste gefunden wurde. Ist am Ende der Suchschleife (nach vollständigem Durchlaufen) der Status immer noch 0 (Vorbelegung), so müssen wir das neue Element ans Listenende hängen.

Syntax

Kommen wir zur Syntaktischen Umsetzung der Theorie. Ein wahres Schlachtfeld aus Zeigern: Zunächst benötigen wir die Struktur selbst und legen gleich noch einen Typ ptr fest, der ein Zeiger auf die Struktur sein soll. Anschaulich sind folgende Anweisungen äquivalent für die Definition des Variablen ANKER in unserem main-Teil: element *anker=NULL und ptr anker=NULL. Der Anker ist also ein Zeiger auf unsere Struktur, den wir gleich auf NULL setzen. Ein undefinierter Wert für einen Zeiger liefert eine SCHUTZVERLETZUNG, wenn wir auf seinen Wert zugreifen (Wert eines Zeigers = Adresse eines Objektes im Speicher).

Um den Wert dieses Ankers in der Funktion verändern zu können, benötigt die Funktion den Zeiger als Referenzparameter in der Parameterliste, das heißt, wir müssen ihr einen Zeiger auf den Anker übergeben. In der Funktion definieren wir noch drei weitere Zeiger auf Elemente, um unsere derzeitige Position in der Liste festzuhalten und ein neues Element anzulegen.

Sind diese Vorarbeiten gemacht, reservieren wir mit malloc den nötigen Speicher (ACHTUNG: malloc ist vom Typ "Zeiger auf void", wir wandeln explizit in ptr um mit (ptr)malloc ) und prüfen, ob evtl der Speicher voll ist (malloc gibt dann NULL zurück). Ist dies nicht der Fall, können wir mit dem einhängen beginnen.

Zunächst wird der Zeiger des neuen Elementes auf NULL gesetzt (wg. Schutverletzung siehe oben) und das Zeichen eingeschrieben. Dann prüfen wir, ob die Liste noch jungfräulich ist. Ist dies der Fall, so soll der Anker auf das neue Element zeigen: *anker = neues; (LIES: Weise dem Wert, auf den anker zeigt, die Adresse von neues zu). Was passiert genau? *anker repräsentiert eine Adresse, die zunächst (laut Definition in main) NULL ist. neues ist ebenfalls eine Adresse, der wir mit malloc einen Wert irgendwo im HEAP zugewiesen haben. Wir verbiegen die Adresse, die in der Speicherstelle anker steht also von NULL auf die Adresse von neues. Fertig.

War die Liste jedoch nicht leer, müssen wir fortfahren. Wir wissen jetzt, das anker auf ein gültiges Listenelement zeigt. Wir könnten also die ->zeichen - Komponente des Ankers auslesen, wenn anker nicht nur ein Zeiger wäre. Wir müssen also den Anker derefferenzieren (seinen Wert ermitteln). Da jedoch der Komponentenoperator -> stärker bindet, müssen wir dem Compiler mitteilen, das der * nur für anker gilt, und nicht für anker->zeichen. Wir setzen also Klammern.

Hat sich bei dem Vergleich ergeben, dass wir das Zeichen an den Anfang hängen müssen, verbiegen wir sofort wieder ein paar Zeiger und sind fertig. Wir weisen dem neuen Zeiger den WERT des Ankers zu (neues->zeiger zeigt nun auf das ehemals erste Listenelement) und den WERT des Ankers setzen wir wie oben auf das neue Element. Fertig

Ist das Zeichen immer noch nicht eingetragen, so müssen wir mit der Suche in der Liste beginnen. Dazu setzen wir den Suchzeiger auf das zweite Listenelement (dorthin zeigt das erste, welches wir über den anker erreichen. Das 2. Element ist das, auf den die Zeigerkomponente des Ankers verweist. Aber derefferenzieren nicht vergessen!) und den Nachlaufzeiger auf das erste Listenelement. Das Ende der Liste ist erreicht, sobald wir einen NULL-Zeiger entdeckt haben. Dies und den Status prüfen wir in unserer Suchschleife ab.

Wir vergleichen in der Schleife wieder die Zeichen und werden hoffentlich fündig. Dann fügen wir das neue Element vor dem Suchzeiger ein (der Zeiger des neuen Elementes muss auf das aktuelle Element zeigen). Den Zeiger des aktuellen Elementes können wir nur noch über den Nachlauf-Zeiger manipulieren. Den Status setzten wir auf 1. Am Ende jedes Durchlaufes schieben wir beide Positionszeiger um ein Element weiter. Fertig.

Immer noch nicht fündig geworden? Dann kann nur noch das Listenende in Frage kommen. Wir setzten einfach den Zeiger des letzten Elementes auf das neue Element und Fertig. neues->zeiger ist schließlich schon NULL. Geschafft.

Ein Zeiger ist ein Zeiger ist ein Zeiger !? Wie geht dem ?????

Was ist den nun bitte ein Zeiger auf einen Zeiger ? Nun, wir wissen alle, was ein Zeiger auf eine Variable ist. Er repräsentiert die Speicherstelle, an der die Variable im Systemspeicher zu finden ist. Ein Zeiger selbst liegt aber auch irgendwo im Speicher und beherbergt einen Wert (eben eine Adresse, die ja auch nur ein Zahlenwert ist). Auch auf diese Speicherstelle können wir einen Zeiger setzten und haben so einen Zeiger auf einen Zeiger. Sehen wir uns ein Schema an, das den Zustand bei einhängen des ersten Elementes zeigt. Der hellblaue Bereich ist der Systemspeicher.Wir haben einen Anker innerhalb von main (schwarz) und einen innerhalb der Funktion (grün). Daneben liegen noch das neue Element und irgendwo das definierte Nichst (NULL). Main setzt nun den schwarzen Anker auf NULL und übergibt die Adresse, an der der Anker steht, der Funktion. Der grüne Anker enthält dadurch den Wert "Linke obere Ecke". Mit x = *anker in der Funktion geschähe folgendes: Gehe zur Adresse, die im grünen Anker steht ("Links oben") und nimm von dort den Wert ("Rechts oben") und gehe zu dieser Adresse. Schreibe dann den Wert, der dort steht ("NULL") in x. Das einhängen geht nun so: Ermittle den Wert, der bei anker (grün) steht und sehe diesen als Adresse an. Gehe dorthin und trage die Adresse des neuen Elementes dort ein. Vorher haben wir natürlich in die Zeigerkomponente des neuen Elementes die Adresse von NULL eingetragen ("Rechts oben").