Rheinwerk Computing < openbook > Rheinwerk Computing - Professionelle Bücher. Auch für Einsteiger.
Professionelle Bücher. Auch für Einsteiger

Kompendium der Informationstechnik  von Sascha Kersken
EDV-Grundlagen, Programmierung, Mediengestaltung
(Die Neuauflage ist erschienen als: "Handbuch für Fachinformatiker")
Buch: Kompendium der Informationstechnik
gp Kapitel 6 Konzepte der Programmierung
  gp 6.1 Algorithmen und Datenstrukturen
    gp 6.1.1 Ein einfaches Praxisbeispiel
    gp 6.1.2 Sortier-Algorithmen
    gp 6.1.3 Such-Algorithmen
    gp 6.1.4 Ausgewählte Datenstrukturen
  gp 6.2 Reguläre Ausdrücke
    gp 6.2.1 Muster für reguläre Ausdrücke
    gp 6.2.2 Programmierung mit regulären Ausdrücken
  gp 6.3 Systemnahe Programmierung
    gp 6.3.1 Prozesse und Pipes
    gp 6.3.2 Threads
  gp 6.4 GUI- und Grafikprogrammierung
    gp 6.4.1 Zeichnungen und Grafiken erstellen
    gp 6.4.2 Animation
    gp 6.4.3 Programmierung fensterbasierter Anwendungen
    gp 6.4.4 Java-Applets
  gp 6.5 Zusammenfassung

gp

Prüfungsfragen zu diesem Kapitel (extern)

Kapitel 6 Konzepte der Programmierung

Wir werden Sie ermutigen, sich die drei großen Tugenden eines Programmierers zu eigen zu machen: Faulheit, Ungeduld und Hochmut.
– Larry Wall, Erfinder von Perl

Nachdem Sie im vorigen Kapitel die grundlegende Syntax der Programmierung in drei verschiedenen Sprachen erlernt haben, ist es nun 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 bis hin zur GUI-Anwendungsentwicklung.

Die Implementierung der verschiedenen Beispiele erfolgt jeweils in einer der drei im vorigen Kapitel vorgestellten Programmiersprachen; es wird für jede Aufgabe eine passende Sprache ausgewählt.


Rheinwerk Computing

6.1 Algorithmen und Datenstrukturen  downtop

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 mit Hilfe der Datentypen einer Programmiersprache so genannte 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.


Rheinwerk Computing

6.1.1 Ein einfaches Praxisbeispiel  downtop

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. Wenn er den Wert 1 hat, werden die beiden Zahlen als teilerfremd bezeichnet. Abbildung 6.1 zeigt einen Ansatz für ein Flussdiagramm, das eine mögliche Lösung beschreibt.


Abbildung 6.1   Flussdiagramm für einen Algorithmus zur Ermittlung des GGT

Abbildung
Hier klicken, um das Bild zu Vergrößern


Im Grunde werden also Schritt für Schritt alle in Frage kommenden Werte ausprobiert. Begonnen wird beim Quotienten der größeren Zahl. Listing 6.1 zeigt eine Implementierung dieses Algorithmus in Java.

Listing 6.1   Ein einfacher Algorithmus zur Ermittlung des GGT

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.


Rheinwerk Computing

6.1.2 Sortier-Algorithmen  downtop

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 Unterabschnitt 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. Wenn 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.

BubbleSort in Perl

Listing 6.2 zeigt eine Implementierung von BubbleSort als Perl-Subroutine, die eine Listenreferenz entgegennimmt und die zugrunde liegende Liste nach diesem Schema sortiert.

Listing 6.2   BubbleSort als Perl-Subroutine

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:

($$listref[$i], $$listref[$i + 1])
     = ($$listref[$i + 1], $$listref[$i]);

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.

BubbleSort in Java

Zu Vergleichszwecken sehen Sie in Listing 6.3 eine weitere Implementierung von BubbleSort als Java-Methode, die ein Array von int-Werten sortiert.

Listing 6.3   BubbleSort als Java-Methode

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

