Mit Ausnahme der Variablen vom Typ File sind alle bisher vorgestellten Strukturen (Arrays, Records, Mengen) statisch. Das heißt, sie behalten während ihrer Gültigkeit die Struktur bei, die bei der Deklaration vereinbart wurde. Die Gültigkeit dieser Variablen reicht vom Eintritt in einen Block (Hauptprogramm, Prozedur oder Funktion) bis zum Verlassen dieses Blockes (Programmende oder Rücksprung aus einer Prozedur).
In diesem Abschnitt wird beschrieben, wie man in Pascal Objekte konstruiert, die während der Programmlaufzeit nicht nur wachsen oder schrumpfen, sondern auch dynamisch zu Listen und beliebigen Netzen verbunden werden können. Zum Zeitpunkt der Übersetzung wird nur die (statische) Struktur der Elemente definiert. Diese Bausteine besitzen meist die Struktur eines Records. Der Speicherplatz für die verschiedenen Records wird dann zur Programmlaufzeit je nach Bedarf zur Verfügung gestellt. Die Verbindung zu komplexen Strukturen geschieht über Zeiger, die von Record zu Record führen.
Das Konzept der Zeigertypen stellt einen großen Fortschritt der Sprache Pascal gegenüber den klassischen Sprachen wie FORTRAN, COBOL und BASIC dar. Oft ist jedoch festzustellen, daß auch ambitionierte Einsteiger in die Sprache Pascal an diesem für sie qualitativ neuen Datentyp scheitern. Tatsächlich stellt die Arbeit mit dynamischen Datenstrukturen den Programmierer vor völlig neue Probleme bei der Programmentwicklung und -überprüfung. Daher soll in diesem Abschnitt ein eher pragmatischer Einstieg in das Thema gefunden werden.
Die Aufgabe besteht darin, in einem Unternehmen eine Liste von Kunden zu bilden. Von jedem Kunden sollen der Name und die Kunden- nummer gespeichert werden. Da a priori nicht bekannt ist, wie viele Kunden in Zukunft zu speichern sind, kann man zur Speicherung kein Array mit Records verwenden. Andererseits ist die rein sequentielle Zugriffsmethode auf ein (langsames) Diskettenfile nicht zu verwenden. Diese Aufgabe ist ein typisches Beispiel für die Anwendung einer Liste, die dynamisch durch Zeiger gebildet wird. Die benötigten Strukturen werden im folgenden Deklarationsteil beschrieben:
TYPE KUNDENZEIGER = ^ KUNDE;
KUNDE = RECORD
NAME : STRING[10];
KNUMMER : INTEGER;
NAECHSTER: KUNDENZEIGER;
END;
VAR KUNDE1, KUNDENEU, LETZTERKUNDE: KUNDENZEIGER;
Bild 89: Deklaration von Zeigertypen
Mit der Typdeklaration in Bild 89 wird ein Typ KUNDE definiert, der die gewünschten Informationen (NAME, KNUMMER) für jeden Kunden speichert. Außerdem existiert ein Typ KUNDENZEIGER, der als Werte Zeiger (pointer) auf solche Kundenrecords besitzt. Als Variablen wurden keine Kundenrecords, sondern nur Zeigervariablen deklariert.
Sie sollten sich einen Zeiger recht plastisch als einen Pfeil (^) vorstellen, der immer auf einen Wert des zugehörigen Typs zeigt (s. Bild 90). KUNDENZEIGER weisen also immer auf Records vom Typ KUNDE.
Bild 90: Zeigerstrukturen
Ordnet man die Zeiger wie in Bild 90, so erhält man eine Kundenliste: Jeder Kunde besitzt einen Zeiger auf seinen Nachfolger in der Liste. Von außerhalb verweisen noch die Zeiger KUNDE1, KUNDENEU und LETZTERKUNDE in die Liste. Bild 90 stellt eine Momentaufnahme der Listenstruktur dar. Durch das Umhängen von Zeigern und Records kann man die Liste umsortieren, verlängern und verkürzen.
Zum Aufbau einer (Kunden-) Liste geht man nun folgendermaßen vor: Man erzeugt sich für jeden neuen Kunden einen Record vom Typ KUNDE. Diese Records werden nun durch Zeiger vom Typ KUNDENZEIGER verkettet. Der Zeiger KUNDE1 zeigt dabei immer auf den ersten Kundenrecord in der Liste. Jeder Record enthält im Feld NAECHSTER einen Zeiger auf seinen Nachfolger in der Liste.
Da die Kundenrecords keinen eigenen Namen besitzen, kann man Kundenrecords auch nur durch die Angabe eines Zeigers ansprechen. Man bezeichnet deshalb dynamische Objekte als anonym.
Um Speicherplatz für einen Kundenrecord zur Verfügung zu stellen, benutzt man die Standardprozedur NEW. Sie erzeugt irgendwo im Speicher Platz für einen Record. Um nun auf diesen Record zuzugreifen, verlangt die Prozedur eine Zeigervariable vom Typ KUNDENZEIGER als aktuellen Parameter. Dieser Zeigervariablen wird die Adresse des neuen Records vom Typ KUNDE zugeweisen:
NEW(KUNDENEU)
Über den Zeiger KUNDENEU kann man jetzt den Record vom Typ KUNDE mit Werten füllen. Da bei den Zuweisungen nicht die Zeigervariable selbst, sondern das Objekt, auf das der Zeiger zeigt, gemeint ist, benutzt man den Pfeil (^) nach dem Variablennamen:
KUNDENEU^.NAME:='Jones'; KUNDENEU^.KNUMMER:= 1111;
Da ein Zeiger eine Referenz auf ein dynamisches Objekt darstellt, nennt man den Pfeil auch Dereferenzier-Operator. Um nun einen anderen Zeiger (nämlich KUNDE1) auf den mit NEW erzeugten Kundenrecord zu setzen, führt man eine Zuweisung zwischen Zeigern durch:
KUNDE1:= KUNDENEU
Damit Sie den Unterschied zwischen Zeigern und den durch sie referenzierten Objekten erkennen, wird noch ein neuer Kunde hinter »Jones« an die Liste gehängt. Zunächst muß ein neuer Record vom Typ KUNDE gebildet werden:
NEW(LETZTERKUNDE)
Dann wird der Inhalt von LETZTERKUNDE^ initialisiert:
LETZTERKUNDE^.NAME := 'Jackson'; LETZTERKUNDE^.KNUMMER:= 2222;
Nun muß »Jackson« als Nachfolger von »Jones« in die Liste gehängt werden. Dazu verwendet man den Zeiger NAECHSTER im Record von »Jones«, auf den ja noch KUNDENEU zeigt. NAECHSTER soll auf den Record von »Jackson« zeigen, der durch LETZTERKUNDE referenziert wird:
KUNDENEU^.NAECHSTER:= LETZTERKUNDE
Bisher wurden nur Zuweisungen an Zeigervariablen oder Kundenrecords durchgeführt. Der Inhalt der Records läßt sich jedoch auch in Ausdrücken und Ausgabeanweisungen verwenden. Zum Zugriff benutzt man wieder die Zeigervariable mit dem nachgestellten De- referenzieroperator (^).
WRITELN(KUNDE1^.NAME, KUNDE1^.KNUMMER); WRITELN(LETZTERKUNDE^.NAME, LETZTERKUNDE^.KNUMMER); WRITELN(KUNDE1^.NAECHSTER^.NAME);
Die Bedeutung der ersten beiden Ausgaben ist offensichtlich: Die durch KUNDE1 und LETZTERKUNDE referenzierten Records (»Jones« und »Jackson«) werden angezeigt. Interessanter ist die letzte Ausgabeanweisung, da dort zweimal dereferenziert wird: Es wird der Name des Nachfolgers des Records KUNDE1 gedruckt. Dies ist demnach der 2. Kunde (»Jackson«).
Bild 91 zeigt alle obigen Operationen zusammenfassend in Form eines vollständigen Programmes. Das Ergebnis jeder durch Zahlen im Listing markierten Operationen wird grafisch in Bild 92 dargestellt. Ein anschauliches Bild dynamischer Strukturen stellt die einzelnen Records als Kästchen dar, während Zeiger durch Pfeile symbolisiert werden, die von Record zu Record führen.
PROGRAM ZEIGER (INPUT, OUTPUT);
TYPE KUNDENZEIGER = ^ KUNDE;
KUNDE = RECORD
NAME : STRING[10];
KNUMMER : INTEGER;
NAECHSTER: KUNDENZEIGER;
END;
VAR KUNDE1, KUNDENEU, LETZTERKUNDE: KUNDENZEIGER;
BEGIN
NEW(KUNDENEU); (* 1. *)
KUNDENEU^.NAME:='Jones';
KUNDENEU^.KNUMMER:= 1111; (* 2. *)
KUNDE1:= KUNDENEU; (* 3. *)
NEW(LETZTERKUNDE);
LETZTERKUNDE^.NAME := 'Jackson';
LETZTERKUNDE^.KNUMMER:= 2222; (* 4. *)
KUNDENEU^.NAECHSTER:= LETZTERKUNDE; (* 5. *)
WRITELN(KUNDE1^.NAME, KUNDE1^.KNUMMER);
WRITELN(LETZTERKUNDE^.NAME, LETZTERKUNDE^.KNUMMER);
WRITELN(KUNDE1^.NAECHTSER^.NAME);
END.
Bild 91: Operationen mit Zeigervariablen
Bild 92: Aufbau der Kundenliste
Ein grundsätzliches Problem wurde noch nicht beachtet: Was passiert mit Zeigern, die (noch) auf keinen Record zeigen? So hat z.B. der Record LETZTERKUNDE^ (»Jackson«) keinen Nachfolger. Eine Möglichkeit besteht darin, jeden Record um ein boolesches Feld zu erweitern, das angibt, ob ein Nachfolger existiert oder nicht. Da dieser Fall bei der Arbeit mit Zeigern ständig auftritt, ist der Wertebereich aller Zeigertypen um den Wert NIL erweitert. Besitzt ein Zeiger P den Wert NIL, so existiert kein Objekt P^. Deshalb belegt man das Feld NAECHSTER bei dem Record »Jackson« mit NIL:
LETZTERKUNDE^.NAECHSTER:= NIL;
Bevor Sie im nächsten Abschnitt typische Datenstrukturen kennenlernen, die mit Zeigern in Pascal realisiert werden, werden die allgemeinen Regeln für die Arbeit mit Zeigern zusammengefaßt:
TYPE Z = ^ T;
TYPE T = RECORD
...
TT : Z; FALSCH! ( Z ist hier noch unbekannt!)
END;
Z = ^ T;
Deshalb gibt es von dieser Regel eine Ausnahme: In der Deklaration eines Zeigertyps kann ein Typname verwendet werden, der noch nicht deklariert wurde. Die Deklaration dieses Namens muß jedoch noch im selben Typvereinbarungsteil erfolgen:
TYPE Z = ^ T; RICHTIG! (T darf hier noch unbekannt sein)
T = RECORD
...
TT: Z;
END;
Eine Tatsache muß noch besonders betont werden. Zwar kann ein Zeiger während der Laufzeit auf beliebige Objekte gesetzt werden, jedoch bleibt in jedem Fall die Typbindung von Pascal in Kraft. Dies unterscheidet Zeiger von reinen Adressen in Assembler. Konkret heißt dies, daß ein Zeigervariable, die mit
VAR V: ^T;
deklariert wurde, nur auf Objekte vom Typ T zeigen kann. So ist also die folgende Anweisung nach der angegebenen Deklaration von ZI^ nicht zulässig:
VAR ZI: ^ INTEGER; ZI^:= 'A'; FALSCH! ZI^:= 312; RICHTIG!
Im vorangegangenen Abschnitt wurden bereits die ersten Schritte zum Aufbau einer Liste von Kundenrecords gemacht. Dabei lag dem Beispiel eine eher intuitive Vorstellung einer Liste zugrunde, die man bei Bedarf am Ende erweitert.
Grundsätzlich bezeichnet man in Pascal jede lineare Datenstruktur, die durch Zeiger gebildet wird, als eine Liste. Linear bedeutet in diesem Zusammenhang, daß jedes Element maximal einen Vorgänger und Nachfolger besitzt. Folgende Operationen sind mit Listen möglich:
Es gibt zahlreiche verschiedene Listentypen, die sich durch die Art der Verzeigerung unterscheiden. Wenn Sie noch einmal Bild 90 betrachten, werden Sie feststellen, daß man mit der Operation
KUNDENEU:= KUNDENEU^.NAECHSTER
ohne Probleme die Liste vorwärts durchlaufen kann. Andererseits ist es (ohne einen Zugriff auf andere Zeiger) nicht möglich, von LETZTERKUNDE zurück zum Vorgänger in der Liste zu gelangen. So bestimmt die Zeigerstruktur die Art der möglichen Zugriffe auf eine Liste.
Bild 93: Verschiedene Listen
In Bild 93 sind die wichtigsten Listentypen grafisch dargestellt.
| A | Kellerspeicher (stack, Stapelspeicher) |
| B | Schlange (queue) |
| C | Ringspeicher |
| D | Doppelt verkettete Liste |
Generell besteht eine Liste (A bis D) aus nur wenigen statischen Zeigervariablen (OBEN, KOPF, SCHWANZ, ANKER, START), die quasi einen Einstiegspunkt für eine komplexe Struktur mit eventuell vielen hundert dynamischen Datenelementen bilden. Die Elemente erreicht man ausgehend vom diesen Einstiegspunkten durch Verfolgen der Zeigerketten.
Bis auf den Ringspeicher wird jeder dieser Typen durch kurze Demonstrationsprogramme vorgestellt, die das Einfügen und Löschen von Namen in einer Liste ermöglichen. Eine etwas erweiterte einfach verkettete Liste wird anschließend zur Speicherung einer alphabetisch sortierten Kundenliste verwendet.
Bei einem Kellerspeicher fügt man Elemente bei OBEN ein und löscht sie auch dort wieder. Weil dadurch das zuletzt eingefügte Element zuerst gelöscht wird, heißt ein Kellerspeicher auch LIFO-Speicher (last in first out). Operationen mit einem Kellerspeicher sind besonders einfach zu realisieren.
PROGRAM STACK (INPUT,OUTPUT);
TYPE ZEIGER = ^ ELEMENT;
ELEMENT = RECORD
TEXT: STRING[20];
NEXT: ZEIGER;
END;
VAR OBEN: ZEIGER;
C : CHAR;
PROCEDURE LEERELISTE;
BEGIN
OBEN:= NIL
END; (* LEERELISTE *)
PROCEDURE EINFUEGEN;
VAR NEU: ZEIGER;
BEGIN
NEW(NEU);
WRITE('Text :'); READLN(NEU^.TEXT);
NEU^.NEXT:= OBEN;
OBEN:= NEU
END; (* EINFUEGEN *)
PROCEDURE LOESCHEN;
BEGIN
IF OBEN = NIL THEN
WRITELN('Die Liste ist leer')
ELSE
BEGIN
WRITE('Gelöscht wurde:', OBEN^.TEXT);
OBEN:= OBEN^.NEXT;
END;
END; (* LOESCHEN *)
PROCEDURE ANZEIGEN;
VAR Z: ZEIGER;
BEGIN
Z:= OBEN;
WHILE Z<>NIL DO
BEGIN
WRITELN(Z^.TEXT);
Z:= Z^.NEXT;
END;
END; (* ANZEIGEN *)
BEGIN
LEERELISTE;
REPEAT
ANZEIGEN;
WRITELN('E infuegen');
WRITELN('L oeschen');
WRITELN('B eenden');
WRITELN;
WRITE('==>');READLN(C);
CASE C OF
'E': EINFUEGEN;
'L': LOESCHEN;
ELSE (* nichts *)
END; (* CASE *)
UNTIL C='B';
END.
Bild 94: Ein Kellerspeicher
In Bild 94 ist jede Operation durch eine separate Prozedur realisiert. Sie können wahlweise Daten einfügen und löschen. Die Daten werden offensichtlich in umgekehrter Reihenfolge gespeichert. Eine wichtige Programmiertechnik bei der Arbeit mit Zeigern besteht darin, immer den Sonderfall zu beachten, daß ein Zeiger den Wert NIL besitzt: Ist zum Beispiel beim Löschen die Liste leer, so besitzt der Zeiger OBEN den Wert NIL. In diesem Fall würde die Zuweisung
OBEN:= OBEN^.NEXT
einen nicht existierenden Wert OBEN^ adressieren, was über kurz oder lang zu einem Programmabsturz führen wird.
Bei einer Schlange (man denke an eine Warteschlange) fügt man Elemente bei dem durch SCHWANZ referenzierten Ende ein und löscht sie bei KOPF. Demnach sind Schlangen FIFO-Speicher (first in first out). Während die Operation ANZEIGEN für Schlangen und Keller- speicher identisch ist, muß bei den Operationen EINFUEGEN und LOESCHEN der Sonderfall beachtet werden, daß die Schlange leer war oder leer wird. Im Falle einer leeren Schlange müssen nämlich beideZeiger (KOPF und SCHWANZ) den Wert NIL erhalten.
PROGRAM QUEUE (INPUT,OUTPUT);
TYPE ZEIGER = ^ ELEMENT;
ELEMENT = RECORD
TEXT: STRING[20];
NEXT: ZEIGER;
END;
VAR KOPF, SCHWANZ: ZEIGER;
C : CHAR;
PROCEDURE LEERELISTE;
BEGIN
KOPF := NIL;
SCHWANZ:= NIL;
END; (* LEERELISTE *)
PROCEDURE EINFUEGEN;
VAR NEU: ZEIGER;
BEGIN
NEW(NEU);
WRITE('Text :'); READLN(NEU^.TEXT);
NEU^.NEXT:= NIL;
IF SCHWANZ = NIL THEN (* Schlange war leer *)
KOPF:= NEU
ELSE
SCHWANZ^.NEXT:= NEU;
SCHWANZ:= NEU;
END; (* EINFUEGEN *)
PROCEDURE LOESCHEN;
BEGIN
IF KOPF = NIL THEN
WRITELN('Die Liste ist leer')
ELSE
BEGIN
WRITE('Gelöscht wurde:', KOPF^.TEXT);
KOPF:= KOPF^.NEXT;
IF KOPF = NIL THEN (* Schlange wird leer *)
SCHWANZ:= NIL
END;
END; (* LOESCHEN *)
PROCEDURE ANZEIGEN;
VAR Z: ZEIGER;
BEGIN
Z:= KOPF;
WHILE Z<>NIL DO
BEGIN
WRITELN(Z^.TEXT);
Z:= Z^.NEXT;
END;
END; (* ANZEIGEN *)
BEGIN
LEERELISTE;
REPEAT
ANZEIGEN;
WRITELN('E infuegen');
WRITELN('L oeschen');
WRITELN('B eenden');
WRITELN;
WRITE('==>');READLN(C);
CASE C OF
'E': EINFUEGEN;
'L': LOESCHEN;
ELSE (* nichts *)
END; (* CASE *)
UNTIL C='B';
END.
Bild 95: Eine Schlange
In einigen Anwendungen sind Ringspeicher sinnvoll. Hierbei ist keine vollständige Ordnung auf den Elementen definiert. Jedes Element ist Nachfolger eines anderen, so daß keines der Elemente als »Anfang« oder »Ende« gesondert behandelt werden muß. Die statische Variable ANKER wird nur benötigt, um einen Einstieg in die dynamische Struktur zu besitzen. Wäre Anker nämlich nicht vor- handen, so könnte man keines der anonymen Objekte über einen Zeiger erreichen!
Relativ aufwendige Operationen beim Löschen und auch beim Einfügen erfordert die Konstruktion einer doppelt verketteten Liste. Ein wesentlicher Vorteil ist die Tatasache, daß man sich in beiden Richtungen in der Liste bewegen kann. Dafür müssen aber in jedem Record zwei Zeiger vorhanden sein, die bei sehr großen Listen auch einen nennenswerten Speicherplatz verbrauchen können.
PROGRAM DOUBLE (INPUT,OUTPUT);
TYPE ZEIGER = ^ ELEMENT;
ELEMENT = RECORD
TEXT: STRING[20];
NEXT: ZEIGER;
PREV: ZEIGER
END;
VAR START: ZEIGER;
C: CHAR;
PROCEDURE LEERELISTE;
BEGIN
START:= NIL;
END; (* LEERELISTE *)
PROCEDURE EINFUEGEN;
VAR NEU: ZEIGER;
BEGIN
NEW(NEU);
WRITE('Text :'); READLN(NEU^.TEXT);
IF START<>NIL THEN
START^.PREV:= NEU;
NEU^.NEXT:= START;
NEU^.PREV:= NIL;
START:= NEU;
END; (* EINFUEGEN *)
PROCEDURE LOESCHEN;
BEGIN
IF START = NIL THEN
WRITELN('Die Liste ist leer')
ELSE
BEGIN
WRITE('Gelöscht wurde:', START^.TEXT);
START:= START^.NEXT;
IF START<>NIL THEN
START^.PRED:= NIL;
END;
END; (* LOESCHEN *)
PROCEDURE ANZEIGEN;
(* Zur Demonstration vorwärts und rückwärts *)
VAR Z,Z1: ZEIGER;
BEGIN
WRITELN('VORWAERTS:);
Z:= START; Z1:= NIL;
WHILE Z<>NIL DO
BEGIN
WRITELN(Z^.TEXT);
Z1:= Z; Z:= Z^.NEXT;
END;
WRITELN('RUECKWAERTS:');
WHILE Z1<>NIL DO
BEGIN
WRITELN(Z1^.TEXT);
Z1:= Z1^.PREV
END;
END; (* ANZEIGEN *)
BEGIN
LEERELISTE;
REPEAT
ANZEIGEN;
WRITELN('E infuegen');
WRITELN('L oeschen');
WRITELN('B eenden');
WRITELN;
WRITE('==>');READLN(C);
CASE C OF
'E': EINFUEGEN;
'L': LOESCHEN;
ELSE (* nichts *)
END; (* CASE *)
UNTIL C='B';
END.
Bild 96: Eine doppelt verkettete Liste
In Bild 98 ist ein komplettes Programm angegeben, das die am Anfang des Abschnittes erwähnte Kundenliste implementiert. Im Unterschied zu den bisher vorgestellten Demonstrationsprogrammen mit Zeigervariablen wird die Kundenliste ständig alphabetisch sortiert gehalten.
Alle Funktionen sind so zu Modulen zusammengefaßt und ausführlich kommentiert, daß Sie die einzelnen Operationen mit den folgenden Hinweisen nachvollziehen können:
Arnold Jackson Jones Overmars Vollmann
durchläuft man die Namen solange, bis man den Namen errreicht, hinter dem »Ross« eingefügt werden soll. Zeigt die Variable VOR auf den Namen »Overmars« und NEU auf den neuen Record mit dem Namen »Ross«, so fügt man NEU folgendermaßen hinter VOR in die Liste ein: (s. Bild 97.A)
NEU^.NAECHSTER:= VOR^.NAECHSTER; VOR^.NAECHSTER:= NEU;
VOR^.NAECHSTER:= VOR^.NAECHSTER^.NAECHSTER
Dadurch wird die in Bild 97.B dargestellte Operation durch- geführt.
Bild 97 A) Einfügen in der Kundenliste
Bild 97 B) Löschen in der Kundenliste
Bild 98: Das Progamm Kundenliste
Zum Abschluß des Abschnittes sollen Sie noch ein Standardverfahren kennenlernen, mit dem man den Speicherplatz, der durch das Löschen von Records frei wird, wiederverwenden kann. Die Idee besteht darin, die (logisch) gelöschten Records zu einer neuen Liste, der Freispeicherliste, zu verketten. Vor jedem Aufruf der Prozedur NEW prüft man dann, ob sich nicht bereits ein unbenutzter Record in der Freispeicherliste befindet.
Einfügungen und Löschungen in der Freispeicherliste erfolgen am einfachsten am selben Ende, so daß diese Liste also ein LIFO (stack) ist. Um diese Freispeicherverwaltung in das Programm Kundenliste zu integrieren, muß man folgende Änderungen vornehmen: Zunächst deklariert man einen Zeiger auf den Kopf der Freiliste:
VAR FREI: KUNDENZEIGER;
Anschließend werden die eigentlichen Prozeduren zur Verwaltung der Freispeicherliste definiert: (s. Operationen Löschen und Einfügen bei Kellerspeichern!)
PROCEDURE NEWKUNDE (VAR Z: KUNDENZEIGER);
(* Liefere Zeiger auf neuen Kundenrecord *)
BEGIN
IF FREI = NIL THEN
(* Freispeicherliste ist leer *)
NEW(Z)
ELSE
BEGIN (* Entferne erstes Element aus der Freiliste *)
Z:= FREI; FREI:= FREI^.NAECHSTER;
END;
END; (* NEWKUNDE *)
PROCEDURE DISPOSEKUNDE (Z: KUNDENZEIGER);
(* Speicherplatz von Z ist freigeworden. Z^ darf nicht *)
(* mehr verwendet werden! Erweitere die Freiliste *)
BEGIN
Z^.NAECHSTER:= FREI; FREI:= Z
END; (* DISPOSEKUNDE *)
Jetzt müssen die Routinen nur korrekt aufgerufen werden. Dazu ersetzt man den Aufruf NEW(NEU) in der Prozedur EINGABE durch NEWKUNDE(NEU). Um in der Prozedur LOESCHEN den Nachfolger von VOR zu löschen, merkt man sich zunächst in einer Variablen ALT den Zeiger auf das zu löschende Objekt. Dann kann man den Record wie gehabt aus der Verzeigerung der Kundenliste entfernen und zum Schluß mit DISPOSEKUNDE(ALT) den Record ALT^ in die Freispeicherliste einfügen.
PROCEDURE LOESCHEN;
VAR N : STRING;
VOR: KUNDENZEIGER; (* VORGAENGER IN DER LISTE *)
ALT: KUNDENZEIGER;
BEGIN
WRITE('NAME:'); READLN(N);
IF VORHANDEN(N,VOR) THEN
BEGIN
WRITELN('GELOESCHT WURDE:');
DRUCKE(VOR^.NAECHSTER);
ALT:= VOR^.NAECHSTER;
VOR^.NAECHSTER:= ALT^.NAECHSTER;
DISPOSEKUNDE(ALT);
END
ELSE
WRITELN(N,' NICHT ALS KUNDE GESPEICHERT!');
END; (* LÖSCHEN *)
Natürlich muß die Freispeicherliste am Programmanfang korrekt initialisiert werden. Da sie zu diesem Zeitpunkt noch leer ist, erhält der Zeiger auf den Listenanfang den Wert NIL:
FREE:= NIL
Dieses Verfahren der Verwaltung von freigewordenem Speicher ist sehr effizient, so daß man meist die Verwendung systemspezifischer Speicherverwaltungsprozeduren (DISPOSE, MARK, RELEASE) vermeiden kann. Die Prozeduren MARK und RELEASE in Pascal 2.0 sind in der Dokumentation in Kapitel 4.4.4.4 beschrieben.