9-4-1 杂凑函数.ppt

資料結構 第9章　搜尋 9-1　循序搜尋 循序搜尋 (sequential search) 非循序搜尋 (nonsequential search) 範例9.1：寫出以 [循序搜尋] 在list[] = {54, 2, 40, 22, 17, 22, 60, 35} 中搜尋22的過程，並計算總共做過幾次比較？ 範例9.2：撰寫一個函數實作 [循序搜尋] 並分析其時間複雜度。 int sequential_search(int list[], int n, int key) { int i; for (i = 0; i n; i++) if (list[i] == key) return i; return -1; } 9-2　二元搜尋 範例9.3：寫出以 [二元搜尋] 在list[] = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19} 中搜尋15的過程，並計算總共做過幾次比較？ 解答： 範例9.5：撰寫一個函數實作 [二元搜尋] 。 int binary_search(int list[], int left, int right, int key) { int middle; if (left = right){ middle = (left + right) / 2; switch (COMPARE(list[middle], key)){ case -1: return binary_search(list, middle + 1, right, key); case 0: return middle; case 1: return binary_search(list, left, middle - 1, key); } } return -1; } 範例9.6：證明二元搜尋的時間複雜度為O(log2n)。 9-3　內插搜尋 範例9.8：寫出以 [內插搜尋] 在list[] = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19} 中搜尋15的過程，並計算總共做過幾次比較？若換成是使用二元搜尋在list[] 中搜尋15，則比較次數又為何？ 解答： middle為 於是拿key (15) 和list[5] (15) 做比較，得到兩者相等，故傳回其索引5，比較次數為一次。若換成是使用二元搜尋在list[] 中搜尋15，則比較次數為三次 。 範例9.9：寫出以 [內插搜尋] 在list[] = {3, 4, 7, 24, 25, 30, 77, 88, 90} 中搜尋30的過程，並計算總共做過幾次比較？若換成是使用二元搜尋在list[] 中搜尋30，則比較次數又為何？ 解答： middle分為 於是拿key (30) 和list[5] (30) 做比較，得到兩者相等，故傳回其索引5，比較次數為四次。若換成是使用二元搜尋在list[] 中搜尋30，則比較次數為三次。 9-4　雜湊法 相關名詞： 雜湊函數 (hash function) 雜湊表 (hash table) 桶子 (bucket) 碰撞 (collision) 槽 (slot) 溢位 (overflow) 同義字 (synonym) 叢集 (cluster) 負載密度/負載因素 (loading density/loading factor) 識別字 (identifier) 識別字密度 (identifier density) 雜湊法的優點 範例9.11：假設雜湊表是由26個桶子所組成，每個桶子是由2個槽所組成，而鍵值則是包含1個大寫英文字母和1個數字的字串，試想出一個雜湊函數將 {A1, B1, C1, A2, D1, B2, C2, E1} 等8個鍵值存放到雜湊表。 9-4-1　雜湊函數 除法 f(x) = x % b 舉例來說，假設有15筆記錄，鍵值分別為0 ~ 14，桶子有5個，位址分別為0 ~ 4，則分配結果如下。 平方後取中間值法 舉例來說，假設鍵值為1234，雜湊表的大小為1000，而1234的平方為1522756，那麼可以從中選取千百十等三位數275，做為該鍵值存放在雜湊表內的位址。 折疊法 移動折疊法 (shift folding)：假設鍵值x為12345678231430，我們將它分割為x1 = 123、x2 = 456、x3 = 782、x4 = 314、x5 = 30，然後計算x