LISTENVERARBEITUNG MIT TURBO PASCAL 4.0                (c) 08/09 1988 e.huber
---------------------------------------                ----------------------
TGM_96: LISTEN.TXT, TGM_97: LISTEN.ARC
Ernst Huber, N86d, #687

1) Einfhrung:
--------------
Innerhalb vieler Programme fallen wrend der Laufzeit Daten an, deren Menge
von Parametern abhngt, die vom Benutzer oft willkrlich festgelegt werden
knnen/drfen. Folglich ist die Menge der Daten (ich mchte im weiteren von
Datenstzen oder Records sprechen) hochgradig variabel.
Viele unerfahrene Programmierer verwenden zur Speicherung solcher Datenmengen
teils aus Unwissenheit, teils aus Bequemlichkeit, teils weil sie es aus einer
anderen Programmiersprache (BASIC) gewhnt sind, Arrays.
Einziger Vorteil dieser Methode ist, da man auf jeden beliebigen Datensatz
(Record) unter Angabe einer Nummer komfortabel und schnell zugreifen kann.
Damit wren wir aber schon bei den Nachteilen.

 a) Die Anzahl der Records, die wrend der Laufzeit des Programmes anfallen,
    mu dem Programmierer von vornherein bekannt sein, oder er dimensioniert
    das Datenarray so gro, da die fr jeden gltigen Eingabefall auftretende
    Datenmenge in das Array pat (Worst-case Dimensionierung). Damit wird aber
    wiederum Speicherplatz belegt, der vielleicht gar nie bentigt und
    anderweitig dringender gebraucht wird (z.B. zustzliche Variable/
    Arrays im Datensegment - siehe Punkt b).

 b) Das Datensegment eines Programmes kann max. 64 kB (65535 Bytes) gro sein.
    Innerhalb dieses Datensegmentes werden in Turbo Pascal jedoch smtliche
    vom Programm benutzten Variablen abgelegt, also auch unser Datenarray.
    Oder anders ausgedrckt: das Array kann theoretisch nur maximal 64 kB
    gro sein. Dies bedeutet, da die Anzahl der Arrayelemente (Records)
    von vornherein beschrnkt ist.

Zur besseren Veranschaulichung mchte ich nun mit einem Beispiel beginnen,
fr da ich im weiteren mehrere Lsungsanstze bringen werde.

Beispiel: Erstellen eines Programmes zur Verwaltung einer Ersatzteilliste;

Aufgabenstellung: Mittels Turbo Pascal 4.0 soll ein (fr uns imaginres)
   Programm geschrieben werden, anhand dessen es mglich ist, eine
   Ersatzteilliste bequem und rasch zu verwalten (komfortables Arbeiten,
   schneller Zugriff auf die einzelne Datenstze). Die Ersatzteilliste (oder
   zumindest immer ein groer Teil davon) soll daher aus
   Geschwindigkeitsgrnden whrend des Programmablaufes im Speicher gehalten
   werden.
   Zu jedem Ersatzteil gibt es charakterische Daten zu speichern (Bezeich-
   nung, Artikelnummer, Anzahl, Preis);

Unser Problem ist jetzt der Aufbau einer geeigneten Datenstruktur und die
dazugehrigen Speicherverwaltung.

Beginnen wir mit der programmiertechnisch naivsten Methode:

  PROGRAM Verwalte1;
  { Zu jedem der oben genannten charakteristischen Daten wird ein Array
    definiert, jedem Ersatzteil eine Nummer zugeordnet. Weiters wird ein
    Zugriff auf einen Ersatzteil-Datensatz demonstriert, der die spezifischen
    Daten zur Anzeige bringt (Voraussetzung ist, da ein Heinzelmnnchen
    bereits alle erforderlichen Datenstze eingegeben hat). }

  USES CRT;

  CONST MaxDaten = 500;            { Max. 500 Datenstze pro Ersatzteilliste }

  VAR Bezeichnung: ARRAY [1..MaxDaten] OF STRING[100];{ 500*100= 50000 Bytes }
      Artikelnr  : ARRAY [1..MaxDaten] OF LONGINT;    { 500*4  =  2000 Bytes }
      Anzahl     : ARRAY [1..MaxDaten] OF WORD;       { 500*2  =  1000 Bytes }
      Preis      : ARRAY [1..MaxDaten] OF WORD;       { 500*2  =  1000 Bytes }
      cnt        : WORD;                              {              2 Bytes }
                                                      { Gesamt:  54002 Bytes }
  { Theoretisch knnen also max. 65531 DIV 108 = 606 Ersatzteile/Liste erfat
    werden }

  BEGIN
    ...
    < S O U R C E >
    ...
    WriteLn ('Zugriff auf den Ersatzteil-Datensatz mit Nr.: ',cnt);
    WriteLn ('Ersatzteil   : ', Bezeichnung [cnt]);
    WriteLn ('Artikelnummer: ', Artikelnr [cnt]);
    WriteLn ('Anzahl       : ', Anzahl [cnt]);
    WriteLn ('Preis        : ', Preis [cnt]);
    ...
    < S O U R C E >
    ...
  END. (* PROGRAM Verwalte1 *)

Bedenkt man, da in einem ansprechenden Programm sicherlich noch weitere
Variable und kleine Arrays hinzukommen werden, so wird es im Datensegment
recht eng zugehen (auerdem sind 500 Datenstze wirklich nicht
viel - hchstens zum Tippen).

Eine etwas elegantere Lsung bietet folgendes Beispiel (jedoch keine
Verbesserung im Bezug auf den Platzbedarf im Datensegment):

  PROGRAM Verwalte2;
  { Fr jeden Ersatzteil wird nun ein RECORD definiert, dies bringt zwar keine
    Platzersparnis, ist jedoch bei weitem bersichtlicher. Weiters wird ein
    Zugriff auf einen Datensatz gezeigt. }

  USES CRT;

  CONST MaxDaten = 500;  { Max. 500 Datenstze pro Ersatzteilliste }

  TYPE Ersatzteil = RECORD   { Definition unseres Ersatzteilrecords}
         Bezeichnung: STRING[100];                     {100  Bytes }
         Artikelnr  : LONGINT;                         {  4  Bytes }
         Anzahl     : WORD;                            {  2  Bytes }
         Preis      : WORD;                            {  2  Bytes }
       END; (* RECORD Ersatzteil *)           { Gesamt: 108  Bytes/RECORD }

  VAR ErsatzListe: ARRAY [1..MaxDaten] OF Ersatzteil; { 500*108= 54000 Bytes }
      cnt        : WORD;                              {              2 Bytes }
                                                      { Gesamt:  54002 Bytes }
  { Theoretisch knnen also max. 65531 DIV 108 = 606 Ersatzteile/Liste erfat
    werden  }

  BEGIN
    ...
    < S O U R C E >
    ...
    WITH ErsatzListe [cnt] DO BEGIN
         WriteLn ('Zugriff auf den Ersatzteil-Datensatz mit Nr: ',cnt);
         WriteLn ('Ersatzteil     : ', Bezeichnung);
         WriteLn ('Artikelnummer  : ', Artikelnr);
         WriteLn ('Anzahl         : ', Anzahl);
         WriteLn ('Preis          : ', Preis);
    END; (* WITH ErsatzListe [cnt] *)
    ...
    < S O U R C E >
    ...
  END. (* PROGRAM Verwalte2 *)

