Die Basis zum Basic, Teil 5: Module, Listen und Bäume

Über sechs Stufen steigen Sie mit uns vom Computeranwender zum Programmierer auf.

Stefan Ems, Arne Wieczorrek

Diesmal zeigen wir Ihnen, wie Sie auch in komplizierten Programmen die Übersicht bewahren. Wir befassen uns mit dem modularen Aufbau von Basic-Programmen und führen Sie anhand von Listen und Binärbäumen in die Verwaltung komplexer Datenstrukturen ein. Die versprochenen Erläuterungen zum »INPUT...USING«-Befehl fehlen selbstverständlich auch nicht.

Doch keine Angst, gar so theoretisch »trocken« wird es auch diesmal nicht. Die Schnellstarter unter Ihnen finden in einem separaten Textkasten eine »Umbauanleitung«, mit deren Hilfe sie das Listing DISK1.BAS aus Kursteil 4 aktualisieren. Wie immer sollten Sie nach der »Tipperei« die Erklärungen zu den neu eingefügten Programmteilen nachlesen. Die in den vorangegangenen Kursteilen angesprochenen Sprung-Befehle wie »GOTO«, »GOSUB«, »ON... GOTO«, »ON... GOSUB«, etc. bieten größte Freiheit beim Programm-Entwurf sowie bei der Strukturierung und Organisation des Programmablaufes. Eine zu weit ausgeschöpfte Freiheit wirkt sich allerdings manchmal negativ aus. Dann nämlich, wenn durch intensives »Vor-, Zurück- oder Hin- und Herspringen« im Programmablauf die Übersicht verloren geht.

Dieser typischen »Basic-Programmierer-Krankheit« mit dem klinischen Namen »Spaghetti-Code-Verschlingung« beugen wir vor, indem wir vor Beginn der Programmierung das zu lösende Gesamtproblem in handliche und übersichtliche Teilprobleme zerlegen. Eine solche Vorgehensweise nennen die Informatiker Modultechnik: Das Programm besteht aus einzelnen Modulen. Ein Hauptprogramm ruft die einzelnen Unterprogramme auf und steuert den Programmablauf. In einem Basic-Listing sollten Sie die folgende typische Struktur verwenden:

Hauptprogramm (meist eine Menü-Steuerung)
    Unterprogramm 1 (Adressen editieren)
        Unterprogramm 1.1 (Adresse eingeben)
        Unterprogramm 1.2 (Adresse löschen)
        Unterprogramm 1.3 (Adresse hinzufügen)
    Unterprogramm 2 (Adressen ausgeben)
        Unterprogramm 2.1 (Monitor) 
        Unterprogramm 2.2 (Drucker) 
        Unterprogramm 2.3 (Akustikkoppler)
    Unterprogramm 3 (Adressen auf Diskette)
        Unterprogramm 3.1 (Speichern) 
            Unterprogramm 3.1.1 (Speichern..)
            Unterprogramm 3.1.2 (Speichern als..) 
        Unterprogramm 3.2 (Laden) 
    Unterprogramm 4 (Dienstprogramme)
        Unterprogramm 4.1 (Diskette) 
        Unterprogramm 4.2 (Sortieren) 

Zur besseren Übersicht empfehlen wir, die Programmzeilen einzurücken. Sie erleichtern sich dadurch das Leben, wenn Sie fast vergessene Programme wieder »lesen« oder erweitern wollen: Die Teilprobleme lassen sich besser unterscheiden, Modul-Hierarchie und Programmablauf werden deutlich, Aufgabe und Funktion der einzelnen Programm-Module sind einfach zu entschlüsseln.

Im ersten (Bei)Spiel-Programm zum Thema »Abstrakte Datenstrukturen« wenden wir die Regeln der strukturierten Programmierung an. Die einzelnen Unterprogramme, Prozeduren und Funktionen stellen zusammengenommen einen Programmblock dar, mit dem wir eine neue Datenstruktur schaffen, die sogenannte »Liste«.

