數據結構和算法的實現 - 字典

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