Die meisten PC XT/AT/... sind aber heute bereits mit mindestens 640 kB
Hauptspeicher ausgestattet (welche unter MS-DOS/PC-DOS maximal ohne Tricks
verwaltet werden knnen). Unter Bercksichtigung von DOS, eventuell residenter
Utilities sowie unseres laufenden Verwaltungsprogrammes bleiben also immer
noch 400 kB (und mehr) an freiem Hauptspeicher ber, der nur darauf wartet,
mit unseren Datenbits und -bytes gefllt zu werden.
Ideal wre also eine Mglichkeit, diesen freien Speicherplatz whrend des
Programmablaufes belegen und wieder freigeben zu knnen. Diese existiert
tatschlich (viele haben sich's doch bereits gedacht -- es ist wie bei einer
dieser Hollywood-Komdien mit Happy End -- oder!??), man spricht dann von
einer dynamischen Speicherverwaltung. Der freie Speicherbereich wird Heap
(dt. Haufen, Menge) genannt. Diese dynamische Speicherverwaltung stellt
Turbo Pascal in hervorragendem Mae zur Verfgung, und mit der wollen wir uns
nun nher befassen.

2) Dynamische Speicherverwaltung:
---------------------------------
Im letzten Kapitel haben wir den Begriff 'Heap' kennengelernt, schauen wir
uns nun anhand einer Skizze nher an, was es damit auf sich hat.

Skizze des Speicherschemas fr ein compiliertes Turbo Pascal 4.0 Programm
(stark vereinfacht)

hchste
Adresse     Ŀ
                                               
                  freier Speicherbereich       
                                               
                        H E A P                
                                               
            Ĵ< HeapOrg (POINTER)
             D A T E N S E G M E N T           
             (globale Variablendefinitionen)   
                             Ĵ<Ŀ
             typisierte Konstanten                  
            Ĵ  Inhalt
             C O D E S E G M E N T               der
             der einzelnen UNITS und des         EXE Datei
             Hauptprogrammes                        
niedrigste  <
Adresse

Am Heap knnen nun einzelne Bytes oder zusammenhngende Speicherbereiche
mittels der unten angefhrten Prozeduren reserviert werden. Innerhalb eines
reservierten Speicherbereiches knnen nun Daten abgelegt werden, man
mu dazu nur seine Startadresse kennen (und eventuell die Gre, mehr dazu
spter). Diese Startadresse wird in einer Variablen gespeichert, man spricht
hier von einer Zeigervariablen oder englisch POINTER.

Turbo Pascal kennt nun zwei Mglichkeiten der dynamischen Speicherverwaltung:
(auf eine dritte mit MARK/RELEASE mchte ich hier nicht nher eingehen, der
interessierte Leser sei auf das Turbo Pascal 4.0 Referenzhandbuch verwiesen).
 a) Speicheranforderung mit: NEW (p: POINTER);
    Speicherfreigabe mit   : DISPOSE (p: POINTER);
 b) Speicheranforderung mit: GetMem (p: POINTER; Size: WORD);
    Speicherfreigabe mit   : FreeMem (p: POINTER; Size: WORD);

(Die Gre einer dynamischen Variablen ist wiederum auf 64 kB beschrnkt, dies
 stellt jedoch im weiteren kein wirkliches Problem dar.)

Die erste Art a) der dynamischen Speicherverwaltung wird verwendet, wenn die
Gre des zu reservierenden Bereiches im Heap von vornherein festeht, hingegen
kann bei b) die Gre des zu reservierenden Speicherbereiches whrend der
Laufzeit festgelegt werden (also selbst wieder variabel sein).

Folgende Prozeduren/Funktionen und Variablen zur dynamischen
Speicherverwaltung werden von Turbo Pascal 4.0 aus vordefiniert.

a) Proceduren/Funktionen:
Dispose  gibt den Speicherplatz einer dynamischen Variablen frei;
         Dekl: Dispose (VAR p: POINTER);
FreeMem  gibt einen dynamisch belegten Speicher bestimmter Gre frei;
         Dekl: FreeMem (VAR p: POINTER; size: WORD);
GetMem   belegt Speicher bestimmter Gre fr eine dynamische Variable, setzt
         einen Zeiger auf den Anfang dieses Bereiches;
         Dekl: GetMem (VAR p: POINTER; size: WORD);
Mark     hlt den Zustand des Heaps in einer Zeigervariablen fest;
         Dekl: Mark (VAR p: POINTER);
MaxAvail liefert die Gre des grten freien Heap-Bereiches, ermittelt,
         wieviele Bytes momentan max. fr eine dyn. Var. belegt werden knnen;
         Dekl: MaxAvail;  Erg: LONGINT;
MemAvail liefert die Gesamtzahl der freien Bytes auf dem Heap;
         Dekl: MemAvail;  Erg: LONGINT;
New      erzeugt eine dynamische Variable, setzt Zeiger auf den Anfang des
         durch diese Variable belegten Bereiches;
         Dekl: New (VAR p: POINTER);
Release  setzt den Heap auf den mit MARK festgehaltenen Zustand zurck;
         Dekl: Release (VAR p: POINTER);

b) Variable (hier mchte ich nur die meiner Ansicht nach wichtigsten
   anfhren):
HeapOrg: POINTER   Zeiger auf die Startadresse des Heapbereiches;
HeapPtr: POINTER   Zeiger auf die Endadresse des belegten Heapbereiches;
FreePtr: POINTER   Zeiger auf die Endadresse des noch freien Heapbereiches;

Anmerkung: mittels RELEASE (HeapOrg) kann jederzeit der gesamte Heapbereich
           freigegeben werden, jedoch Vorsicht im Zusammenhang mit der UNIT
           GRAPH, hier kann es zu so manchen Problemen kommen;

