双重杂凑法DoubleHashing分开链结法.PPT

楊正宏 編著 全華科技圖書股份有限公司 印行 第十章 搜 尋(1/4) 10-1 前言 10-2 循序搜尋法(Sequential Search) 10-3 二分搜尋法(Binary Search) 10-4 費氏搜尋法(Fibonacci Search) 10-5 區塊搜尋(Block Search) 10-6 插補搜尋(Interpolation Search) 10-7 基數搜尋(Radix Search) 10-8 樹狀搜尋法 10-8-1 二元搜尋樹(Binary Search Tree) 第十章 搜 尋(2/4) 10-8 樹狀搜尋法 10-8-2 B樹搜尋法(B Tree Search) 10-8-3 B+樹(B+ Tree) 10-8-4 數位搜尋樹(Digital Search Tree) 10-8-5 補償樹 10-8-6 K-D樹搜尋(K-D Tree Search) 10-9 雜湊搜尋法(Hashing Search) 10-9-1 直接定址法(Direct Addressing) 10-9-2 摘取注(Extraction) 第十章 搜 尋(3/4) 10-9 雜湊搜尋法(Hashing Search) 10-9-3 除法(Division Method) 10-9-4 乘法(Multiplicative Method) 10-9-5 中段平方法(Midsquare Method) 10-9-6 折壘法(Folding Method) 10-9-7 解決雜湊碰撞方法 10-9-7-1 開放定址法(Open Addressing) 10-9-7-2 雙重雜法(Double Hashing) 10-9-7-3 分門鏈結法(Separate Chaining) 第十章 搜 尋(4/4) 10-9 雜湊搜尋法(Hashing Search) 10-9-8 自雜湊表刪除項目 10-9-9 雜湊表的評估 前言 可依不同的資料型態採用適當的搜尋方法，以獲得較高的效率。 搜尋的資料都存放在主記憶體內，此方式就稱為內部搜尋(Internal Search)。 資料大，無法同時全部儲存在主記憶體中，則必須利用輔助記憶體，如硬碟，這樣的搜尋方式就稱為外部搜尋(External Search)。 靜態搜尋(Static Search)，動態搜尋(Dynamic Search)。 循序搜尋法 (Sequential Search) (1/3) 又稱為線性搜尋法(Linear Search) 搜尋法中最簡單的一種 程式容易設計，可應用於鏈結串列或矩陣的資料結構上。 方法： 由第一筆資料開始，依序將一筆一筆資料逐次搜尋，直到搜尋到所需要的資料為止。 循序搜尋法(2/3) 步驟： 設i=1 比較：若key =P[i]搜尋成功可結束搜尋。 繼續：i=i+1; 資料搜尋是否結束？若i ≤ n則回到(2)，否則查詢結束，搜尋失敗。 不適合用在較大的檔案搜尋。 優點：搜尋的資料可以不經過排序。 循序搜尋法(3/3) 資料:82,16,9,95,27,75,42,69,34，欲尋找鍵值=27 尋找第一筆資料:82 ? 鍵值27 尋找第二筆資料:16 ? 鍵值27 尋找第三筆資料: 9 ? 鍵值27 尋找第四筆資料:95 ? 鍵值27 尋找第五筆資料:27 ? 鍵值27 效率： 找尋任一key，需要n-i+1次，故平均比較次數是 time complexity 是Ｏ(n)。 二分搜尋法 (Binary Search) (1/2) 執行步驟： 首先將在這一群資料中找出其中間項m，其位置在( low + high ) / 2，其中low和high分別代表搜尋範圍的下限及上限索引值，以中間項為分界畫分成上、下兩半部，並將要搜尋的資料值key和中間項m作比較。 若key比中間項大則捨棄下半；若比中間項小則保留下半部。 再畫分成兩部分並與第二次中間項做比較，如此依次繼續下去，直到找到所要的資料key為止。 若low high時，則表示下限和上限已經交錯了，不能再二分資料下去，便是搜尋失敗。 二分搜尋法(2/2) 資料為82,16,9,95,27,75,42,69,34 ，欲取鍵值：69 排序9,16,27,34,42,69,75,82,95 搜尋過程： pass(1)：找出中間項 42 ? 鍵值 69 pass(2)：找出中間項 75 ? 鍵值 69 pass(3)：找出中間項 69 ? 鍵值 69 效率： 最壞的情形是最後只剩下一個資料才找到。 平均時間為O(log2 n)。 費氏搜尋法 (Fibonacci Search) (