Rekursion Im nächsten Unterabschnitt wird ein sehr komplexer, aber erheblich effizienterer Sortier-Algorithmus vorgestellt. Dieser verwendet die besondere Technik der Rekursion, bei der eine Funktion sich selbst mit geänderten Parametern aufruft. Rekursion ist immer dann nützlich, wenn Sie gleichartige, ineinander verschachtelte Aufgaben lösen müssen. Beispielsweise lässt sich die Fakultät eines Werts sehr leicht rekursiv berechnen. Die Fakultät n! einer natürlichen Zahl n ist das Ergebnis der Multiplikation 1 x 2 x 3 x ... x n. Durch Rekursion lässt sich das Problem schrittweise reduzieren, beispielsweise gilt im ersten Schritt: n! = n * (n – 1)!. Das folgende Beispiel zeigt eine rekursive C-Funktion, die auf diese Weise die Fakultät eines übergebenen Werts berechnet: int fakultaet (int n)
{
if (i > 1)
return n * fakultaet (n - 1);
else
return 1;
} Solange das übergebene n noch größer als 1 ist, wird das Problem an einen weiteren Aufruf von fakultaet() delegiert; das aktuelle n wird mit dem Rückgabewert dieses Aufrufs multipliziert. Die Aufrufe werden schließlich von innen nach außern abgearbeitet: Der letzte oder innerste Aufruf gibt 1 zurück, die mit der 2 des darüber liegenden Aufrufs multipliziert wird und so weiter. Der Gegenbegriff zur Rekursion ist übrigens Iteration. Natürlich lässt sich die Fakultät auch iterativ (in einer Schleife) berechnen, allerdings ist der Aufwand größer und die Schreibweise umständlicher: 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 aufwändigen Initialisierung nicht ausspielen.

QuickSort-Funktionsweise

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 des Medians 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. Listing 6.4 zeigt eine Implementierung in Java.

Listing 6.4   QuickSort als Java-Methode

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) {
   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 > 1 && 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 weiter oben 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);

Rheinwerk Computing

6.1.3 Such-Algorithmen  downtop

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. Listing 6.5 zeigt 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, wenn der gesuchte Wert nicht im Array vorkommt.

Listing 6.5   Lineare Suche als Java-Methode

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

Dieser Code müsste 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.

In Listing 6.6 finden 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, wenn das Elements nicht gefunden wird.

Listing 6.6   Die binäre Suche als Java-Methode

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);
}

Rheinwerk Computing

6.1.4 Ausgewählte Datenstrukturen  toptop

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 nun 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. Mit Hilfe 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. Mit Hilfe 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.

Listen in C

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. 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 diesen 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.

Listing 6.7 ist 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.

Listing 6.7   Arbeiten mit einer Liste in C

#include <stdio.h>
#include <mem.h>
 
struct liste {
   int wert;
   struct liste *nachfolger;
};
 
int main (int argc, char *argv[]) {
   int i;
   int w;
   /* Element erzeugen */
   struct liste *aktuell = (struct liste *)malloc();
   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 = (struct liste *)malloc();
      aktuell = aktuell->nachfolger;
   }
   aktuell = erster;
   for (i = 0; i < 10; i++) {
      printf ("%d\n", aktuell->wert);
      aktuell = aktuell->nachfolger;
   }
   return 0;  }

malloc( )

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 mem.h definiert. malloc() besitzt einen etwas merkwürdigen Datentyp: void *. Dies ist nicht etwa ein »Zeiger auf gar nichts«, sondern ein Zeiger auf einen beliebigen Datentyp. Mit Hilfe von Typecasting können Sie den korrekten Datentyp auswählen, damit die richtige Menge Speicher reserviert wird.

In diesem Beispielprogramm werden zwei verschiedene Zeiger auf ein Listenelement verwendet, damit das erste Element der Liste auch dann noch verfügbar ist, wenn 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. Darauf kann hier allerdings nicht näher eingegangen werden.

Listing 6.8 zeigt 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.

Listing 6.8   Ein Satz-Umkehrer in Perl

#!/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:

push (@rwords, pop (@words));

Mit Hilfe von pop wird jeweils das letzte Zeichen der Liste @words entnommen und mittels 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. Mit Hilfe von Binärbäumen werden beispielsweise schnelle Such- und Sortierverfahren implementiert.

Binärbäume in C

In 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;
}

Listing 6.9 zeigt eine Variante des Programms aus Listing 6.7, 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.

Listing 6.9   Eine einfache Binärbaum-Anwendung in C

#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 = (struct baum *)malloc();
   /* 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 = (struct baum *)malloc();
               aktuell = aktuell->links;
               break;
            }
         }
         else {
            if (aktuell->rechts) {
               aktuell = aktuell->rechts;
            } else {
               aktuell->rechts = (struct baum *)malloc();
               aktuell = aktuell->rechts;
               break;
            }
         }
      }
      aktuell->wert = w;
   }
   printf ("\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 sie noch einmal für den rechten Nachfolger aufgerufen, falls er existiert. Auf diese Weise wird der Baum nacheinander von links nach rechts ausgegeben.

  
Wie hat Ihnen das <openbook> gefallen?
Ihre Meinung


IT-Handbuch
für Fach-
informatiker

Java ist auch
eine Insel

Linux
Handbuch

Computer
Netzwerke

Schrödinger
lernt HTML5,
CSS3 und
JavaScript
Versandkostenfrei bestellen in Deutschland und Österreich
Info





Copyright © Rheinwerk Verlag GmbH 2004
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das <openbook> denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.


[Rheinwerk Computing]

Rheinwerk Verlag GmbH, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, service@rheinwerk-verlag.de