Kurs:Programmieren in Oberon/Kapitel 8

Dieses Kapitel gehoert zum Kurs Programmieren in Oberon des Fachbereichs Informatik.

Mit dem Pointer zeigen

Bis jetzt haben wir ziemlich konventionell und sicher programmiert: am Anfang jedes Programmes haben wir uns ziemlich gut überlegt, was für, und wieviele, Variablen wir brauchen. Was ist aber, wenn die Anzahl Variablen plötzlich von etwas vollkommen willkürlich doofem abhängen soll, wie zum Beispiel von einem Benutzer? In unserem Beispiel mit der SchuelerListe haben wir eine Frage offen gelassen: unser ARRAY OF Schueler hat nur Platz für 100 Elemente. Was ist, wenn wir mehr brauchen? Programm umschreiben und neu compilieren? Eher nicht, es geht auch einfacher.

Variablen und Zeiger darauf

Wie gesagt wurden bei allen unseren Programmen die Variablen im voraus festgelegt. Wie sehen die Variablen aber für den Computer aus? Ruft man zum Beispiel folgende Prozedur auf,

PROCEDURE CountTo ( n : INTEGER );
    VAR
        count : INTEGER;
    BEGIN
        count := 1;
        WHILE count <= n DO
            Out.Int(count,5);
            INC(count);
        END;
    END CountTo;

werden dann im Speicher die Variablen n und count etwa so angelegt:

1000	n
1002	count

wobei die Zahl links die Adresse der Variablen darstellen soll (so in etwa). Zu bemerken ist einersets, dass INTEGER-Variablen 16 Bit, also 2 Byte gross sind, anderseits dass n auch eine Variable der Prozedur ist, denn obwohl sie in der Parameterliste sitzt, ist sie nicht als VAR deklariert, ruft man also

CountTo(10);

auf, so wird der wert 10 in n kopiert. Wäre n als VAR deklariert, würde die Prozedur keine Kopie erstellen und bräuchte deswegen keinen Platz dafür. Genug aber vom Exkurs: was hier wichtig ist, ist die Erkenntnis, dass jede Variable an einer bestimmten Adresse im Speicher sitzt.

Eigentlich kann man sich den Arbeitsspeicher jedem Computer wie ein riesiges ARRAY OF BYTE vorstellen. Gemaess unserem Beispiel würden dann die Zellen 1000 und 1001 die Bytes von n enthalten, 1002 und 1003 die von count.

...	anderes...		n		count		frei...		...
	0998	0999	1000	1001	1002	1003	1004	1005

Wenn wir uns also unsere Prozedur count genauer anschauen, so wird die Anweisung

count := 1;

verstanden als

schiebe den wert 1 in das Speicher-ARRAY an die positionen 1002 und 1003.

Obwohl wir in Oberon, ohne den Einsatz unkonventioneller Mittel, die Adresse einer Variable nicht ausfindig machen können, können wir Variablen deklarieren, welche eben eine solche Adresse darstellen. Wollen wir zum Beispiel eine Variable, welche die Adresse eines INTEGER enthält, deklarieren wir sie wie folgt:

VAR
    p : POINTER TO INTEGER;

Die Variable p "zeigt" jetzt auf einen Wert vom Typus INTEGER. Naja, ganz richtig ist das nicht: die Variable p ist ein Zeiger auf ein INTEGER, zeigt aber momentan auf nix, da wir sie noch nicht initialisiert haben.

Einige von euch werden beim Programmieren schon bemerkt haben, dass Oberon alle Variablen auf 0 initialisiert. Dies tut er auch mit Zeigern indem er sie auf NIL setzt. NIL ist eigentlich nichts anderes als null, oder die Adresse null. Dies ist sehr hilfreich, denn wir wissen jetzt, dass die Variable auf nichts zeigt, also werden wir gar nicht versuchen, irgend einen Wert an dieser Position zu lesen oder zu schreiben.

Genesis -- die Geburt einer neuen Variable

