Claus Schönleber

Hitchhacker´s Guide To PASCAL  [Vol. 2]

Inhalt

Pointer

Trotzdem sind Pointer notwendig, und viele Probleme lassen sich nur durch Pointer vernünftig lösen.

Datenstruktur

Normale Variablen werden statisch im Speicher abgelegt und über eine Tabelle referenziert. Immer wenn in einem Programmtext auf eine Variable "a" zugegriffen werden soll, wird über die Tabelle die eigentliche Adresse des gewünschten Wertes ermittelt und dann auf die entsprechende Speicherzelle zugegriffen. Statische Daten haben aber den Nachteil, daß man schon während der Programmierzeit über die Anzahl der zu verarbeitenden Daten Bescheid wissen muß. Es gibt jedoch viele Probleme, die das nicht erlauben. Deswegen gibt es einen speziellen Bereich im Arbeitsspeicher, den Heap (engl.: Haufen), in dem bei Bedarf beliebige Werte abgelegt werden können. Da das während der Laufzeit passiert, kann diesen Werten kein (Variablen-)Name zugewiesen werden; man richtet sich deswegen einen "Merkzettel" ein, einen Wert, der auf die entsprechende Adresse im Heap "zeigt", einen sogenannten Zeiger oder pointer. Er ersetzt den Variablennamen. Solche Daten können genausoschnell weggeräumt werden, wie sie angelegt wurden. Manche Sprachen erlauben eine automatische "Heap-Reinigung" (garbage collection), zum Beispiel LISP oder JAVA. In PASCAL oder C/C++ muß der Programmierer das selbst tun; das ist dann ein Quell mannigfaltiger und schwer zu entdeckender Fehler.

Oftmals werden Zeiger jedoch zu einem besonderen Zweck eingesetzt. Die erlauben, unterschiedliche Objekte so zu verknüpfen, daß Strukturen entstehen, mit denen man gerne arbeitet: 

• Linerare, verkettete Listen
• Bäume
• Netze

Diese Listen sind dynamisch, d.h. im Gegensatz zum "Array", dessen Größe schon vor der Laufzeit des Programms festgelegt werden muß, ist es bei einer verketteten Liste auch während der Laufzeit eines Programms völlig offen, wieviel Elemente sie enthalten darf.

Um das zu erreichen, muß bei Bedarf für ein neu einzugebendes Element im System Platz angefordert werden. Die Verkettung der einzelnen Elemente wird dadurch erreicht, daß man dem letzten Element mitteilt, wo das nächste steht. Das Ganze kann man dann mit einer sequentiellen Datei vergleichen, nur daß die "Datei" nicht auf der Platte, sondern im Arbeitsspeicher (Adressraum der Hardware) steht.

Es interessiert uns momentan noch nicht, welcher Art die Elemente dieser Art von Liste sein dürfen. Zunächst ist interessant, wie der Verkettungsmechanismus funktioniert. Dazu ein paar Momentaufnahmen von einem Programm, das nacheinander insgesamt drei Listenelemente anfordert. Elemente werden links angefügt, bestehende werden nach rechts geschoben.

In Schritt 1 wird ein Element vom System angefordert. Das Element wird durch den Kasten dargestellt. Es enthält die Daten. Der kleine Kasten mit dem Punkt, das ist der Teil, der uns hier interessiert. Denn hier wird gleich die Adresse des nächsten Elements hineingeschrieben, dargestellt durch einen Pfeil.

In Schritt 2 ist das zweite Element angefordert worden. Diesem wurde die Adresse des ersten Elementes beigegeben, damit die Liste verkettet werden kann. So kann man sich nun von Element Nr. 2 nach Element Nr. 1 "hangeln" (nicht umgekehrt!).

Im letzten Schritt ist das dritte Element angefordert und in die schon bestehende Liste eingefügt, sprich angehängt, worden.

Wenn man die fertige Liste betrachtet, dann merkt man zweierlei:

1. Erstens, wo ist der Anfang der Liste? Ohne die Information, wo die Liste beginnt, kann sie ja nicht benutzt werden. Und was bedeutet der Punkt in Datensatz 1 anstelle des Kästchens?
2. Zweitens, warum kann die Liste denn nach dem Aufbau nur "von hinten" durchgelesen werden? Die Zeiger gehen doch in die verkehrte Richtung!

