10 Konzepte der Programmierung

Intelligente Fehler zu machen ist eine große Kunst.
– Federico Fellini

Nachdem Sie im vorigen Kapitel die grundlegende Syntax der Programmierung in vier verschiedenen Sprachen erlernt haben, ist es nun an der Zeit, dieses Handwerkszeug in der Praxis einzusetzen. In diesem Kapitel werden deshalb verschiedene konkrete Aspekte der Programmierung vorgestellt, von der Implementierung wichtiger Algorithmen und Datenstrukturen über eine Einführung in die systemnahe Programmierung und Netzwerkprogrammierung bis hin zur GUI-Anwendungsentwicklung und zur Arbeit mit einer integrierten Entwicklungsumgebung.

Die Implementierung der verschiedenen Beispiele erfolgt jeweils in einer (in seltenen Fällen auch mehreren) der vier im vorigen Kapitel vorgestellten Programmiersprachen; es wird für jede Aufgabe eine passende Sprache ausgewählt.

10.1 Algorithmen und Datenstrukturen

Wenn Sie Programmieraufgaben lösen müssen, genügt es nicht, die einzelnen Befehle und Datentypen der gewählten Programmiersprache zu kennen. Sie benötigen vor allem ein Gespür dafür, wie sich Informationen und Tätigkeiten aus der realen Welt am effektivsten in einem Computerprogramm darstellen lassen. Für die Speicherung der verschiedenen Arten von Informationen werden mithilfe der Datentypen einer Programmiersprache sogenannte Datenstrukturen entwickelt. Die Strategien zur Verarbeitung der Datenstrukturen werden als Algorithmen bezeichnet – der theoretische Hintergrund der Algorithmik wurde bereits in Kapitel 2, »Mathematische und technische Grundlagen«, angesprochen. In diesem Abschnitt werden einige verbreitete Standard-Algorithmen und Datenstrukturen dargestellt.

10.1.1 Ein einfaches Praxisbeispiel

Die Entwicklung eines Algorithmus soll hier zunächst Schritt für Schritt an einem Beispiel erläutert werden. Bevor Sie nämlich konkreten Programmcode hinschreiben, sollten Sie sich zunächst mit Papier und Bleistift theoretische Gedanken über den Ablauf des gewünschten Programms machen. Das Ergebnis solcher Überlegungen ist ein Flussdiagramm.

Es soll ein Algorithmus entwickelt werden, um den größten gemeinsamen Teiler (GGT) zweier ganzzahliger Werte zu ermitteln. Dies ist eine der wichtigsten Aufgaben im Bereich der Bruchrechnung. Der GGT zweier Werte m und n ist im günstigsten Fall m/2 oder n/2, im ungünstigsten Fall 1. Hat er den Wert 1, werden die beiden Zahlen als teilerfremd bezeichnet.

Abbildung 10.1 Flussdiagramm für einen einfachen Algorithmus zur Berechnung des größten gemeinsamen Teilers (GGT)

Abbildung 10.1 zeigt ein Flussdiagramm, das einen Ansatz für eine mögliche Lösung beschreibt. In einem solchen Diagramm steht ein Rechteck für einen einfachen linearen Arbeitsschritt, eine Raute für eine Ja-Nein-Fallunterscheidung und ein abgerundetes Rechteck für Start oder Ende.

Es gibt erheblich effizientere Verfahren zur GGT-Berechnung. Hier geht es aber nur um das grundlegende Prinzip.

Erheblich mehr Darstellungsmöglichkeiten bieten die im nächsten Kapitel vorgestellten Diagrammtypen der UML. Sie beziehen nicht nur Algorithmus und Programmablauf ein, sondern zum Beispiel auch die Aktionen verschiedener beteiligter Personen, Geräte und Programme.

Wie die Diagramme zeigen, werden Schritt für Schritt alle infrage kommenden Werte ausprobiert. Begonnen wird bei der Hälfte der größeren Zahl. Hier sehen Sie eine Implementierung dieses Algorithmus in Java:

static int ggt(int m, int n) {
   // Trivialer Fall: m und n gleich:
   if (m == n)
      return m;
   // Größeren und kleineren Wert ermitteln:
   int gr = (m > n) ? m : n;
   int kl = (m < n) ? m : n;
   // Jeden möglichen Teiler testen:
   for (int i = gr / 2; i >= gr / kl; i--) {
      // Sind beide Werte durch i teilbar?
      if (gr % i == 0 && kl % i == 0)
         return i;
   }
   // Hier bleibt nur noch die 1:
   return 1;
}

