Home > Informatik > Stufe Q1 > ADTs

14.5 Der ADT Dictionary

Allgemeines - Abstrakte Datentypen - Stack - Queue - Dictionary - List - ADTs im Abitur - Axiome

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

Der ADT Dictionary wird durch folgende Operationen definiert:

  • Init(): Erzeugt eine leeres Lexikon.
  • Insert(x): Das Element x wird hinzugefügt.
  • Delete(x): Das Element x wird entfernt.
  • Member(x): Falls x im Lexikon enthalten ist, wird TRUE zurück geliefert, ansonsten FALSE.
  • Empty(): Falls das Lexikon leer ist, wird TRUE zurückgeliefert, sonst FALSE.
  • Length(): Liefert die Anzahl der enthaltenen Elemente zurück.

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 oberste Element, bei einer Schlange nur das vorderste Element löschen.

Übung 14.5-1 (7 Punkte)

Entwickeln Sie eine Klasse Dictionary, welche den ADT Dictionary realisiert. Schreiben Sie anschließend ein Testprogramm, das die Operationen der Klasse Dictionary testet. Als Inhaltselemente der Klasse Dictionary können Sie Objekte der Klasse String verwenden.

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, der sogenannten Signatur, bestehen, gefolgt von einem Semikolon. Ein Methodenrumpf ist nicht vorhanden. Mit diesem Quelltext schreibt man den 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 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. Und die Methode compareTo() wird ebenfalls überschrieben. Mit dieser Methode wird der 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. Ist der "eigene" Bruch kleiner als der übergebene Bruch neu, 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.

Übung 14.5-2 (5 Punkte)

Verändern Sie eine Klasse Dictionary so, dass Objekte von Tochterklassen von DictEntry (wie zum Beispiel Bruch) in ihr gespeichert werden können. Testen Sie die Klasse Dictionary mit einem Testprogramm bzw. einer Testklasse.

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

Seitenanfang -
Allgemeines - Abstrakte Datentypen - Stack - Queue - Dictionary - List - ADTs im Abitur - Axiome