问用Java实现字典
EN

Stack Overflow用户

提问于 2011-01-02 10:03:20

回答 2查看 26.9K关注 0票数 6

任务字典ADT

字典ADT用相同的键建立可搜索的密钥元素entries

Multiple项的集合是allowed

Applications:字定义对

。

字典ADT方法：

查找(K)：如果字典中有一个键为k的条目，则返回它，否则，返回null

findAll(k)：返回所有条目的迭代器，其中包含键k

insert(k，o)：插入并返回条目(k，o)

remove(e)：从dictionary

size()，isEmpty()

中删除条目e)

操作输出字典

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)

详细解释:否

java

dictionary

map

回答 2

Stack Overflow用户

发布于 2011-01-02 10:07:44

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