Nun, wir können zwar Zeiger auf Variablen deklarieren, können sie aber nicht auf die Adresse einer Variable setzen, denn wir können diese nicht ausfindig machen. Tolle Dinger, diese Zeiger, nicht? Jetzt im Ernst, um einen Zeiger an einer Variablen zu hängen, muss man zuerst die Variable am Zeiger erzeugen.

Bleiben wir doch bei unserem Beispiel

VAR
    p : POINTER TO INTEGER

Nun wollen wir eine neue Variable vom Typus INTEGER erzeugen und p auf deren Adresse setzen. Dies geht mit der tollen Prozedur

NEW(p);

Alles klar? Wir haben also irgendwo in unserem Speicher eine Variable vom Typus INTEGER kreiert und p auf deren Adresse gesetzt.

...	frei...		INTEGER		frei...				...
	0998	0999	p	1001	1002	1003	1004	1005

So, wir haben also eine Variable erzeugt, welche gar nicht in unserer Variablendeklaration vorgesehen war. Jedesmal wenn wir NEW aufrufen, wird ein neues INTEGER irgendwo im Speicher erzeugt, auch wenn wir es immer mit dem gleichen Zeiger aufrufen. Der Zeiger wird jeweils auf die Adresse der neu erstellten Variable gesetzt.