Datenstrukturen sind charakterisiert durch die Art der Zusammenfassung und des Zugriffs auf die Einzeldaten sowie durch die darauf anwendbaren Operationen. Ein einfaches Beispiel: Die Integer- und Stringvariablen unterscheiden sich nicht nur darin, daß der eine Typ Zahlen speichert, der andere Typ dagegen alphanumerische Zeichen enthält. Auch im Daten-Zugriff besteht ein Unterschied: Zahlen in String-Variablen (z.B. A$= "123" und B$= "456") lassen sich nicht mathematisch addieren. Eine Addition von A$ und B$ ergibt den String »123456« und nicht die Summe »579«. Diese erhalten wir nur dann, wenn zwei Integer-Variablen mit den Werten A = 123 und B = 456 belegt sind. Die Addition von A und B führt zum gewünschten Ergebnis »A + B = 579«. Wir halten fest, daß mit dem Datentyp »Integer« Operationen durchführbar sind, die sich mit anderen Datentypen nicht verwirklichen lassen.

Bevor wir auf die Datenstruktur »Liste« eingehen, wollen wir einem Mißverständnis Vorbeugen. Mit »Liste« meinen Informatiker nicht etwa eine Einkaufsliste oder eine Namensliste, sondern vielmehr eine Art Stapel, in dem die einzelnen Datenelemente kettenähnlich miteinander verbunden sind. Bis auf das oberste und das unterste Element — beide sind besonders markiert — hat jedes Element einen Vorgänger und einen Nachfolger. Um die Elemente in der Liste richtig anzuordnen, weisen Zeiger auf den Nachfolger oder den Vorgänger hin.

Wie bei einem natürlichen Stapel können wir auch in einer Liste nur auf das oberste Element direkt zugreifen. Wollen wir auf ein Element im unteren Bereich zugreifen, so müssen wir die Liste von oben an bis zum gesuchten Element durchlaufen. Wir müssen die einzelnen Elemente »Stück für Stück« oben vom Stapel wegnehmen, bis das gesuchte Element ganz oben liegt. Wenn wir ein Element aus der Stapelmitte herausziehen, bringen wir den Stapel in Unordnung:

Genau wie bei dem beliebten Gag aus Slapstick-Komödien, wenn der Held der Geschichte eine Konservendose aus der untersten Ebene des aufgeschichteten Dosenturmes zieht — Krawumm!

Zurück zur Datenliste: Jedes Element einer Liste ist gleich aufgebaut. Es besteht aus einem Inhaltsbereich mit frei wählbarem Datentyp und dem Zeiger, der auf das nachfolgende Element weist. Um die Datenstruktur »Liste« aufzubauen, dimensionieren wir in unserem Beispielprogramm »LISTE.BAS« (aus Platzgründen nur auf der Leserservice-Diskette) zwei Felder:

DIM Speicher$(100) ' für den Inhalt der 100 Elemente 
DIM Sp_Zeiger(100) ' für die Zeiger

In der Variable Sp_Zeiger speichern wir jeweils die Adresse des nachfolgenden Elements. Auf diese Weise simulieren wir das in Pascal unmittelbar enthaltene Zeiger-Prinzip. Außerdem benötigen wir für jeden Stapel den »Wurzelzeiger«, also eine Variable, die auf das oberste Element eines jeden Stapels zeigt (Variable »Wu_Zeiger()« im Programm). Das letzte Element hat keinen Nachfolger. Es wird durch einen Zeiger gekennzeichnet, der auf »0« weist. In Basic:

If Sp_Zeiger(X)=0 then Print Speicher$(X);

oder

»Speicher$(X) ist unterstes Element des Stapels«

Wie auch bei Stapeln verwendet man in Listenstrukturen das sogenannte »Lifo-Prinzip«. Lifo steht für »Last in — first out«. Das Element, das Sie zuletzt auf den Stapel gelegt haben und das deshalb ganz oben liegt, läßt sich als erstes Element wieder bearbeiten. Dieses Prinzip verdeutlicht das Demonstrationsprogramm »LISTE.BAS«.

Nach Start des Programmes sehen Sie links oben den Menüblock, aus dem die fünf Unterprogramme anwählbar sind. Dafür sorgen die Zeilen 100-300. Mit »Eingabe« bestimmen Sie den Inhalt eines Elements. Das Programm übernimmt Ihre Eingabe in die Variable »Speicher$(Aktuell)«. Inhalt, Adresse und Zeiger (in Basic also die Speicheradresse des Nachfolgers) erscheinen rechts oben auf dem Bildschirm. Nach Eingabe eines neuen Elements enthält die Zeigervariable den Wert »-1« (Zeile 590) zum Zeichen, daß das Element noch nicht in einem Stapel integriert ist.

