算法—符号表

定義：符号表是一種存儲鍵值對的資料結構，支援兩種操作：插入（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));
	}
}
           

【源碼下載下傳】

轉載于:https://www.cnblogs.com/joey-hua/p/5004509.html