Da das "erste" (zuerst angelegte) Element auf kein weiteres zeigt, kann hier keine echte Adresse stehen. Deswegen gibt es auch für diesen "Zeigertyp" ein neutrales Element. Es heißt NIL und zeigt auf kein anderes Element. Dem System zeigt NIL an, daß die Kette hier zu Ende ist. Eine Variable vom Typ Zeiger kann auf diesen Wert abgefragt werden. Der "dicke" Punkt in der Ecke des "letzten" Elementes ist der besondere Wert. In C/C++ heißt er NULL.

Der "Anfangszeiger" (er heißt oft "first") muß natürlich mit jedem neu angeforderten Element verändert werden! Da das der Programmierer, also Sie, zu machen haben, sollten Sie sich diesen Schritt genau einprägen!

Zu Punkt zwei: Man kann eine einfach verkettet Liste auch anders organisieren, aber das hier ist die einfachste Form. Die Einfachheit wird jedoch mit der Eigenschaft bezahlt, daß das zuletzt angefügte Element beim Auslesen der (sequentiellen) Liste als erstes Element wiedergefunden wird. Die Reihenfolge wird umgedreht. Das läßt sich aber kompensieren.

Deklaration von Pointern

Um eine Variable vom Typ Pointer in einem Record zu benutzen, ist "ein wenig" Vorarbeit notwendig. 

• Zunächst muß der Zeigertyp deklariert werden (hier: link).
• Dann wird der Record eingeführt, von dessen Datenfeldern eines vom gerade eingeführten Zeigertyp ist (hier: next).
• Jetzt können die Variablen eingeführt werden für die entsprechende Anzahl von Zeigern zur Verwaltung der Liste (hier: p,first).

TYPE link = ^person;
     person = RECORD
                name : STRING [40];
                next : link;
              END;
VAR p,first : link;

Einsatz von Pointern

Wir müssen vorher nur noch zwei Dinge klären:

1. Wie fordert man einen neuen Record an?
2. Wie greift man auf die Datenfelder der Listenelemente zu?

new (<zeigervariable>)

new (p)

Um dabei den Anschluß an die Liste nicht zu verlieren, muß der Anfangszeiger natürlich diesen neuen Wert erhalten. Der alte Wert des Anfangszeigers muß vorher der Zeigervariablen des neuen Records zugewiesen werden, damit das neue Element mit der Liste verbunden wird.

Üblicherweise werden, wenn man keine spezielleren Bezeichnungen benötigt, der Listenzeiger "p" und der Anfangszeiger "first" genannt. Natürlich kann man auch der Problematik angepaßte Namen verwenden, aber für Übungszwecke sollte man diese Nomenklatur übernehmen.

Zur Antwort auf die zweite Frage: Wie man gleich im Beispiel sehen wird, gibt es keine extra Variable, die den Record repräsentieren würde. Das ist auch überflüssig, denn wir wissen ja, wo der Record im Speicher steht, nämlich ab der Adresse, die in "p" steht. Dadurch brauchen wir keinen Variablennamen. Also sprechen wir die Datenfelder durch die Zeigervariable fast wie gewohnt an. Der Unterschied ist nur, daß man dem System mitteilen muß, daß man nicht ein Datenfeld des Pointers haben möchte, sondern ein Datenfeld des Records, auf das der Pointer zeigt! Das geschieht dann folgendermaßen:

<zeigervariable>^.<datenfeldbezeichner>

p^.name

Wenden wir das bisher Gesagte im Beispiel an:

PROGRAM pointer (input,output);

  TYPE link  = ^liste;
       liste = RECORD
                 name : STRING [80];
                 next : link;
               END;

  VAR p,first : link;
      index   : integer;
      n       : STRING [80];

BEGIN
  (* Das später letzte Element der Liste zeigt auf *)
  (* keinen weiteren Datensatz. *)
    first := NIL;

  FOR index := 1 TO 10 DO
  BEGIN
    (* Pointerelemente einlesen *)
      write ('->');
      readln (n);
    (* Anfordern eines neuen Records *)
      new (p);
    (* Zuweisen des Recorddatenfeldes *)
      p^.name := n;
    (* Der neue Record bekommt die Adresse des *) (* letzten Records, die ja in "first" noch *)
    (* steht. *)
      p^.next := first;
    (* Aktualisieren des Anfangszeigers *)
      first := p
  END;
  (* Vorbereitung der Ausgabe: Zeiger "p" wird auf *)
  (* das "erste" Element der Liste gesetzt *)
    p := first;
  WHILE (p <> NIL) DO
  BEGIN
    (* Pointerelemente ausgeben *)
      write (p^.name);
    (* Setzen des Zeigers auf den nächsten Record *)
      p := p^.next
  END
