數(shù)據(jù)結(jié)構(gòu)之查找課件-資料下載頁
2025-07-31 09:41本頁面
【導(dǎo)讀】查找又稱為查詢或檢索，是在一批記錄。在計(jì)算機(jī)中，被查找的數(shù)據(jù)對(duì)象是由同。在實(shí)際應(yīng)用問題中，每個(gè)記錄一般包含。若表中不存在相應(yīng)的記錄，查找算法中的基本運(yùn)算是記錄的關(guān)鍵字與給。因此，通常以關(guān)鍵字與給定值。找算法好壞的依據(jù)。成功，返回0作為查找失敗的信息。最壞的情況查找成功需比較n次，最好的情。時(shí)間復(fù)雜度為O。順序查找的優(yōu)點(diǎn)是算法簡單、適應(yīng)面廣，且。較大，特別是當(dāng)n較大時(shí)，查找效率較低，首先用k與查找表中間元素的關(guān)鍵字比。比較結(jié)果有三種可能：。數(shù)組的前半部分進(jìn)行二分查找；重復(fù)上述過程，查找范圍每次縮小1/2，當(dāng)范。折半查找的判定樹。查找成功時(shí)的最大查找長度為折半查找。分塊查找又稱為索引順序查找，是順序查找方。值小于后一塊中的最小關(guān)鍵字值。還需要建立一個(gè)索引表，索引表中的一項(xiàng)對(duì)應(yīng)。于線性表中的一塊，索引項(xiàng)由鍵域和鏈域組成，本塊第一個(gè)結(jié)點(diǎn)和最末一個(gè)結(jié)點(diǎn)的指針。塊內(nèi)元素是無序的，只能采用順序查找。定keytype缺省是int類型。
【正文】 (hashed table)。 ?設(shè)有關(guān)鍵字為 1， 3， 7， 12，定義一個(gè)散列函數(shù)為： h(k)=k mod p 其中 k 為關(guān)鍵字 ， mod 取余數(shù) ， p 為一整數(shù) 。 若取 p=7， 則 h(1)=1, h(3)=3, h(7)=0, h(12)=5， ?可能有不同的關(guān)鍵字計(jì)算出相同的函數(shù)值。 例如， h(1)=1， (15)=1 也就是不同記錄占用同一地址單元，這種情況稱為發(fā)生了 沖突 （ collision）。 若 Ki≠Kj, 但 H(Ki)=H(Kj),則稱 Ki和 Kj為同義詞 。 裝填因子 ：記錄數(shù) /表的長度 7 1 3 12 0 1 2 3 4 5 6 ?散列是一種重要的存儲(chǔ)方法 ， 又是一種查找方法 。 ?應(yīng)用散列法存儲(chǔ)記錄的過程是對(duì)每個(gè)記錄的關(guān)鍵字進(jìn)行散列函數(shù)的運(yùn)算 ， 計(jì)算出該記錄存儲(chǔ)的地址 ， 并將記錄存入此地址中 。 ?查找一個(gè)記錄的過程與存儲(chǔ)記錄的過程一樣 ，就是對(duì)待查找記錄的關(guān)鍵字進(jìn)行計(jì)算 ， 得到地址 ， 并到此地址中查找記錄是否存在 。 散列函數(shù)構(gòu)造方法 ? 1. 直接定址法 ： 直接取關(guān)鍵字本身或者關(guān)鍵 字加上一個(gè)常數(shù)作為散列地址。 H(K)=K H(K)= a*K + b ? 2. 數(shù)字分析法： 又稱為數(shù)字選擇法。適用于所有關(guān)鍵字事先都知道，并且關(guān)鍵字的位數(shù)比散列地址的位數(shù)多的情況，在這種情況下，可將各個(gè)關(guān)鍵字列出，分析它們的每一位數(shù)字，舍去各關(guān)鍵字取值比較集中的位，僅保留取值比較分散的位作為散列地址。 數(shù)字分析法例子 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 3 1 1 9 9 8 6 7 6 8 1 2 9 3 4 4 4 1 1 1 6 3 2 5 2 4 4 4 3 3 3 3 5 1 0 9 3 4 1 6 7 8 9 5 3 6 0 9 位： ? ： 折疊法是將關(guān)鍵字按要求的長度分成位數(shù)相等的幾段，最后一段如不夠長可以短些，然后把各段重疊在一起相加并去掉進(jìn)位，以所得的和作為地址。 ? 4. 除留余數(shù)法：這是一種最簡單也最常用的構(gòu)造散列函數(shù)的方法，如 h(k) = k mod p （ p≤m) m: 存放記錄的表長 p :一般地 ,P應(yīng)選則小于散列表長度的質(zhì)數(shù) . 處理沖突的方法 ? 1. 開放地址法： 當(dāng)插入的記錄時(shí)，計(jì)算出來的地址已被其它記錄占用時(shí)，要尋找其它尚未占用的單元。 Hi(K)=( H(k)+di) % m (i=1,2,??,m) 其中： H(k)為哈希函數(shù) m為表長 di增量序列 di有兩種選擇方法： di=1,2,?,n ( 線性探測(cè)法 ) di=12,12,22,22,32,32,?, 177。 k2 (k≤m/2 ） （二次探測(cè)法 ) ?例： ? 2. 鏈地址法 把同義詞都放在一個(gè)鏈表中。 例： 平均查找長度 ? 散列表的運(yùn)算 小結(jié) ?查找 ?順序查找 ?二分查找 ?分塊查找 ?樹型查找 ?平衡樹 ?散列法 ?處理沖突的方法 開放地址法 鏈接表法 返回 習(xí)題與練習(xí) ?一、基礎(chǔ)知識(shí)題 1. 解釋下列名詞 (1) 查找 (2) 樹型查找 (3) 平衡因子 (4) 散列函數(shù) (5) 沖突 2. 設(shè)有序表為 {a,b,c,d,e,f,g}，請(qǐng)分別畫出對(duì)給定值 f,g和 h進(jìn)行拆半查找的過程。 3. 試述順序查找法、二分查找法和分塊查找法對(duì)被查找表中元素的要求，每種查找法對(duì)長度為 n的表的等概率查找長度是多少？ 4. 設(shè)散列表長 m=14，哈希函數(shù)為 H(k)=k mod 11，表中一共有 8個(gè)元素 {15,27,50,73,49,61,37,60} ，試畫出采用二次探測(cè)法處理沖突的散列表。 5. 線性表的關(guān)鍵字集合為{113,12,180,138,92,67,94,134,252,6,70,323,60}，共有 13個(gè)元素，已知散列函數(shù)為： H（ k） =k mod 13，采用鏈接表處理沖突，試設(shè)計(jì)這種鏈表結(jié)構(gòu)。 6. 設(shè)關(guān)鍵字集合為 {27,49,79,5,37,1,56,65,83}，散列函數(shù)為： H（ k） =k mod 7，散列表長度 m=10，起始地址為 0，分別用線性探測(cè)和鏈接表法來解決沖突。試畫出對(duì)應(yīng)的散列表。 ?二、算法設(shè)計(jì)題 1. 從小到大排列的，試寫出對(duì)此鏈表的查找算法，并說明是否可以采用折半查找。 2. 如果線性表中各結(jié)點(diǎn)查找概率不等，則可以使用下面的策略提高順序表的查找效率：如果找到指定的結(jié)點(diǎn)，則將該結(jié)點(diǎn)和其前趨（若存在）結(jié)點(diǎn)交換，使得經(jīng)常被查找的結(jié)點(diǎn)盡量位于表的前端。試對(duì)線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)寫出實(shí)現(xiàn)上述策略的順序查找算法（注意查找時(shí)必須從表頭開始向后掃描）。 3. 試設(shè)計(jì)一個(gè)在用開放地址法解決沖突的散列表上刪除一個(gè)指定結(jié)點(diǎn)的算法。 4. 設(shè)給定的散列表存儲(chǔ)空間為 H[1~m]，每個(gè)單元可存放一個(gè)記錄， H[i](1≤i≤m)的初始值為零，選取散列函數(shù)為 H()，其中 key為記錄 R的關(guān)鍵字，解決沖突方法為線性探測(cè)法，編寫一個(gè)函數(shù)將某記錄 R填入到散列表 H中。 返回
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1