Folge 17:

Zeiger

17.1 Was sind Zeiger?

Schon früher sind wir Zeigern in Java begegnet. Betrachten Sie doch einmal das folgende Objektdiagramm:

Das Objekt auto der Klasse Auto hat fünf Attribute, nämlich motor, tankvolumen, benzinstand, verbrauch und kmstand. Vier dieser Attribute gehören zu den primitiven Attributen. Dagegen ist motor kein primitives Attribut, sondern ein Objekt der Klasse Motor. In dem Objektdiagramm werden die Attribute durch Kästchen repräsentiert. Bei den primitiven Attributen stehen die Werte direkt in den Kästchen. In dem Kästchen für das Objektattribut motor steht dagegen kein Wert, sondern die Speicheradresse des eigentlichen Objektes motor. In der Informatik symbolisiert man Attribute, die die Adressen von Objekten speichern, häufig durch Pfeile, die auf die referenzierten Objekte zeigen. Daher nennt man solche Attribute auch gern Zeiger, Pointer oder Referenzen.

Expertenwissen:

17.2 Zeiger und Referenzen

In manchen Programmiersprachen wird zwischen Zeigern bzw. Pointern einerseits und Referenzen andererseits unterschieden. Obwohl beide Datentypen miteinander verwandt sind, weil sie die Adressen von Speicherbereichen enthalten und nicht konkrete Daten, gibt es doch einen wichtigen Unterschied, was die Behandlung dieser Adressen angeht.

Bei Zeigern oder Pointern kann der Programmierer die Adresse nicht nur sehen, sondern diese auch manipulieren. So ist dann eine regelrechte Zeigerarithmetik möglich. Man kann in der Sprache C bzw. C++ beispielsweise den Wert einer Zeigervariable um 4 inkrementieren und gelangt so zu der benachbarten Speicherstelle, vorausgesetzt, die Daten, auf die der Zeiger verweist, sind exakt 4 Byte groß.

Bei Referenzen dagegen kann man die gespeicherte Adresse unter Umständen sehen (lesen, anzeigen), aber nicht verändern, eine Speicherarithmetik ist also nicht möglich.

Wenn Sie in Java ein Objekt einer Klasse deklarieren, beispielsweise mit

Element alt, neu;

so stehen in den Attributen alt und neu die Adressen von zwei Objekten. Auf diese Adressen kann man aber nicht nur lesend zugreifen, sondern auch schreibend, wie folgende Zuweisung zeigt:

neu = alt;

Egal, welche Adresse vorher in neu gespeichert war, nach Ausführung der Zuweisung steht in neu die gleiche Adresse wie in alt. Auch die Zuweisung

alt = null;

verändert die in alt gespeicherte Adresse. Sie sehen also, dass man auf die „Referenzen“ der Sprache Java durchaus schreibend zugreifen kann. Eine Zeigerarithmetik ist allerdings in der Tat nicht möglich, wir können mit den Referenzen also nicht rechnen. Aber um reinrassige Referenzen handelt es sich bei unseren Objekten jedenfalls nicht. Aus diesem Grunde werden wir in unserem Skript also weiterhin abwechselnd von Zeigern und Referenzen sprechen, gemeint ist immer dasselbe.

In der englischen Wikipedia wird - im Gegensatz zur deutschen - nicht zwischen Referenzen und Pointern unterschieden: „Typically, a reference is the physical address of where the data is stored in memory or in the storage device. For this reason, a reference is often called a pointer or address, and is said to point to the data.“

Workshop:

17.3 Ein dynamischer Stack

Zielsetzung

Wir wollen in diesem Workshop eine Stack-Klasse mit Hilfe von Zeigern entwickeln. Bisher hatten wir die Klasse Stack ja mithilfe eines Arrays programmiert. Nähere Einzelheiten siehe Folge 14 (Abstrakte Datentypen) oder "Die Klasse Stack".

Ein abstrakter Datentyp macht bekanntlich keinerlei Aussagen darüber, wie man ihn zu implementieren hat. Bisher hatten wir den ADT Stack stets mit Hilfe eines Arrays programmiert. Neue Elemente wurden einfach hinten angehängt, und beim Ausführen von Pop() wurde eine Hilfsvariable, die auf das "oberste" Array-Element zeigte, um 1 dekrementiert. In diesem Workshop wollen wir nun einen Stack mit Hilfe von Zeigern implementieren.

Schritt 1 - neues Projekt erstellen

Erzeugen Sie ein neues Projekt Stack01 und speichern Sie es in einem neuen Ordner.

Schritt 2 - Klasse Element

Erzeugen Sie die Klasse Element und geben Sie folgenden Quelltext in den Editor ein:

