查找技術(shù)ppt課件-資料下載頁
2024-11-03 23:08本頁面
【正文】 散列表的查找技術(shù) 散列函數(shù) —— 除留余數(shù)法 一般情況下，選 p為小于或等于表長(zhǎng)（最好接近表長(zhǎng) ）的最小素?cái)?shù)或不包含小于 20質(zhì)因子的合數(shù)。 除留余數(shù)法是一種最簡(jiǎn)單、也是最常用的構(gòu)造散列函數(shù)的方法，并且不要求事先知道關(guān)鍵碼的分布。 適用情況？ 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 根據(jù)關(guān)鍵碼在各個(gè)位上的分布情況，選取分布比較均勻 的若干位組 成散列地址。 例：關(guān)鍵碼為 8位十進(jìn)制數(shù)，散列地址為 2位十進(jìn)制數(shù) 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 散列表的查找技術(shù) 散列函數(shù) —— 數(shù)字分析法 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 處理沖突的方法 —— 開放定址法 由關(guān)鍵碼得到的散列地址一旦產(chǎn)生了沖突，就去尋找下一個(gè)空 的散列地址，并將記錄存入。 如何尋找下一個(gè)空的散列地址 ? 散列表的查找技術(shù) （ 1）線性探測(cè)法 （ 2）二次探測(cè)法 （ 3）隨機(jī)探測(cè)法 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 線性探測(cè)法 當(dāng)發(fā)生沖突時(shí)，從沖突位置的下一個(gè)位置起，依次尋找空的散列地 址。 對(duì)于鍵值 key， 設(shè) H(key)=d， 閉散列表的長(zhǎng)度為 m，則發(fā)生沖突時(shí) ， 尋找下一個(gè)散列地址的公式為： Hi=(H(key)＋ di) % m （ di=1， 2， … ， m1） 散列表的查找技術(shù) 用開放定址法處理沖突得到的散列表叫 閉散列表 。 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 例：關(guān)鍵碼集合為 {47, 7, 29, 11, 16, 92, 22, 8, 3}， 散列表表長(zhǎng)為 11， 散列函 數(shù)為 H(key)=key mod 11， 用線性探測(cè)法處理沖突 ， 則散列表為： 0 1 2 3 4 5 6 7 8 9 47 7 29 11 16 92 29 22 22 8 8 3 3 3 3 堆積： 在處理沖突的過程中出現(xiàn)的 非同義詞 之間對(duì)同一個(gè)散列地址爭(zhēng)奪的現(xiàn)象 。 散列表的查找技術(shù) 線性探測(cè)法 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 二次探測(cè)法 當(dāng)發(fā)生沖突時(shí)，尋找下一個(gè)散列地址的公式為： Hi=(H(key)＋ di)% m （ di=12，－ 12， 22，－ 22， … ， q2，－ q2且 q≤ m/2） 散列表的查找技術(shù) 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 0 1 2 3 4 5 6 7 8 9 47 7 29 11 16 92 29 22 22 8 8 3 3 3 例：關(guān)鍵碼集合為 {47, 7, 29, 11, 16, 92, 22, 8, 3}， 散列表表長(zhǎng)為 11， 散列函 數(shù)為 H(key)=key mod 11， 用二次探測(cè)法處理沖突 ， 則散列表為： 二次探測(cè)法 散列表的查找技術(shù) 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 隨機(jī)探測(cè)法 當(dāng)發(fā)生沖突時(shí)，下一個(gè)散列地址的位移量是一個(gè)隨機(jī)數(shù)列，即 尋找下一個(gè)散列地址的公式 為： Hi=(H(key)+di)% m （ di是一個(gè)隨機(jī)數(shù)列， i=1， 2， …… ， m1） 散列表的查找技術(shù) 計(jì)算機(jī)中產(chǎn)生隨機(jī)數(shù)的方法通常采用線性同余法 ， 其中 ， d稱為隨機(jī)種子 。 當(dāng) b、 c和 m的值確定后 ，給定一個(gè)隨機(jī)種子 ， 產(chǎn)生確定的隨機(jī)數(shù)序列 。 0 = d a = + = 1, 2,L mod ) ( 1 n m c ba a n n 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 基本思想 ：將所有散列地址相同的記錄，即所有同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中（稱為同義詞子表），在散列表中存儲(chǔ)的是所有同義詞子 表的頭指針。 用拉鏈法處理沖突構(gòu)造的散列表叫做 開散列表 。 設(shè) n個(gè)記錄存儲(chǔ)在長(zhǎng)度為 m的散列表中，則同義詞子表的平均長(zhǎng)度為 n / m。 散列表的查找技術(shù) 處理沖突的方法 —— 拉鏈法（鏈地址法） 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 例：關(guān)鍵碼集合 {47, 7, 29, 11, 16, 92, 22, 8, 3}，散列函數(shù)為 H(key)=key mod 11， 用拉鏈法處理沖突，構(gòu)造的開散列表為： 散列表的查找技術(shù) 0 1 2 3 4 5 6 7 8 9 10 11 ∧ ∧ ∧ ∧ ∧ ∧ 22 47 ∧ 3 92 ∧ 16 ∧ 7 ∧ 29 8 ∧ 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 基本思想 ：散列表包含 基本表 和 溢出表 兩部分（通常溢出表和基本表的大小相同），將發(fā)生沖突的記錄存儲(chǔ)在溢出表中。查找時(shí)，對(duì)給定值通過散列函數(shù)計(jì)算散列地址，先與 基本表 的相應(yīng)單元進(jìn) 行比較，若相等，則查找成功；否則，再到 溢出表 中進(jìn)行順序查找。 散列表的查找技術(shù) 處理沖突的方法 —— 公共溢出區(qū) 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 例：關(guān)鍵碼集合 {47, 7, 29, 11, 16, 92, 22, 8, 3}，散列函數(shù)為 H(key)=key mod 11， 用公共溢出區(qū)法處理沖突，構(gòu)造的散列表為： 散列表的查找技術(shù) 0 1 2 3 4 5 6 7 8 9 10 基本表 溢出表 11 47 92 16 7 8 0 1 2 3 4 5 6 7 8 9 10 29 22 3
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1