資料結構 第9章　搜尋.

Presentation on theme: "資料結構 第9章　搜尋."— Presentation transcript:

1 資料結構 第9章　搜尋

2 9-1　循序搜尋 循序搜尋 (sequential search) 非循序搜尋 (nonsequential search)

3 範例9.1：寫出以 [循序搜尋] 在list[] = {54, 2, 40, 22, 17, 22, 60, 35} 中搜尋22的過程，並計算總共做過幾次比較？

4 範例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; }

5 9-2　二元搜尋 範例9.3：寫出以 [二元搜尋] 在list[] = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19} 中搜尋15的過程，並計算總共做過幾次比較？ 解答：

6 範例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;

7 範例9.6：證明二元搜尋的時間複雜度為O(log2n)。

8 9-3　內插搜尋

9 範例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，則比較次數為三次 。

10 範例9.9：寫出以 [內插搜尋] 在list[] = {3, 4, 7, 24, 25, 30, 77, 88, 90} 中搜尋30的過程，並計算總共做過幾次比較？若換成是使用二元搜尋在list[] 中搜尋30，則比較次數又為何？ 解答： middle分為 於是拿key (30) 和list[5] (30) 做比較，得到兩者相等，故傳回其索引5，比較次數為四次。若換成是使用二元搜尋在list[] 中搜尋30，則比較次數為三次。

11 9-4 雜湊法 相關名詞： 雜湊法的優點 雜湊函數 (hash function) 雜湊表 (hash table) 桶子 (bucket)
9-4　雜湊法 相關名詞： 雜湊函數 (hash function) 雜湊表 (hash table) 桶子 (bucket) 碰撞 (collision) 槽 (slot) 溢位 (overflow) 同義字 (synonym) 叢集 (cluster) 負載密度/負載因素 (loading density/loading factor) 識別字 (identifier) 識別字密度 (identifier density) 雜湊法的優點

12 範例9.11：假設雜湊表是由26個桶子所組成，每個桶子是由2個槽所組成，而鍵值則是包含1個大寫英文字母和1個數字的字串，試想出一個雜湊函數將 {A1, B1, C1, A2, D1, B2, C2, E1} 等8個鍵值存放到雜湊表。

13 9-4-1　雜湊函數 除法 f(x) = x % b 舉例來說，假設有15筆記錄，鍵值分別為0 ~ 14，桶子有5個，位址分別為0 ~ 4，則分配結果如下。

14 平方後取中間值法 舉例來說，假設鍵值為1234，雜湊表的大小為1000，而1234的平方為 ，那麼可以從中選取千百十等三位數275，做為該鍵值存放在雜湊表內的位址。

15 折疊法 移動折疊法 (shift folding)：假設鍵值x為 ，我們將它分割為x1 = 123、x2 = 456、x3 = 782、x4 = 314、x5 = 30，然後計算x1 + x2 + x3 + x4 + x5 = = 1705，得到鍵值x在雜湊表內的位址為1705。 邊界折疊法 (folding at the boundaries) ：假設鍵值x為 ，我們將它分割為x1 = 123、x2 = 456、x3 = 782、x4 = 314、x5 = 30，接著將偶數部分x2、x4、…的位數反轉過來成為x2’ = 654、x4’ = 413，、然後計算x1 + x2’ + x3 + x4’ + x5 = = 2002，得到鍵值x在雜湊表內的位址為2002。

16 位數分析法 舉例來說，假設鍵值如下表所示，雜湊表的大小為100，那麼所需的位數為兩位，於是從中刪除分佈較不均勻的位數，包括第1、2、3、5位 (從左邊算起)，只取第4位和第6位，得到結果如下。

17 9-4-2 處理碰撞 開放位址法 (open addressing) 鏈結法 (chaining)
9-4-2　處理碰撞 開放位址法 (open addressing) 線性探測法 (linear probing) 二次方程探測法 (quadratic probing) 重雜湊法 (rehashing) 鏈結法 (chaining)

18 範例9.13：假設雜湊表ht的大小為13，試使用 [線性探測法] 將13、14、26、39、45、32等鍵值放入雜湊表。

19 範例9.14：撰寫一個函數實作 [線性探測法]。 int linear_probe(int ht[], int key) {
int address; address = key % b; while(ht[address] != EMPTY) address = (address + 1) % b; ht[address] = key; }

20 範例9.15：撰寫一個函數在使用線性探測法的雜湊表內搜尋鍵值。
int linear_search(int ht[], int key) { int address; address = key % b; while(ht[address] != key){ address = (address + 1) % b; if (ht[address] == EMPTY || address == key % b) return -1; } return address;

21 二次方程探測法 (f(x) ± i2) % b 舉例來說，假設雜湊表的內容如下，現在要放入鍵值19，而f(19) = 19 % 13 = 6，此時發生碰撞，於是往位址ht[7] ((6 + 12) % 13) 探測，仍發生碰撞，於是往位址ht[5] ((6 - 12) % 13) 探測，故將鍵值19放入ht[5]，探測次數為兩次。

22 重雜湊法 範例9.16：假設雜湊表ht的大小為13，第一、二、三個雜湊函數f1(x)、f2(x)、f3(x)分別如下，試使用 [重雜湊法] 將13、14、26、39、40等鍵值放入雜湊表。 f1(x) = x % 13 f2(x) = (f1(x) * x + 7) % 13 f3(x) = (f2(x) * x + 3) % 13

23 鏈結法 範例9.17：假設雜湊表ht的大小為13，雜湊函數f(x) = x % 13，試使用 [鏈結法] 將13、14、26、60、39、40、86、15、25等鍵值放入雜湊表。