数据结构和算法的实现 - 字典

Question

我已经实现了Dictionary with Vector（Array）。在数组中我存储一个String数据。现在我已经获得位置方法。但我想在某个位置检索数据。什么将是该方法？谢谢。

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

我dictionaryPair ::

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的复古Vector类。这看起来不像通用的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();  
} 

你的钥匙应该是一成不变的。

这是我认为适当的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()); 
    } 
}