An dieser Stelle mchte ich eine weitere Lsung zu dem oben angegeben Beispiel
bringen. Der folgende Programmansatz stellt bereits eine recht gute Lsung des
obigen Problems dar, kann aber noch verbessert werden (die einzelnen
Datenstze werden zwar dynamisch gespeichert, jedoch mu noch immer die max.
Anzahl der Ersatzteile/Liste vom Programmierer festgelegt werden).

  PROGRAM Verwalte3;
  { Fr jeden Ersatzteil wird nun ein RECORD definiert, weiters wird ein
    ARRAY OF POINTER TO ERSATZTEIL definiert, das heit jedes Arrayelement
    zeigt auf einen Speicherbereich im Heap, in dem ein Datensatz gespeichert
    wird. Gezeigt wird nun sowohl die Belegung vom Heap, das Ein- und Auslesen
    eines Datensatzes sowie ein anschlieendes Freigeben des belegten
    Speicherplatzes fr einen Datensatz. }

  USES CRT;

  CONST MaxDaten = 500;  { Max. 500 Datenstze pro Ersatzteilliste }

  TYPE Ersatzteil = RECORD
         Bezeichnung: STRING[100];                     {100  Bytes }
         Artikelnr  : LONGINT;                         {  4  Bytes }
         Anzahl     : WORD;                            {  2  Bytes }
         Preis      : WORD;                            {  2  Bytes }
       END; (* RECORD Ersatzteil *)           { Gesamt: 108  Bytes/RECORD }

  VAR ErsatzListe: ARRAY [1..MaxDaten] OF ^Ersatzteil; { 500*4 = 2000 Bytes }
      cnt        : WORD;                               {            2 Bytes }
      Ende       : CHAR;                               {            1 Byte  }
                                         { Datensegment: Gesamt: 2003 Bytes }
                                         { Heapbereich : Gesamt:54000 Bytes }
  { Max. knnen also 65531 DIV 4 = 16382 Ersatzteile/Liste erfat werden; dazu
    mte man jedoch einen freien Heapbereich von 16382*108 = 1.769.337 Bytes
    haben, (keine Sorge, DOS schafft sowieso nur 640 kB) - und unser heiliges
    Datensegment wre wieder voll. }

  BEGIN
    ...
    < S O U R C E >
    ...
    REPEAT
      INC (cnt);
      NEW (ErsatzListe[cnt]);           (* Belegt einen 108 Byte groen     *)
      WITH ErsatzListe[cnt]^ DO BEGIN   (* Bereich und speichert die St.adr *)
           WriteLn ('Einlesen eines Ersatzteil Datensatz mit Nr: ',cnt);
           Write ('Ersatzteil     : '); ReadLn (Bezeichnung);
           Write ('Artikelnummer  : '); ReadLn (Artikelnr);
           Write ('Anzahl         : '); ReadLn (Anzahl);
           Write ('Preis          : '); ReadLn (Preis);
      END; (* WITH ErsatzListe [cnt] *)
      WriteLn; WriteLn ('Weiter n/Taste : '); Ende:=ReadKey;
      Ende:=UpCase(Ende);
    UNTIL ((cnt >= MaxDaten) OR (Ende = 'N'));
    ...
    < S O U R C E >
    ...
    REPEAT
      INC (cnt);
      WITH ErsatzListe[cnt]^ DO BEGIN
           WriteLn ('Zugriffs auf den Ersatzteil Datensatz mit Nr: ',cnt)
           WriteLn ('Ersatzteil     : ', Bezeichnung);
           WriteLn ('Artikelnummer  : ', Artikelnr);
           WriteLn ('Anzahl         : ', Anzahl);
           WriteLn ('Preis          : ', Preis);
      END; (* WITH ErsatzListe [cnt]^ *)
      WriteLn ('Weiter n/Taste : '); Ende:=ReadKey;
      Ende:=UpCase(Ende);
      DISPOSE (ErsatzListe[cnt]);
    UNTIL ((cnt >= MaxDaten) OR (Ende = 'N'));
    ...
    < S O U R C E >
    ...
  END. (* PROGRAM Verwalte3 *)

3) Listen und andere dynamische Datenstrukturen:
------------------------------------------------
Mit dem vorhergehenden Programmansatz (bzw. mit der erstellten Datenstruktur)
ist es gelungen, den Platzbedarf im Datensegment zur Speicherung von 500
Elementen erheblich zu reduzieren. Im Datensegment wird nur noch ein POINTER-
ARRAY gespeichert (500*4 = 2000 Bytes), die eigentlichen Daten (Records)
werden im Heap abgelegt, der hierfr gengend freien Speicherplatz
bereitstellt. Optimal wre es nun, wenn es gelnge, selbst dieses
ARRAY bzw. die Information, die dieses beinhaltet, ebenfalls im Heap
unterzubringen.

Eine Idee, mit der wir uns jetzt nher befassen werden (und die uns
schlielich zum Ziel fhren wird) ist die folgende:

Im letzten Beispiel haben wir ein Array bestehend aus Pointern auf eine
Datenstruktur definiert, das heit jeweils ein Pointer zeigt auf einen
Datensatz, der im Heap gespeichert wird. Was passiert nun, wenn man in jedem
Record (der ja selbst aus Variablen besteht) eine Pointervariable unterbringt,
die auf den jeweils nchsten Record zeigt.

Dazu folgenden Skizze:

  H E A P Ŀ
  Ŀ     Ŀ     Ŀ                   Ŀ 
  DatenPtr>DatenPtr>DatenPtr> ....... >DatenNIL 
                                
                                                                           
 ĳ D A T E N S E G M E N T Ĵ
  Ŀ                                                                     
  Ptr                                                                     
                                                                       
 

Die einzige Information, die man sich nun im Hauptprogramm mit Hilfe einer
Variablen (und damit im Datensegment) merken mu, ist ein Pointer auf das
erste Element dieser Recordfolge. Datenstrukturen dieser Art heien in der
Fachsprache Listen, anstatt von Elementen (Datenstze, Records) spricht man
auch von Knoten (engl. Nodes).

3.1) Die einfach verkettete Liste:
----------------------------------
Eine einfach verkettete Liste besteht aus einer Folge von Knoten. Jeder Knoten
beinhaltet einen Pointer auf seinen Nachfolger in der Liste. Am Ende der Liste
hat dieser Pointer den Wert NIL (Not-In-List).
Die Datenstruktur, die wir uns vorher erarbeitet haben, ist also eine einfach
verkettete Liste.

Graphische Darstellung einer einfach verketteten Liste:

Ŀ     Ŀ     Ŀ                   Ŀ
Ptr>DatenPtr>DatenPtr> ....... >DatenNIL
                             
