Top-Down

Willemers Informatik-Ecke

Die Funktionen ermöglichen es nicht nur, dass Code, der nur einmal geschrieben wird, mehrfach verwendet werden kann. Funktionen sind vor allem auch eine Möglichkeit, umfangreichere Programme zu gliedern. Bei einer gelungenen Aufgliederung entstehen Funktionen, die selbst nur aus Funktionsaufrufen bestehen und damit das Problem in groben Schritten beschreiben.

Grobgliederung

Das Top-Down-Verfahren ist eine Entwurfstechnik, um komplexe Probleme schrittweise zu zerlegen. Das Hauptprogramm beginnt beispielsweise mit den Aufruf einer Initialisierungsfunktion. Es folgt eine Schleife, in der Benutzereingaben und Verarbeitung so lange wiederholt werden, bis ein Ereignis eintritt, das das Programm beendet. Auch diese Bedingung kann in einer Funktion formuliert werden, deren Rückgabetyp bool ist. Anschließend wird die Initialisierungsfunktion weiter untergliedert. Hier könnte beispielsweise für die wichtigsten Datenstrukturen des Programms je ein Funktionsaufruf aufgeführt werden. Auf die gleiche Art können die anderen Funktionen wiederum in etwas feinere Funktionen untergliedert werden. Dabei werden die Funktionen immer einfacher und überschaubarer, bis sie schließlich mit wenigen Zeilen ausprogrammiert werden können.

Funktionale Komplexität

Diese Entwicklungsstrategie wurde mit den prozeduralen Sprachen entwickelt und nutzt die Möglichkeit, mit Funktionen Programme sinnvoll zu untergliedern. Auch wenn wir noch sehen werden, dass die objektorientierte Programmierung andere Entwicklungsstrategien mitbringt, kann das Top-Down-Verfahren bei funktionalen Teilproblemen oder Projekten, die weniger daten- als funktional orientiert sind, eine Hilfe sein.

Beispiel: Bermuda

Ein Beispiel zeigt am besten, wie Sie mit Hilfe der Top-Down-Methode ein Problem zerlegen und vereinfachen. Dazu betrachten Sie das Bermuda-Spiel anhand der Aufgabenbeschreibung. Diese lässt sich aus den Spielregeln ableiten.

Grobrasterung

Das Spiel Bermuda wird zunächst in groben Schritten beschrieben. In der Initialisierungsphase wird zunächst das Spielfeld aufgebaut. Dann wird das Spielfeld angezeigt, der Benutzer bekommt die Möglichkeit einer Eingabe, und das Programm berechnet, wie viele Schiffe von dem Punkt aus zu sehen sind. Diese letzten Schritte wiederholen sich so lange, bis das Spiel gewonnen ist oder der Benutzer keine Lust mehr hat und abbricht. In Abbildung (diabermuda) ist die Hauptschleife als Struktogramm zu sehen.

An dieser Stelle steht im Buch die Abbildung "Struktogramm des Bermuda-Spiels" (diabermuda)

C++ Programm

Das Struktogramm wird direkt in das folgende C++-Programm umgesetzt. Die Teilprobleme des Programms werden auf Funktionen verteilt. Sie können nach und nach entwickelt werden.

[Hauptprogramm] 

int main()
{
    initSpielFeld():
    do
    {
        zeigeSpielFeld();
        Benutzereingabe();
        sucheSchiffe();
        Eintragen();
    }
    while (!SpielEnde());
}

Die erforderlichen Parameter wurden bisher noch nicht betrachtet. Dabei ist der Datenfluss ein wichtiger Aspekt. Die Qualität der Zerlegung in Teilaufgaben lässt sich auch daran ablesen, wie viele Parameter übergeben werden müssen. Wenn zu viele Daten durch die Parameter fließen, ist das ein Hinweis darauf, dass die Funktionen unglücklich unterteilt worden sind.

Daten

Für Bermuda wird ein Spielfeld benötigt. Dazu kommt ein Array von vier Schiffen. Zwischen der Benutzereingabe und der Suche nach den Schiffen werden natürlich auch Koordinaten benötigt. Und schließlich muss die Anzahl der ermittelten Richtungen in das Spielfeld eingetragen werden. Daraus ergibt sich das folgende Listing:

[Hauptprogramm] 

int main()
{
    char SpielFeld[X][Y];
    tSchiff Schiff[MaxSchiff];
    int x, y;
    int Anzahl;

    initSpielFeld(SpielFeld, Schiff);
    do
    {
        zeigeSpielFeld(SpielFeld);
        Benutzereingabe(&x, &y);
        Anzahl = sucheSchiffe(Schiff, x, y);
        Eintragen(SpielFeld, x, y, Anzahl);
    }
    while (!SpielEnde(Schiff));
}

Initialisierung

Betrachten wir die Funktion initSpielFeld(). Sie muss zwei Dinge tun. Zunächst muss das zweidimensionale Array vorbereitet werden. Dann müssen die Schiffe auf ihre Positionen verteilt werden. Die beiden Teilaufgaben sind bereits hier und dort gelöst worden. Der einzige Aufwand besteht nun darin, die Aufgaben in Funktionen zu verpacken und die benötigten Parameter festzulegen.

