java - 数据结构与算法实现-字典

Question

我已经用 Vector(Array) 实现了 Dictionary。在数组中我存储一个字符串数据。现在我有了定位方法。但我想在某个位置检索数据。方法是什么？谢谢。

private int findpositionProfile(String smkey){      
    DictionaryProfile p = new DictionaryProfile(smkey,null);  
    return data.getposi(p);  
}


public Profile getProfile(int i){
//  DictionaryProfile p = new DictionaryProfile(null,null);
    return data.get(i);

这是行不通的

public class Dictionary {

private Vector data;
private Vector data1;

public Dictionary() {
    data = new Vector(100);
    data1 = new Vector(100);
}

public void addProfile(String smkey, Profile smvalue) {
    DictionaryProfile d = new DictionaryProfile(smkey, smvalue);
    if (data.getposi(d) == -1) {
        data.addLast(d);
    }
    data.replace(d);
}
public void addCorporate(String smkey, CorporateProfile smvalue) {
    DictionaryCorporate d = new DictionaryCorporate(smkey, smvalue);
    if (data1.getposi(d) == -1) {
        data1.addLast(d);
    }
    data1.replace(d);
}

private int findpositionProfile(String smkey) {
    DictionaryProfile p = new DictionaryProfile(smkey,null);
    return data.getposi(p);
}
public CorporateProfile getCorporate(int i){
    return data.get(i);
}
public Profile getProfile(int i){
    DictionaryProfile p = new DictionaryProfile(null,null);
    return data.get(i);
}

我的字典对::

public class DictionaryProfile implements Comparable
    {
    private String userName ;
    private Profile completeProfile ;

    public DictionaryProfile ( String name,Profile p){
        userName = name;
        completeProfile = p;
    }

    public String getUserName(){
        return userName;
    }

    public Profile getProfile(){
        return completeProfile;
    }

    public void setUsename ( String newname ){
        userName= newname;
    }

    public void setProfile ( Profile pro ){
        completeProfile = pro;
    }

    public int compareTo(Object obj){
        DictionaryProfile dp = (DictionaryProfile) obj;
        return (this.getUserName()).compareTo(dp.getUserName());
    }

}

Answer 1

没有人应该使用 JDK 1.0 vintage Vector类(class)。这看起来不像一个通用的 Dictionary对我来说是 ADT。

这个方法毫无意义:

public Profile getProfile(int i){
    DictionaryProfile p = new DictionaryProfile(null,null);
    return data.get(i);
}

局部变量 p 被实例化，从未使用过，并且在超出范围时符合 GC 条件。数据是 Vector控股型Object .您希望在哪里获得 Profile来自？

这段代码毫无意义。

除非您传递越界的索引，否则这将起作用。

public Profile getProfile(int i){
    return (Profile) data.get(i);
}

这些都没有描述 Dictionary作品。它是 Map 的同义词，它有一个键/值对。您的代码没有这样做。不对键或值使用泛型。你为什么要这样做而不是只使用 Map<K, V> ？

我认为你应该从这个开始:

package collections;   

public interface Dictionary<K, V> {
    V get(K key);
    V put(K key, V value);
    boolean containsKey(K key);
    int size();    
}

您的 key 应该是不可变的。

这是我认为适当的 Dictionary 的最小界面。 .

这是一个使用支持 ArrayList 的实现:

package collections;

import java.util.ArrayList;
import java.util.List;

/**
 * Implementation of a Dictionary interface
 * Created by Michael
 * Creation date 12/30/2015.
 * @link https://stackoverflow.com/questions/34538520/data-structures-and-algorithms-implementation-dictionary/34538668?noredirect=1#comment56819702_34538668
 */
public class DictionaryImpl<K, V> implements Dictionary<K, V> {

    private List<K> keys;
    private List<V> values;

    public DictionaryImpl() {
        this.keys = new ArrayList<>();
        this.values = new ArrayList<>();
    }

    @Override
    public V get(K key) {
        V value = null;
        if (this.keys.contains(key)) {
            int index = this.getIndex(key);
            if (index != -1) {
                value = this.values.get(index);
            }
        }
        return value;
    }

    @Override
    public V put(K key, V value) {
        V previousValue = null;
        if (this.keys.contains(key)) {
            previousValue = this.get(key);
        }
        this.keys.add(key);
        this.values.add(value);
        return previousValue;
    }

    @Override
    public boolean containsKey(K key) {
        return this.keys.contains(key);
    }

    @Override
    public int size() {
        return this.keys.size();
    }

    private int getIndex(K keyToFind) {
        int index = -1;
        if (this.keys.contains(keyToFind)) {
            for (K key : this.keys) {
                ++index;
                if (key.equals(keyToFind)) {
                    break;
                }
            }
        }
        return index;
    }
}

这是一个 Junit 测试来证明一切正常:

package collections;

import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

/**
 * Junit test for Dictionary
 * Created by Michael
 * Creation date 12/30/2015.
 * @link https://stackoverflow.com/questions/34538520/data-structures-and-algorithms-implementation-dictionary/34538668?noredirect=1#comment56819702_34538668
 */
public class DictionaryTest {

    private Dictionary<String, Integer> testDictionary;

    @Before
    public void setUp() {
        this.testDictionary = new DictionaryImpl<>();
        this.testDictionary.put("foo", 17);
        this.testDictionary.put("bar", 23);
        this.testDictionary.put("baz", 31);
        this.testDictionary.put("bat", 41);
    }

    @Test
    public void testContainsKey_True() {
        String [] keys = { "foo", "bar", "baz", "bat" };
        for (String key : keys) {
            Assert.assertTrue(String.format("Should have contained key '%s'", key), this.testDictionary.containsKey(key));
        }
    }

    @Test
    public void testContainsKey_False() {
        String [] keys = { "dopey", "sleepy", "doc", "sneezy" };
        for (String key : keys) {
            Assert.assertTrue(String.format("Should not have contained key '%s'", key), !this.testDictionary.containsKey(key));
        }
    }

    @Test
    public void testGet_Success() {
        String [] keys = { "foo", "bar", "baz", "bat" };
        Integer [] values = { 17, 23, 31, 41 };
        for (int i = 0; i < keys.length; ++i) {
            Assert.assertEquals(String.format("Should have returned value %d for key '%s'", values[i], keys[i]), values[i], this.testDictionary.get(keys[i]));
        }
    }


    @Test
    public void testGet_NoSuchKey() {
        String [] keys = { "dopey", "sleepy", "doc", "sneezy" };
        for (String key : keys) {
            Assert.assertNull(String.format("Should have returned null for key '%s'", key), this.testDictionary.get(key));
        }
    }

    @Test
    public void testSize() {
        int expected = 4;
        Assert.assertEquals(expected, this.testDictionary.size());
    }
}