public class Element
{
   public int value;
   public Element next;

   public void show()
   {
      System.out.println(value);
   }
}

							

Schritt 3 - Innehalten und überlegen

Fällt Ihnen an diesem Quelltext etwas Besonderes auf?

Besonderheit 1: Die Klasse besitzt keinen Konstruktor. So etwas ist in Java durchaus möglich; allerdings können wir dann beim Erzeugen neuer Elemente keine Parameter übergeben und auch keine Initialisierungen durchführen, wofür ja normalerweise der Konstruktor einer Klasse zuständig ist.

Besonderheit 2: Die Klasse besitzt ein Attribut next, das ein Objekt der eigenen Klasse Element ist.

Sinn des ganzen ist Folgendes: Wir wollen den Stack nicht als Array implementieren, sondern jedes Stack-Element soll a) den eigentlichen Wert und b) die Adresse des nächsten Stack-Elements speichern. Der eigentliche Wert wird in dem Attribut value gespeichert, und die Adresse des nächsten Stack-Elements in dem Attribut next.

Das Attribut next ist also ein klassischer Zeiger, der Inhalt von next ist die Speicheradresse des nächsten Element-Objektes. Nach dem Kompilieren des Quelltextes sollte im BlueJ-Hauptfenster die Klasse Element zu sehen sein, die mit einem Pfeil auf sich selbst verweist:

Schritt 4 - Die Klasse Stack

public class Stack
{
   Element TOS;

   public Stack()
   {
      TOS = null;
   }
}

Schritt 5 - Die Push-Operation

Das Objektdiagramm 17-4 zeigt die Situation direkt nach dem Erzeugen eines Objektes s der Klasse Stack. Im Konstruktor der Klasse Stack wurde das Zeiger-Attribut TOS auf den Wert null gesetzt. Betrachten Sie nun die Situation nach dem ersten Ausführen der Push()-Operation:

Das Attribut TOS des Stack-Objekts zeigt nicht mehr auf null, sondern auf ein konkretes Objekt der Klasse Element. Die Daten für dieses Objekt sind irgendwo im Arbeitsspeicher des Rechners untergebracht, und die Adresse dieser Daten ist jetzt im Attribut TOS gespeichert. Das Element-Objekt besitzt zwei Attribute value und next. Der Wert von value ist 17, der Wert von next dagegen null, weil das neue Stack-Element noch keinen Nachfolger hat.

Als nächstes wollen wir ein weiteres Element auf den Stack pushen, nämlich den Wert 12.

Das Attribut TOS des Stacks muss nun auf das zuletzt eingefügte neue Element zeigen und nicht mehr auf das bisherige oberste Element. Der Zeiger TOS muss also "umgebogen" oder "verbogen" werden, wie man im Informatik-Jargon sagt. Und nicht nur das. Der next-Zeiger des neuen Elementes darf nicht den Wert null haben, sondern muss auf das bisherige oberste Element verweisen. Also muss auch dieser Zeiger "umgebogen" werden.

Schritt 6 - Kästchendiagramme

Wie kann man das in Java erreichen? Damit wir den entsprechenden Algorithmus schneller entwickeln können, wollen wir die doch recht umständlichen Objektdiagramme durch eine einfachere Darstellung ersetzen, nämlich durch sogenannte Kästchendiagramme. Schauen wir uns dazu einmal das Kästchendiagramm an, welches die Situation nach dem zweiten Aufruf der Push()-Operation darstellt:

Jedes Stack-Element wird durch einen Doppelkasten dargestellt. In der oberen Hälfte finden wir den Wert des Elementes, in der unteren Hälfte den Zeiger auf das nächste Element. Der Zeiger TOS wird hier durch einen einfachen Kasten dargestellt. Da das value-Attribut von TOS keine Rolle spielt, ist es hier auch nicht gezeichnet worden.

Schritt 7 - Entwicklung der push()-Methode

Wir wollen jetzt die push()-Methode für die Klasse Stack entwickeln und dabei die eben eingeführten Kästchendiagramme als Hilfsmittel einsetzen.

Schritt 7.1 - Erzeugen des neuen Elements

Der obere Teil der Abbildung 17-7 zeigt die Situation vor dem Ausführen von push(): Es existiert bereits ein Stack mit den zwei Elementen 12 und 17. Das Element 12 wurde zuletzt eingefügt, daher zeigt TOS auf die 12:

Der untere Teil des Bildes zeigt schon die ersten Maßnahmen, die ergriffen werden müssen, um ein neues Element auf den Stack zu pushen. Das neue Element ist bereits als leerer Kasten angelegt, und der Hilfszeiger h zeigt auf das neue leere Element. Einen solchen Hilfszeiger erzeugen wir mit der Anweisung

