數(shù)據(jù)結(jié)構(gòu)第七章查找(參考版)
2025-05-17 21:27本頁(yè)面
【正文】 分塊查找是二者的折中方法。 2. 本章的基本內(nèi)容是 線性表 的查找（順序查找、二分法查找和分塊查找），順序查找比較慢，但適用面廣 。在許多軟件系統(tǒng)中最耗時(shí)間的部分是查找。試畫出分別用線性探查法和鏈接法解決沖突時(shí) 所構(gòu)造的散列表，并求等概率下這兩種方法查找成功的平均 查找長(zhǎng)度。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 26 41 15 68 44 6 36 38 12 51 1 1 2 2 1 1 1 1 2 3 存入 51后的散列表 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 26 25 41 15 68 44 6 36 38 12 51 1 5 1 2 2 1 1 1 1 2 3 存入 25后的散列表 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 26 41 15 68 44 36 38 12 1 1 2 2 1 1 1 2 存入 1 6 12后的散列表 散列表及其查找 （ 2）散列表用鏈表實(shí)現(xiàn)，用動(dòng)態(tài)鏈接地址法解決散列沖突。 H（ K） = K % P中， P取接近 14的最大素?cái)?shù) 13，即散列函數(shù)為 H（ K） = K % 13。 令裝填因子 α= 。 2. 鏈接法 (將所有哈希地址 相同的記錄 都鏈接在同一鏈表中 ) 0 1 2 3 4 5 6 14 1 36 19 82 23 11 68 55 ? ? ? ? ? ? ? ASL=(6 1+2 2+3)/9=13/9 例如 : 關(guān)鍵字集合 { 19, 1, 23, 14, 55, 68, 11, 82, 36 } 哈希函數(shù)為 H(key)=key ％ 7 〔 動(dòng)態(tài)鏈接法 〕 2. 鏈接法 什么是裝填因子？？ 由于發(fā)生的沖突次數(shù)與表的填滿程度直接有關(guān)，所以引進(jìn)裝填因子 α（ α 1） : α= 表中已有的記錄數(shù) / 表的長(zhǎng)度 散列表及其查找 例： 已知一組關(guān)鍵字為（ 26， 36， 41， 38， 44， 15，68， 12， 6， 51， 25），分別用線性探查法和鏈接法解決散列沖突。 靜態(tài)鏈接法： 首先要把整個(gè)散列表分為基本區(qū)和溢出區(qū) ( 即鏈接區(qū) )，按照元素的關(guān)鍵字計(jì)算出的散列地址 d被存儲(chǔ)在基本區(qū)上，若發(fā)生沖突就從溢出區(qū)中取出一個(gè)空結(jié)點(diǎn)，把對(duì)應(yīng)的元素存入該結(jié)點(diǎn)的值域，再把它鏈接到下標(biāo)為 d的單鏈表上。它需要在散列表的每個(gè)單元中增加一個(gè)指針域，用來(lái)存儲(chǔ)由發(fā)生沖突的同義詞元素所構(gòu)成的單鏈表的表頭結(jié)點(diǎn)指針。不過(guò)在實(shí)際應(yīng)用中，能探查到一半單元也就足夠了，若探查到一半單元仍找不到一個(gè)空閑單元，表明此散列表太滿應(yīng)該重新建立。 （ 1）線性探查法 （ 2） 平方探查法 平方探查法的探查序列為 d， d+12， d+22 ， … ，或表示為（ d+i2） % m （ 0≤i≤m1） 平方探查法是一種較好的處理沖突的方法，它 能夠減少堆積現(xiàn)象的發(fā)生 。 這種方法的探查序列為 d， d+1， d+2， … ， 或表示為 （ d+i） % m（ 0≤i≤m1） （ 1）線性探查法 散列表及其查找 例如 : 關(guān)鍵字集合 { 19, 1, 23, 14, 55, 68, 11, 82, 36 } 設(shè)定哈希函數(shù) H(key) = key ％ 11 ( 表長(zhǎng) =11 ) 0 1 2 3 4 5 6 7 8 9 1019 1 23 14 55 68 若采用線性探測(cè)再散列處理沖突 11 82 36 1 1 2 1 3 6 2 5 1 ASL = （ 1+1+2+1+3+6+2+5+1） /9= 22/9 探查 次數(shù) （ 1）線性探查法 【 線性探測(cè)法的 缺點(diǎn) 】 ： (2) 容易產(chǎn)生 堆積 (又稱 聚集 現(xiàn)象 )，即 存入哈希表的記錄在表中連成一片 ；但它是開放地址處理沖突最簡(jiǎn)單的一種探查方法。 從發(fā)生沖突的單元起查找空閑單元的主要方法有 :線性探查法 、 平方探查法 和 雙散列函數(shù)探查法 等。在散列表未滿時(shí)，從發(fā)生沖突的那個(gè)單元開始，按照一定的次序，從散列表中查找出一個(gè)空閑的存儲(chǔ)單元，把發(fā)生沖突的待插入元素存入到該空閑單元中。 散列表及其查找 1. 開放地址法 所謂“開放地址”，就是表中尚未被占用的地址。而“ 處理沖突 ”就是為該關(guān)鍵字的記錄找到一個(gè)“空”的散列地址。 散列表及其查找 例 關(guān)鍵字為 ： 0442205864，哈希地址位數(shù)為 4 5 8 6 4 4 2 2 0 0 4 1 0 0 8 8 H(key)=0088 移位疊加 5 8 6 4 0 2 2 4 0 4 6 0 9 2 H(key)=6092 間界疊加 4. 折疊法 H（ k） = k % p （ p≤m） k －關(guān)鍵字 m－表長(zhǎng) 注意： p應(yīng)取小于表長(zhǎng) m的最大 素?cái)?shù) ，才
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1