zeigt auf den Listenanfang


Das Programmbeispiel sieht dann folgendermaen aus:

  PROGRAM Verwalte4;
  { Fr jeden Ersatzteil wird wiederum ein Record definiert, der sowohl die
    blichen Daten als auch einen Zeiger auf das nchste Listenelement
    enthlt; gezeigt wird nun sowohl die Belegung vom Heap, das Ein- und
    Auslesen eines Datensatzes sowie ein anschlieendes Freigeben des belegten
    Speicherplatzes fr einen Datensatz. }


  USES CRT;

  TYPE Liste = POINTER ^Ersatzteil;
       Ersatzteil = RECORD
         Bezeichnung: STRING[100];                     {100  Bytes }
         Artikelnr  : LONGINT;                         {  4  Bytes }
         Anzahl     : WORD;                            {  2  Bytes }
         Preis      : WORD;                            {  2  Bytes }
         Nachfolger : Liste;                           {  4  Bytes }
       END; (* RECORD Ersatzteil *)           { Gesamt: 112  Bytes/RECORD }

  VAR z1, z2, ListenAnfang: Liste;             (* z1, z2 = Hilfsvariable *)
      cnt                 : WORD;
      Ende                : CHAR;

  { Maximal knnen HeapSize DIV 112 = ??? Ersatzteile/Liste erfat werden }

  BEGIN
    ...
    < S O U R C E >
    ...
    RELEASE (HeapOrg);        (* lschen des gesamten Heap                  *)
    NEW (ListeAnfang);        (* Platz bel. fr den 1. Knoten in der Liste  *)
    z1:=ListenAnfang; cnt:=0; (* Adr. des reservierten Bereichs in Hilfsvar.*)
    REPEAT
      INC (cnt);
      WriteLn ('Einlesen des Ersatzteil Datensatz mit Nr: ',cnt);
      Write ('Ersatzteil     : '); ReadLn (z1^.Bezeichnung);
      Write ('Artikelnummer  : '); ReadLn (z1^.Artikelnr);
      Write ('Anzahl         : '); ReadLn (z1^.Anzahl);
      Write ('Preis          : '); ReadLn (z1^.Preis);
      WriteLn; WriteLn ('Weiter n/Taste : '); Ende:=ReadKey;
      Ende:=UpCase(Ende);
      IF (Ende <> 'N') THEN BEGIN   (* Wenn eine weitere Eingabe erwnscht, *)
         NEW (z2);                  (* dann ber z2 Platz fr den nchsten  *)
         z1^.Nachfolger:=z2;        (* Record belegen und dessen Startadr.  *)
         z1:=z2;                    (* als Nachfolger berweisen; nachher   *)
      END;                          (* wird der neue Record als aktueller   *)
                                    (* Datensatz gesetzt                    *)
    UNTIL ((cnt >= MaxDaten) OR (Ende = 'N'));
    z1^.Nachfolger:=NIL;   (* letzter Nachfolger in der Liste mu NIL sein *)
    ...
    < S O U R C E >
    ...
    cnt:=0;
    REPEAT
      z1:=ListenAnfang;                 (* Startadresse des 1.Records Laden *)
      INC (cnt);
      WriteLn ('Zugriff auf den Ersatzteil Datensatz mit Nr: ',cnt)
      WriteLn ('Ersatzteil     : ', z1^.Bezeichnung);
      WriteLn ('Artikelnummer  : ', z1^.Artikelnr);
      WriteLn ('Anzahl         : ', z1^.Anzahl);
      WriteLn ('Preis          : ', z1^.Preis);
      WriteLn ('Weiter n/Taste : '); Ende:=ReadKey;
      Ende:=UpCase(Ende);
      IF (Ende <> 'N') THEN BEGIN       (* wenn kein Ende erwnscht, dann   *)
          ListenAnfang:=z1^.Nachfolger; (* neuer Listenanf.= nchster Knoten*)
          DISPOSE (z1);                 (* lschen des alten Knotens        *)
      END;
    UNTIL ((ListenAnfang = NIL) OR (Ende = 'N')); (* bis Listenende od. Ende*)
    ...
    < S O U R C E >
    ...
  END. (* PROGRAM Verwalte4 *)

Ein Nachteil dieser Speichermethode ist, da man, um z.B. im Extremfall an
das letzte Listenelement heranzukommen, die gesamte vorhergehende
Liste durchlaufen mu.
Die Vorteile wren: keine Festlegung der max. Anzahl von Listenelementen durch
                    den Programmierer und
                    das Datensegment eines Programmes bleibt (fast) unbelegt.

3.2) Die doppelt verkettete Liste:
----------------------------------
Eine doppelt verkettete Liste besteht aus Knoten, die jeweils einen Zeiger
auf den Vorgnger in der Liste als auch einen Zeiger auf den Nachfolger in
der Liste beinhalten. Der Vorgnger des ersten Knotens sowie der Nachfolger
des letzten Knotens hat jeweils den Wert NIL.

Graphische Darstellung einer doppelt verkettete Liste:

Ŀ    > > ... Ŀ    Ŀ
Ptr>NILDatenPtr     PtrDatenPtr         PtrDatenNIL<ĴPtr
     < ... <    
zeigt auf den Listenanfang                           zeigt auf das Listenende

Vorteil: Man kann sowohl vom Listenanfang, als auch vom Listenende aus linear
         zu suchen beginnen (bzw. von jedem Knoten innerhalb der Liste).
Nachteil: Hherer Platzbedarf (ein Pointer/Node mehr gegenber einer einfach
          verketten Liste (bei 5000 Nodes sind dies immerhin ca. 20 kB).
          Dies wirkt sich vor allem bei Listen mit kleinen Datenfeldern pro
          Knoten stark aus (z.B. LONGINT Listen).

3.3) Die zyklische Liste:
-------------------------
Der Unterschied zu den beiden vorigen Listenarten besteht hierin, da der
Zeiger des letzten Knotens nicht gleich NIL ist, sondern auf das erste
Listenelement zeigt (bzw. auch der Zeiger auf den Vorgnger bei doppelt
verketteten zyklischen Listen auf das letzte Listenelement zeigt).
Fr solche Listen ist auch die Bezeichnung Datenring gebruchlich.

Graphische Darstellung einer einfach verketteten zyklischen Liste:

Einsprungsadresse
> Ŀ    Ŀ                 Ŀ
Ptr     DatenPtr>DatenPtr> ....... >DatenPtrĿ
 >                        
                                                                 
      