Mit »3 Einkellern« legen Sie das aktuelle Element auf den Stapel. Das funktioniert natürlich nur dann, wenn Sie vorher einen Stapel erzeugt haben. Dies erledigt »2 Stapel eröffnen«. Mit welchem Stapel Sie gerade arbeiten, zeigt das Anzeigefeld rechts oben. Durch »5 Stapel_Nr ändern« wählen Sie die Nummer des aktuellen Stapels. Die »Auskeller«-Funktion ist die Umkehrung der »Einkeller«-Routine. Selbstverständlich läßt sich ein Element aus einem Stapel auskellern und anschließend in einen neuen Stapel wieder einkellern. Führen Sie diese Prozedur zur Verdeutlichung durch!

Informatiker entwickelten die Liste weiter zur Datenstruktur »Baum«. Während jedes Element der Liste nur einen Nachfolger hat, zeichnen sich die Elemente in Daten-Bäumen durch mehrere Nachfolger aus. Hier begnügen wir uns mit einer speziellen Baumstruktur, bei der jedes Element maximal zwei Nachfolger besitzt, nämlich dem sogenannten Binär-Baum. Er ordnet die Elemente nach einem genau festgelegten Prinzip an und erzeugt ein Datenfeld, das auf den ersten Blick einen ungeordneten Eindruck erweckt. Durchläuft man diese Datenstruktur jedoch mit dem sogenannten »LWR-Durchlaufverfahren« (Links-Wurzel-Rechts-Verfahren), so erhält man ein sortiertes Datenfeld. Nach welchen Kriterien sortiert wird, entscheiden Sie in der Anordnungsphase.

Nehmen wir diese Phase genauer unter die Lupe. Das Prinzip ist einfach: Das erste Element legen wir als Wurzel des Baumes fest. Die Wurzel des Baumes hat keinen Vorgänger. An den anderen »Enden« des Baumes stehen Elemente, die keine Nachfolger besitzen. Man bezeichnet sie in Analogie zu einem natürlichen Baum als »Blätter«. Die Abzweigungen hinter einem Element heißen Äste. Mit jedem weiteren Element wächst der Baum. Aus einem Vergleich mit der Wurzel entscheidet sich, in welche Richtung der Baum wächst. Ist der Inhalt des neuen Elements kleiner als die Wurzel, zweigt der Baum nach links ab, ist er größer, fährt das Wachstum nach rechts fort. »Fortfahren« bedeutet, daß das neue Element mit dem rechten Nachfolger der Wurzel verglichen wird. Die Prozedur des Vergleichens und Fortfahrens setzt sich so lange fort, bis wir auf das Element stoßen, das an seiner Position keinen Nachfolger hat. Hier koppeln wir das neue Element logisch an: Ist das neue Element kleiner als der Vergleichspartner — die Wurzel des unvollständigen Teilbaumes —, wird es zum linken Nachfolger, anderenfalls zum rechten Nachfolger.

Wichtig: Hat das Einordnungsverfahren zuerst die linke Seite eingeschlagen, bedeutet dies natürlich nicht, daß es von nun an immer nur links abzweigt. Es arbeitet zwar immer auf der linken Hälfte des Baumes, zweigt jedoch im Teilbaum nach rechts ab, wenn das Vergleichsresultat dies erfordert.

Dieser Algorithmus, den unser Bild am Beispiel von Einzelbuchstaben erklärt, zeigt auch, daß der Baum aus vielen Teilbäumen besteht. Die Teilbäume wiederum setzen sich ebenfalls aus Teilbäumen zusammen.