Element h = new Element();

Jetzt müssen wir "nur noch" den leeren Kasten mit Inhalt füllen und anschließend in den bereits bestehenden Stack einbauen.

Angenommen, wir wollen die Zahl 5 pushen. Dann müssen wir jetzt den Wert 5 in den oberen Teil des leeren Doppelkästchens hineinschreiben. Das machen wir mit der konkreten Anweisung

h.value = 5;

Anschließend haben wir folgende Situation:

Schritt 7.2 - Einbauen des neuen Elements

Der Hilfszeiger h zeigt auf das Element 5, und TOS verweist immer noch auf das bisherige oberste Stack-Element, nämlich die 12. Wir müssen jetzt etwas machen, das man in der Informatik oft als "Zeigerumbiegen" bezeichnet. TOS muss auf die 5 zeigen, und der next-Zeiger der 5 muss auf die 12 zeigen.

Um diese zwei Ziele zu erreichen, gehen wir in zwei Teilschritten vor. Zunächst erzwingen wir die folgende Situation:

Jetzt zeigt der next-Zeiger der 5 auf die 12. Erreicht wird dieses "Zeigerumbiegen" durch die Java-Anweisung:

h.next = TOS;

Diese Anweisung ist eine normale Zuweisung. Allerdings werden jetzt keine Daten von TOS nach h.next kopiert, sondern eine Speicheradresse wird übertragen. Nach dem Ausführen der Zuweisung ist in h.next die gleiche Adresse gespeichert wie in TOS, was man mit den einfachen Worten umschreiben kann „h.next zeigt dorthin, wo auch TOS hinzeigt".

Schritt 7.3 - Aktualisierung von TOS

Als letztes müssen wir TOS aktualisieren, der Zeiger soll ja jetzt auf die 5 zeigen. Die Adresse dieses Stack-Elements ist in dem Hilfszeiger h gespeichert. Also schreiben wir jetzt

TOS = h;

Dann erhalten wir schließlich die folgende Situation:

Das Kästchendiagramm wurde bei der Gelegenheit etwas "gestrafft". Sie sehen also selbst, dass Kästchendiagramme ein hervorragendes Hilfsmittel zur Veranschaulichung von Zeiger-Operationen sind.

Schritt 8 - die push()-Methode

Jetzt sind wir so weit, dass wir die komplette push()-Methode entwerfen können. Notieren wir noch einmal, welche Schritte zum Einfügen der Zahl 5 in den bereits bestehenden Stack notwendig waren:

Element h = new Element();
h.value = 5;
h.next = TOS;
TOS = h;

Nun soll die push()-Methode aber etwas allgemeiner formuliert werden, denn schließlich wollen wir ja beliebige Zahlen auf den Stack pushen und nicht immer nur die Zahl 5. Die Zahl, die gepusht werden soll, übergeben wir als int-Parameter v (für value). Also schreiben wir:

public void push(int v)
{
   Element h;

   h = new Element();
   h.value = v;
   h.next = TOS;
   TOS = h;
}

Wir müssen jetzt nur noch überprüfen, ob die push()-Methode auch dann funktioniert, wenn der Stack noch leer ist.

Wenn der Stack leer ist, zeigt TOS auf null. Wird nun eine Zahl gepusht, wird ein Hilfszeiger h angelegt, der auf ein leeres Element zeigt. Dann wird v in dieses leere Element hineingeschrieben. Als Nächstes wird der next-Zeiger des neuen Elements auf TOS gesetzt. Da TOS den Wert null hat, hat auch der next des ersten Elements den Wert null - was durchaus mit unseren Erwartungen übereinstimmt. Als letztes wird TOS auf h gesetzt. Da h auf das einzige Element des Stacks zeigt, zeigt auch TOS auf dieses Element. Damit hat alles seine Richtigkeit; die push()-Methode funktioniert auch dann, wenn der Stack noch leer ist.

Schritt 9 - Testen der push()-Methode

Das war ja ein ziemlich langer und aufwändiger Schritt 5. Wir wollen jetzt mit Hilfe des Objektinspektors testen, ob die Push-Operation tatsächlich so arbeitet, wie die Kästchendiagramme es vorgeben.

