查找技術(shù)ppt課件(參考版)
2024-11-06 23:08本頁面
【正文】 散列表的查找技術(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 。 散列表的查找技術(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ā)生沖突的記錄存儲在溢出表中。 用拉鏈法處理沖突構(gòu)造的散列表叫做 開散列表 。 當(dāng) b、 c和 m的值確定后 ，給定一個(gè)隨機(jī)種子 ， 產(chǎn)生確定的隨機(jī)數(shù)序列 。 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 例：關(guān)鍵碼集合為 {47, 7, 29, 11, 16, 92, 22, 8, 3}， 散列表表長為 11， 散列函 數(shù)為 H(key)=key mod 11， 用線性探測法處理沖突 ， 則散列表為： 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)的 非同義詞 之間對同一個(gè)散列地址爭奪的現(xiàn)象 。 如何尋找下一個(gè)空的散列地址 ? 散列表的查找技術(shù) （ 1）線性探測法 （ 2）二次探測法 （ 3）隨機(jī)探測法 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 線性探測法 當(dāng)發(fā)生沖突時(shí)，從沖突位置的下一個(gè)位置起，依次尋找空的散列地 址。 適用情況？ 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 根據(jù)關(guān)鍵碼在各個(gè)位上的分布情況，選取分布比較均勻 的若干位組 成散列地址。 散列表的查找技術(shù) 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 散列函數(shù)為： H(key)=key mod p 散列表的查找技術(shù) 散列函數(shù) —— 除留余數(shù)法 14 7 14 14 7 0 14 散列地址 56 49 42 35 28 21 14 關(guān)鍵碼 如何選取合適的 p，產(chǎn)生較少同義詞？ 例： p ＝ 21＝ 3 7 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 散列表的查找技術(shù) 散列函數(shù) —— 除留余數(shù)法 一般情況下，選 p為小于或等于表長（最好接近表長 ）的最小素?cái)?shù)或不包含小于 20質(zhì)因子的合數(shù)。函數(shù)值要盡量均勻散布在地址空間，這樣才能保證存儲空間的有效利用并減少沖突。散列函數(shù)不應(yīng)該有很大的計(jì)算量，否則會降低查找效率。 散列表的查找技術(shù) 概 述 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 沖突： 對于兩個(gè)不同關(guān)鍵碼 ki≠kj， 有 H(ki)＝ H(kj)，即兩個(gè)不同的記錄 需要存放在同一個(gè)存儲位置 ,ki和 kj相對于 H稱做 同義詞 。 ⑵ 沖突的處理。 概 述 散列表的查找技術(shù) 散列技術(shù)適合于哪種類型的查找？ 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 散列技術(shù)的關(guān)鍵問題： ⑴ 散列函數(shù)的設(shè)計(jì)。散列方法也不適用于范圍查找，換言之，在散列表中，我們不可能找到最大或最小關(guān)鍵碼的記錄，也不可能找到在某一范圍內(nèi)的記錄。 散列只是通過記錄的關(guān)鍵碼定位該記錄，沒有完整地表達(dá)記錄之間的邏輯關(guān)系，所以，散列主要是 面向查找 的存儲結(jié)構(gòu)。 概 述 散列表的查找技術(shù) 散列表 關(guān)鍵碼集合 ki ri H(ki) …… …… H 散列函數(shù) 數(shù)組 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 散列地址： 由散列函數(shù) 所得的存儲位置址 。 散列表的查找技術(shù) 關(guān)鍵碼集合 ki ri H(ki) …… …… H 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 散列表： 采用散列技術(shù)將記錄存儲在一塊 連續(xù) 的存儲空間中， 這塊連續(xù)的存儲空間 稱為散列表。 查找操作要完成什么任務(wù)？ 待查值 k 確定 k在存儲結(jié)構(gòu)中的位置 我們學(xué)過哪些查找技術(shù)？這些查找技術(shù)的共性？ 在存儲位置和關(guān)鍵碼之間建立一個(gè)確定的對應(yīng)關(guān)系 能否不用比較，通過關(guān)鍵碼直接確定存儲位置？ 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 概 述 散列的基本思想： 在記錄的存儲地址和它的關(guān)鍵碼之間建立一個(gè)確定的對應(yīng)關(guān)系。 樹表的查找技術(shù) 35 20 40 15 30 25 20 25 15 35 40 30 35 40 30 20 25 15 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 設(shè)結(jié)點(diǎn) A為 最小不平衡子樹 的根結(jié)點(diǎn)，對該子樹進(jìn)行平衡調(diào)整歸納起來有以下四種情況： 1. LL型 2. RR型 3. LR型 4. RL型 樹表的查找技術(shù) 平衡二叉樹 第 7章 查找技術(shù) 數(shù)據(jù)結(jié)構(gòu) 插入前 插入后 ， 調(diào)整前 調(diào)整后 樹表的查找技術(shù) 平衡二叉樹 —— LL型 A 1 BL h BR h 0 AR h B h 2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1