




已閱讀5頁,還剩66頁未讀, 繼續(xù)免費(fèi)閱讀
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
數(shù)據(jù)結(jié)構(gòu) 第九章 查找,本章內(nèi)容 9.1 查找的基本概念 9.2 靜態(tài)查找表 9.3 動(dòng)態(tài)查找表 9.4 哈希表,9-3,9.1 查找的基本概念,查找表(Search Table) 查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。對(duì)查找表的操作主要有: 查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中; 檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性; 在查找表中插入一個(gè)數(shù)據(jù)元素; 從查找表中刪去某個(gè)數(shù)據(jù)元素。 查找表分類 靜態(tài)查找表 僅作查詢和檢索操作的查找表。 動(dòng)態(tài)查找表 在查找過程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素,或者從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素,9-4,9.1 查找的基本概念,關(guān)鍵字(Key) 關(guān)鍵字是數(shù)據(jù)元素(或記錄)中某個(gè)數(shù)據(jù)項(xiàng)的值,用以標(biāo)識(shí)(識(shí)別)一個(gè)數(shù)據(jù)元素(或記錄)。 主關(guān)鍵字:可以識(shí)別唯一的一個(gè)記錄的關(guān)鍵字 次關(guān)鍵字:能識(shí)別若干記錄的關(guān)鍵字 查找(Searching) 是根據(jù)給定的某個(gè)值,在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素(或記錄)。,9-5,9.1 查找的基本概念,衡量查找算法的標(biāo)準(zhǔn) 時(shí)間復(fù)雜度; 空間復(fù)雜度; 平均查找長度ASL:定義為確定記錄在表中的位置所進(jìn)行的和關(guān)鍵字比較的次數(shù)的平均值 n ASL = PiCi i=1 n為查找表的長度,即表中所含元素的個(gè)數(shù) Pi為查找第i個(gè)元素的概率(Pi=1) Ci是查找第i個(gè)元素時(shí)同給定值K比較的次數(shù),9-6,9.2 靜態(tài)查找表,9.2.1 順序表的查找 順序查找算法是順序表(既無序表)的查找方法。在順序查找算法中,以順序表或線性鏈表表示靜態(tài)查找表。 面臨的問題 下標(biāo)越界的檢查,需要相當(dāng)?shù)臅r(shí)間和空間代價(jià)。解決的辦法是,將ST.elem0.key 置為key,所有元素檢查完還沒有找到時(shí),在ST.elem0處一定找到。從而免去了檢查下標(biāo)越界的時(shí)間。 順序查找算法 從表中最后一個(gè)記錄開始 逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較 若某個(gè)記錄比較相等,則查找成功 若直到第1個(gè)記錄都比較不等,則查找不成功,9-7,9.2 靜態(tài)查找表,順序查找算法描述 設(shè)置“哨兵”的目的是省略對(duì)下標(biāo)越界的檢查,提高算法執(zhí)行速度。當(dāng)然,哨兵也可以設(shè)置在高下標(biāo)處。,int Search_Seq(SSTable ST, KeyType key) / 若查找成功,返回位置 ST.elem0.key = key; / “哨兵”, for (i=ST.length; ST.elemi.key!=key; -i); / 從后往前找 return i; / 找不到時(shí),i=0 ,9-8,9.2 靜態(tài)查找表,順序查找示舉例 在下列順序表中尋找62,如果找到,給出其所在位置的下標(biāo)。,監(jiān)視哨兵,比較次數(shù)=5,比較次數(shù)分析: 查找第n個(gè)元素: 1次 查找第n-1個(gè)元素: 2次 . 查找第1個(gè)元素: n次 查找第i個(gè)元素: n+1-i次 查找失敗: n+1次,0 1 2 3 4 5 6 7 8 9 10 11,9-9,9.2 靜態(tài)查找表,順序查找性能分析 對(duì)順序表而言,Ci=n-i+1 在等概率查找的情況下,Pi=1/n 平均查找長度 ASLss=n*P1 +(n-1)P2 + 2Pn-1+ Pn = (n+1)/2 如果被查找的記錄概率不等時(shí), ASLss在 PnPn-1 P2P1 時(shí)取極小值 若查找概率無法事先測(cè)定,則查找過程采取的改進(jìn)辦法是,在每次查找之后,將剛剛查找到的記錄直接移至表尾的位置上。 順序查找特點(diǎn) 優(yōu)點(diǎn): 1.簡單 2.適應(yīng)面廣(對(duì)表的結(jié)構(gòu)無任何要求) 缺點(diǎn): 1.平均查找長度較大 2.特別是當(dāng)n很大時(shí),查找效率很低,9-10,9.2 靜態(tài)查找表,9.2.2 折半查找 折半查找算法是有序表的查找方法。在折半查找算法中,靜態(tài)查找表按關(guān)鍵字大小的次序,有序地存放在順序表中。 折半查找的原理 先確定待查記錄所在的范圍(前部分或后部分) 逐步縮小(一半)范圍直到找(不)到該記錄為止,9-11,9.2 靜態(tài)查找表,折半查找算法 n個(gè)對(duì)象從小到大存放在有序順序表ST中,k為給定值 設(shè)low、high指向待查元素所在區(qū)間的下界、上界,即low=1, high=n 設(shè)mid指向待查區(qū)間的中點(diǎn),即 mid=(low+high)/2 讓k與mid指向的記錄比較 若 k=STmid.key,查找成功 若 kSTmid.key,則low=mid+1 下半?yún)^(qū)間 重復(fù)3,4操作,直至lowhigh時(shí),查找失敗。,9-12,9.2 靜態(tài)查找表,折半成功查找舉例:在下列有序表中用折半查找法查找62所在位置。Key = 62,第一步:low=1, high=11, mid=6,STmid=ST6=5662, 則改變low;,第二步:low=mid+1=7, mid=9,STmid=ST9=8062, 則改變high;,第三步:high=mid-1=8, mid=7,STmid=ST7=62=62, 找到!,62,9-13,9.2 靜態(tài)查找表,折半查找失敗舉例:在上例有序表中找61。,high=6,low=7,找61,當(dāng)下界low大于上界high時(shí),說明有序 表中沒有關(guān)鍵字等于K的元素,查找失敗,9-14,9.2 靜態(tài)查找表,折半查找的性能分析 折半查找過程可以用二叉樹(也叫判定樹)來描述: 判定樹上每個(gè)結(jié)點(diǎn)需要的查找次數(shù)剛好為該結(jié)點(diǎn)所在的層數(shù); 查找成功時(shí)查找次數(shù)不會(huì)超過判定樹的深度 n個(gè)結(jié)點(diǎn)的判定樹的深度為 log2n +1 比較次數(shù)最多不超過 log2n +1 折半查找的算法復(fù)雜度為 log2n +1,9-15,9.2 靜態(tài)查找表,折半查找特點(diǎn) 折半查找的效率比順序查找高,特別是查找表的長度很長時(shí); 折半查找只能適用于等概率有序表,并且以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。,9-16,9.2 靜態(tài)查找表,9.2.3 分塊查找 分塊查找是一種索引順序表(分塊有序表)查找方法,是折半查找和順序查找的簡單結(jié)合; 索引順序表(分塊有序表)將整個(gè)表分成幾塊,塊內(nèi)無序,塊間有序 所謂塊間有序是指后一塊表中所有記錄的關(guān)鍵字均大于前一塊表中的最大關(guān)鍵字,9-17,9.2 靜態(tài)查找表,基本概念 主表:用數(shù)組存放待查記錄,每個(gè)數(shù)據(jù)元素至少含有關(guān)鍵字域 索引表:每個(gè)結(jié)點(diǎn)含有最大關(guān)鍵字域和指向本塊第一個(gè)結(jié)點(diǎn)的指針,9-18,9.2 靜態(tài)查找表,分塊查找舉例 采用折半查找方法在索引表中找到塊(第2塊) 用順序查找方法在主表對(duì)應(yīng)塊中找到記錄(第3個(gè)記錄),找62,9-19,9.2 靜態(tài)查找表,分塊查找性能分析 若將長度為n的表分成b塊,每塊含s個(gè)記錄,并設(shè)表中每個(gè)記錄查找概率相等 用折半查找方法在索引表中查找索引塊,ASL塊間log2(n/s+1) 用順序查找方法在主表對(duì)應(yīng)塊中查找記錄,ASL塊內(nèi)=s/2 ASLlog2(n/s+1) + s/2,9-20,9.3 動(dòng)態(tài)查找表,動(dòng)態(tài)查找表 如果應(yīng)用問題涉及的數(shù)據(jù)量很大,而且數(shù)據(jù)經(jīng)常發(fā)生變化,如圖書館經(jīng)常購進(jìn)圖書,每購進(jìn)新書,需將新書記錄插入圖書表,對(duì)這類表除了提供前面的介紹的查找外,還要提供動(dòng)態(tài)查找功能: 查找某個(gè)“特定”元素是否在表中,若不在,將該元素插入; 查找某個(gè)“特定”元素是否在表中,若在,從表中刪除; 如何組織動(dòng)態(tài)查找表? 用靜態(tài)查找方法不能滿足要求了。本節(jié)介紹幾種方法。,9-21,9.3 動(dòng)態(tài)查找表,9.3.1 二叉排序樹 二叉排序樹又稱二叉查找樹 空樹或者是具有如下特性的二叉樹: 若左子樹不空,則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值; 若右子樹不空,則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值; 左、右子樹也都分別是二叉排序樹。,21,二叉排序樹,非二叉排序樹,9-22,9.3 動(dòng)態(tài)查找表,二叉排序樹查找算法 給定值與根結(jié)點(diǎn)比較: 若相等,查找成功 若小于,查找左子樹 若大于,查找右子樹,例1:在右圖二叉排序樹中查找關(guān)鍵字值等于37,37,找到,例2:在右圖二叉排序樹中查找關(guān)鍵字值等于88,找到,例3:在右圖二叉排序樹中查找關(guān)鍵字值等于94,無此數(shù),9-23,9.3 動(dòng)態(tài)查找表,二叉排序樹插入 二叉排序樹是一種動(dòng)態(tài)樹表。 當(dāng)樹中不存在查找的結(jié)點(diǎn)時(shí),作插入操作 新插入的結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)(只需改動(dòng)一個(gè)結(jié)點(diǎn)的指針) 該葉子結(jié)點(diǎn)是查找不成功時(shí)路徑上訪問的最后一個(gè)結(jié)點(diǎn)左孩子或右孩子(新結(jié)點(diǎn)值小于或大于該結(jié)點(diǎn)值),例:在右圖二叉樹中插入結(jié)點(diǎn)94。,9-24,9.3 動(dòng)態(tài)查找表,二叉排序樹生成 例:畫出在初始為空的二叉排序樹中依次插入56,64,92,80,88,75時(shí)該樹的生長全過程,56,9-25,9.3 動(dòng)態(tài)查找表,二叉排序樹中序遍歷 中序遍歷二叉排序樹,可得到一個(gè)關(guān)鍵字的有序序列,如5,13,19,21,37,56,64,92,75,80,88,9-26,9.3 動(dòng)態(tài)查找表,二叉排序樹刪除 刪除二叉排序樹中的一個(gè)結(jié)點(diǎn)后,必須保持二叉排序樹的特性:左子樹的所有結(jié)點(diǎn)值小于根結(jié)點(diǎn),右子樹的所有結(jié)點(diǎn)值大于根結(jié)點(diǎn)。也即保持中序遍歷后,輸出為有序序列 被刪除結(jié)點(diǎn)具有以下三種情況 是葉子結(jié)點(diǎn) 只有左子樹或右子樹 同時(shí)有左、右子樹 下面針對(duì)三種情況各舉一例。,9-27,9.3 動(dòng)態(tài)查找表,被刪除結(jié)點(diǎn)是葉子結(jié)點(diǎn):直接刪除結(jié)點(diǎn),并讓其父結(jié)點(diǎn)指向該結(jié)點(diǎn)的指針變?yōu)榭铡?例:刪除右二叉排序樹中的88節(jié)點(diǎn),56,64,5,92,37,88,19,80,21,13,75,9-28,9.3 動(dòng)態(tài)查找表,被刪除結(jié)點(diǎn)只有左子樹或右子樹 刪除結(jié)點(diǎn),讓其父結(jié)點(diǎn)指向該結(jié)點(diǎn)的指針指向其左子樹(或右子樹),即用孩子結(jié)點(diǎn)替代被刪除結(jié)點(diǎn)即可 例:對(duì)于右邊二叉排序樹中,先刪除節(jié)點(diǎn)37,再刪除節(jié)點(diǎn)64。,56,5,13,9-29,9.3 動(dòng)態(tài)查找表,被刪除結(jié)點(diǎn)p既有左子樹,又有右子樹 以中序遍歷時(shí)的直接前驅(qū)s替代被刪除結(jié)點(diǎn)p,然后再按照前面介紹的發(fā)刪除該直接前驅(qū)s(只可能有左孩子),56,64,5,92,37,88,80,13,75,例:在右邊二叉排序樹中,節(jié)點(diǎn)56 的中序遍歷的直接前趨是節(jié)點(diǎn)37。,9-30,9.3 動(dòng)態(tài)查找表,二叉排序樹性能分析 在最好的情況下,二叉排序樹為一近似完全二叉樹時(shí),其查找深度為log2n量級(jí),即其時(shí)間復(fù)雜性為O(log2n) 在最壞的情況下,二叉排序樹為近似線性表時(shí)(如以升序或降序輸入結(jié)點(diǎn)時(shí),見右圖),其查找深度為n量級(jí),即其時(shí)間復(fù)雜性為O(n),9-31,9.3 動(dòng)態(tài)查找表,二叉排序樹特性 一個(gè)無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個(gè)有序序列(通過中序遍歷) 插入新記錄時(shí),只需改變一個(gè)結(jié)點(diǎn)的指針,相當(dāng)于在有序序列中插入一個(gè)記錄而不需要移動(dòng)其它記錄 二叉排序樹既擁有類似于折半查找的特性,又采用了鏈表作存儲(chǔ)結(jié)構(gòu) 但當(dāng)插入記錄的次序不當(dāng)時(shí)(如升序或降序),則二叉排序樹深度很深(見右圖),增加了查找的時(shí)間,9-32,9.3 動(dòng)態(tài)查找表,平衡二叉樹 平衡二叉樹(Balanced Binary Tree, Height-Balanced Tree,又稱AVL樹,Adelsen - Velskii and Landis,阿德爾森一維爾斯和蘭迪斯)是二叉排序樹的另一種形式。其特點(diǎn)為:樹中每個(gè)結(jié)點(diǎn)的左、右子樹深度之差的絕對(duì)值不大于1,即|hL-hR|1??梢宰C明,它們的深度和logn是同數(shù)量級(jí)的(其中n為節(jié)點(diǎn)個(gè)數(shù))。,AVL樹,非AVL樹,9-33,9.3 動(dòng)態(tài)查找表,平衡二叉樹平衡因子 每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字, 給出該結(jié)點(diǎn)左子樹的高度減去右子樹的高度所得的高度差,這個(gè)數(shù)字即為結(jié)點(diǎn)的平衡因子(balance factor) AVL樹任一結(jié)點(diǎn)平衡因子只能取 -1, 0, 1 若某個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1,則這棵二叉搜索樹就失去了平衡,不再是AVL樹。,9-34,9.3 動(dòng)態(tài)查找表,非平衡二叉樹的平衡處理 若一棵二叉排序樹是平衡二叉樹,扦入某個(gè)結(jié)點(diǎn)后,可能會(huì)變成非平衡二叉樹,這時(shí),就可以對(duì)該二叉樹進(jìn)行平衡處理,使其變成一棵平衡二叉樹。 處理的原則應(yīng)該是處理與插入點(diǎn)最近的、而平衡因子又比1大或比-1小的結(jié)點(diǎn)。下面將分四種情況討論平衡處理。,9-35,9.3 動(dòng)態(tài)查找表,LL型 的處理(左左型) 如下圖所示,若在C的左孩子B上扦入一個(gè)左孩子結(jié)點(diǎn)A,使C的平衡因子由1變成了2,成為不平衡的二叉樹序樹。 平衡處理:將C順時(shí)針旋轉(zhuǎn),成為B的右子樹,而原來B的右子樹則變成C的左子樹,待扦入結(jié)點(diǎn)A作為B的左子樹。,結(jié)點(diǎn)旁邊的數(shù)字表示該 結(jié)點(diǎn)的平衡因子,9-36,9.3 動(dòng)態(tài)查找表,LR型的處理(左右型) 如下圖所示,在C的左孩子A上扦入一個(gè)右孩子B,使的C的平衡因子由1變成了2,成為不平衡的二叉排序樹。 平衡處理:將B變到A與C 之間,使之成為LL型,然后按第1種情形LL型處理。,結(jié)點(diǎn)旁邊的數(shù)字表示該 結(jié)點(diǎn)的平衡因子,9-37,9.3 動(dòng)態(tài)查找表,RR型的處理(右右型) 如下圖所示,在A的右孩子B上扦入一個(gè)右孩子C,使A的平衡因子由-1變成-2,成為不平衡的二叉排序樹。 平衡處理:將A逆時(shí)針旋轉(zhuǎn),成為B的左子樹,而原來B的左子樹則變成A的右子樹,待扦入結(jié)點(diǎn)C成為B的右子樹。,結(jié)點(diǎn)旁邊的數(shù)字表示該 結(jié)點(diǎn)的平衡因子,9-38,9.3 動(dòng)態(tài)查找表,RL型的處理(右左型) 如下圖所示,在A的右孩子C上扦入一個(gè)左孩子B,使A的平衡因子由-1變成-2,成為不平衡的二叉排序樹。 平衡處理:將B變到A與C之間,使之成為RR型,然后按第(3) 種情形RR型處理。,結(jié)點(diǎn)旁邊的數(shù)字表示該 結(jié)點(diǎn)的平衡因子,9-39,9.3 動(dòng)態(tài)查找表,例1:給定一個(gè)關(guān)鍵字序列4,5,7,2 ,1,3,6,試生成一棵平衡二叉樹。 分析:平衡二叉樹實(shí)際上也是一棵二叉排序樹,故可以按建立二叉排序樹的思想建立,在建立的過程中,若遇到不平衡,則進(jìn)行相應(yīng)平衡處理,最后就可以建成一棵平衡二叉樹。具體生成過程見下圖。,9-40,9.3 動(dòng)態(tài)查找表,9-41,9.3 動(dòng)態(tài)查找表,9-42,9.3 動(dòng)態(tài)查找表,平衡二叉樹的查找及性能分析 平衡二叉樹本身就是一棵二叉排序樹,故它的查找與二叉排序樹完全相同。但它的查找 性能優(yōu)于二叉排序樹,不像二叉排序樹一樣,會(huì)出現(xiàn)最壞的時(shí)間復(fù)雜度O(n),它的時(shí)間復(fù)雜度與二叉排序樹的最好時(shí)間復(fù)雜相同,都為O(log2n)。,9-43,9.3 動(dòng)態(tài)查找表,例2,對(duì)例1給定的關(guān)鍵字序列4,5,7,2,1,3,6,試用二叉排序樹和平衡二叉樹兩種方法查找,給出查找6的次數(shù)及成功的平均查找長度。 分析:由于關(guān)鍵字序列的順序己經(jīng)確定,故得到的二叉排序樹和平衡二叉樹都是唯一的。得到的平衡二叉樹見下座圖,得到的二叉排序樹見下右圖。,從右圖的二叉排序樹可知,查找6需4次,平均查找長度 ASL=(1+2+2+3+3+3+4)/7=18/72.57 從左圖的平衡二叉樹可知,查找6需2次,平均查找長度 ASL=(1+2+2+3+3+3+3)=17/72.43 從結(jié)果可知,平衡二叉樹的查找性能優(yōu)于二叉排序樹。,9-44,9.4 哈希表,9.4.1 哈希表 哈希(Hash)表又稱散列表,是一種直接計(jì)算記錄存放地址的方法,它在關(guān)鍵碼與存儲(chǔ)位置之間直接建立了映象。 哈希函數(shù) 哈希函數(shù)是從關(guān)鍵字空間到存儲(chǔ)地址空間的一種映象 哈希函數(shù)在記錄的關(guān)鍵字與記錄的存儲(chǔ)地址之間建立起一種對(duì)應(yīng)關(guān)系??蓪懗桑?addr(ai)= H(keyi) H( )為哈希函數(shù) keyi是表中元素ai關(guān)鍵字,addr(ai)是存儲(chǔ)地址,9-45,9.4 哈希表,哈希查找 哈希查找也叫散列查找,是利用哈希函數(shù)進(jìn)行查找的過程 首先利用哈希函數(shù)及記錄的關(guān)鍵字計(jì)算出記錄的存儲(chǔ)地址 然后直接到指定地址進(jìn)行查找 不需要經(jīng)過比較,一次存取就能得到所查元素 哈希沖突 不同的記錄,其關(guān)鍵字通過哈希函數(shù)的計(jì)算,可能得到相同的地址 把不同的記錄映射到同一個(gè)散列地址上,這種現(xiàn)象稱為沖突,9-46,9.4 哈希表,哈希表定義 根據(jù)設(shè)定的哈希函數(shù) H(key) 和所選中的處理沖突的方法 將一組關(guān)鍵字映象到一個(gè)有限的、地址連續(xù)的地址集上 以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲(chǔ)位置 如此構(gòu)造所得的查找表稱之為“哈希表”。 哈希函數(shù)均勻性 哈希函數(shù)實(shí)現(xiàn)的一般是從一個(gè)大的集合(部分元素,空間位置上一般不連續(xù))到一個(gè)小的集合(空間連續(xù))的映射 一個(gè)好的哈希函數(shù),對(duì)于記錄中的任何關(guān)鍵字,將其映射到地址集合中任何一個(gè)地址的概率應(yīng)該是相等的 即關(guān)鍵字經(jīng)過哈希函數(shù)得到一個(gè)“隨機(jī)的地址”,9-47,9.4 哈希表,9.4.2 哈希函數(shù) 要求 哈希函數(shù)應(yīng)是簡單的,能在較短的時(shí)間內(nèi)計(jì)算出結(jié)果 哈希函數(shù)的定義域必須包括需要存儲(chǔ)的全部關(guān)鍵字,如果散列表允許有 m 個(gè)地址時(shí),其值域必須在 0 到 m-1 之間 散列函數(shù)計(jì)算出來的地址應(yīng)能均勻分布在整個(gè)地址空間中,9-48,9.4 哈希表,哈希函數(shù)(直接定址法) 直接定址法中,哈希函數(shù)取關(guān)鍵字的線性函數(shù) H(key) = a key + b 其中a和b為常數(shù) 直接定址法舉例 H(key) = key - 2005131000,9-49,9.4 哈希表,直接定址法特性 直接定址法僅適合于地址集合的大小與關(guān)鍵字集合的大小相等的情況 當(dāng)a=1時(shí),H(key)=key,即用關(guān)鍵字作地址 在實(shí)際應(yīng)用中能使用這種哈希函數(shù)的情況很少,9-50,9.4 哈希表,哈希函數(shù)(數(shù)字分析法) 假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由 s 位數(shù)字組成 (u1, u2, , us) 分析關(guān)鍵字集中的全體 從中提取分布均勻的若干位或它們的組合作為地址。,9-51,9.4 哈希表,數(shù)字分析法舉例 有80個(gè)記錄,關(guān)鍵字為8位十進(jìn)制數(shù),哈希地址為2位十進(jìn)制數(shù),分析:只取8 只取1 只取3、4 只取2、7、5 數(shù)字分布近乎隨機(jī) 所以:取任意兩位或兩位與另兩位的疊加作哈希地址,9-52,9.4 哈希表,數(shù)字分析法特性 數(shù)字分析法僅適用于事先明確知道表中所有關(guān)鍵碼每一位數(shù)值的分布情況 數(shù)字分析法完全依賴于關(guān)鍵碼集合。 如果換一個(gè)關(guān)鍵碼集合,選擇哪幾位要重新決定。,9-53,9.4 哈希表,哈希函數(shù)(平方取中法) 以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地址。 求“關(guān)鍵字的平方值” 的目的是“擴(kuò)大差別” 同時(shí)平方值的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響。,9-54,9.4 哈希表,平方取中法舉例 此方法在詞典處理中使用十分廣泛。它先計(jì)算構(gòu)成關(guān)鍵碼的標(biāo)識(shí)符的內(nèi)碼的平方, 然后按照散列表的大小取中間的若干位作為散列地址。 標(biāo)識(shí)符的八進(jìn)制內(nèi)碼表示及其平方值,標(biāo)識(shí)符 內(nèi)碼 內(nèi)碼的平方 散列地址 A 01 01 001 A1 0134 20420 042 B 02 4 004 DMAX 04150130 21526443617100 443 DMAX1 0415013034 5264473522151420 352 AMAX 01150130 135423617100 236 AMAX1 0115013034 3454246522151420 652,9-55,9.4 哈希表,平方取中法特性 平方取中法是較常用的構(gòu)造哈希函數(shù)的方法 適合于關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)且頻度很高的情況 中間所取的位數(shù),由哈希表長決定,9-56,9.4 哈希表,哈希函數(shù)(折疊法) 將關(guān)鍵字分割成位數(shù)相同的若干部分(最后部分的位數(shù)可以不同),然后取它們的疊加和(舍去進(jìn)位)為哈希地址。 移位疊加:將分割后的幾部分低位對(duì)齊相加 間界疊加:從一端沿分割界來回折送,然后對(duì)齊相加,9-57,9.4 哈希表,折疊法舉例:關(guān)鍵字為:0442205864,哈希地址位數(shù)為4 折疊法特性 折疊法適合于關(guān)鍵字的數(shù)字位數(shù)特別多,而且每一位上數(shù)字分布大致均勻的情況,9-58,9.4 哈希表,哈希函數(shù)(除留余數(shù)法) 取關(guān)鍵字被某個(gè)不大于哈希表長m的數(shù)p除后所得余數(shù)為哈希地址 H(key) = key MOD p ( pm ) m為表長 p為不大于m的素?cái)?shù)或是不含20以下的質(zhì)因子 哈希函數(shù)(除留余數(shù)法p值) 給定一組關(guān)鍵字為: 12,39,18,24,33,21,若取 p=9, 則他們對(duì)應(yīng)的哈希函數(shù)值將為: 3, 3, 0, 6, 6, 3 可見,若p中含質(zhì)因子3, 則所有含質(zhì)因子3的關(guān)鍵字均映射到“3 的倍數(shù)”的地址上,從而增加了“沖突”的可能 除留余數(shù)法特性 除留余數(shù)法是一種最簡單、最常用的構(gòu)造哈希函數(shù)的方法 可以對(duì)關(guān)鍵字直接取模(MOD),也可在折疊、平方取中等運(yùn)算之后取模。,9-59,9.4 哈希表,9.4.3 處理沖突法 “處理沖突” 的實(shí)際含義是:為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址。處理沖突的方法主要有三種: 開放定址法 再哈希法 鏈地址法,9-60,9.4 哈希表,處理沖突的方法(開放定址法) 為產(chǎn)生沖突的地址 H(key) 求得一個(gè)空的地址序列:H0, H1, H2, , Hs,1sm-1 Hi = H(key)+di MOD m ( i=1,2,s ) H(key)為哈希函數(shù) m為哈希表長 當(dāng)di取1,2,3,m-1時(shí),稱這種開放定址法為線性探測(cè)再散列。,9-61,舉例:在長度為11的哈希表中已填有關(guān)鍵字分別為17,60和29的記錄(哈希函數(shù)H(key) key MOD 11),現(xiàn)有第四個(gè)記錄,其關(guān)鍵字為38,由哈希函數(shù)得到的哈希地址為5,產(chǎn)生沖突。 線性探測(cè)再散列:得到下一個(gè)地址6,仍沖突;再求下一個(gè)地址7,仍沖突;直到哈希地址為8的位置(“空”)時(shí)止。 二次探測(cè)再散列:應(yīng)填入序號(hào)為4的位置。 偽隨機(jī)探測(cè)再散列:偽隨機(jī)數(shù)列9, 應(yīng)填入序號(hào)為2的位置。,9.4 哈希表,9-62,9.4 哈希表,用開放定址處理沖突時(shí),關(guān)鍵字為38的記錄插入前后的哈希表,9-63,9.4 哈希表,處理沖突的方法(再哈希法) Hi = RHi (key) ( i = 1, 2, , k ) 其中,R、Hi均是不同的哈希函數(shù),即在同義詞產(chǎn)生地址沖突時(shí)計(jì)算另一個(gè)哈希函數(shù)地址,直到?jīng)_突不再發(fā)生。 再哈希法特點(diǎn):不易產(chǎn)生聚集,但增加計(jì)算時(shí)間 處理沖突的方法(鏈地址法) 將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性鏈表中。假設(shè)某哈希函數(shù)產(chǎn)生的哈希地址區(qū)間0, m1上,則設(shè)立一個(gè)指針型向量: Chain Chain Hashm; 其每個(gè)分裂的初始狀態(tài)都是空指針。凡哈希地址為i的記錄都插入到頭指針為Chain Hashm的鏈表中。在鏈表中的插入位置可以在表頭或表尾,也可以在中間,以保持同義詞在同一線性鏈表中按關(guān)鍵字有序。,9-64,9.4 哈希表,舉例:給定關(guān)鍵字集合19,01,23,14,55,68, 11,82,36,設(shè)定哈希函數(shù)H(key)=key MOD 11 (表長=11)表后插入 查找不成功,再插入新結(jié)點(diǎn)時(shí),用表后插入方法較好,9-65,9.4 哈希表,舉例:給定關(guān)鍵字集合19,01,23,14,55,68, 11,82,36,設(shè)定哈希函數(shù)H(key)=key MOD 11 (表長=11)表頭插入 給定關(guān)鍵字集合,逐步生成哈希表時(shí),用表頭插入方法較好,9-66,9.4 哈希表,9.4.4 哈希表的實(shí)現(xiàn) 假設(shè)哈希函數(shù)為關(guān)鍵字求模運(yùn)算,哈希表用拉鏈法解決沖突,其結(jié)構(gòu)可以定義如下:,#define LEN 31 / 表長LEN最好為質(zhì)數(shù) type
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 電視劇在線平臺(tái)企業(yè)制定與實(shí)施新質(zhì)生產(chǎn)力戰(zhàn)略研究報(bào)告
- 沙漠越野車輛租賃行業(yè)跨境出海戰(zhàn)略研究報(bào)告
- 海報(bào)與宣傳冊(cè)設(shè)計(jì)行業(yè)深度調(diào)研及發(fā)展戰(zhàn)略咨詢報(bào)告
- 環(huán)保型油漆噴涂系統(tǒng)行業(yè)深度調(diào)研及發(fā)展戰(zhàn)略咨詢報(bào)告
- 智能輪椅語音導(dǎo)航企業(yè)制定與實(shí)施新質(zhì)生產(chǎn)力戰(zhàn)略研究報(bào)告
- 八年級(jí)上學(xué)期班主任的學(xué)生評(píng)估計(jì)劃
- 小學(xué)寒假學(xué)習(xí)計(jì)劃模板集錦(29篇)
- 2025年疫情下初中數(shù)學(xué)在線教學(xué)計(jì)劃
- 2025建筑公司項(xiàng)目管理優(yōu)化計(jì)劃
- 2025年加氣柱項(xiàng)目發(fā)展計(jì)劃
- 風(fēng)濕免疫科類風(fēng)濕關(guān)節(jié)炎一病一品優(yōu)質(zhì)護(hù)理匯報(bào)課件
- 2022-2023學(xué)年重慶市重慶市兩江新區(qū)部編版四年級(jí)下冊(cè)期末考試語文試卷答案
- 2022年火力發(fā)電廠焊接技術(shù)規(guī)程-電力焊接規(guī)程
- JCT2156-2012 纖維玻璃原料及配合料COD值的測(cè)定
- (完整版)庭審筆錄(刑事普通程序)
- 安化十二中學(xué)生違紀(jì)處分登記表
- 網(wǎng)格絮凝池計(jì)算書
- 07J501-1鋼雨篷玻璃面板圖集
- 【教案】第五課+雅與俗的交流-經(jīng)濟(jì)、科技發(fā)展與美術(shù)作品的關(guān)系+教學(xué)設(shè)計(jì)高中美術(shù)湘美版(2019)美術(shù)鑒賞
- 醫(yī)院網(wǎng)絡(luò)布線改造施工方案
- 普通診所污水、污物、糞便處理方案及周邊環(huán)境情況說明
評(píng)論
0/150
提交評(píng)論