3.4) Der binre Baum:
---------------------
Ein Baum besteht im Unterschied zu einer Liste aus Knoten, die jeweils mehr
als einen Nachfolger haben knnen. Beim binren Baum besitzt jeder Knoten
zwei Nachfolger, das heit er enthlt zwei Zeiger. Am Ende des Baumes haben
diese Zeiger den Wert NIL.

4) Die UNIT List_Man(anger):
----------------------------
In diesem Kapitel mchte ich eine selbstgeschriebene UNIT vorstellen, mit
der es mglich ist, die Verwaltung von mehreren Listen gleichzeitig auf recht
einfache Weise zu gestalten. Dabei wurden fr manche Prozeduren bewut Namen
verwendet, wie sie bei rein listenverarbeitenden Programmiersprachen
vorkommen (z.B. aus LOGO - das meiner Meinung nach zu Unrecht den Ruf einer
Kinderprogrammiersprache geniet).

Grundstzlich knnen mittels der UNIT List_Man (doppelt verkettete) Listen
mit beliebigen Datenstrukturen fr einen Knoten angelegt werden. Einzige
Bedingung ist nur, da eine Variable vom Knotentyp im Hauptprogramm bzw.
in der aufrufenden Routine erzeugt wird (mehrer Knotentypen/Liste sind im
Normalfall unzulssig, mit einigen Tricks kann auch diese Schranke umgangen
werden). ber diese Variable findet dann jegliche Kommunikation zwischen dem
Hauptprogramm bzw. der aufrufenden Routine und der Listenverarbeitung statt,
das heit Daten werden ber diese Variable in die Liste bergeben und
abgeholt.
Weiters  m u    u n b e d i n g t   V O R  dem Anlegen einer Liste die Gre
eines Listenknotens bestimmt und das Ergebnis ber die vordefinierte Variable
'ObjectSize' der UNIT List_Man mitgeteilt werden.
Es empfiehlt sich die UNIT nach den Systemunits (CRT, DOS, PRINTER, GRAPH)
und vor den selbstgeschriebenen Units ber USES in das Programm aufzunehmen.

4.1) Vordefinierte (ffentliche) Variable der UNIT List_Man:
------------------------------------------------------------
VAR CurrentNo, LastNo, FirstNo, ObjectSize, IORes: WORD;
    NotExist                                     : BOOLEAN;
    SysPtr                                       : POINTER;
    Current                                      : List;
    ActiveListNo, TopOfList                      : BYTE;

CurrentNo: WORD;    Nummer des gerade aktuellen Listenelementes;
FirstNo: WORD;      Nummer des ersten Listenelementes (Nummerierung beginnt
                    mit 1);
LastNo: WORD;       Nummer des letzten Listenelementes;
IORes: WORD;        Fehlerstatus der letzten IO-Operation bei Diskzugriffen
                    (SaveList, LoadList, KillDisk);
ObjectSize: WORD;   In dieser Variablen erwartet sich die UNIT die Gre eines
                    Knotens in Byte, aus dem die Liste zusammengesetzt werden
                    soll. Eine Bestimmung der Knotengre ist immer vor der
                    Verwendung des ML Befehls notwendig (also auch vor
                    LoadList);
NotExist: BOOLEAN;  Diese Variable wird auf TRUE gesetzt, wenn eine aufgerufene
                    Liste nicht aktiviert werden kann (SetActiveList nicht
                    erfolgreich) bzw. keine Liste aktiviert ist.
SysPtr: POINTER;    In diesem Zeiger wird der Zustand des Heap vor der
                    Verwendung der UNIT List_Man (automatisch) festgehalten.
Current: List;      Zeiger auf den gerade aktuellen Knoten;
ActiveListNo: BYTE; Beinhaltet die Nummer der gerade aktiven Liste;
TopOfList: BYTE;    Gibt die Nummer der letzten Liste im Liststack an.

4.2) Vordefinierte (ffentliche) Prozeduren und Funktionen der UNIT List_Man:
-----------------------------------------------------------------------------
PROCEDURE SetFirstNode;                (* Setzt erstes Listenel als akt.El. *)
PROCEDURE SetLastNode;                 (* Setzt letztes Listenel als akt.El.*)
FUNCTION Next: List;                   (* lft Pointer auf das naechste El.  *)
FUNCTION Prev: List;                   (* lft Pointer auf das vorige El     *)
FUNCTION ListSize: LONGINT;            (* lft Listengroesze in Bytes        *)
FUNCTION DataSize: LONGINT;            (* lft Bytes gebraucht fuer Daten    *)
FUNCTION ListName: STR08;              (* lft Listennamen                   *)
PROCEDURE SetActiveList (Name: STR08); (* Setzt ein Liste auf aktiv         *)
PROCEDURE ML (VAR Data; Name: STR08);  (* Legt eine Liste an                *)
PROCEDURE KillMem;                     (* Loescht komplette Liste           *)
PROCEDURE LPut (VAR Data);             (* fuegt ein El. a.d. Listenende     *)
PROCEDURE FPut (VAR Data);             (* fuegt ein El. a.d. Listenanf.     *)
PROCEDURE InsCur (VAR Data);           (* Efg eines El nach akt. Position   *)
PROCEDURE DelCur;                      (* loescht El. an akt. Position      *)
PROCEDURE GetNext (VAR Data);          (* gibt das naechst El. zurueck      *)
PROCEDURE GetPrev (VAR Data);          (* gibt das vorherg. El. zurueck     *)
PROCEDURE GetData (VAR Data);          (* gibt das akt El. zurueck          *)
PROCEDURE PutData (VAR Data);          (* berschreibt den akt. Datensatz   *)
PROCEDURE SeekNo (No: WORD);           (* Sucht das Listenel. mit No        *)
PROCEDURE SaveList (VAR Buf; FileName: STR12); (* Speichern auf akt. Disk   *)
PROCEDURE LoadList (VAR Buf; FileName: STR12; ListName: STR08); (* Laden    *)
PROCEDURE KillDisk (FileName: STR12);  (* Loescht bel. File von akt. Lw     *)

Hinweise:
Smtliche Routinen werden nur ausgefhrt, wenn die Variable NotExist=FALSE ist!
Die Liste der Variablen, die von der jeweiligen Routine verwendet werden, ist im
Listing angefhrt!

PROCEDURE SetFirstNode;
Setzt Current als Zeiger auf das erste Listenelement, CurrentNo = FirstNo;

PROCEDURE SetLastNode;
Setzt Current als Zeiger auf das letzte Listenelement, CurrentNo = LastNo;