[Initialisierung] 

void initAnzeige(char SpielFeld[X][Y])
{
    ...
}

void initSchiffe(tSchiff Schiff[])
{
    ...
}

void initSpielFeld(char SpielFeld[X][Y], tSchiff Schiff[])
{
    initAnzeige(SpielFeld);
    initSchiffe(Schiff);
}

Die Anzeige des Spielfeldes ist ebenfalls bereits programmiert worden, und die Benutzereingabe ist durch eine einfache Zeile zu lösen. Der Eintrag in das Spielfeld ist nicht besonders schwierig. Auch die boolesche Funktion SpielEnde() ist leicht zu schreiben. Sie besteht aus einer einfachen Schleife, die prüft, ob alle Schiffe gefunden wurden. Die spannendste Aufgabe ist das Berechnen der Antwort auf die Benutzerfrage. Da eine offensichtliche Lösung nicht ins Auge springt, wird die Funktion sucheSchiffe() wiederum in Teilaufgaben zerlegt.

Richtungssuche

Die Suche nach den Schiffen beginnt an der Position, die der Benutzer auswählt. Zunächst muss festgestellt werden, ob der Anwender direkt ein Schiff entdeckt hat. In diesem Fall wird das Schiff als gefunden markiert, und mit der Konstanten MaxSchiff wird ein Wert zurückgegeben, der keinesfalls mit der Anzahl der zu sehenden Schiffe verwechselt werden kann. Andernfalls muss nach links, rechts, oben, unten und in allen Diagonalen gesucht werden.

[Schiffsuche] 

int sucheSchiffe(tSchiff Schiff[], int x, int y)
{
    int Anzahl=0;

    if (istHierEinSchiff(Schiff, x, y, true))
    {
        return MaxSchiff;
    }
    else
    {
        Anzahl += suchelinks(Schiff, x, y);
        Anzahl += suchelinksoben(Schiff, x, y);
        Anzahl += sucheoben(Schiff, x, y);
        Anzahl += sucherechtsoben(Schiff, x, y);
        Anzahl += sucherechts(Schiff, x, y);
        Anzahl += sucherechtsunten(Schiff, x, y);
        Anzahl += sucheunten(Schiff, x, y);
        Anzahl += suchelinksunten(Schiff, x, y);
    }
    return Anzahl;
}

Die acht Suchfunktionen werden sich weit gehend ähneln. Exemplarisch betrachten wir die Funktion sucherechtsoben(). Sie dürfte eine der komplizierteren Funktionen sein. Wenn sie gelöst ist, sind die anderen leicht abzuleiten. Die Funktion wird von der Ausgangsposition die x-Position schrittweise erhöhen und die y-Position herunterzählen, bis sie an einen Rand stößt oder ein Schiff findet.

[Diagonalsuche] 

int sucherechtsoben(tSchiff Schiff[], int x, int y)
{
    x++; y--;
    while(x<X && y>=0)
    {
        if (istHierEinSchiff(Schiff, x, y))
        {
            return 1;
        }
        x++; y--;
    }
    return 0;
}

Zu guter Letzt muss nur noch die Funktion istHierEinSchiff() implementiert werden. Das ist relativ einfach durch eine for-Schleife zu bewerkstelligen, die alle Schiffe daraufhin überprüft, ob eines die angegebene Position innehat. Die Funktion liefert false, wenn kein Schiff gefunden wurde. Diese Funktion markiert auch das gefundene Schiff als gefunden. Allerdings darf sie das nicht immer tun. Die Funktion wird ja auch benutzt, um die Richtungen zu durchlaufen. Dabei wird gezählt, wie viele Schiffe zu sehen sind. Also wird ein weiterer Parameter benötigt, der angibt, ob die Funktion das Schiff markieren soll oder nicht. Damit er nur dann verwendet werden muss, wenn ein Schiff entdeckt wurde, wird sein Wert mit false vorbelegt.

[Trefferfrage] 

bool istHierEinSchiff(tSchiff Schiff[], int x, int y
                      bool markieren=false)
{
    for (int i=0; i<MaxSchiff; i++)
    {
        if (Schiff[i].x==x && Schiff[i].y==y)
        {
            if (markieren)
            {
                Schiff[i].gefunden = true;
            }
            return true;
        }
    }
    return false;
}

Sie sehen, dass das zunächst recht unüberschaubar wirkende Problem recht schnell in leicht lösbare Probleme aufgeteilt werden konnte. Sie finden das komplette Listing auf der CD unter dem Namen bermuda3.cpp. In dieser Datei ist bereits die Lösung der folgenden Übungsaufgabe integriert.

Übung

Diese Seite basiert auf Inhalten aus dem Buch Arnold Willemer: Einstieg in C++
Mit freundlicher Genehmigung und Unterstützung des Verlags galileo computing

Informatik-Ecke Einstieg in C++ (C) Copyright 2005 Arnold Willemer