END.

Ausgabe der Liste: Für die Ausgabe bzw. für das lineare Durchsuchen sind also wesentlich weniger Schritte notwendig. Wichtig ist die Bedingung in der WHILE-Schleife, die das Ende der Liste über den Wert NIL ermittelt.

Schwierig wird das Ganze, wenn ein Datensatz aus der Liste entfernt oder eingefügt werden soll. 

Formulieren wir ein Programmfragment, welches sich an dem gerade besprochenen Beispiel orientiert und wahlweise einen Datensatz löscht oder einfügt. 

VAR ...
  insert,last : link;
  answer : char;
  position,i : integer;
.
.
  write ('(1) Einfügen, (2) Löschen: ');
  readln (answer);
  REPEAT
    write ('Position, an der eingefügt/gelöscht werden soll:');
    readln (position);
  UNTIL (position IN [1..10]);
  p := first;
  i := 1;
  WHILE (p <> NIL) AND (i < position) DO
  BEGIN
    last := p;
    p := p^.next;
    i := succ (i);
  END;
  CASE answer OF
    1 : BEGIN
          new (insert);
          insert^.next := p^.next;
          p^.next := insert; 
        END;
    2 : BEGIN
          last^.next := p^.next; 
        END;
  END;
  (*** Ausgabe ***)
    p := first;
    WHILE (p <> NIL) DO
    BEGIN
      writeln (p^.name);
      p := p^.next;
    END;
END.

Einfügen

Dabei müssen folgende Schritte ausgeführt werden:

1. Anfordern eines neuen Records mittels "new"

new (insert);
2. Dem Verkettungszeiger des neuen Records wird der Verkettungszeiger des Records zugewiesen, auf den der Record (Nr. 2 im Beispiel) verwies, hinter den derneue eingefügt werden soll.

insert^.next := p^.next;
3.  Zum Schluß muß der Verkettungszeiger des Records, hinter den der neue eingefügt werden soll, noch auf den neuen gesetzt werden.

p^.next := insert;

Löschen:

Folgende Schritte sind hier nötig:

1. Zunächst muß beim Durchhangeln ein zusätzlicher Zeiger mitgeführt werden, der immer auf den zuletzt betrachteten Record zeigt ("last").

last := p;
p := p^.next;
2. Dann muß der Verkettungszeiger des vor dem zu löschenden Records auf den Nachfolger des zu löschenden Records gesetzt werden.

last^.next := p^.next;

Verwaltung des "Heap"

Doch dafür kurz ein Wort über die Zeigerverwaltung von Turbo PASCAL. Die Datensätze, auf die die Zeiger verweisen, werden in einem gesonderten Speicherbereich, genannt "Heap", abgelegt. Man kann ihn sich ungefähr so vorstellen:
 

Datensatz 1

Datensatz 2

Datensatz 3

...

Datensatz n

[Heapgrenze]

[freier Platz]
...
...

Wenn man jetzt einen Datensatz aus der verketteten Liste herausnimmt, dann will man auch dessen Speicherplatz wieder als frei kennzeichnen, d.h. für die Prozedur new wieder zur Verfügung stellen.

dispose

dispose (<zeigervariable>)

Nach 

dispose (p2)

Es gibt in Turbo PASCAL noch eine weitere Methode:

mark, release

Mit der Prozedur mark markiert man zunächst die Position eines bestimmten Datensatzes, indem man einfach den aktuellen Zeiger in einer gesonderten Zeigervariablen "markiert" (sichert). Durch die spätere Verwendung von release in Bezug auf diesen Zeiger wird der komplette Heap ab dieser Position gelöscht.

Welche Methode vorzuziehen ist, hängt von der Anwendung ab. Sie dürfen nur nicht gemischt werden. Es soll hier auch nicht diskutiert werden. Das Turbo PASCAL Handbuch gibt ausführlich Informationen zu diesem Thema.