Implementieren Wörterbuch Java

Question

mit

Aufgabe Wörterbuch ADT

• Die Wörterbuch ADT Modelle eine durchsuchbare Sammlung von Schlüsselelement Einträge
• Mehrere Elemente mit dem gleichen Schlüssel erlaubt sind
• Anwendungen: Wort-Definition-Paare

Wörterbuch ADT Methoden:

• find (k): Wenn das Wörterbuch einen Eintrag mit dem Schlüssel k hat, kehrt er, sonst, gibt null zurück
• findAll (k): gibt einen Iterator aller Einträge mit Schlüssel k
• Einsatz (k, o): Einsätze und gibt den Eintrag (k, o)
• remove (e): den Eintrag e aus dem Wörterbuch
• size(), isEmpty() entfernen

Betrieb Ausgang Wörterbuch

insert(5,A) (5,A) (5,A) 
insert(7,B) (7,B) (5,A),(7,B) 
insert(2,C) (2,C) (5,A),(7,B),(2,C) 
insert(8,D) (8,D) (5,A),(7,B),(2,C),(8,D) 
insert(2,E) (2,E) (5,A),(7,B),(2,C),(8,D),(2,E) 
find(7) (7,B) (5,A),(7,B),(2,C),(8,D),(2,E) 
find(4) null (5,A),(7,B),(2,C),(8,D),(2,E) 
find(2) (2,C) (5,A),(7,B),(2,C),(8,D),(2,E) 
findAll(2) (2,C),(2,E) (5,A),(7,B),(2,C),(8,D),(2,E) 
size() 5 (5,A),(7,B),(2,C),(8,D),(2,E) 
remove(find(5)) (5,A) (7,B),(2,C),(8,D),(2,E) 
find(5) null (7,B),(2,C),(8,D),(2,E) 

Detaillierte Erklärung: NO

Answer 1

Java hat bereits eine Sammlung, die fast alles hat, was Sie brauchen. Sie müssen nur eine Methode hinzufügen. Für Anfänger erkunden Sie java.util.Collection ... Klassen. Erweitern Sie dann einen, um die erforderlichen Methoden hinzuzufügen. Wenn es richtig gemacht wird, ist es nur eine Frage von ein paar Dutzend Zeilen.

Für mich ist der einfachste Weg zu gehen mit Map<Object, Set<Object>>. Das Schwierige ist, einen Iterator zurückzugeben.

EDIT:

Auf der anderen Seite ich mit diesem Entry.java gehen würde:

public class Entry<K, V> { 

    K key; 
    V value; 

    public Entry(K key, V value) { 
     this.key = key; 
     this.value = value; 
    } 

    public K key() { 
     return key; 
    } 

    public V value() { 
     return value; 
    } 

    @Override 
    public String toString() { 
     return "(" + key + ", " + value + ")"; 
    } 

    // Methods needed to correctly behave in containers like sets, hashmaps: 
    // (I generated those automatically in NetBeans) 
    @Override 
    public boolean equals(Object obj) { 
     if (obj == null) 
      return false; 
     if (getClass() != obj.getClass()) 
      return false; 
     final Entry<K, V> other = (Entry<K, V>) obj; 
     if (this.key != other.key && (this.key == null || !this.key.equals(other.key))) 
      return false; 
     if (this.value != other.value && (this.value == null || !this.value.equals(other.value))) 
      return false; 
     return true; 
    } 

    @Override 
    public int hashCode() { 
     int hash = 7; 
     hash = 23 * hash + (this.key != null ? this.key.hashCode() : 0); 
     hash = 23 * hash + (this.value != null ? this.value.hashCode() : 0); 
     return hash; 
    } 
} 

... auch mit diesem: Dictionary.java

import java.util.Iterator; 
import java.util.LinkedList; 
import java.util.List; 

public class Dictionary<K, V> { 

    private List<Entry<K, V>> set; 

    public Dictionary() { 
     this.set = new LinkedList<Entry<K, V>>(); 
    } 

    /** 
    * find(k): if the dictionary has an entry with key k, returns it, else, returns null 
    */ 
    public Entry<K, V> find(K key) { 
     // for all entries in set... 
     // check if key mathches 
     //  - if it does than return it 

     // else 
     return null; 
    } 

    /** 
    * findAll(k): returns an iterator of all entries with key k 
    * @return 
    */ 
    public Iterator<Entry<K, V>> findAll(K key) { 
     // make a temporary list 
     // for all entries in set... 
     // check if key matches 
     //  - if it does than add it to temporary list 

     // return the temporary list iterator (list.iterator()) 
     return null; 
    } 

    /** 
    * insert(k, o): inserts and returns the entry (k, o) 
    */ 
    public Entry<K, V> insert(K key, V value) { 
     // obvious 
     return null; 
    } 

    /** 
    * remove(e): remove the entry e from the dictionary 
    */ 
    public Entry<K, V> remove(Entry<K, V> entry) { 
     return entry; 
    } 

    public int size() { 
     return set.size(); 
    } 

    public boolean isEmpty() { 
     return size() == 0; 
    } 

    @Override 
    public String toString() { 
     return set.toString(); 
    } 
} 

... und diese DictionaryTest.java:

public class DictionaryTest { 

    static Dictionary<Integer, Character> dict = new Dictionary<Integer, Character>(); 

    public static void main(String[] args) { 

     /* 

     Test cases: 

     1. insert(5,A) (5,A) (5,A) 
     2. insert(7,B) (7,B) (5,A),(7,B) 
     3. insert(2,C) (2,C) (5,A),(7,B),(2,C) 
     4. insert(8,D) (8,D) (5,A),(7,B),(2,C),(8,D) 
     5. insert(2,E) (2,E) (5,A),(7,B),(2,C),(8,D),(2,E) 
     6. find(7) (7,B) (5,A),(7,B),(2,C),(8,D),(2,E) 
     7. find(4) null (5,A),(7,B),(2,C),(8,D),(2,E) 
     8. find(2) (2,C) (5,A),(7,B),(2,C),(8,D),(2,E) 
     9. findAll(2) (2,C),(2,E) (5,A),(7,B),(2,C),(8,D),(2,E) 
     10. size() 5 (5,A),(7,B),(2,C),(8,D),(2,E) 
     11. remove(find(5)) (5,A) (7,B),(2,C),(8,D),(2,E) 
     12. find(5) null (7,B),(2,C),(8,D),(2,E) 
     */ 

     // Test case #1: 
     test("insert(5,A)", dict.insert(5, 'A')); 

     // Test case #2: 
     test("insert(7,B)", dict.insert(7, 'B')); 

     // Test case #3: 
     test("insert(2,C)", dict.insert(2, 'C')); 

     // ... 

     // Test case #6: 
     test("find(7))", dict.find(7)); 

     // implement all and check them during implementation 


    } 

    private static void test(String string, Object result) { 
     System.out.print(string + " "); 
     System.out.print(result); 
     System.out.println(" " + dict); 
    } 
} 

Answer 2

Ich schlage vor, Hash-Tabellen mit separaten Verkettung zu lesen. Hash-Tabellen sind eine gute Möglichkeit, Wörterbücher zu implementieren. Es gibt MIT-Vorträge in der offenen Kursware für dieses. Sieh das http://en.wikipedia.org/wiki/Hash_table für mehr Details