前面我們學習了三種基本數(shù)據(jù)結(jié)構(gòu).ppt

前面我們學習了三種基本數(shù)據(jù)結(jié)構(gòu):,一般線性表（數(shù)據(jù)元素、關(guān)系、操作無限制） 棧和隊列（操作有限制） 字符串（數(shù)據(jù)元素有限制） 廣義表和數(shù)組（參與關(guān)系有限制） 樹和二叉樹結(jié)構(gòu) 圖結(jié)構(gòu),ADT的定義： 數(shù)據(jù)結(jié)構(gòu)的邏輯特性； 數(shù)據(jù)結(jié)構(gòu)上定義的操作； ADT的虛擬實現(xiàn)： 邏輯結(jié)構(gòu)的虛擬實現(xiàn)（存儲結(jié)構(gòu)） 操作的虛擬實現(xiàn)（算法）； ADT應(yīng)用舉例：,講授的方法:,前面學習的每一種數(shù)據(jù)結(jié)構(gòu)都定義了一 些常用的操作，如：初始化、訪問某數(shù) 據(jù)元素等等，因此，研究操作的實現(xiàn)（ 不是操作的定義）即算法也是數(shù)據(jù)結(jié)構(gòu) 的范疇。,有兩個操作在每個數(shù)據(jù)結(jié)構(gòu)上、在計算 機應(yīng)用中是非常重要的： 其一，確定元素的位置查找； 其二，將元素按某種順序排列分類 后面兩章我們分別學習這兩類操作的算 法（思想、效率、優(yōu)缺點等等）；,第九章 查找,本章學習各種查找算法，了解算法的思想、 效率、優(yōu)缺點、適用范圍等等。,預備知識,1、查找：在某一數(shù)據(jù)集合中查找數(shù)據(jù)元素是否存 在，若存在，返回其位置，否則，返回 失敗信息。,2、查找表：被查找數(shù)據(jù)元素的集合（一般都是一 種數(shù)據(jù)結(jié)構(gòu)，元素的位置是指在該數(shù) 據(jù)結(jié)構(gòu)中的邏輯位置，但是查找方法 還依賴與元素的存儲，即與存儲結(jié)構(gòu) 有關(guān)），一般是虛擬實現(xiàn)了的邏輯結(jié) 構(gòu)（數(shù)據(jù)結(jié)構(gòu)+存儲結(jié)構(gòu)）。,3、查找表的種類： 靜態(tài)查找表：數(shù)據(jù)集合在查找前后不變； 動態(tài)查找表：數(shù)據(jù)集合在查找后會改變；,注意： 查找表一般可以描述為： 數(shù)據(jù)對象D0：D0是具有相同特性的數(shù)據(jù)元素的 集合。每個數(shù)據(jù)元素含有類型相 同的關(guān)鍵字，可唯一標識數(shù)據(jù)元 素。 數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個集合（關(guān)系描述）。,4、查找方法： 查找表不同，查找方法就會不同。有很多不同 的查找方法。,5、查找算法的評價： 空間：占用的輔助空間少； 時間：時間少。查找的基本操作是比較，因此 時間主要體現(xiàn)為比較次數(shù)。,查找成功： 最大比較次數(shù)MSL 平均比較次數(shù)ASL,查找失敗： 最大比較次數(shù)MSL 平均比較次數(shù)ASL,9.1 靜態(tài)查找表的查找,靜態(tài)查找表有很多種，查找方法也不一樣， 下面介紹幾種常見的靜態(tài)查找表的查找方法。,一、靜態(tài)查找表是順序或鏈式存儲的線性表 順序查找,1、查找表的要求：線性表,2、查找方法：略,1、查找表的要求：,3、特點： 思想簡單，對查找表要求少，適應(yīng)面廣； 比較次數(shù)較大O(n)； （考慮查找概率不相等時應(yīng)該如何處理？）,二、靜態(tài)查找表是順序存儲的、有序的線性表 折半查找（Fibonacci查找、插值查找）,1、查找表的要求：順序存儲、有序的線性表,2、查找方法：,x=Rmid OK! xRmid mid+1hig,R,3、特點： 對查找表要求多； 比較次數(shù)較少O(log2n)；,折半查找的過程可以用一棵二叉樹表示，稱之為 “折半查找的判定樹”。（構(gòu)造方法自己總結(jié)， 該樹是唯一的嗎？） 例如: 折半查找在n=11 時的判定樹如下：,一般情況下，表長為n的折半查找的判定樹的深度和 含有n個結(jié)點的完全二叉樹的深度相同。 假設(shè) n=2h-1 并且查找概率相等則：,在n50時，可得近似結(jié)果：,三、靜態(tài)查找表是樹 靜態(tài)樹查找,1、查找表的要求：二叉分類樹,2、查找方法：,X與根比較： 相等： OK！ X根： 在右子樹上找,3、特點： 類似折半，最大是樹的深度； 等概率時，折半查找的判定樹是最好的； 不等概率時，概率高的應(yīng)該靠近根。,四、靜態(tài)查找表是分塊索引表 分塊查找,1、查找表的要求：順序存儲、分塊有序,2、查找方法：,折半方法確定可能在的塊； 順序查找確定元素；,3、特點： 要建立索引表； 效率介于折半和順序之間；,9.2 動態(tài)查找表的查找 動態(tài)二叉分類樹的查找,1、查找表的要求：二叉分類樹,2、查找方法：,若二叉排序樹為空，則查找不成功；否則 1）若給定值等于根結(jié)點的關(guān)鍵字，則查找成功； 2）若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左 子樹上進行查找； 3）若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右 子樹上進行查找。,Btreenode * find( Btreenode *BST,elentype x) /在以BST為根指針的二叉排隊 樹中查找值為x的結(jié)點 if ( BST= =NULL) return NULL; /查找失敗 else if (BST-data= =x) /查找成功 return BST; else if (BST-datax) /進入左子樹查找 return find ( BST-left,x); else /進入右子樹查找 return find (BST-right,x); ,3、特點： 與樹的深度有關(guān)；,對于每一棵特定的二叉排序樹，均可按照平均 查找長度的定義來求它的ASL值，顯然，由值 相同的n個關(guān)鍵字構(gòu)造所得的，不同形態(tài)的各棵 二叉排序樹的平均查找長度的值不同，甚至可 能差別很大，例如： 由關(guān)鍵字序列1，2，3，4，5構(gòu)造而得的二叉 排序樹，ASL =（1+2+3+4+5）/ 5 = 3 由關(guān)鍵字序列3，1，2，5，4構(gòu)造而得的二叉 排序樹，ASL =（1+2+3+2+3）/ 5 = 2.2,一般情況下，考慮含有n個關(guān)鍵字可能出現(xiàn)的n!種 序列出現(xiàn)的可能性相等。 不失一般性，假設(shè)某個序列中有k個關(guān)鍵字小于第 一個關(guān)鍵字，即有n-k-1個關(guān)鍵字大于第一個關(guān)鍵 字，由它構(gòu)造的二叉排序樹的平均查找長度是n和 k的函數(shù)： P(n, k) (0kn-1),則含n個關(guān)鍵字的二叉排序樹的平均查找長度：,而在等概率的情況下，,由此：,可類似于解差分方程，此遞歸方程有解：,從查找的角度看，希望由任意序列生成的二叉 排序樹，其左、右子樹的深度近似相等，但實際 上有47%的情況生成的二叉排序樹非如此。 那么，如何構(gòu)造高度比較低的二叉分類樹呢？,9.3 平衡二叉樹,一、平衡二叉樹的定義,1、定義：一棵分類二叉樹是平衡的，當且僅當每個結(jié)點 的左右子樹的高度至多相差為1 。由G.M.Adelson_Velskii 和E.M.Landis給出的定義AVL樹。,遞歸定義： （）空樹是二叉分類樹； （）它的左右子樹都是二叉分類樹，且左右子樹 的高度最多相差為；,、平衡因子： 左子樹的高度右子樹的高度，即 BF(t)=Hl-Hr 平衡二叉樹中，對任意結(jié)點：BF=、 ,、平衡二叉樹的特點： 其深度和log2n同數(shù)量級，即樹的平均查找長度 為O(log2n);,4、AVL樹的構(gòu)造和調(diào)整過程：,（）基本原則： 按照二叉分類樹的構(gòu)造方法，構(gòu)造過程中判斷是否 為平衡二叉樹（平衡因子），是，則繼續(xù)構(gòu)造；否則， 按一定的原則（保持是二叉分類和平衡）將其調(diào)整為平 衡，然后繼續(xù)。,（）插入過程中的調(diào)整原則： 二叉分類樹在插入前平衡，插入一個結(jié)點后如果失去 平衡，則至少有一個結(jié)點的平衡因子變?yōu)榛颉?若平衡因子，則左分支高于右分支； 若平衡因子，則右分支高于左分支；,失去平衡的四種情況：,型：左分支的左子樹上插入，使之失去平衡因子 平衡因子；,特殊地：,型：右分支的右子樹上插入，使之失去平衡因子 平衡因子；,特殊地：,型：左分支的右子樹上插入，使之失去平衡因子 平衡因子；,特殊地：,L型：右分支的左子樹上插入，使之失去平衡因子 平衡因子；,特殊地：,略（參見教材236-238）,5、算法：,6、舉例：有下列元素，構(gòu)造平衡二叉樹 13,24,37,90,53,13,24,37,RR型,24,13,37,13,24,37,90,53,90,53,RL型,24,13,37,53,90,53,37,90,9.3 平衡二叉樹,二、平衡二叉樹的查找,1、查找過程：同二叉分類樹一樣！,、效率分析： 查找過程中和給定值進行比較的關(guān)鍵字的個數(shù)不 超過平衡樹的深度。 假設(shè)深度為h的二叉平衡樹上所含結(jié)點數(shù)的最小值 為Nh，則顯然 Nh = Nh-1 + Nh-2 + 1 由此可以推導出：hlog（n） 因此，在平衡樹上進行查找的時間復雜度為O(log(n),9.4 哈希查找,一、哈希技術(shù)介紹,1、哈希技術(shù)的提出背景：,一般的線性表，樹中，記錄在結(jié)構(gòu)中的相對位置是隨機的，即和記錄的關(guān)鍵字之間不存在確定的關(guān)系，因此，在結(jié)構(gòu)中查找記錄時需進行一系列和關(guān)鍵字的比較。這一類查找方法建立在“比較“的基礎(chǔ)上，查找的效率依賴于查找過程中所進行的比較次數(shù)。,“哈?！笔怯⑽腍ASH的音譯，又翻譯作“散列”、 “雜湊”等。,那么，有沒有不用比較的查找方法？,9.4 哈希查找,理想的情況是能直接找到需要的記錄，因此必須在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系f，使每個關(guān)鍵字和結(jié)構(gòu)中一個唯一的存儲位置相對應(yīng)。,因此，如果有一個函數(shù)，它能夠根據(jù)要查找的關(guān)鍵字直接計算出要查找記錄的地址，該地址的內(nèi)容為空，則查找的元素不存在，否則，查找成功。顯然，這樣的查找不需要比較！,基于這種思想的技術(shù)就是HASH技術(shù)；,9.4 哈希查找,哈希表最常見的例子是以學生學號為關(guān)鍵字的成績表，號學生的記錄位置在第一條， 2號學生的記錄位置在第二條， 號學生的記錄位置在第條.,如果我們以學生姓名為關(guān)鍵字，如何建立查找表，使得根據(jù)姓名可以直接找到相應(yīng)記錄呢？,其次，我們?nèi)⌒彰鱾€字的拼音字頭字母的編號和為該 記錄的存儲位置，例如吳軍，wj=33，存儲位置33； 吳曉燕，wxy=72,存儲位置為72；,首先，我們規(guī)定每個字母的編號：,9.4 哈希查找,顯然存儲地址從378。如果76個學生的姓名的拼音字頭字母都互不相同，則我們可以按這種方式存儲這些學生的信息，而且很容易的查找一個學生的信息。,例如：要查吳曉燕的信息，則計算wxy=72，第72個位置存儲的就是該學生的信息。,如果我們有m個空間，n個數(shù)據(jù)元素，n=m，且每個 數(shù)據(jù)元素能按某種映射關(guān)系得到唯一的空間地址，則 我們很容易的實現(xiàn)查找！,但是，千萬不要忘了我們假設(shè)的前提： 互不相同！,例如，如果學生中還有一個學生姓名為王新云，wxy=72 怎么辦？,9.4 哈希查找,一、哈希技術(shù)介紹,2、什么情況下使用HASH技術(shù)？,如果問題的數(shù)據(jù)元素已知，很容易地建立數(shù)據(jù)元素 和存儲地址之間的一一映射函數(shù)關(guān)系，HASH技術(shù)是很 簡單的，HASH技術(shù)也就失去了意義，實際上HSAH技 術(shù)是針對下類問題的：,問題的數(shù)據(jù)元素的可用集合很大，而一個問題的 具體數(shù)據(jù)元素是取自該可用集合的一個很小的任意一 個集合，因此，解決問題時需要的空間大小是根據(jù)小 集合大小確定的，但是，如果要建立函數(shù)映射，函數(shù) 的定義域應(yīng)該是大集合，而值域是由小集合確定的， 因此建立這樣的一一映射是很困難的，所以才有了HASH 技術(shù)。,9.4 哈希查找,一、哈希技術(shù)介紹,3、HASH類問題的描述：,假設(shè)問題可能用到的關(guān)鍵字集合為U，|U|=n0，即該集合 的元素個數(shù)為n0，而一個問題實際用到的關(guān)鍵字集合為S， |S|=n，nn0，且S是取自U的任意一個子集合，表示 為R1,R2,R3,.Rn，其關(guān)鍵字集合為K1,K2,.,Kn； T是解決問題需要的連續(xù)空間，它由m個存儲單元組成， 表示為T0m-1，mn。,有一個函數(shù)H，其定義域是keyU，值域是i 0m-1， 它將關(guān)鍵字映射到存儲空間地址上； H(key)= i key U, i0m-1,9.4 哈希查找,一、哈希技術(shù)介紹,n,H,9.4 哈希查找,一、哈希技術(shù)介紹,4、有關(guān)基本概念：,（1）HASH函數(shù)：將關(guān)鍵字映射到存儲空間地址的函數(shù)， 記作：H(key),（2）HASH地址：由HSAH函數(shù)計算出的關(guān)鍵字地址；,（3）HASH表：存儲記錄的連續(xù)地址空間T；,（4）HASH造表：利用HASH函數(shù)將記錄存儲到HASH表 中的過程；,（5）HASH表的填充度（裝填因子）： 表中填入的記錄數(shù) = HASH表的長度,9.4 哈希查找,一、哈希技術(shù)介紹,（6）沖突：由于HASH函數(shù)的定義域是U，而S是U的任 意一個小子集，映射地址空間是由S的大小 確定的，因此，對于不同的關(guān)鍵字可能得到 相同的HASH地址，即： 若 key1key2 , 而 H(key1)=H(key2)，則稱為 沖突。,（7）同義詞： 若 H(key1)=H(key2)，則key1和key2互稱 為同義詞。,5、HASH技術(shù)的關(guān)鍵：, HASH函數(shù)的構(gòu)造, 解決沖突的方法,9.4 哈希查找,一、哈希技術(shù)介紹,5、HASH問題舉例：,我們寫程序時，可以用的標識符是一個很大集合（U） 因為凡是符合語言詞法定義的都是合法、可用的標 識符，但是對于你寫的每一個程序，真正使用到的 標識符卻是一個很小的子集（S），編譯程序存儲和 處理程序時只要能存儲和處理任意的小子集S即可， 但是，要注意S的特點！,例如：標準PASCAL的標識符為字母開頭的8個長度的 字母數(shù)字串，則|U|=C(26,1)*C(36,1)*7=1.093881012，而 一個程序中可能出現(xiàn)的標識符不會太多，1000足矣！即 |S|=1000。,9.4 哈希查找,二、哈希函數(shù)的構(gòu)造方法,1、直接定址法： H(key)=key 或 H(key)=a*key+b a,b為常數(shù),特點： * 關(guān)鍵字必須是整數(shù)； * 地址集合和關(guān)鍵字集合大小相同，沒有沖突； * 空間浪費大；,2、數(shù)字分析法： H(key)=關(guān)鍵字的某進制的若干位組成,特點： * 要求關(guān)鍵字已知； * 取幾位，哪幾位的原則是盡量避免沖突， 均勻性好；,9.4 哈希查找,3、平方取中法： H(key)=關(guān)鍵字平方后的中間幾位,4、折疊法： H(key)=將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取 這幾部分的疊加和（舍去進位）,特點：這是一種較常用的方法。 * 關(guān)鍵字不一定全部知道； * 由于一個數(shù)平方后的中間幾位和數(shù)的每一位相關(guān)， 均勻性較好，取的位數(shù)與表長有關(guān)； * 乘和截取的代價較高；,特點： * 關(guān)鍵字位數(shù)很多，而且關(guān)鍵字中每一位上數(shù)字 分布大致均勻時，均勻性很好；,9.4 哈希查找,5、除留余法： H(key)= key MOD P P是不大于m的素數(shù)，m是 HASH表的長度；,6、隨機數(shù)法： H(key)= Random(key)； Random位隨機函數(shù),特點：這是一種最簡單、最常用的方法。 * P的選擇很重要，選擇不好會產(chǎn)生同義詞； * P一般取位素數(shù)或不包含小于20的質(zhì)數(shù)的合數(shù)；,HASH函數(shù)考慮的因素： （1）計算HASH函數(shù)的時間； （2）關(guān)鍵字的長度； （3）HASH表的長度； （4）關(guān)鍵字的分布情況； （5）記錄的查找頻率；,9.4 哈希查找,三、沖突的解決方法,1、開放定址法：（閉散列） 發(fā)生沖突后，按一定的原則尋找新的地址： Hi=(H(key)+di) MOD m i=1,2,.,k di為增量，m為HASH表的長度； di的取法： 線性探測：di=1,2,3,.,m-1 二次探測：di=12,-12,22,-22,.,k2,解決沖突的策略分為兩類： (1) 閉散列方法(Closed Hashing):同義詞放在HASH表 的其他位置；(Open addressing,又稱為開地址法) (2) 閉散列方法(Open Hashing):同義詞放在HASH表 之外的空間中；(Separate chaining,又稱為拉鏈法),9.4 哈希查找,三、沖突的解決方法,2、再造HASH法：（閉散列） Hi=RHi(key) 用一系列HASH函數(shù)計算地址,3、鏈地址法：（開散列） 將同義詞存放在同一個鏈 表中；,9.4 哈希查找,4、建立公共溢出區(qū)法： 除了HASH表外，開辟一個公共溢出區(qū)，一旦沖突，將同義詞放入公共溢出區(qū)；,HASH表:,溢出表:,9.4 哈希查找,四、哈希查找,1、哈希查找的方法,給定關(guān)鍵字 k ： （1）用給定的HASH函數(shù)計算出k的HASH地址； i=H(key) （2）若該地址為空，則查找失??； 否則，若 Ti=k ,則查找成功，返回地址； 否則，按HASH造表時解決沖突時的 方法計算出新的地址； （3）重復（2）直到查找成功或失敗。,9.4 哈希查找,、哈希查找的算法,參見教材259頁,9.4 哈希查找,3、舉例：,已知有一組元素：19,14,23,01,6