Da die Methode ggt() als static deklariert wurde, kann sie innerhalb einer Programmklasse von der Methode main() aus aufgerufen werden, ohne dass ein Objekt der Klasse bestehen muss. static-Methoden sind gewissermaßen der Java-Ersatz für imperative Funktionen. Hier sehen Sie ein Beispiel für eine main()-Methode, die den GGT zweier Kommandozeilenparameter ausgibt:

public static void main (String args[]) {
   int m = Integer.parseInt (args[0]);
   int n = Integer.parseInt (args[1]);
   System.out.println ("Der GGT von " + m + " und "
        + n + " ist " + ggt(m, n));
}

Nach dem Kompilieren können Sie das Programm beispielsweise folgendermaßen aufrufen, falls die Klasse GGTtest heißt:

$ java GGTtest 18 24
Der GGT von 18 und 24 ist 6.

Die statische Methode parseInt() der Klasse Integer (einer objektorientierten Umhüllung für einen int-Wert) wandelt den übergebenen String in eine Ganzzahl um.

10.1.2 Sortier-Algorithmen

Zu den häufigsten Aufgaben bei der Programmierung gehört die Sortierung von Daten nach einem bestimmten Kriterium. Im Laufe der Informatikgeschichte wurden Dutzende von verschiedenen Sortier-Algorithmen entwickelt, die für unterschiedliche Einsatzzwecke geeignet sind. In diesem Abschnitt werden zwei davon vorgestellt. Der erste ist intuitiv verständlich, der zweite gerade für größere Datenmengen besonders effizient.

BubbleSort

Dieser einfachste aller Sortier-Algorithmen durchwandert ein Array elementweise: Er vergleicht jedes Element mit seinem direkten Nachbarn. Falls die beiden Nachbarn in der falschen Reihenfolge stehen, ist es erforderlich, sie zu vertauschen. Außerdem steht dann fest, dass das Array noch nicht fertig sortiert ist, sodass ein weiterer Durchgang erforderlich ist.

Hier sehen Sie eine Implementierung von BubbleSort als Perl-Subroutine, die eine Listenreferenz entgegennimmt und die zugrunde liegende Liste nach diesem Schema sortiert:

sub bubblesort {
   $listref = shift;   # Listenreferenz entgegennehmen
   @liste = @$listref; # Kopie der Liste anfertigen
   do {
      $sortiert = 1;   # Annahme: Bereits sortiert.
      for ($i = 0; $i < $#liste; $i++) {
         # Element i größer als Element i + 1?
         if ($liste[$i] > $liste[$i + 1]) {
            # Die beiden Elemente vertauschen:
            ($liste[$i], $liste[$i + 1])
                 = ($liste[$i + 1], $liste[$i]);
            # Aha! Noch nicht sortiert:
            $sortiert = 0;
         }
      }
   } while (!$sortiert);
   return @liste;      # Sortiert zurückgeben
}

Das Kopieren der Liste und die Rückgabe der Kopie sind nicht unbedingt erforderlich, verhindern aber das umständliche Hantieren mit Dereferenzierungen im Kern des eigentlichen Algorithmus. Wenn am Anfang nicht die Kopie @liste angefertigt würde, müsste zum Beispiel der eigentliche Tauschbefehl folgendermaßen lauten:

Die spezielle Formulierung $#array gibt übrigens den höchsten Index des Arrays @array zurück, bei einem Array mit 13 Elementen also beispielsweise 12. Da für den Vergleich jedes Elements mit seinem rechten Nachbarn eine Schleife vom ersten bis zum vorletzten Element benötigt wird, lautet die Bedingung der for()-Schleife im vorliegenden Fall $i < $#liste.

Die Subroutine bubblesort können Sie zum Beispiel so aufrufen:

@zahlen = qw(2 7 9 1 3 8 6 7);
@zahlen = bubblesort(\@zahlen);
print join(", ", @zahlen);

Die Ausgabe dieses Beispiels lautet:

1, 2, 3, 6, 7, 7, 8, 9

Beachten Sie, dass für die Sortierung von Strings eine separate Fassung erforderlich wäre, die den Vergleichsoperator gt statt des numerischen > verwendet (siehe voriges Kapitel). Wenn Sie im Übrigen nicht aufsteigend, sondern absteigend sortieren möchten, muss statt > der Operator < eingesetzt werden, bei Strings entsprechend lt.

Zu Vergleichszwecken sehen Sie hier eine weitere Implementierung von BubbleSort als Java-Methode, die ein Array von int-Werten sortiert:

