Kapitel 11 Datenstrukturen und Algorithmen

Einen Rat befolgen heißt,
die Verantwortung verschieben.
– Urzidil

Algorithmen¹  sind ein zentrales Thema der Informatik. Ihre Erforschung und Untersuchung nimmt dort einen bedeutenden Platz ein. Algorithmen operieren nur dann effektiv mit Daten, wenn diese geeignet strukturiert sind. Schon das Beispiel Telefonbuch zeigt, wie wichtig die Ordnung der Daten nach einem Schema ist. Die Suche nach einer Telefonnummer bei gegebenem Namen gelingt schnell, jedoch ist die Suche nach einem Namen bei bekannter Telefonnummer ein mühseliges Unterfangen. Datenstrukturen und Algorithmen sind also eng miteinander verbunden und die Wahl der richtigen Datenstruktur entscheidet über effiziente Laufzeiten; beide erfüllen alleine nie ihren Zweck. Leider ist die Wahl der »richtigen« Datenstruktur nicht so einfach, wie es sich anhört, und eine Reihe von schwierigen Problemen in der Informatik sind wohl noch nicht gelöst, da eine passende Datenorganisation bis jetzt nicht gefunden wurde.

Die wichtigsten Datenstrukturen wie Liste, Vektor und Hashtabelle sollen in diesem Kapitel vorgestellt werden. In der zweiten Hälfte des Kapitels wollen wir uns dann den Algorithmen stärker widmen, die auf diesen Datenstrukturen operieren.

11.1 Mit einem Iterator durch die Daten wandern

Wir wollen bei den Datenstrukturen eine Möglichkeit kennen lernen, wie sich die gespeicherten Daten unabhängig von der Implementierung immer mit derselben Technik abfragen lassen. Bei den Datenstrukturen handelt es sich meistens um Daten in Arrays, Bäumen oder Ähnlichem. Oft wird nur die Frage nach der Zugehörigkeit eines Werts zum Datenbestand gestellt, also: »Gehört das Wort dazu?«. Dieses Wortproblem ist durchaus wichtig, aber die Möglichkeit, die Daten in irgendeiner Weise aufzuzählen, ist nicht minder bedeutend. Bei Arrays können wir über den Index auf die Elemente zuzugreifen. Da wir jedoch nicht immer ein Array als Datenspeicher haben und uns auch die objektorientierte Programmierung verbietet, hinter die Kulisse zu sehen, benötigen wir möglichst einen allgemeineren Weg. Hier bieten sich Enumeratoren an. Das Interface Enumeration bietet die zwei Funktionen hasMoreElements() und nextElement() an, mit denen durch eine Datenstruktur iteriert werden kann – wir sprechen in diesem Fall auch von einem Iterator.²  Bei jedem Aufruf von nextElement() erhalten wir ein weiteres Element der Datenstruktur. Im Gegensatz zum Index eines Felds können wir nicht noch einmal ein Objekt auslesen oder hin und her springen. Wollten wir ein Element zweimal besuchen, zum Beispiel von rechts nach links noch einmal durchwandern, dann müssen wir wieder ein neues Enumeration-Objekt erzeugen.

Damit wir durch eine Datenstruktur iterieren können, muss das Objekt beide Funktionen so implementieren, dass sie die Daten ihrer zugrunde liegenden Datenstruktur preisgeben. Wenn wir später die anderen Datenstrukturen wie Vector oder Stack kennen lernen, so werden wir sehen, dass auch sie das Interface Enumeration implementieren.

boolean hasMoreElements() Testet, ob noch ein weiteres Element aufgezählt werden kann.3

Object nextElement() Liefert das nächste Element der Enumeration zurück. Diese Funktion kann eine NoSuch ElementException auslösen, wenn nextElement() aufgerufen wird und das Ergebnis false beim Aufruf von hasMoreElements() ignoriert wird.

Die Aufzählung erfolgt meistens über einen Zweizeiler: Die Datenstruktur ds besitzt eine Methode elements(), die ein Enumeration-Objekt zurückgibt, welches die Elemente von ds aufzählen kann.

for ( Enumeration e = ds.elements(); e.hasMoreElements(); )
  System.out.println( e.nextElement() );

11.1.1 Bauernregeln aufzählen 

Doch nun zu einem Beispiel. Es zeigt die Möglichkeit, Bauernregeln⁴  aufzuzählen. Die Funktion nextElement() löst eine NoSuchElementException aus, wenn das Ergebnis false von hasMoreElements() ignoriert wird. NoSuchElementException ist eine RuntimeException, sodass sie nicht ausdrücklich aufgefangen werden muss.

Listing 11.1   Bauernregeln.java, Teil 1

import java.util.*;

class BauernregelnEnumerator implements Enumeration
{
  private int counter = 0;

  private String slogan[] =
  {
    "Der dümmste Bauer erntet die dicksten Kartoffeln.",
    "Wenn der Hahn kräht auf dem Mist, dann ändert sich "+
      "das Wetter oder es bleibt wie es ist.",
    "Ist der Juni kalt und nass, füllt's dem Bauern Scheun' "+
 "und Fass.",
    "Sind die Hühner platt wie Teller, war der Bauer "+
      "wieder schneller.",
    "Jodelt laut die Magd im Stall, kriegt die Kuh 'nen "+
 "Herzanfall",
    "Regnet es ins Hühnerhaus, holt der Hahn das Shampoo raus!",
    "Liegt der Bauer im Mist, weiß er nicht wie spät es ist.",
 "Liegt der Bauer tot im Zimmer, lebt er nimmer.",
    "Bauen im April die Schwalben, gibt es viel Futter, Korn "+
 "und Kalben."
  };

  public boolean hasMoreElements()

  {
    return ( counter < slogan.length );
  }

  public Object nextElement()

  {
    if ( !hasMoreElements() )
      throw new
        NoSuchElementException("Keine Bauernregeln mehr!");

    return slogan[counter++];
  }
}

Listing 11.2   Bauernregeln.java, Teil 2

public class Bauernregeln
{
 public static void jederZweite( Enumeration e )
 {
 boolean toggle = true;

 while ( e.hasMoreElements() )
 {
 if ( toggle ^= true )
 e.nextElement();

 System.out.println( e.nextElement() );
 }
 }

   public static void main( String args[] )
  {
 BauernregelnEnumerator e1 = new BauernregelnEnumerator();

 while ( e1.hasMoreElements() )
 System.out.println( e1.nextElement() );

 System.out.println();

 BauernregelnEnumerator e2 = new BauernregelnEnumerator();
 jederZweite( e2 );
  }
}

Schön zu erkennen ist der Vorteil der Schnittstellen an der Funktion jederZweite(). Es ist der Funktion egal, was für Objekte reinkommen, hautsache sie sind vom Typ Enumeration.

¹   Das Wort »Algorithmus« geht auf den im 9. Jahrhundert lebenden persisch-arabischen Mathematiker Ibn Mûsâ Al-Chwârismî zurück.

²   Es gibt auch eine Schnittstelle mit dem Namen »Iterator«, die eine neuere Variante von Enumeration ist.

³   Enumeratoren können nicht serialisiert werden, da diese die Schnittstelle Serializable nicht implementieren.

⁴   Mehr von diesen nicht ganz ernst zu nehmenden Bauernregeln gibt’s unter http://www.butterbrot.de/wahnsinn/bauer.htm.