Atari Logo
Atari Computer

Hauptseite -
Welches System? -
Hardware -
Software -
Emulatoren -
Internet
MausNet
Programmieren
Verweise
Über

Algorithmen

Home Inhaltsverzeichnis Indices einfach verkettete Liste

3 Botanik: Basisalgorithmen für Container

Soll eine variable Anzahl Elemente flexibel verwaltet werden, kann ein Element mit einem oder mehreren Zeiger verknüpft werden. Damit kann der Zeiger wieder auf ein weiteres Element verweisen. Sämtliche Elemente können damit aneinander gekettet werden und es wird nur für die Elemente Speicher benötigt, die auch vorhanden sind. Die folgenden Beispiele zeigen einige Basisalgorithmen. Da sie Daten aufnehmen, werden sie auch Container genannt. Die hier beschriebenen Container speichern die Daten sortiert ab. Es sind aber auch andere Kriterien für den Zugriff auf die Daten möglich, wie es im Kapitel abstrakte Container beschrieben wird.

Die Verknüpfung der Daten läßt sich anschaulich grafisch beschreiben.


Ein Zeiger ist ein Kreis mit einem Pfeil. Eine Struktur, der ein Zeiger enthält, wird als Kasten mit einem Pfeil gezeichnet. Der Pfeil kann nun auf andere Daten zeigen und dadurch wird eine Verknüpfung von Zeigern grafisch beschrieben. Zeigt der Zeiger auf kein bestimmtes Element, wird er auf einen Wert gesetzt, der mit Sicherheit keiner Adresse entspricht. Dies ist in C der Nullzeiger NULL und in Pascal und Modula NIL. Damit läßt sich unterscheiden, ob der Zeiger auf ein Element zeigt oder auf nichts zeigt. In den folgenden Beispielen wird nicht jedesmal NULL bzw. NIL dazugeschrieben. Wenn der Zeiger nicht auf eine Struktur zeigt, wird angenommen, daß er auf NULL bzw. NIL steht.

Achtung: Ein gleichzeitiges Abfragen auf einen NULL/NIL Zeiger und dem Wert des Elements, auf den der Zeiger zeigt, ist nur möglich, wenn die Programmiersprache die Bewertung eines Ausdrucks beendet, wenn das Ergebnis feststeht. Dies ist z.B. in C möglich. Dort sind Ausdrücke wie

if (p != NULL) && (p->x == 2)

möglich. Ist der Zeiger NULL, steht das Ergebnis fest und es wird nicht versucht, den Zeiger zu dereferenzieren. Bei einer Sprache wie Pascal wird der Ausdruck dennoch ausgewertet. Hier müssen beide Abfragen getrennt werden. In den Beispielen sind beide Abfragen getrennt.

Bei jeder Operation mit Zeigern ist darauf zu achten, daß immer mindestens ein Zeiger auf jedes Objekt zeigt. Andernfalls geht der Zugriff auf Objekte verloren und es entstehen Leichen, auf die man nicht mehr zugreifen kann. Bei einer Liste erfüllt die Verkettung der Elemente untereinander diese Bedingung. Wegen dieser Gefahr sollten Operationen mit Zeigern immer gut geplant werden! Hilfreich ist es, die Zeiger grafisch zu planen.

Die Beispiele fassen Daten und den Zeiger in einer Struktur zusammen. Steht ein typloser Zeiger zu Verfügung, können die Knoten der Liste bzw. Bäume von den Datengetrennt werden. Damit lassen sich die Algorithmen unabhängig von den Daten implementieren.



Home Inhaltsverzeichnis Indices einfach verkettete Liste


Best viewed with any browser English version not yet available.

Änderungen und Irrtümer vorbehalten. Letzte Änderung:
14 September 2001.
Home - Mail an den Webmaster - Impressum