算法—符號表，算法符號

算法—符號表，算法符號

定義：符號表是一種存儲鍵值對的數據結構，支持兩種操作：插入（put），即將一組新的鍵值對存入表中；查找（get），即根據給定的鍵得到相應的值。

1.有序符號表

2.成本模型

查找的成本模型：在學習符號表的實現時，我們會統計比較的次數（等價性測試或是鍵的相互比較）。在內循環不進行比較（極少）的情況下，我們會統計數組的訪問次數。

 3.符號表的用例

/**
 * 符號表用例
 */
public class FrequencyCounter {

	public static void main(String[] args) {
		int minlen = Integer.parseInt(args[0]);	//最小鍵長
		ST<String, Integer> st = new ST<String, Integer>();
		//構造符號表並統計頻率
		while(!StdIn.isEmpty()){
			String word = StdIn.readString();
			//忽略較短的單詞
			if(word.length() < minlen){
				continue;
			}
			if(!st.contains(word)){
				st.put(word, 1);
			}
			else{
				st.put(word, st.get(word) + 1);
			}
		}
		//找出出現頻率最高的單詞
		String max = " ";
		st.put(max, 0);
		for (String word : st.keys()) {
			if(st.get(word) > st.get(max)){
				max = word;
			}
		}
		StdOut.println(max + " " + st.get(max));
	}
}

【源碼下載】