Einige von euch werden sich sicher jetzt schon fragen, was passiert wohl, wenn ich hunderte, nein, tausende dieser Variablen erzeugen lasse? Kann ich den Speicher füllen? Natürlich kann man das, aber nur wenn man für jede erzeugte Variable einen Zeiger drauf behält. Oberon ist nämlich nicht so doof und lässt sich mit Müll füllen, sondern sucht, wenn der Speicher knapp ist, vergessene oder einfach liegengelassene Variablen und gibt deren Platz wieder frei (das nennt man uebrigens Garbage Collection.

Ein wenig rumzeigen

Wir wissen nun, was Zeiger sind und wie man sie erstellt, jedoch wie hantiert man mit diesen Dingern rum? Was bei einem Zeiger immer mühsam ist, ist dass man immer zwischen zwei Werten unterscheiden muss: zwischen der Adresse, auf die gezeigt wird, und der Variablen, die dort sitzt. Da die Variable POINTER TO irgendwas heisst, dürfen wir ruhig annehmen, dass wenn man die Variable direkt anspricht, so wie bei jedem anderen Typen, man die Adresse anspricht. So dann zum Beispiel:

VAR
    p1, p2 : POINTER TO INTEGER;
BEGIN
    NEW(p1);
    p2 := p1;
END;

Obwohl p1 und p2 verschiedene Variablen sind, zeigen sie nun auf die gleiche Adresse. Will man jetzt aber den INTEGER-Wert an der Adresse, die von p1 angegeben wird, ansprechen, muss man ein Pfeilchen (man zeigt ja) zu hilfe nehmen.

VAR
    p1 : POINTER TO INTEGER;
BEGIN
    NEW(p1);
    p1^ := 10;
END;

Ok, ich hab euch beschissen, das ^ erscheint in Oberon als Pfeil nach oben, dafür kann man vergebens nach dem Circonflex suchen, den gibt's nicht. Nun können wir beide Beispiele kombinieren und sehen was passiert.

VAR
    p1, p2 : POINTER TO INTEGER;
BEGIN
    NEW(p1);
    p1^ := 10;
    p2 := p1;
    IF p1^ = p2^ THEN
        Out.String("duh...");
    ELSE
        Out.String("ist eigentlich unmoeglich.");
    END;
END;

Ist ja irgendwie klar oder? Da die beiden Zeiger auf die gleiche Adresse im Speicher gesetzt sind, zeigen demzufolge beide auf den gleichen Wert, der gleich sich selber ist. Probieren wir doch was schwierigeres:

VAR
    p1, p2 : POINTER TO INTEGER;
BEGIN
    NEW(p1);
    NEW(p2);
    p1^ := 10;
    p2^ := p1^;
    IF p1 # p2 THEN
        Out.String("waere richtig...");
    ELSE
        Out.String("ist eigentlich unmoeglich.");
    END;
END;

Obwohl p1 und p2 auf gleiche Werte zeigen, sitzen diese Werte an unterschiedliche Adressen. In der IF-Anweisung haben wir keine Pfeile benützt, also sprechen wir die Adressen an, und die sind verschieden. Nur noch ein letztes Beispiel:

VAR
    p1, p2 : POINTER TO INTEGER;
BEGIN
    NEW(p1);
    p2 := p1;
    p1^ := 10;
    p2^ := 0;
    IF p1^ = 0 THEN
        Out.String("eigentlich klar, oder?");
    ELSE
        Out.String("kommt gar nicht in Frage.");
    END;
END;

Da p1 und p2 auf die gleiche Variable zeigen, bewirkt jede Änderung auf den Wert von einem Zeiger aus die Änderung des Wertes auf den beide zeigen.

Spass mit Zeigern

So, wir können nun neue Variablen erzeugen und diese herumreichen, aber das Ganze scheint doch irgendwie limitiert, nicht? Am Anfang dieses Kapitels (das ist ja lange her) wollten wir doch die Möglichkeit haben, unendlich viele Variablen erzeugen zu können, ohne von VAR-Anweisungen eingeschränkt zu werden. Wir sind aber immer noch insofern limitiert, als wir für jeden Zeiger eine Variable vom Typus POINTER erzeugen müssen.

Um unser Ziel jedoch erreichen zu können, müssen wir einige Tricks anwenden. Man betrachte folgende Typendeklaration:

TYPE
    dings = RECORD
        data : INTEGER;
        next : dings;
    END;

Dies ist unter Oberon nicht erlaubt. Warum wohl? Naja, wie gross ist denn ein dings? Es enthält ein INTEGER, also 2 Byte, und noch ein dings, welches ein INTEGER, also 2 Byte, und ein dings, welches... So kommen wir doch nirgendwo hin. Klar, oder? Viel besser wäre doch sowas:

TYPE
    pdings = POINTER TO dings;
    dings = RECORD
        data : INTEGER;
        next : pdings;
    END;

Der Typus POINTER muss ja nicht unbedingt nur auf INTEGERs zeigen können, denn an einer Speicheradresse kann jeder beliebige Datentyp sitzen, auch eigens deklarierte. Wie gross ist nun ein dings? Naja, es enthält ein INTEGER, also 2 Byte, und ein Zeiger auf ein dings, also 4 Byte. Ein dings ist also 6 Byte gross und vollends in Oberon einsetzbar.

Dieses Konstrukt können wir nun verwenden, um eine verkettete Liste beliebiger Grösse zu erzeugen, alles ausgehend von einem einzigen Zeiger. Wie? Nun, wir haben ein Zeiger auf ein dings. Ist dieser Zeiger NIL, ist unsere Liste leer. Ist er es nicht, so haben wir mindestens ein dings. Ist dieses dings nicht das gesuchte, so schauen wir uns dings.next an usw...

Da das ganze ziemlich schwer vorstellbar ist, machen wir doch eine kleine Zeichnung dazu:

Die Bezeichnung verkettete Liste kommt eben nicht aus heiterem Himmel gefallen... Es ist nicht allzu schwer sich vorzustellen, wie das Einfügen eines neuen dings in der Liste aussehen kann:

Wir wollen das dings neu an der dritten Position unserer verketteten Liste einfügen. Dazu setzen wir neu.next auf das dritte dings der Liste und setzen den Zeiger next des zweiten dings auf neu. Das Resultat sieht dann so aus:

Die Tatsache, dass man bei einer verketteten Liste neue Elemente einfach in die Mitte schieben kann bringt sehr grosse Vorteile gegenüber einem ARRAY mit sich. Will man zum Beispiel eine sortierte Liste erhalten, muss man nicht nach dem Einfügen jedes Elementes die Liste sortieren, sondern fügt es von Anfang an am richtigen ort ein. Eine Prozedur, welche dies tut, könnte wie folgt aussehen:

PROCEDURE Einfuegen ( start, neu : pdings );
    BEGIN
        WHILE (start^.next # NIL) & 
              (start^.next^.data < neu^.data) DO
            start := start^.next;
        END;
        neu^.next := start^.next;
        start^.next := neu;
    END Einfügen;

Man übergibt der Prozedur den Zeiger auf das erste, und einen Zeiger auf das einzufügende dings. Die Prozedur geht die Liste mit

start := start^.next;

durch, bis start^.next = NIL oder start^.next grösser als der Wert des einzufügenden dings ist. Mit den zwei Zeilen

neu^.next := start^.next;
start^.next := neu;

wird dann neu dazwischengeschoben.

Obwohl diese Prozedur jetzt zu schön aussieht, um falsch zu sein, ist sie es. Was passiert nämlich, wenn wir ein dings einfügen wollen, dessen data kleiner als das erste der Liste ist? Wir schauen uns immer nur den Wert start^.next an, können also nicht erkennen, ob eigentlich schon das data von start grösser als derjenige von neu ist.

Dieses kleine Dilemma lässt sich auf zwei Arten lösen. Einerseits kann man explizit vor dem Aufruf von einfuegen testen, ob das neue Element nicht etwa an den Anfang gehört, so etwa

IF (start # NIL) & (start^.data > neu.data) THEN
    neu^.next := start;
    start := neu;
ELSE
    Einfuegen(start,neu);
END;

Dies ist jedoch lästig, wenn wir mehrmals an verschiedenen Stellen im Programm der Liste etwas antun möchten.

Die zweite,elegantere Lösung besteht darin, dass wir in der Prozedur Einfuegen start als VAR-Parameter deklarieren. Somit koennen wir dann start direkt in der Prozedur manipulieren, obwohl uns die Variable vom Benutzer mitgegeben wird:

PROCEDURE Einfuegen ( VAR start : pdings ; neu : pdings );
    BEGIN
        IF (start # NIL) & (start^.data > neu.data) THEN
            neu^.next := start;
            start := neu;
        ELSE        
            WHILE (start^.next # NIL) & 
                  (start^.next^.data < neu^.data) DO
                start := start^.next;
            END;
            neu^.next := start^.next;
            start^.next := neu;
        END;
    END Einfuegen;

Jetzt im Ernst

Also, nun wollen wir doch mal so eine Liste in der Form eines praktischen (sinnvoll wäre auch gut) Beispieles sehen. Nehmen wir doch unsere SchuelerListe aus dem vorherigen Kapitel und bauen sie aus.

Im Grunde genommen soll das Programm das gleiche machen wie sein Vorgänger, jedoch jetzt auch noch um die Funktion Loesche erweitert und auf einer Zeigerliste basierend. Zudem verlangen wir auch, dass die Schueler nach dem Wert legi aufsteigend sortiert seien.

Die Typendeklaration modifizieren wir wie folgt:

TYPE
    pSchueler = POINTER TO dSchueler;
    dSchueler = RECORD
        name, vorname : String;
        legi : LONGINT;
        next : pSchueler;
    END;

Es wird pSchueler als Zeiger auf einen dSchueler erzeugt, und dSchueler wird um den Wert next erweitert, um die Verkettung zu ermöglichen.

Die Deklaration der liste als globale Variable sieht nun wie folgt aus.

VAR
    liste : pSchueler;

Auf die Variable anzSchueler können wir bewusst verzichten, da, wie wir sehen werden, weder das Einfügen noch das Löschen eines Schuelers davon Gebrauch macht.

Die erste Prozedur, welche wir modifizieren müssen, ist wohl die einfachste.

PROCEDURE PrintSchueler ( s : pSchueler );
    BEGIN
        Out.String(s^.name); Out.Char(9X); (* tabulator *)
        Out.String(s^.vorname); Out.Char(9X);
        Out.Int(s^.legi,10); Out.Ln;
    END PrintSchueler;

Anstatt einen Schueler als Argument rüberzuschieben, geben wir den Zeiger drauf weiter. Die zweite Prozedur, welche eines Umbaus bedürftig ist, ist Neu. Die alte Version hat uns nicht nur einen Schueler erzeugt, sondern diesen grad noch in die liste eingefügt. Dies wollen wir auch tun, das Einfügen in die liste jedoch lassen wir von einer separaten Prozedur erledigen.

PROCEDURE Neu*;
    VAR
        neu : pSchueler;
    BEGIN
        NEW(neu);
        In.Open;
        getString(neu^.name);
        getString(neu^.vorname);
        In.LongInt(neu^.legi);
        Einfuegen(liste,neu);
    END Neu;

Das Einfügen geschieht, siehe da, genau gleich wie im dings-Beispiel

PROCEDURE Einfuegen ( VAR start : pSchueler ; neu : pSchueler );
    BEGIN
        IF (start # NIL) & (start^.data > neu.data) THEN
            neu^.next := start;
            start := neu;
        ELSE        
            WHILE (start^.next # NIL) & 
                  (start^.next^.data < neu^.data) DO
                start := start^.next;
            END;
            neu^.next := start^.next;
            start^.next := neu;
        END;
    END Einfuegen;

Der Umbau der Prozedur Finde gestaltet sich auch ziemlich einfach. Anstatt durch die Elemente eines ARRAYs zu kriechen, gehen wir Schueler für Schueler die liste durch.

PROCEDURE Finde*;
    VAR
        legi : LONGINT;
        s : pSchueler
    BEGIN
        In.Open;
        In.LongInt(legi);
        s := liste;
        WHILE s # NIL DO
            IF legi = s^.legi THEN
                PrintSchueler(s);
                RETURN;
            END;
            s := s^.next;
        END;
        Out.String("Schueler nicht gefunden!"); Out.Ln;
    END Finde;

Die letzte Prozedur, welche jetzt noch modifiziert werden muss, ist das Auflisten der Schueler. Wie bei Finde, können wir jetzt wieder einfach durch die liste tanzen und die Schueler einzeln ausdrucken.

PROCEDURE Liste*;
 VAR
        s : pSchueler;
    BEGIN
        s := liste^.next;
        WHILE s # NIL DO
            PrintSchueler(s);
            s := s^.next;
        END;
    END Liste;

Ziemlich einfach, was? Nun müssen wir zu guter Letzt noch wie versprochen Schueler von der liste löschen können (es dürfen ja welche vorzeitig ausscheiden, oder?). Das Löschen eines Elementes in einer Zeigerliste geht genau umgekehrt wie das Einfügen: wir suchen den zu löschenden Schueler aus der liste aus und biegen den Zeiger vom Vorgänger auf den nächsten Schueler um. Einfach, oder? In Oberon sieht das etwa so aus:

PROCEDURE Loesche*;
    VAR
        s : pSchueler;
        l : LONGINT;
    BEGIN
        In.Open;
        In.LongInt(l);
        IF liste^.legi = l THEN
            liste := liste^.next;
        ELSIF liste # NIL THEN
            s := liste;
            WHILE (s^.next # NIL) & (s^.next^.legi # l) DO
                s := s^.next;
            END;
            IF s^.next # NIL THEN
                s^.next := s^.next^.next;
            END;
        END;
    END Loesche;

Die Prozedur lässt sich wie folgt lesen: wir lesen die zu löschende Legi-Nummer ein, ist der erste Schueler der liste der gesuchte, wird er prompt geloescht, ansonsten, wenn die liste nicht NIL (sprich leer) ist, gehen wir die liste durch bis wir die Nummer finden oder wir am Ende der liste sind, haben wir was gefunden, so biegen wir den Zeiger des vorhergehenden Schuelers darauf aufs nachfolgende um.

Da die liste noch sortiert ist, lässt sich diese letzte Prozedur noch optimieren, was aber eine Leser-Aufgabe bleiben möchte.