FUNCTION Next: List;
Gibt den Zeiger auf das nchste Listenelement (vom aktuellen Knoten aus
gesehen) zurck.
Hinweis: CurrentNo wird nicht neu gesetzt. Soll eine Liste mit diesem Befehl
         durchlaufen werden, so mu sich der Programmierer selbst um ein
         Updaten der Variable kmmern;

FUNCTION Prev: List;
Gibt den Zeiger auf das vorhergehende Listenelement (vom aktuellen Knoten aus
gesehen) zurck.
Hinweis: CurrentNo wird nicht neu gesetzt. Soll eine Liste mit diesem Befehl
         durchlaufen werden, so mu sich der Programmierer selbst um ein
         Updaten der Variable kmmern;

FUNCTION ListSize: LONGINT;
Liefert die Anzahl Bytes als Ergebnis, die zur Speicherung der gerade
aktuellen Liste gebraucht werden.

FUNCTION DataSize: LONGINT;
Liefert die Anzahl Bytes als Ergebnis, die effektiv zur Speicherung der
Benutzerdaten gebraucht werden.

FUNCTION ListName: STR08;
Liefert den Listennamen der aktuellen Liste zurck.

PROCEDURE SetActiveList (Name: STR08);
Setzt die Liste mit dem Namen, der in der Variable Name bergeben wird, als
aktive Liste. Die Parameter (smtliche listenspezifische Variable) der vorher
aktuellen Liste werden am Liststack abgelegt sowie die der neuen aktuellen
Liste geladen.

PROCEDURE ML (VAR Data; Name: STR08);
Legt eine neue, einelementige Liste unter dem Namen, der in der Variable Name
angegeben wird, an und speichert die Parameter am Liststack (hier auf maximal
100 Listen gleichzeitig dimensioniert).

PROCEDURE KillMem;
Lscht die momentan gesetzte Liste auf dem Heap, smtliche Parameter werden
aus dem Liststack gelscht, die Variable TopOfList um 1 erniedrigt.
Hinweis: nach einem Aufruf von KillMem ist natrlich keine Liste aktiv.

PROCEDURE LPut (VAR Data);
Fgt die Variable, die mit Data bergeben wird, als Knoten an das Listenende
an (LastPut). LastNo wird inkrementiert.

PROCEDURE FPut (VAR Data);
Fgt die Variable, die mit Data bergeben wird, als Knoten an den Listenanfang
an (FirstPut). LastNo und CurrentNo werden inkrementiert.

PROCEDURE InsCur (VAR Data);
Fgt die Variable, die mit Data bergeben wird, als Knoten an der gerade
aktuellen Stelle ein, LastNo wird inkrementiert.
Hinweis: Diese Procedure arbeitet nicht, wenn der gerade aktive Knoten das
         erste oder letzte Element in der Liste ist.

PROCEDURE DelCur;
Lscht das Element, auf das Current gerade zeigt (=das aktuelle Element),
aus der aktiven Liste. handelt es sich um eine einelementige Liste (LastNo=1),
so wird automatisch ein KillMem ausgefhrt.

PROCEDURE GetNext (VAR Data);
Liefert ber die Variable Data den Datenteil des nchsten Listenelementes,
Current und CurrentNo werden neu gesetzt.
Hinweis: wird eine Liste linear mit GetNext durchlaufen, so ist darauf zu
         achten, da GetNext nicht auf das letzte Listenelement angewandt wird.

PROCEDURE GetPrev (VAR Data);
Liefert ber die Variable Data den Datenteil des vorhergehenden
Listenelementes, Current und CurrentNo werden neu gesetzt.
Hinweis: wird eine Liste linear mit GetPrev durchlaufen, so ist darauf zu
         achten, da GetPrev nicht auf das erste Listenelement angewandt wird.

PROCEDURE GetData (VAR Data);
Gibt ber Data den Datenteil des gerade aktuellen Knotens zurck.

PROCEDURE PutData (VAR Data);
berschreibt den Datenteil des gerade aktuellen Knotens mit dem Inhalt von
Data.

PROCEDURE SeekNo (No: WORD);
Sucht auf dem krzesten Weg linear nach dem Listenelement mit der Nummer No,
setzt Current und CurrentNo neu.

PROCEDURE SaveList (VAR Buf; FileName: STR12);
Speichert die gerade aktive Liste unter dem mit FileName angegebenen Namen
auf dem gerade gesetzten Laufwerk. Die Speicherung erfolgt blockweise, ein
Block entspricht einem Listenknoten. Die Statusvariable IORes wird gesetzt.

PROCEDURE LoadList (VAR Buf; FileName: STR12; ListName: STR08);
Ladet das File mit dem in der Variablen FileName angegebenen Namen als Liste
mit dem in ListName angegebenen Namen. Existiert im Liststack eine Liste
gleichen Namens, so wird keine Liste geladen. Die Statusvariable IORes wird
gesetzt.
Hinweis: Vor der Verwendung von LoadList mu unbedingt ObjectSize
         initialisiert werden.

PROCEDURE KillDisk (FileName: STR12);
Lscht das File mit dem in der Variable FileName angegebenen Namen vom gerade
aktuellen Laufwerk. Die Statusvariable IORes wird gesetzt.

4.3) Interne Datails der UNIT List_Man:
---------------------------------------
4.3.1) Interne Variablendefinitionen:
-------------------------------------
CONST MaxList = 101;
TYPE STR08 = STRING [8];

     ListenName = RECORD
       LName: STR08;                   (* Speicherung des Listennamens *)
       FPtr, LPtr, Cur      : List;    (* Speicherung der Listenpointer*)
       FNo, LNo, CurNo, ObjS: WORD;    (* weitere Listendaten          *)
     END; (* RECORD ListenName *)

VAR FirstPtr, LastPtr: List;
    ListField        : ARRAY [0..MaxList] OF ListenName;

FirstPtr: List; zeigt auf den ersten Knoten der aktiven Liste.
LastPtr: List;  zeigt auf den letzten Knoten der aktiven Liste.
ListField: ARRAY [0..MaxList] OF ListenName;
           Stellt den Liststack dar, d.h. in diesem Array, bestehend aus
           einzelnen Records (ListenName), werden smtliche Informationen der
           sich gerade im Heap befindlichen Listen gespeichert.

Die Konstante MaxList:
Mit MaxList wird die Anzahl der Listen festgelegt, die sich maximal
gleichzeitig im Heap befinden drfen (bei MaxList = 101 -> 100 Listen).

4.3.2) Speicherung eines Knotens:
---------------------------------
Um beliebige Datenstrukturen innerhalb eines Knotens zu ermglichen, wurde
folgender Lsungsweg gegangen:
Ein Knoten besteht aus drei Pointern