static int[] bubbleSort(int[] liste) {
   boolean sortiert;
   do {
      sortiert = true;
      for (int i = 0; i < liste.length - 1; i++) {
         if (liste[i] > liste[i + 1]) {
            // Tauschen:
            int temp = liste[i];
            liste[i] = liste[i + 1];
            liste[i + 1] = temp;
            // Nicht sortiert!
            sortiert = false;
         }
      }
   } while (!sortiert);
   return liste;
}

Die folgende main()-Methode generiert ein Array mit unsortierten Werten, ruft bubbleSort() auf und gibt anschließend die sortierte Liste aus:

public static void main (String args[]) {
   int[] werte = {3, 7, 1, 9, 2, 5, 2};
   werte = bubbleSort(werte);
   for (int i = 0; i < werte.length; i++) {
      System.out.print(werte[i] + " ");
   }
}

Die Ausgabe sieht natürlich folgendermaßen aus:

1 2 2 3 5 7 9

int fakultaet (int n) {
   if (i > 1)
      return n * fakultaet (n – 1);
   else
      return 1;
}

int fakultaet (int n) {
   int i;
   int fak = 1;
   for (i = 2; i <= n; i++) {
      fak *= i;
}
   return fak;
}

QuickSort

Wie der Name vermuten lässt, handelt es sich bei QuickSort um einen besonders geschwindigkeitsoptimierten Sortier-Algorithmus. Für eine ausreichend große Anzahl von Elementen ist er tatsächlich eines der schnellsten verfügbaren Sortierverfahren. Bei einer zu kleinen Elementanzahl kann er seinen theoretischen Geschwindigkeitsvorteil wegen der relativ aufwendigen Initialisierung nicht ausspielen.

QuickSort funktioniert nach dem Verfahren »Teile und herrsche«: Das gesamte zu sortierende Array wird in zwei Teile unterteilt (partitioniert), die an rekursive Aufrufe der Funktion übergeben werden. Dazu wird zunächst ein Vergleichselement namens Median gesucht; die Daten rechts neben dem Median müssen größer sein, die Daten links von ihm kleiner. Dies geschieht für jede Partition so lange immer wieder, bis jeweils nur noch zwei Elemente übrig sind, die in die richtige Reihenfolge gebracht werden. Hier eine QuickSort-Implementierung in Java:

static int[] quickSort(int[] liste) {
   /* quickSort ist nur ein bequemer Starter für die
      eigentliche Arbeits-Methode qSort().           */
   // qSort mit dem gesamten Array aufrufen:
   qSort (liste, 0, liste.length - 1);
   return liste;
}

static void qSort(int[] liste, int lo, int hi) {
   int median;
   if (lo < hi) {
      // Vergleichselement Median ermitteln:
      median = liste[hi];
      int i = lo - 1;
      int j = hi;
      for ( ; ; ) {
         // Werte von beiden Enden aus vergleichen:
         while (liste[++i] < median);
         while (j > 0 && liste[--j] > median);
         // Schleife verlassen, falls sortiert:
         if (j <= i) {
         break;
         }
         // Tauschen
         int temp = liste[i];
         liste[i] = liste[j];
         liste[j] = temp;
      }
      liste[hi] = liste[i];
      liste[i] = median;

      // Linke/rechte Partition sortieren:
      qSort (liste, lo, i - 1);
      qSort (liste, i + 1, hi);
   }
}

Die Verwendung von quickSort() könnte beispielsweise genauso aussehen wie der eingangs gezeigte Aufruf von bubbleSort(); Sie müssten lediglich den Namen der aufgerufenen Methode ändern und könnten alles andere stehen lassen.

Auffällig sind an dieser Implementierung von QuickSort die etwas gewöhnungsbedürftigen Schleifenkonstruktionen. for ( ; ; ) ist eine Endlosschleife, die allerdings durch den gezielten Aufruf von break; verlassen wird. Eine solche Schreibweise ist immer dann nützlich, wenn sich erst während der Ausführung des Schleifenrumpfs herausstellt, dass der weitere Ablauf nicht mehr erforderlich ist.

Ähnlich seltsam sind die beiden in sich geschlossenen while()-Schleifen wie diese:

while (liste[++i] < median);

Da nichts weiter getan werden muss, als die Elemente der Liste nacheinander mit dem Median zu vergleichen, ist dies eine erheblich kompaktere Schreibweise für die folgende Fassung:

do {
   --i;
} while (liste[i] < median);