So ergibt sich die folgende rekursive Definition des Binärbaumes: Ein Binärbaum besteht aus einer Wurzel und zwei Binärbäumen. »Rekursive Definitionen« benutzen ihrerseits das zu definierende Wort. Aus der rekursiven Definition heraus gewinnen wir das bereits angesprochene rekursive Durchlaufverfahren. Rekursive Algorithmen bzw. (Unterprogramme rufen sich selbst auf und arbeiten rückwärts (rekursiv von lat. »recurrere = zurücklaufen«). Erklären wir uns das Prinzip der Rekursion an der »Durchlauf«-Prozedur des »LWR-Verfahrens« in Binärbäumen: Zunächst »wandern« wir in der Abbildung zum kleinsten Element, anschließend zu den sortierlogisch folgenden Elementen.

Wenn die »Einordne«-Routine (siehe Erweiterungslisting zu DISK1.BAS, Prozedur »Einordnen«) richtig funktioniert hat, müßte das kleinste Element links unten im Baum angeordnet sein. Da wir jedoch, wie bei der Liste auch, immer nur bei der Wurzel mit dem Durchlaufverfahren beginnen, müssen wir uns zuerst bis nach unten durchkämpfen und dann langsam zurücklaufen.

Zur Lösung des Problems untersuchen wir, was sich hinter dem Links-Wurzel-Rechts-Verfahren verbirgt: Wir betrachten zuerst den linken Ast eines jeden Teilbaums, dann die Wurzel und dann die rechte Abzweigung. Dies ist deshalb notwendig, weil die kleineren Elemente links von der Wurzel des Teilbaums angeschlossen sind. Daher müssen wir auch so lange links abzweigen, bis wir auf das am weitesten links stehende Element ohne linken Nachfolger gestoßen sind. Immer wieder links abzweigen bedeutet eigentlich, den Links-Nachfolger zur Wurzel des neuen Teilbaums zu machen, den wir anschließend durchlaufen (Erweiterungslisting zu DISK1.BAS, Prozedur Durchlauf).

Da die Prozedur sich selbst aufruft, speichert Omikron-Basic die Absprungzeile und den Wert der zu übergebenden Variablen auf einem Stapel. Schließen wir mit der Return-Anweisung einen Teil des Durchlaufs ab, holt der Interpreter die nächste Gosub-Anweisung vom Stapel. Das Lifo-Prinzip des Stapels erzeugt den rekursiven Effekt. Das bedeutet für uns: Ist das Durchlaufverfahren auf das kleinste Element gestoßen, gibt die Routine es auf dem Bildschirm aus und untersucht den rechten Teilbaum.

Das neu Erlernte wenden wir sofort sinnvoll an: Nur wenige Änderungen integrieren die Binärbaum-Struktur in das bekannte Diskettenverwaltungs-Programm »DISK1.BAS« aus Kursteil 4.

In der nächsten Ausgabe des ST-Magazins entführt Sie unser letzter Kursteil in das Land der GEM-Programmierung. Dort bekommt unser Diskettenverwalter ein hübsches GEM-Gesicht.

(W. Fastenrath/ps)

100 DIM Name$(C),Laenge(C),Disk$(C),Z_Links(C),Z_Rechts(C) 

720 Durchlauf(0)

1045 Einordnen(X,0)

DEF PROC Einordnen(X,I)
    Abr=0
    REPEAT
        IF Name$(X)>Name$(I) THEN
            IF Z_Rechts(I)=0 THEN Z_Rechts(I)=X:Abr=1 ELSE I=Z_Rechts(I) 
        ENDIF
        IF Name$(X)<=Name$(I) THEN 
            IF Z_Links(I)=0 THEN Z_Links(I)=X:Abr=1 ELSE I=Z_Links(I)
        ENDIF 
    UNTIL Abr=1 
RETURN

DEF PROC Durchlauf(X)
    IF Z_Links(X)<>0 THEN Durchlauf(Z_Links(X))
    IF X<>0 THEN PRINT Name$(X)+SPC(16-LEN(Name$(X)));Laenge(X),Disk$(X)
    IF Z_Rechts(X)<>0 THEN Durchlauf(Z_Rechts(X)) 
RETURN

INPUT [@(y,x);] ["Text";] < Eingabe-String> USING [Steuer-String], 
[< Return-Variable >],[<Länge >],[< Füllzeichencode >], [< Cursorpositions-Variable >]

KURSÜBERSICHT

Basis zum Basic

Einsteiger lernen, den Atari ST in Omikron-Basic zu programmieren

Teil 1: □ wichtige Fachbegriffe □ Aufbau von Basic-Interpretern □ der Editor □ Variable □ die ersten Befehle

Teil 2: □ Schleifen □ Programmsprünge und Unterprogramme □ Funktionen und Prozeduren □ Befehle selbstgemacht

Teil 3: □ Grafikbefehle □ überraschende Effekte □ Regeln der strukturierten Programmierung

Teil 4: □ Omikron-spezifische Befehle □ Tips & Tricks □ komplexe Programmelemente □ Datenfernübertragung im Basic

Teil 5: □ Programmiertechniken □ Rekursion □ Listen

Teil 6: □ Einführung in die GEM-Programmierung □ die internen Omikron-GEM-Befehle □ Arbeiten mit der EasyGEM-Bibliothek