TYPE List = ^ListElement;
     ListElement = RECORD
       Next, Prev: List;
       DataPtr   : POINTER;
     END; (* RECORD ListElement *)

Next, Prev sind Pointer auf den jeweils nchsten bzw. vorhergenden Knoten in
der Liste.
DataPtr ist ein Zeiger auf den eigentlichen Datensatz, d.h. die Speicherung der
Benutzerdaten erfolgt nicht innerhalb eines Listenknotens, sondern extern im
Heap. Innerhalb eines Knotens wird demnach nur ein Zeiger auf den zugehrigen
im Heap gespeicherten Datensatz erzeugt.
Die Reservierung des Speicherplatzes fr einen Benutzerdatensatz mu aus
Grnden der Flexibilitt der UNIT via GetMem erfolgen (bei NEW mu die
Datensatzgre fr alle Zeiten von vornherein feststehen, jeder Benutzer
mchte jedoch andere Daten in einer Liste speichern (Textdatei,
Metabellen...)).
Daher mu ber die in Turbo Pascal vordefinierte Funktion SizeOf (oder
anderweitig) die Gre eines Records ermittelt und in der vordefinierten
Variable ObjectSize abgelegt werden (GetMem reserviert einen Speicherblock,
der Gre ObjectSize).
Die Startadresse des mittels GetMem belegten Speicherblocks wird dann in dem
aktuellen ListNode als Pointer (in DataPtr) gespeichert. So ist es mglich
auch ber eigene, (noch) nicht in der UNIT List_Man definierte Routinen auf
diesen Datenbereich zuzugreifen.
Die Speicherung der Daten aus der angegebenen Variablen in den reservierten
Speicherbereich wird dann ber den MOVE-Befehl abgewickelt.

Die Lschung eines Datensatzes erfolgt dann umgekehrt analog zur Reservierung.

4.3.3) Der Liststack:
---------------------
Hierbei handelt es sich nicht, wie die berschrift vermuten lt, um einen
Stack im herkmlichen Sinne (LIFO), sondern um ein Recordarray, das pro
Arrayelement (= ein RECORD) smtliche listenspezifischen Daten enthlt:

Die einzelnen Arrayelemente wurden als RECORD folgendermaen definiert:

TYPE STR08 = STRING [8];

     ListenName = RECORD
       LName: STR08;                   (* Speicherung des Listennamens *)
       FPtr, LPtr, Cur      : List;    (* Speicherung der Listenpointer*)
       FNo, LNo, CurNo, ObjS: WORD;    (* weitere Listendaten          *)
     END; (* RECORD ListenName *)

Die Anzahl der Listen, die gleichzeitig im Speicher gehalten werden knnen,
kann ber die Konstante MaxDaten im INTERFACE-Teil der UNIT festgelegt werden.
Zu beachten ist dabei nur, da die Konstante um 1 grer sein mu als die
gewnschte Anzahl Listen (siehe KillMem im Listing).
Der Liststack wird von den folgenden Routinen verwaltet:
SetActiveList: speichert die Parameter der aktuellen Liste und setzt die in
               der Variable Name angegebene Liste als aktuelle Liste (das
               Array wird auf den Listennamen hin abgesucht, bis TopOfList).
ML (MakeList): wird MakeList aufgerufen, so werden ebenfalls die Parameter
               der gerade aktuellen Liste gespeichert, die Variable TopOfList
               inkrementiert und smtliche Parameter der neuen Liste in das
               zugehrige, ber TopOfList angegebene, Record eingetragen.
KillMem: lscht die aktive Liste; alle Arrayelemente von ActiveListNo bis
         TopOfList werden jeweils in das logisch "vor ihnen" liegende kopiert.

4.4) Beispiele:
---------------
4.4.1) Ersatzteilverwaltung (letzte Version!):
----------------------------------------------
  PROGRAM Verwalte5;
  USES CRT;

  TYPE Ersatzteil = RECORD
         Bezeichnung: STRING[100];                     {100  Bytes }
         Artikelnr  : LONGINT;                         {  4  Bytes }
         Anzahl     : WORD;                            {  2  Bytes }
         Preis      : WORD;                            {  2  Bytes }
       END; (* RECORD Ersatzteil *)           { Gesamt: 108  Bytes/RECORD }

  VAR User: Ersatzteil;
      Name: STR08;
      Ende: CHAR;

  PROCEDURE Read_Record (VAR u: Ersatzteil);
  BEGIN
    WriteLn ('Einlesen des Ersatzteil Datensatz mit Nr: ',(CurrentNo+1));
    Write ('Ersatzteil     : '); ReadLn (u.Bezeichnung);
    Write ('Artikelnummer  : '); ReadLn (u.Artikelnr);
    Write ('Anzahl         : '); ReadLn (u.Anzahl);
    Write ('Preis          : '); ReadLn (u.Preis);
  END; (* PROC Read_Record *)

  PROCEDURE Write_Record (u: Ersatzteil);
  BEGIN
    WriteLn ('Zugriff auf den Ersatzteil Datensatz mit Nr: ',CurrentNo);
    WriteLn ('Ersatzteil     : ', u.Bezeichnung);
    WriteLn ('Artikelnummer  : ', u.Artikelnr);
    WriteLn ('Anzahl         : ', u.Anzahl);
    WriteLn ('Preis          : ', u.Preis);
  END; (* PROC Write_Record *)

  BEGIN
    ...
    < S O U R C E >
    ...
    Read_Record (User);
    ObjectSize:=SizeOf (User);
    ML (User, Name);
    REPEAT
      WriteLn ('Weiter n/Taste : '); Ende:=ReadKey;
      Ende:=UpCase(Ende);
      IF (Ende <> 'N') THEN BEGIN
         Read_Record (User);
         LPut (User);
      END;
    UNTIL (Ende = 'N');
    ...
    < S O U R C E >
    ...
    SetFirstNode;
    GetData (User);
    Write_Record (User);
    REPEAT
      GetNext (User);
      Write_Record (User);
      WriteLn ('Weiter n/Taste : '); Ende:=ReadKey;
      Ende:=UpCase(Ende);
    UNTIL ((Next = NIL) OR (Ende = 'N')); (* bis Listenende od. Ende*)
    ...
    < S O U R C E >
    ...
  END. (* PROGRAM Verwalte5 *)

4.4.2) Testprogramm (dt2.pas):
------------------------------
PROGRAM Dt2;
USES DOS, CRT, List_Man;

TYPE Name = RECORD       (* TestRecord definieren *)
       VN: STRING[20];
       NN: STRING[20];
     END;