10.1.3 Such-Algorithmen

Eine weitere häufig gestellte Aufgabe bei der Entwicklung von Computerprogrammen ist die Suche nach Elementen in Arrays. Es gibt zwei grundsätzliche Arten dieser Suche: Die lineare Suche durchsucht nacheinander die einzelnen Elemente des Arrays, die binäre Suche erfordert dagegen ein bereits sortiertes Array und sucht darin durch fortgesetztes Halbieren und rekursives Durchsuchen der einzelnen Teilbereiche.

Lineare Suche

Die einfachste Art der Suche ist die lineare. Der Algorithmus besteht einfach darin, die Elemente eines Arrays nacheinander mit einem Suchwert zu vergleichen. Sobald der gesuchte Wert das erste Mal gefunden wird, wird dessen Index zurückgegeben; eine andere Variante würde alle Fundstellen zurückliefern. Es folgt eine Implementierung dieses Algorithmus in Java. Die Methode suchen() erwartet die Übergabe eines Arrays von int-Werten und den gesuchten Wert. Sie gibt den Index des ersten Vorkommens dieses Werts im Array zurück oder –1, falls der gesuchte Wert nicht im Array vorkommt. Hier der Code:

static int suchen(int[] liste, int wert) {
   for (i = 0; i < liste.length; i++) {
      if (liste[i] == wert)
         return i;
   }
   // Nicht gefunden:
   return -1;
}

Dieser Code sollte im Großen und Ganzen selbsterklärend sein. Ein Aufruf dieser Methode könnte folgendermaßen aussehen:

public static void main (String args[]) {
   int zahlen[] = {5, 1, 8, 3, 9, 2, 7};
   int suchwert = 8;
   System.out.println (suchwert +
        " kommt in der Liste an Position " +
        suchen (zahlen, suchwert) + " vor.");
}

Die Ausgabe dieses Hauptprogramms sieht natürlich so aus:

8 kommt in der Liste an Position 2 vor.

Binäre Suche

Bei der binären Suche muss zunächst ein sortiertes Array vorliegen. Dieses sortierte Array wird anschließend durch eine rekursive Methode immer weiter unterteilt, dadurch kann der gesuchte Wert sehr schnell gefunden werden.

Hier sehen Sie eine Implementierung dieses Algorithmus in Java. Die Methode binSuche() erwartet die Übergabe eines sortierten Arrays (die Sortierung wird nicht überprüft!) und den gesuchten Wert. Der Rückgabewert ist wieder der Index des gesuchten Elements oder –1, falls das Element nicht gefunden wird:

int binSuche (int[] liste, int wert) {
   //Initialisierung der eigentlichen Methode bSuche()
   return bSuche (liste, wert, 0, liste.length);
}

int bSuche (int[] liste, int wert, int lo, int hi) {

   // Nicht gefunden?
   if (lo > hi)
      return -1;
   int m = (lo + hi) / 2;
   int mwert = liste[m];
   if (mwert == wert)
      return wert;
   if (wert < mwert)
      return bSuche (liste, wert, lo, m - 1);
   if (wert > mwert)
      return bSuche (liste, wert, m + 1, hi);
}

10.1.4 Ausgewählte Datenstrukturen

Auf der Basis der grundlegenden Datentypen, die im vorigen Kapitel vorgestellt wurden, lassen sich diverse komplexe Datenstrukturen für die Darstellung der verschiedensten Arten von Informationen aus der Realität einrichten. Einige wichtige Datenstrukturen, die häufig für Programmieraufgaben verwendet werden, werden im Folgenden vorgestellt.

Stacks und Queues

Die Eigenschaften von Stacks (Stapeln) und Queues (Warteschlangen) wurden bereits im vorigen Kapitel bei der Vorstellung der Programmiersprache Perl erwähnt. Es handelt sich um Arrays mit einer dynamischen Anzahl von Elementen. Bei einem Stack werden Elemente nacheinander am Ende angehängt und bei Bedarf von diesem Ende wieder entfernt. Es handelt sich also um einen »Last In, First Out«-(LIFO-) Speicher. Eine Queue ist dagegen ein »First In, First Out«-Speicher (FIFO): Elemente werden am Anfang der Liste hineingeschoben und am Ende nacheinander entnommen.