Dazu legen Sie bitte ein Objekt der Klasse Stack an und rufen mit der rechten Maustaste dreimal hintereinander die push()-Methode auf. Pushen Sie zunächst die Zahl 17, dann die Zahl 12, und schließlich die Zahl 6. Gehen Sie dann mit der rechten Maustaste auf Ihr Stack-Objekt und rufen Sie den Befehl Inspizieren bzw. inspect auf. Das Attribut TOS enthält dann als Wert einen Zeiger. Wenn Sie einen Doppelklick auf den Zeiger ausführen, kommt ein neues Fenster für das erste Stack-Element. Hier sehen Sie den Wert 6 und den Zeiger auf das nächste Element. Doppelklicken Sie diesen, und wieder erscheint ein Fenster. Hier sehen wir den Wert 12. Auf die gleiche Weise kommen wir schließlich zum letzten Stack-Element mit dem Wert 17. Der Stack ist also genau so aufgebaut worden, wie wir es in Schritt 5 geplant haben.

17-11 Testen der push()-Methode mit Hilfe des Objekt-Inspektors

Der Stack ist also genau so aufgebaut worden, wie wir es in den Schritten 5 bis 8 geplant haben.

Schritt 10 - Die Pop-Operation

Diesen Schritt des Workshops habe ich ausführlich in der Buchversion erläutert, die Sie bei Interesse von mir erhalten können. Für die Leser dieser Webversion stelle ich die Entwicklung der pop()-Methode als zusätzliche Aufgabe. Gehen Sie genau so vor, wie ich es Ihnen bei der push()-Methode vorgemacht habe. Ohne Bleistift und Papier werden Sie nicht viel Glück haben; entwerfen Sie erst ein Kästchendiagramm, und dann programmieren Sie das Ganze.

Workshop:

17.4 Eine dynamische sortierte Liste

Zielsetzung

Wir wollen nun eine sortierte Liste entwerfen, bei der die einzelnen Elemente durch Zeiger miteinander verkettet sind. Um uns die Arbeit zu vereinfachen, soll die Liste doppelt verkettet sein, das heißt jedes Element zeigt auf seinen Vorgänger und seinen Nachfolger.

Mehr erfahren Sie in der Buchversion. Auf den Seiten 62 bis 75 erkläre ich Ihnen dort Schritt für Schritt, wie man eine solche doppelt verkettete und gleichzeitig sortierte Liste programmiert.

Dieser Abschnitt geht teilweise weit über die Abitur-Vorgaben hinaus, daher habe ich ihn nicht in diese Web-Version des Lehrgangs aufgenommen.

Abitur NRW

17.5 Implementation der Liste

Zielsetzung

Das Wissenschaftsministerium des Landes NRW hat im Juli 2006 einen offiziellen „Werkzeugkasten" herausgegeben, in dem allerlei Klassen vorgegeben werden, unter anderem auch die Klassen Stack, Queue und List. Ziel dieses Werkzeugkastens ist es, in Hinblick auf das Zentralabitur NRW einen einheitlichen Standard zu setzen. Schüler(innen) in Köln sollen unter dem ADT List das Gleiche verstehen wie Schüler(innen) in Espelkamp.

Mehr erfahren Sie in der Buchversion. Auf 12 Seiten erkläre ich Ihnen Schritt für Schritt, wie man die NRW-Liste konkret mit BlueJ programmiert. Dieser Abschnitt geht teilweise weit über die Abitur-Vorgaben hinaus, daher habe ich ihn nicht in diese Web-Version des Lehrgangs aufgenommen.

Expertenteil

17.6 Expertenaufgaben

17.6.1 Aufgabe: Vokabelliste

17.6.2 Aufgabe: Super-Lexikon

Diese beiden Aufgaben wurden ausschließlich für Experten unter den Schüler(innen) erstellt. Das Niveau geht weit über die Abitur-Anforderungen hinaus, daher habe ich diesen Teil des Skripts in die Buchversion ausgelagert, die Sie bei mir erhalten können.

Aufgabe "Vokabelliste"

Hier sollen die Schüler(innen) eine vierfach verkette dynamische Liste von Vokabeln programmieren. Jede Vokabel soll einen deutschen Vorgänger und einen deutschen Nachfolger sowie einen englischen Vorgänger und einen englischen Nachfolger haben.

Aufgabe "Super-Lexikon"

Hier sollen die Schüler(innen) aus 26 Objekten des "einfachen" Lexikons (siehe Übung 17.4) ein Super-Lexikon basteln. Eine einfach verkettete dynamische Liste von 26 Zeigern - für jeden Buchstaben ist ein eigener Zeiger verantwortlich - bildet das Rückgrat dieser 26 Objekte.

Zu beiden Aufgaben habe ich ausführlich kommentierte Lösungen entwickelt, die Sie von mir erhalten, wenn Sie den zweiten Teil des Lehrerbandes erwerben, was natürlich nur geht, wenn Sie selbst Lehrer oder Lehrerin sind.

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 27. Oktober 2007 und vollständig überarbeitet, ja fast ganz neu geschrieben am 9. Dezember 2009.