java - 使用Java实现字典

Question

任务 字典 ADT

• 字典 ADT 为可搜索的关键元素条目集合建模
• 允许多个项目具有相同的键
• 应用:词定义对

字典式 ADT 方法:

• find(k):如果字典中有一个键为 k 的条目，则返回它，否则，返回 null
• findAll(k): 返回所有具有键 k 的条目的迭代器
• insert(k, o):插入并返回条目(k, o)
• remove(e):从字典中删除条目e
• size(), isEmpty()

操作输出字典

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)

详细解释:无

Answer 1

Java 已经有了一个集合，它几乎拥有你所需要的一切。您只需要添加一种方法。对于初学者，探索 java.util.Collection... 类。然后扩展一个以添加所需的方法。如果处理得当，这只是几十行的问题。

对我来说，最简单的方法是使用 Map<Object, Set<Object>> .棘手的事情是返回一个迭代器。

编辑:

另一方面，我会选择这个 Entry.java :

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

...还有这个: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();
    }
}

...，还有这个 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);
    }
}