使用Java实现字典

Question

任务词典ADT

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

字典ADT方法:

• find(k):如果字典有一个带有键k的条目,则返回它,否则返回null
• findAll(k):返回键k的所有条目的迭代器
• insert(k,o):insert并返回条目(k,o)
• 删除(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);
    }
}