14.5 Der ADT Dictionary

Ein Dictionary oder Lexikon ist ein Speicher für Strings oder komplexere Datensätze. Hier die allgemeine Definition des ADT Dictionary:

Sie sehen, das hier überhaupt keine Angaben gemacht werden, wie und wo die hinzugefügten Elemente im Lexikon gespeichert werden oder ob die Elemente innerhalb des Lexikons irgendwie sortiert werden. Allerdings ist - im Gegensatz zu einem Stapelspeicher (Stack) oder einem Schlangenspeicher (Queue) ein direkter Zugriff auf die Elemente erlaubt. Mit Delete(x) beispielsweise wird das Element x direkt gelöscht, falls es vorhanden ist. Bei einem Stack kann man dagegen nur das zuletzt hinzugefügte ("oberste") Element, bei einer Schlange nur das zuerst hinzugefügte ("vorderste") Element löschen.

Lösungsvorschlag auf den Lehrerseiten / nähere Infos dazu

Ein Lexikon mit allgemeinen Objekten

Die nächste Übung ist eher für Experten gedacht. Und zwar sollen Sie ein Lexikon programmieren, das beliebige Datentypen speichern kann. Dazu müssen wir aber vorher noch ein bisschen ausholen.

Betrachten Sie dazu die ersten Zeilen einer Klasse Dictionary:

public class Dictionary
{
    DictEntry[] liste;
    int      anzahl;
    
    public Dictionary()
    {
       liste    = new DictEntry[100];
       anzahl   = 0;
    }
    ...

Das Lexikon enthält einen Array von Objekten der Klasse DictEntry (Kurzform für dictionary entry, also Lexikoneintrag). Das ist keine von Java vorgegebene Klasse, sondern eine von mir selbst erstellte. Hier der vollständige Quelltext dieser Klasse:

public abstract class DictEntry
{
   
    public abstract String getString();
    
    public abstract int compareTo(DictEntry b);
}

Das ist kein sehr langer Quelltext. Die Klasse DictEntry ist eine sogenannte abstrakte Klasse, was man leicht an dem Schlüsselwort abstract erkennt, das sowohl die Klasse selbst wie auch die beiden Methoden kennzeichnet.

Eine abstrakte Klasse muss mindestens eine abstrakte Methode enthalten. Eine abstrakte Methode ist eine Art Platzhalter für "richtige" Methoden. Tochterklassen von DictEntry müssen die abstrakten Methoden dann durch "richtige" Methoden überschreiben.

Abstrakte Methoden erkennt man daran, dass sie lediglich aus dem Methodenkopf (mit eventuellen Parametern) bestehen, der sogenannten Signatur, gefolgt von einem Semikolon. Ein Methodenrumpf ist nicht vorhanden.

Mit diesem Quelltext schreibt man allen möglichen noch zu entwickelnden Tochterklassen von DictEntryvor, dass sie eine Methode getString() sowie eine Methode compareTo() zur Verfügung stellen müssen.

Die Methode compareTo() wird benötigt, um zwei Lexkoneinträge miteinander zu vergleichen. Wie sollte man sonst beispielsweise eine member()-Methode implementieren, wenn man keine Möglichkeit hat, festzustellen, ob ein gegebenes Element x mit einem bereits vorhandenem Element y übereinstimmt.

Schauen wir uns nun eine Tochterklasse von DictEntry an, die Klasse Bruch:

public class Bruch extends DictEntry
{
    int nenner, zaehler;
    
    public Bruch(int z, int n)
    {
        nenner = n;
        zaehler = z;
    }
    
    public String getString()
    {
       return zaehler + "/" + nenner;
    }
    
    public int compareTo(DictEntry neu)
    {
       Bruch b = (Bruch) neu;
       
       double wert1 = (double) zaehler/nenner;
       double wert2 = (double) b.zaehler/b.nenner;

       if (wert1 == wert2) 
          return 0;
       else if (wert1 < wert2)
          return -1;
       else
          return 1;
    }
}

Die abstrakte Methode getString() der abstrakten Mutterklasse wird überschrieben, so dass der Zähler und der Nenner des Bruchs von anderen Klassen beispielsweise im System.out.println()-Befehl angezeigt werden können.

Die Methode compareTo() wird ebenfalls überschrieben. Mit dieser Methode wird der objekt-eigene Bruch mit dem als Parameter übergebenem Bruch neu verglichen. Sind beide Brüche gleich, wird der Wert 0 zurückgegeben. Das ist auch der Fall, wenn beispielsweise die Brüche 1/5 und 2/10 verglichen werden, denn der Zahlenwert beider Brücke ist identisch 0,2.

Ist der "eigene" Bruch kleiner als der übergebene Bruch, wird -1 zurück gegeben, andernfalls +1.

Kommen wir nun zur Testklasse:

public class Test
{
    Dictionary lexikon;
    
    public Test()
    {
       lexikon = new Dictionary();
       lexikon.insert(new Bruch(1,4));
       lexikon.insert(new Bruch(1,3));
       lexikon.insert(new Bruch(1,2));
       lexikon.insert(new Bruch(1,5));
       lexikon.insert(new Bruch(2,3));
       lexikon.show();
       
       check(new Bruch(1,2));
       check(new Bruch(1,7));
       check(new Bruch(2,10));
       check(new Bruch(2,5));       
    }
    
    public void check(Bruch b)
    {
       if (lexikon.member(b))
          System.out.println("Der Bruch "+b.getString()+ " ist im Lexikon enthalten"); 
       else
          System.out.println("Der Bruch "+b.getString()+ " ist nicht im Lexikon enthalten"); 
    }
}

Dieser Quelltext zeigt auch schön, wie man die methode getString() der Klasse Bruch sinnvoll einsetzen kann.

Hier die Ausgabe dieser Klasse, direkt aus der Konsole kopiert:

Das Lexikon enthaelt 5 Eintraege: 
1/4
1/3
1/2
1/5
2/3
=============================
Der Bruch 1/2 ist im Lexikon enthalten
Der Bruch 1/7 ist nicht im Lexikon enthalten
Der Bruch 2/10 ist im Lexikon enthalten
Der Bruch 2/5 ist nicht im Lexikon enthalten

Der Bruch 2/10 ist im Lexikon enthalten, denn er ist ja identisch mit dem Bruch 1/5.

Lösungsvorschlag auf den Lehrerseiten / nähere Infos dazu