In Perl ist die Unterstützung für Stacks und Queues bereits eingebaut. Mithilfe der Funktionen push(@liste, $wert) und pop(@liste) wird ein Stack realisiert: push hängt den angegebenen Wert an das Ende der Liste an, pop entfernt das letzte Element und gibt es zurück. Mithilfe von unshift und pop lässt sich dagegen eine Queue einrichten: Mit unshift (@liste, $wert) wird ein Wert am Anfang einer Liste eingefügt, pop entfernt wie gehabt den letzten Wert.

In anderen Programmiersprachen ist die Implementierung dieser Datenstrukturen dagegen ein wenig schwieriger. In C und Java haben die eingebauten Arrays eine feste Anzahl von Elementen, sind also zur Darstellung dynamischer Listen nicht geeignet. Die Standardbibliothek neuerer Java-Versionen bietet allerdings zahlreiche eingebaute Klassen für diverse Listen, die verwendet oder erweitert werden können.

In C wird in der Regel ein struct definiert, der jeweils einen einzelnen Wert und einen Zeiger auf das nächste dieser Elemente enthält. Eine solche Struktur sieht also beispielsweise so aus:

struct element {
   int wert;
   struct element *nachfolger;
}

Auch wenn es ein wenig seltsam aussieht, dass innerhalb der struct-Definition ein Zeiger auf diesem Datentyp selbst steht, ist dies überhaupt kein Problem. Zwar kann eine Struktur keine Variable enthalten, deren Datentyp die Struktur selbst ist, aber ein Zeiger darauf funktioniert.

Hier ein kleines C-Beispielprogramm, in dem eine Liste verwendet wird, um zehn eingegebene Werte aufzunehmen, die anschließend durch sequenzielles Durchwandern der Liste wieder ausgegeben werden:

#include <stdio.h>
#include <stdlib.h>

struct liste {
   int wert;
   struct liste *nachfolger;
};

int main (int argc, char *argv[]) {
   int i;
   int w;
   /* Element erzeugen */
   struct liste *aktuell = malloc(sizeof *aktuell);
   struct liste *erster = aktuell; /* Anfang merken */
   printf ("Bitte 10 int-Werte!\n");
   for (i = 0; i < 10; i++) {
      scanf ("%d", &w);
      aktuell->wert = w;
      aktuell->nachfolger = malloc(sizeof *aktuell);
      aktuell = aktuell->nachfolger;
   }
   aktuell = erster;
   printf ("\n");
   printf ("Ihre Eingaben:\n");
   for (i = 0; i < 10; i++) {
      printf ("%d\n", aktuell->wert);
      aktuell = aktuell->nachfolger;
   }
   return 0;
}

Die Funktion malloc() dient dazu, dynamisch Speicher zu allozieren. Das bedeutet, dass ein Bereich im Arbeitsspeicher für einen neuen Wert reserviert wird. Die Speicherverwaltungsfunktionen sind in der Header-Datei stdlib.h definiert. malloc() besitzt einen etwas merkwürdigen Datentyp: void *. Dies ist nicht etwa ein »Zeiger auf gar nichts«, sondern einfach ein Zeiger auf einen beliebigen Datentyp. Damit die richtige Menge Speicher reserviert wird, benötigt malloc() die gewünschte Speichermenge (Datentyp size_t) als Argument. Hierzu bietet sich der Operator sizeof an, der die Speichergröße einer Variablen oder eines Datentyps angibt.

In robusten Programmen für echte Anwendungszwecke sollten Sie malloc() stets mithilfe von if überprüfen, damit Sie Fälle abfangen können, in denen die Speicherzuteilung nicht möglich ist (etwa wenn insgesamt zu wenig Speicher zur Verfügung steht).

In diesem Beispielprogramm werden zwei verschiedene Zeiger auf ein Listenelement verwendet, damit das erste Element der Liste auch dann noch verfügbar ist, falls der andere Zeiger zum Durchwandern der Liste genutzt wird.

In Java lässt sich eine Liste noch erheblich einfacher realisieren: Wegen der Objektorientierung können Sie leicht eine Klasse implementieren, die ein Listenelement und einen Verweis auf seinen Nachfolger darstellt. Eine solche Klasse könnte beispielsweise so aussehen:

public class Element {
   private int wert;
   private Element nachfolger;
}

Es ist leicht vorstellbar, dass sich Funktionen zum Hinzufügen oder Entfernen von Elementen als Methoden einer solchen Klasse implementieren lassen.

Es folgt ein kleines Beispiel für die praktische Anwendung von Listen. Das Programm ist in Perl geschrieben, weil Listen in dieser Sprache bereits eingebaut sind und keinen komplexen Programmieraufwand erfordern. Das Beispiel verwendet einen Stack, um die Wörter in einem String umzukehren:

#!/usr/bin/perl -w
use strict;
print "Bitte eine Zeile eingeben:\n";
my $line = <>;
chomp $line;
# An Leerzeichen zerlegen:
my @words = split (/\s+/, $line);
# Umgekehrte Liste erstellen:
my @rwords;
while (@words) {
   push (@rwords, pop (@words));
}
# Umgekehrte Liste ausgeben:
print join (" ", @rwords);

Die Ausgabe des Programms sieht beispielsweise so aus:

Bitte eine Zeile eingeben:
Diese Liste wird nun umgekehrt
umgekehrt nun wird Liste Diese

Die wichtige Anweisung in diesem Programm ist folgende:

Mithilfe von pop wird jeweils das letzte Zeichen der Liste @words entnommen und mithilfe von push an die Liste @rwords angehängt.

Bäume

Eine weitere interessante Datenstruktur ist der Baum. Die einzelnen Elemente eines Baums ähneln denjenigen einer Liste, mit dem Unterschied, dass ein Element eines Baums jeweils mehrere Nachfolger haben kann. Die wichtigste Art der Baumstruktur ist der Binärbaum. Jedes Element dieses Baums kann genau zwei Nachfolger besitzen. Mithilfe von Binärbäumen werden beispielsweise schnelle Such- und Sortierverfahren implementiert.

In der Sprache C sieht die Datenstruktur für ein einzelnes Element eines Binärbaums beispielsweise so aus:

struct baum {
   int wert;
   struct baum *links;
   struct baum *rechts;
}

Hier sehen Sie eine Variante des zuvor gezeigten Listenbeispiels, bei der Eingabewerte zwischen 1 und 100 erwartet werden. Sie werden jeweils nach ihrer Größe in den Binärbaum einsortiert; bei der Ausgabe wird der Baum rekursiv von ganz links nach ganz rechts durchwandert.

#include <stdio.h>
#include <mem.h>

struct baum {
   int wert;
   struct baum *links;
   struct baum *rechts;
};
void zeige_baum (struct baum *aktuell) {
   if (aktuell->links)
      zeige_baum (aktuell->links);
   printf ("%d\n", aktuell->wert);
   if (aktuell->rechts)
      zeige_baum (aktuell->rechts);
}

int main (int argc, char *argv[]) {
   int i;
   int w;
   /* Element erzeugen: */
   struct baum *aktuell = malloc (sizeof *aktuell);
   /* Anfangsposition merken: */
   struct baum *erster = aktuell;
   /* mittleren Wert speichern: */
   aktuell->wert = 50;
   printf ("Bitte 10 Werte von 1 bis 100 eingeben.\n");
   for (i = 0; i < 10; i++) {
      printf ("%2d. ", i + 1);
      scanf ("%d", &w);
      /* Wert einsortieren */
      aktuell = erster;
      for ( ; ; ) {
         if (w <= aktuell->wert) {
            if (aktuell->links) {
               aktuell = aktuell->links;
            } else {
               aktuell->links =
                    malloc (sizeof *aktuell);
               aktuell = aktuell->links;
               break;
            }
         }
         else {
            if (aktuell->rechts) {
               aktuell = aktuell->rechts;
            } else {
               aktuell->rechts =
                    malloc (sizeof *aktuell);
               aktuell = aktuell->rechts;
               break;
            }
         }
      }
      aktuell->wert = w;
   }
   printf ("\n");
   printf ("Ihre Eingaben:\n");
   zeige_baum (erster);
   return 0;
}

Interessant ist, wie dieses Programm die einzelnen Werte in den Baum einsortiert. Für jedes einzelne Element wird bei der Wurzel des Baums begonnen: Wenn das Element kleiner oder gleich dem Wert an der Wurzel ist, wird weiter nach links gewandert, andernfalls weiter nach rechts. Auf diese Weise sucht sich jeder Wert seinen passenden Platz im Baum. Je kleiner ein Wert ist, desto weiter links steht er im fertigen Baum.

Die rekursive Funktion zeige_baum() wird zunächst mit der Wurzel des Baums aufgerufen. Falls das Baumelement, mit dem sie aufgerufen wurde, einen linken Nachfolger hat, wird sie zuerst für diesen aufgerufen. Anschließend wird der Wert das Element selbst ausgegeben, schließlich wird die Funktion noch einmal für den rechten Nachfolger aufgerufen, falls er existiert. Auf diese Weise wird der Baum nacheinander von links nach rechts ausgegeben.

Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.