VAR H1, H2, H3, H4     : LONGINT;         (* Anzahl freier Bytes am HEAP *)
    Name1, Name2, Name3: STR08;           (* Listennamen                 *)
    s                  : STRING[100];     (* Testvariable *)
    r                  : Name;            (* Testvariable *)
    li                 : LONGINT;         (* Testvariable *)
    Hour, Min, Sec, S100, MaxNodes: WORD; (* Var. f. Zeitmessung, MaxNodevar *)

PROCEDURE Line;                           (* Zieht eine horiz. Linie *)
VAR x: BYTE;
BEGIN
  FOR x:=1 TO 80 DO Write (#196);
END; (* PROC Line *)

PROCEDURE Write_Title;
BEGIN
  ClrScr;
  WriteLn ('List_Manager Demonstrationsprogramm:  (c) e.huber');
  Line;
END; (* PROC Write_Title *)

PROCEDURE GiveStatistics;    (* Gibt einige Zahlen, den Heap betreffend, aus *)
BEGIN
  Line;
  WriteLn ('Statistik:');
  WriteLn ('Gesamt verfuegbarer Platz am Heap       : ',H1:6,' Bytes');
  WriteLn ('Platz belegt durch die gesamte/n Liste/n: ',(H1-H3):6,' Bytes');
  WriteLn ('Noch freier Speicherplatz               : ',H3:6,' Bytes');
  WriteLn ('Verfgbarer Platz nach Lschen der Liste: ',H4:6,' Bytes');
  WriteLn ('                               Weiter mit RETURN');
  Line;
  ReadLn;
END; (* PROC Statistics *)


BEGIN
H1:=MemAvail;
Name1:='Name1'; Name2:='Name2'; Name3:='Name3';
s:='My Name is';
r.VN:='Ernst'; r.NN:='HUBER';

Write_Title;

ObjectSize:=SizeOf (li);  (* ObjectSize init. - Gre des Datenfeldes best. *)
ML (li, Name1);           (* Einelementige Liste anlegen                    *)

MaxNodes:=(MemAvail DIV (13+ObjectSize)); (* Max. mgl. Anz. d. Knoten best.*)

Write ('Gen. Liste mit ',MaxNodes:6,' Nodes (LongInt)    : ');
GetTime (Hour,Min,Sec,S100);
WriteLn (Hour:2,' h ',Min:2,' m ',Sec:2,' s ',S100:2);

REPEAT                    (* Liste solange erweitern, bis die max. mgl.   *)
  li:=CurrentNo;          (* Anzahl von Knoten erreicht ist                *)
  LPut (li);
UNTIL ((CurrentNo >= MaxNodes) OR (NotExist));

GetTime (Hour,Min,Sec,S100);
Write ('Liste mit ',MaxNodes:6,' Knoten erzeugt          : ');
WriteLn (Hour:2,' h ',Min:2,' m ',Sec:2,' s ',S100:2);
H3:=MemAvail;

Write ('Speichere Liste auf dem gerade aktiven Lw: ');
GetTime (Hour,Min,Sec,S100);
WriteLn (Hour:2,' h ',Min:2,' m ',Sec:2,' s ',S100:2);
SaveList (li,'test.lst');

GetTime (Hour,Min,Sec,S100);
Write ('Fertig mit SaveList/beginne mit KillMem  : ');
WriteLn (Hour:2,' h ',Min:2,' m ',Sec:2,' s ',S100:2);
KillMem;

GetTime (Hour,Min,Sec,S100);
Write ('Fertig mit KillMem/beginne mit LoadList  : ');
WriteLn (Hour:2,' h ',Min:2,' m ',Sec:2,' s ',S100:2);
ObjectSize:=SizeOf(li);
LoadList (li,'test.lst',Name1);

GetTime (Hour,Min,Sec,S100);
Write ('Fertig mit LoadList                      : ');
WriteLn (Hour:2,' h ',Min:2,' m ',Sec:2,' s ',S100:2);
KillMem;
H4:=MemAvail;
GiveStatistics;

H1:=MemAvail;
Write_Title;
WriteLn ('Erzeuge 3 Listen bestehend aus jeweils 10 Elementen:');
WriteLn (' LONGINT            STRING            RECORD');
WriteLn ('                                      Vorname        Nachname');
li:=0;
ObjectSize:=SizeOf(li);     (* Generiere Liste 1 mit LONGINT-Datenfeld   *)
ML (li,Name1);
REPEAT
  li:=CurrentNo;
  LPut (li);
UNTIL (CurrentNo >= 10);

ObjectSize:=SizeOf(s);      (* Generiere Liste 2 mit String100-Datenfeld *)
ML (s,Name2);
REPEAT
  Lput (s);
UNTIL (CurrentNo >= 10);

ObjectSize:=SizeOf(r);      (* Generiere Liste 3 mit RECORD-Datenfeld    *)
ML (r,Name3);
REPEAT
  LPut (r);
UNTIL (CurrentNo >= 10);

H3:=MemAvail;

SetActiveList (Name1);                   (* Liste 1 aktivieren         *)
SetFirstNode;                            (* zum Listenangfang springen *)
GetData (li);                            (* 1. Datensatz holen         *)
GotoXY (5,6+CurrentNo); WriteLn (li);    (* und am Bildschirm ausgeben *)
REPEAT
  GetNext (li);                          (* nchsten Datensatz holen   *)
  GotoXY (5,6+CurrentNo); WriteLn (li);  (* am Bildschirm ausgeben,    *)
UNTIL (Next=NIL);                        (* solange bis Listenende     *)

s:='';
SetActiveList (Name2);                   (* wie bei Liste 1            *)
SetFirstNode;
GetData (s);
GotoXY (19,6+CurrentNo); WriteLn (s);
REPEAT
  GetNext (s);
  GotoXY (19,6+CurrentNo); WriteLn (s);
UNTIL (Next=NIL);

r.VN:=''; r.NN:='';                      (* wie bei Liste 1            *)
SetActiveList (Name3);
SetFirstNode;
GetData (r);
GotoXY (39,6+CurrentNo); WriteLn (r.VN,'          ',r.NN);
REPEAT
  GetNext (r);
  GotoXY (39,6+CurrentNo); WriteLn (r.VN,'          ',r.NN);
UNTIL (Next=NIL);

SetActiveList (Name1); KillMem;   (* Liste1 aktivieren und lschen *)
SetActiveList (Name2); KillMem;   (* Liste2 aktivieren und lschen *)
SetActiveList (Name3); KillMem;   (* Liste3 aktivieren und lschen *)
H4:=MemAvail;
GiveStatistics;

END. (* PROGRAM DT2 *)