1、第第 6 章章 查找表查找表6.1 6.1 基本概念基本概念查找表是一種查找表是一種以集合為邏輯結構以集合為邏輯結構、以查找、以查找為為“核心核心”運算、同時包括其它運算的數據結運算、同時包括其它運算的數據結構。構。 6.1.1 6.1.1 集合的基本概念集合的基本概念集合：由任意一些可分辨的對象構成的整集合：由任意一些可分辨的對象構成的整體。例如，所有整數放在一起構成一個集合，體。例如，所有整數放在一起構成一個集合，稱為整數集。空集是不含任何元素的集合，記稱為整數集。空集是不含任何元素的集合，記為為。 在數據結構課程中，通常只考慮那些由具在數據結構課程中，通常只考慮那些由具有相同類型的數據元

2、素構成的集合。有相同類型的數據元素構成的集合。 6.1.2 6.1.2 查找表的基本概念查找表的基本概念 查找是一種常用運算，其功能是從大查找是一種常用運算，其功能是從大量的數據元素中找出某個特定的數據元素。量的數據元素中找出某個特定的數據元素。標識數據元素的數據項稱為標識數據元素的數據項稱為關鍵字關鍵字，簡稱簡稱鍵鍵。該數據項的值稱為。該數據項的值稱為鍵值鍵值。能夠唯一地標識能夠唯一地標識數據元素數據元素的的關鍵字稱關鍵字稱為為主關鍵字主關鍵字。不不能唯一地標識能唯一地標識數據元素數據元素的的關鍵字稱關鍵字稱為為次關鍵字次關鍵字。查找運算的功能的確切表述：根據查找運算的功能的確切表述：根據給

3、定的某個值給定的某個值K，在查找表中尋找一個，在查找表中尋找一個其鍵值等于其鍵值等于K的數據元素。若找到一個的數據元素。若找到一個這樣的數據元素，則查找成功，運算結這樣的數據元素，則查找成功，運算結果為該數據元素在表中的位置；否則，果為該數據元素在表中的位置；否則，查找不成功，此時的運算結果為一個特查找不成功，此時的運算結果為一個特殊標志。殊標志。查找表：具有同一類型的數據元素組成的集合。查找表：具有同一類型的數據元素組成的集合。靜態查找表包括下列三種基本運算：靜態查找表包括下列三種基本運算： 建表建表CREATE(ST), 其作用是生成一個由用戶給其作用是生成一個由用戶給定的若干數據元素組成

4、的靜態查找表定的若干數據元素組成的靜態查找表ST。 查找查找SEARCH(ST，K)，若，若ST中存在關鍵字值中存在關鍵字值等于等于K的數據元素，運算結果為該數據元素在的數據元素，運算結果為該數據元素在ST中中的位置；否則，運算結果為一特殊標志。的位置；否則，運算結果為一特殊標志。 讀表元讀表元GET(ST，pos)，其運算結果是，其運算結果是ST中中pos位置上的數據元素。位置上的數據元素。 (靜態查找表是僅對查找表進行查找操作，而不能靜態查找表是僅對查找表進行查找操作，而不能被改變的表。被改變的表。) )動態查找表動態查找表 包括包括查找查找讀表元以及下讀表元以及下列三種基本運算：列三種基

5、本運算：插入插入INSERT(ST，K)，若，若ST中不存在中不存在關鍵字值等于關鍵字值等于K的數據元素，則將一個關鍵的數據元素，則將一個關鍵字值等于字值等于K的新數據元素插入到的新數據元素插入到ST中。中。刪除刪除DELETE(ST，K)，當，當ST中存在關中存在關鍵字值等于鍵字值等于K的數據元素時，將其刪除。的數據元素時，將其刪除。初始化初始化INITIATE(ST)，其作用是設置一，其作用是設置一個空的動態查找表個空的動態查找表ST。 (動態查找表：除了對查找表進行查找操作動態查找表：除了對查找表進行查找操作外，還能向表中插入數據元素，或刪除表中外，還能向表中插入數據元素，或刪除表中的數

6、據元素，因而表可以被改變。的數據元素，因而表可以被改變。) )6.2 6.2 靜態查找表的實現靜態查找表的實現6.2.1 6.2.1 順序表上的查找順序表上的查找 靜態查找表的順序表的類型定義如下：靜態查找表的順序表的類型定義如下：#definemaxsize靜態查找表的表長；靜態查找表的表長；typedefstructkeytypekey;/*關鍵字關鍵字*/./*其它域其它域*/rec;typedefstructrecitemmaxsize+1;intn;/*最后一個數據元素的下標最后一個數據元素的下標*/sqtable;靜態查找表中的數據元素存放在上述數組靜態查找表中的數據元素存放在上述

7、數組的第的第1 1到第到第n n個單元，第個單元，第n+1n+1到最后一個單元為到最后一個單元為備用區。不同的是，這里多說明了一個單元備用區。不同的是，這里多說明了一個單元即第即第0 0個單元，該單元被用于設置個單元，該單元被用于設置 崗哨崗哨 以便以便簡化查找運算的實現。簡化查找運算的實現。在上述存儲結構上實現查找運算的一種直在上述存儲結構上實現查找運算的一種直觀方法是觀方法是 順序查找法順序查找法 ：從表的第：從表的第n n個位置開個位置開始，從后往前依次將各個位置上的數據元素始，從后往前依次將各個位置上的數據元素的鍵值與給定值的鍵值與給定值K K比較。若某個位置上的數據比較。若某個位置上

8、的數據元素的鍵值與元素的鍵值與K K相等則查找成功，回送該位置相等則查找成功，回送該位置作為結果；若所有數據元素的鍵值均與作為結果；若所有數據元素的鍵值均與K K不等，不等，回送回送0,0,標記查找不成功。標記查找不成功。 順序查找算法順序查找算法intsearch-sqtable(sqtableR,keytypeK)R.item0.key=K;/*設置崗哨設置崗哨*/i=R.n;/*設置比較位置初值設置比較位置初值*/While(R.itemi.key!=K)i-;/*未找到時修改比較位置繼續查找未找到時修改比較位置繼續查找*/return(i);18714 18 21 23 29 31 3

9、5 38 42 46 49 52012345678910 11 12 13R.nk=18順序查找算法順序查找算法(順序表采用普通數組形式順序表采用普通數組形式)intsearch-sqtable(intitem,intn,intk)inti;item0=k;/*在數組的低端設置監視哨在數組的低端設置監視哨*/While(itemi!=k)i-;/*從后往前找從后往前找*/returni;/*找不到時，找不到時，i為為0*/崗哨崗哨R.item0的作用是：保證的作用是：保證while循環一定終止循環一定終止(即使查找不成功、即即使查找不成功、即R中無鍵值等于中無鍵值等于K的數據元素，當的數據元素

10、，當i=0時時循環終止條件循環終止條件被迫被迫成立成立)。因此，不。因此，不必將必將i0寫入循環條件從而使循環條寫入循環條件從而使循環條件得到簡化件得到簡化(對比第對比第2章定位算法章定位算法locate_sqlist)。有關測試表明：當。有關測試表明：當n1000時，進行一次查找所花費的時時，進行一次查找所花費的時間平均減少約一半。間平均減少約一半。查找運算通常以查找運算通常以 數據元素的鍵值與給定值的比較數據元素的鍵值與給定值的比較 作為標準操作，也就是用作為標準操作，也就是用 數據元素的鍵值與給定值數據元素的鍵值與給定值的比較次數的比較次數 來作為查找算法的時間性能。上述比較來作為查找算

11、法的時間性能。上述比較次數稱為次數稱為 查找長度查找長度 。顯然，查找長度與鍵值等于給。顯然，查找長度與鍵值等于給定值定值K K的元素在順序表中的位置有關。的元素在順序表中的位置有關。若順序表中第若順序表中第n n個元素的鍵值為個元素的鍵值為K K，則順序查找算法，則順序查找算法的查找長度為的查找長度為1 1；若第；若第1 1個元素的鍵值為個元素的鍵值為K K，則查找長，則查找長度為度為n n；若表中無鍵值等于；若表中無鍵值等于K K的元素的元素( (查找不成功查找不成功) )，則，則查找長度為查找長度為n+1n+1。可見差別很大。較合理的辦法是以。可見差別很大。較合理的辦法是以 查找成功時的

12、查找成功時的平均查找長度平均查找長度(記為記為ASL)ASL)作為查找算法作為查找算法時間性能的度量，其定義為：時間性能的度量，其定義為： n nASLASL P Pi iC Ci i i=1i=1順序查找算法的平均查找長度順序查找算法的平均查找長度ASL:查找成功：查找成功：ASL=(n+1)/2查找失敗：查找失敗：ASL=n+1可見，順序查找算法時間復雜度為可見，順序查找算法時間復雜度為O(n)6.2.2 6.2.2 有序表上的有序表上的查找查找( (二分查找二分查找)有序表：對于任何一個順序表，若有序表：對于任何一個順序表，若其中的所有數據元素按鍵值的某種次其中的所有數據元素按鍵值的某種

13、次序序( (升序或降序升序或降序) )排列，則稱為有序表。排列，則稱為有序表。由于有序表中所有元素按鍵值遞增的次序排由于有序表中所有元素按鍵值遞增的次序排列，若將表中任一元素的鍵值列，若將表中任一元素的鍵值R.itemi.keyR.itemi.key與與給定值給定值K K比較，可根據三種比較結果區分出三種比較，可根據三種比較結果區分出三種情況：情況：R.itemi.key=KR.itemi.key=K，查找成功，查找成功，R.itemiR.itemi即為待查元素；即為待查元素；R.itemi.keyKR.itemi.keyK，說明待查元素若在表中，說明待查元素若在表中，則一定排在則一定排在R.

14、itemiR.itemi之前；之前；R.itemi.keyKR.itemi.keyK，說明待查元素若在表中，說明待查元素若在表中，則一定排在則一定排在R.itemiR.itemi之后。之后。因此，在一次比較之后，若沿未找到待查元因此，在一次比較之后，若沿未找到待查元素，則可根據比較結果縮小進一步查找的區間。素，則可根據比較結果縮小進一步查找的區間。二分查找法的基本思想：首先選取表二分查找法的基本思想：首先選取表中間位置的元素，將其關鍵碼與給定值進行中間位置的元素，將其關鍵碼與給定值進行比較，若相等，則查找成功；若給定值比該比較，若相等，則查找成功；若給定值比該關鍵碼小，則要找的元素一定在表的左

15、半區，關鍵碼小，則要找的元素一定在表的左半區，則繼續對左半區進行折半查找。若給定值比則繼續對左半區進行折半查找。若給定值比該關鍵碼大，則要找的元素一定在表的右半該關鍵碼大，則要找的元素一定在表的右半區，則繼續對右半區進行折半查找。如此遞區，則繼續對右半區進行折半查找。如此遞推，直到查找成功或查找區間長度為推，直到查找成功或查找區間長度為0(0(查找查找不成功不成功) )為止。為止。二分查找算法中的變量含義：二分查找算法中的變量含義：lowlow : : 查找區間的下界；查找區間的下界；highig: : 查找區間的上界；查找區間的上界；midmid=(low+hig)/2=(low+hig)/

16、2：區間的中間位置；：區間的中間位置；K K ：給定值：給定值 ( ( 如如 K=18 )K=18 )。二分查找算法如下：二分查找算法如下： int binsearch(sqtable R, keytype K)int binsearch(sqtable R, keytype K)low=1; hig=R.n; /low=1; hig=R.n; /* *置查找區間初值置查找區間初值* */ / while(low=hig) / while(low=hig) /* *區間長度不為區間長度不為0 0時繼續查找時繼續查找* */ / mid=(low+hig)/2; / mid=(low+hig)/

17、2; /* *找出區間的中間位置找出區間的中間位置* */ /switchswitch case K=R.itemmid.key: return mid case K=R.itemmid.key: return mid； case KR.itemmid.key: hig=mid-1; break;case KR.itemmid.key: low=low+1; break case kR.itemmid.key: low=low+1; break / /* *調整到右半區調整到右半區* */ / return(0); return(0); / /* *返回返回0 0，表示查找不成功，表示查找不成

18、功* */ / 15 17 18 22 35 51 60 88 930123456789hig=9low=1mid=5hig=4low=1 mid=2hig=4low=3mid=3K=18 K=18 ( (查找成功的例子查找成功的例子) )15 17 18 22 35 51 60 88 930123456789hig=9low=1mid=5hig=4low=1 mid=2hig=4low=3 mid=3K=20 K=20 ( (查找不成功的例子查找不成功的例子) )low=4hig=4 mid=4hig=3 low=4二分查找算法每進行一次鍵值與給定值的二分查找算法每進行一次鍵值與給定值的比較

19、，查找區間的長度至少減小為原來二分比較，查找區間的長度至少減小為原來二分之一之一(“二分查找二分查找”由此得名由此得名)。由此易推算出。由此易推算出二分查找的查找長度不超過二分查找的查找長度不超過log2n+1。二分查找的平均查找長度為：二分查找的平均查找長度為：ASLblog2(n+1)-1二分查找的時間復雜性為：二分查找的時間復雜性為：T(n)=O(log2n)由此可見，二分查找的時間性能比由此可見，二分查找的時間性能比順序查找好。但二分查找要求以有序順序查找好。但二分查找要求以有序表作為存儲表示。當采用的存儲結構表作為存儲表示。當采用的存儲結構不是順序表、或者表中元素未按鍵值不是順序表、

20、或者表中元素未按鍵值的次序的次序( (遞增或遞減遞增或遞減) )排列時，則不能排列時，則不能進行二分查找。而順序查找則無此限進行二分查找。而順序查找則無此限制。制。6.2.3 6.2.3 索引順序表上的查找索引順序表上的查找 索引順序表是按索引存儲方式構造的一種索引順序表是按索引存儲方式構造的一種存儲結構。一個索引順序表由兩個部分組成：存儲結構。一個索引順序表由兩個部分組成：一個順序表和一個索引表。其中的順序表在一個順序表和一個索引表。其中的順序表在組織形式上與普通的順序表完全相同；而索組織形式上與普通的順序表完全相同；而索引表本身在組織形式上也是一個順序表。索引表本身在組織形式上也是一個順序

21、表。索引順序表的特點表現為以下兩個方面引順序表的特點表現為以下兩個方面 ：順序表中的數據元素順序表中的數據元素“按塊有序按塊有序”；索引表反映了這些索引表反映了這些“塊塊”的有關特性。的有關特性。所謂所謂 按塊有序按塊有序 是指：順序表中的數據元是指：順序表中的數據元素被劃分成一些子表素被劃分成一些子表( (塊塊) )；并且對其中任意；并且對其中任意兩個相鄰表來說，排在前面的子表中的任一兩個相鄰表來說，排在前面的子表中的任一數據元素的鍵值小于排在后面的子表中的所數據元素的鍵值小于排在后面的子表中的所有數據元素的鍵值。有數據元素的鍵值。圖圖6-16-1中的順序表被分成三塊中的順序表被分成三塊:(

22、22:(22，1212，1313，8 8，9 9，20)20)，(33(33，4242，4444，3838，2424，4848，) )，(60(60，5858，7474，4747，8686，53)53)，并且，并且它們中的數據元素是按塊有序的它們中的數據元素是按塊有序的( (但每一塊但每一塊中的數據元素不要求有序中的數據元素不要求有序) )。224886171322 12 138920 33 42 44 38 24 48 60 58 74 47 86 5312345678910 11 12 13 14 15 16 17 18圖圖6-16-1 索引順序表示例索引順序表示例 索引表索引表塊內最大鍵

23、值塊內最大鍵值塊起始位置塊起始位置 索引順序表上的查找分兩個階段：索引順序表上的查找分兩個階段：確定待查元素所在的塊；確定待查元素所在的塊；在塊內查找待查的元素。在塊內查找待查的元素。以以6-16-1所示的索引順序為例。假如給定所示的索引順序為例。假如給定K=24K=24，應先將應先將K K與索引表中的各個塊內最大鍵值比較，與索引表中的各個塊內最大鍵值比較，得知只能在第二塊，然后在第二塊中進行查找。得知只能在第二塊，然后在第二塊中進行查找。第二階段只能采用順序查找法，而第一階段既第二階段只能采用順序查找法，而第一階段既可采用順序查找法，也可采取二分查找法可采用順序查找法，也可采取二分查找法(

24、(索索引表中的索引項按引表中的索引項按 塊內最大鍵值塊內最大鍵值 域的值有域的值有序序) )。索引順序表上的上述查找方法稱為分塊查找。索引順序表上的上述查找方法稱為分塊查找。 6.3 6.3 樹表樹表 前面所述的靜態查找表所含數據元素前面所述的靜態查找表所含數據元素(在檢索在檢索階段內階段內)是固定不變的。而動態查找表則不然，是固定不變的。而動態查找表則不然，其所含數據元素可以經插入、刪除運算而不斷其所含數據元素可以經插入、刪除運算而不斷的改變。動態查找表的這種動態特性要求我們的改變。動態查找表的這種動態特性要求我們采用靈活的存儲表示方法來組織動態查找表中采用靈活的存儲表示方法來組織動態查找表

25、中的數據元素。的數據元素。本節介紹幾種用來表示動態查找表的樹表本節介紹幾種用來表示動態查找表的樹表(主主要是二叉排序樹和平衡二叉排序樹。要是二叉排序樹和平衡二叉排序樹。6.3.1 6.3.1 二叉排序樹二叉排序樹一棵一棵二叉排序樹二叉排序樹(又稱又稱二叉查找樹二叉查找樹)或者是一棵或者是一棵空樹，或者是一棵同時滿足下列條件的二叉樹：空樹，或者是一棵同時滿足下列條件的二叉樹：1若它的左子樹不空，則左子樹上所有結點若它的左子樹不空，則左子樹上所有結點的鍵值均小于它的根結點的鍵值；的鍵值均小于它的根結點的鍵值；2若它的右子樹不空，則右子樹上所有結點若它的右子樹不空，則右子樹上所有結點的鍵值均大于它的

26、根結點的鍵值；的鍵值均大于它的根結點的鍵值；3它的左、右子樹也分別為二叉排序樹。它的左、右子樹也分別為二叉排序樹。37圖圖6-26-2 二叉排序樹示例二叉排序樹示例2151632852333606563559042981067584583例如例如:是二叉排序樹。是二叉排序樹。66不不70二叉排序樹給查找運算的實現提供了二叉排序樹給查找運算的實現提供了便利條件：在表示一棵二叉排序樹的二便利條件：在表示一棵二叉排序樹的二叉鏈表上，要找鍵值比某結點叉鏈表上，要找鍵值比某結點X X的鍵值小的鍵值小( (大大) )的結點，只需通過結點的結點，只需通過結點X X的左指針的左指針( (右指針右指針) )到它

27、的左到它的左( (右右) )子樹中去找。子樹中去找。二叉排序樹具有下述重要性質；中二叉排序樹具有下述重要性質；中根遍歷一棵二叉排序樹所得的結點訪問根遍歷一棵二叉排序樹所得的結點訪問序列是鍵值的遞增有序序列。序列是鍵值的遞增有序序列。 1 1二叉排序樹上的查找二叉排序樹上的查找(1)(1)若查找樹為空，則查找失敗；若查找樹為空，則查找失敗；(2)(2)若查找樹非空，將若查找樹非空，將給定值與給定值與查找樹的查找樹的根結點關鍵碼比較；根結點關鍵碼比較；(3)(3)若相等，則查找成功；否則若相等，則查找成功；否則 若給定值小于根結點關鍵碼，則繼若給定值小于根結點關鍵碼，則繼續在左子樹上進行查找；續在

28、左子樹上進行查找； 若給定值大于根結點關鍵碼，則繼若給定值大于根結點關鍵碼，則繼續在右子樹上進行查找。續在右子樹上進行查找。50308020908540358832例如例如:二叉排序樹二叉排序樹查找關鍵碼查找關鍵碼=50,505035,503040355090,50809095,2 2二叉排序樹的插入二叉排序樹的插入在二叉排序樹上進行插入的原則是：在二叉排序樹上進行插入的原則是：(1)(1)必須保證插入一個結點之后仍為必須保證插入一個結點之后仍為一棵二叉排序樹。一棵二叉排序樹。(2)(2)僅當二叉排序樹上不存在鍵值等僅當二叉排序樹上不存在鍵值等于于 K K 的結點時才插入一個這樣的結點。的結點

29、時才插入一個這樣的結點。因此，插入算法必須包含查找過程；因此，插入算法必須包含查找過程；并且當查找不成功時實施插入新結點的并且當查找不成功時實施插入新結點的操作。操作。在動態查找表的定義中沒有生成運算，在動態查找表的定義中沒有生成運算，只有初始化運算。這是因為動態查找表只有初始化運算。這是因為動態查找表是從空表開始經反復的插入是從空表開始經反復的插入( (及刪除及刪除) )而而動態生成的。另一方面，假如需要的話，動態生成的。另一方面，假如需要的話，可以通過調用初始化算法和插入算法而可以通過調用初始化算法和插入算法而實現生成運算。實現生成運算。 63559042981067584583從空樹開始

30、建立二叉排序樹的過程從空樹開始建立二叉排序樹的過程70【例】已知關鍵碼序列為【例】已知關鍵碼序列為: : 63,90,70,55,67,42,98,83,10,45,58 63,90,70,55,67,42,98,83,10,45,58建立一棵二叉排序樹的過程建立一棵二叉排序樹的過程3 3二叉排序樹的刪除二叉排序樹的刪除 與插入相反，刪除在查找成功之后進與插入相反，刪除在查找成功之后進行，并且要求在刪除二叉排序樹上某個行，并且要求在刪除二叉排序樹上某個結點之后，仍然保持二叉排序樹的特性。結點之后，仍然保持二叉排序樹的特性。 可分三種情況討論：可分三種情況討論：(1)(1)被刪除的結點是葉子；被

31、刪除的結點是葉子；(2)(2)被刪除的結點只有左子樹或只有右子被刪除的結點只有左子樹或只有右子樹；樹；(3)(3)被刪除的結點既有左子樹，也有右子被刪除的結點既有左子樹，也有右子樹。樹。50308020908540358832(1)被刪除的結點是葉子結點葉子結點例如例如:被刪關鍵碼被刪關鍵碼=2088其雙親結點中相應指針域的值改為其雙親結點中相應指針域的值改為“空空”50308020908540358832(2)被刪除的結點只有左子樹只有左子樹或者只有右子樹只有右子樹其雙親結點的相應指針域的值改為其雙親結點的相應指針域的值改為“指向被刪除結點的左子樹或右子樹指向被刪除結點的左子樹或右子樹”。被

32、刪關鍵碼被刪關鍵碼=408050308020908540358832(3)被刪除的結點既有左子樹，也有右子樹既有左子樹，也有右子樹4040以其前驅替代之，然以其前驅替代之，然后再刪除該前驅結點后再刪除該前驅結點被刪結點前驅結點被刪關鍵碼被刪關鍵碼=50可以證明，在隨機情況下，含有可以證明，在隨機情況下，含有n n個結個結點的二叉排序樹的平均查找長度為點的二叉排序樹的平均查找長度為1+4log1+4log2 2n n 其時間效率很高。同時，其它運算如其時間效率很高。同時，其它運算如插入和刪除亦易于實現。相對而言，有插入和刪除亦易于實現。相對而言，有序表上的二分查找效率也很高；但若在序表上的二分查

33、找效率也很高；但若在有序表上進行插入和刪除顯然十分不便有序表上進行插入和刪除顯然十分不便且低率。且低率。333262321232163233圖圖6-86-8 單支二叉排序樹示例單支二叉排序樹示例 二叉排序的查找效率與樹的形態有關。二叉排序的查找效率與樹的形態有關。當二叉排序樹退化為一棵深度為當二叉排序樹退化為一棵深度為n n的單的單支樹時，查找算法退化為順序查找，平支樹時，查找算法退化為順序查找，平均查找長度上升為均查找長度上升為(n+1)/2(n+1)/2。為了避免。為了避免出現這種情況，需要在二叉排序樹的動出現這種情況，需要在二叉排序樹的動態變化過程中隨時調整其形態，使之保態變化過程中隨時

34、調整其形態，使之保持持“平衡平衡”。當二叉排序樹的形態比較。當二叉排序樹的形態比較勻稱時，它的平均查找長度接近于勻稱時，它的平均查找長度接近于loglog2 2n n。6.3.2 6.3.2 平衡二叉排序樹平衡二叉排序樹 一棵平衡二叉排序樹一棵平衡二叉排序樹( (簡稱簡稱AVLAVL樹樹) )或或者是一棵空樹，或者是一棵任一結點者是一棵空樹，或者是一棵任一結點的左子樹與右子樹的高度至多差的左子樹與右子樹的高度至多差1 1的二的二叉排序樹。叉排序樹。 對于二叉排序樹上的任何結點，其平衡對于二叉排序樹上的任何結點，其平衡因子定義為該結點左子樹的高度減去該結因子定義為該結點左子樹的高度減去該結點右子

35、樹的高度。易知平衡二叉排序樹上點右子樹的高度。易知平衡二叉排序樹上任一結點的平衡因子只可能是任一結點的平衡因子只可能是 -1-1、0 0、1 1。反之，一棵二叉排序樹上只要有一個結點反之，一棵二叉排序樹上只要有一個結點的平衡因子不是的平衡因子不是-1-1、0 0或或1 1，則此二叉排序，則此二叉排序樹不是平衡的。樹不是平衡的。 1511112008037121-151-160320760230圖圖6-9(a)AVL樹的例子樹的例子3301521112008037021-151-260320761230圖圖6-9(b)非非AVL樹的例子樹的例子3301411306006.4 6.4 散列表散列表

36、 散列表又名哈希表散列表又名哈希表, ,因其英文單詞因其英文單詞HashHash而得名。而得名。前幾節討論的查找方法的共同特點是：前幾節討論的查找方法的共同特點是：數據元素的存儲位置與關鍵碼之間不存在數據元素的存儲位置與關鍵碼之間不存在確定的關系，查找的過程為給定值依次和確定的關系，查找的過程為給定值依次和各個關鍵碼進行比較，查找的效率取決于各個關鍵碼進行比較，查找的效率取決于和給定值進行比較的關鍵碼個數。理想的和給定值進行比較的關鍵碼個數。理想的情況是依據關鍵碼直接得到其對應的數據情況是依據關鍵碼直接得到其對應的數據元素位置。元素位置。 散列表散列表: :按散列存儲方式構造的存儲結構按散列存

37、儲方式構造的存儲結構稱為散列表。散列技術的核心是散列函數。稱為散列表。散列技術的核心是散列函數。散列函數散列函數: :是一種將鍵值映射為散列表中是一種將鍵值映射為散列表中的存儲位置的函數。的存儲位置的函數。對任意給定的動態查找表對任意給定的動態查找表T T，如果選定了某，如果選定了某個個“理想的理想的”散列函數散列函數H H及相應的散列表及相應的散列表L L，則，則對對T T中的每個數據元素中的每個數據元素X X，函數值，函數值 H(X.key) H(X.key)就就是是X X在散列表在散列表L L中的存儲位置。插入中的存儲位置。插入( (或建表或建表) )時時數據元素數據元素X X將被安置在

38、該位置上，并且查找將被安置在該位置上，并且查找X X時時也到該位置上去查找。也到該位置上去查找。散列地址散列地址: :由散列函數決定的數據元素在由散列函數決定的數據元素在散列表中的存儲位置稱為散列地址。散列表中的存儲位置稱為散列地址。散列的基本思想散列的基本思想: :通過由散列函數決定的通過由散列函數決定的鍵值鍵值(X.key)(X.key)與散列地址與散列地址(H(X.key)(H(X.key)之間的對之間的對應關系來實現存儲組織和查找運算。應關系來實現存儲組織和查找運算。在理想的情況下，散列函數是一個一一對應，在理想的情況下，散列函數是一個一一對應，即每個鍵值對應于一個散列地址，且不同的鍵

39、即每個鍵值對應于一個散列地址，且不同的鍵值對應不同的散列地址。但在實際應用中，這值對應不同的散列地址。但在實際應用中，這種情況很少出現。在大多數情況下，出現種情況很少出現。在大多數情況下，出現“同同義詞義詞”并發生并發生“沖突沖突”是不可避免的。是不可避免的。同義詞同義詞: :設有散列函數設有散列函數H H和鍵值和鍵值k1k1、k2k2，若，若k1k2k1k2且且H(k1)=H(k2)H(k1)=H(k2)，則稱，則稱k1k1、k2k2是是同義詞同義詞。沖突：假如動態查找表中有兩個數據元素沖突：假如動態查找表中有兩個數據元素X1X1、X2X2存入同一個散列表，而且它們的鍵值是存入同一個散列表，

40、而且它們的鍵值是同義詞，這種情況稱為同義詞，這種情況稱為沖突沖突。我們希望同義詞盡量少以便減少沖突。另一我們希望同義詞盡量少以便減少沖突。另一方面，由于沖突的不可避免性，又必須考慮在方面，由于沖突的不可避免性，又必須考慮在沖突發生時的處理辦法。因此，采用散列技術沖突發生時的處理辦法。因此，采用散列技術時需要考慮的兩個問題是：時需要考慮的兩個問題是：如何構造如何構造( (選擇選擇)均勻的均勻的 散列函數？散列函數？用什么方法解決沖突？用什么方法解決沖突？沖突：沖突： 通常關鍵碼的集合比哈希地址集合大得通常關鍵碼的集合比哈希地址集合大得多，因此經過哈希函數變換后，可能將不多，因此經過哈希函數變換后

41、，可能將不同的關鍵碼映射到同一個地址上，這種現同的關鍵碼映射到同一個地址上，這種現象稱為象稱為沖突沖突。 同義詞同義詞: : 映射到同一個地址上的關鍵碼稱為映射到同一個地址上的關鍵碼稱為同義同義詞詞。6.4.1 6.4.1 散列函數的構造法散列函數的構造法 這里介紹幾種常用的構造方法。按這這里介紹幾種常用的構造方法。按這些方法構造出來的散列函數計算簡單而些方法構造出來的散列函數計算簡單而且比較且比較 均勻均勻(即同義詞較少即同義詞較少) )。以下假。以下假定散列地址是自然數。另外假定鍵值也定散列地址是自然數。另外假定鍵值也都是自然數都是自然數( (事實上，鍵值通常總可以事實上，鍵值通常總可以轉

42、換為自然數轉換為自然數) )。 數字分析法數字分析法數字分析法又稱為數字選擇法數字分析法又稱為數字選擇法, ,適用適用于下述場合于下述場合: :事先知道所有可能出現的事先知道所有可能出現的鍵值鍵值, ,并且鍵值的位數比散列地址的位并且鍵值的位數比散列地址的位數多數多. .在這種情況下可以對鍵值的各位在這種情況下可以對鍵值的各位進行分析進行分析, ,選擇分布較均勻的若干位組選擇分布較均勻的若干位組成散列地址。成散列地址。假定已知可能出現的所有鍵值中的一假定已知可能出現的所有鍵值中的一部分如下：部分如下：0 0 10 0 1 3 3 1 1 9 9 4 4 2 2 1 10 0 1 6 1 8 3

43、 0 90 0 1 6 1 8 3 0 90 0 1 7 3 9 4 3 40 0 1 7 3 9 4 3 40 0 1 6 4 1 5 1 60 0 1 6 4 1 5 1 60 0 1 8 1 6 3 7 80 0 1 8 1 6 3 7 80 0 1 1 4 3 3 9 50 0 1 1 4 3 3 9 50 0 1 2 4 2 3 6 30 0 1 2 4 2 3 6 30 0 1 9 1 5 4 0 90 0 1 9 1 5 4 0 9 ( (左起左起) )前三位分布不均勻，第前三位分布不均勻，第5 5、7 7位亦有很多重位亦有很多重復，故應將這五位丟棄。剩下的第復，故應將這五位丟棄

44、。剩下的第4 4、6 6、8 8、9 9位都位都是分布較均勻的，可考慮它們或它們中的幾位組合是分布較均勻的，可考慮它們或它們中的幾位組合起來作為散列地址。起來作為散列地址。2.除余法除余法( (重點重點) ) 選擇一個適當的正整數選擇一個適當的正整數p，以鍵值除以，以鍵值除以p所所得的余數作為散列地址，即令散列函數得的余數作為散列地址，即令散列函數H為為H(key)keymodp這一方法的關鍵在于這一方法的關鍵在于p的選取。若選的選取。若選p為為偶數，則所得的散列函數總是將奇數鍵值映偶數，則所得的散列函數總是將奇數鍵值映射成奇數地址。偶數鍵值映射為偶數地址。射成奇數地址。偶數鍵值映射為偶數地址

45、。因而增加了沖突的機會。通常選因而增加了沖突的機會。通常選p為大于或為大于或等于散列表容量的最小素數。等于散列表容量的最小素數。 【例】【例】 已知已知1111個元素的關鍵碼序列個元素的關鍵碼序列: : 18,27,1,20,22,6,10,13,41,15,25 18,27,1,20,22,6,10,13,41,15,25 選取關鍵碼與數據元素位置間的函數為選取關鍵碼與數據元素位置間的函數為f(key) = key mod 11f(key) = key mod 11(1) (1) 建立散列表：建立散列表：01234567891022113251527618412010(2) (2) 查找時，

46、對給定值查找時，對給定值 kx kx 通過該函數計通過該函數計算出地址，再與該地址單元中的元素進行算出地址，再與該地址單元中的元素進行比較，若相等，查找成功。比較，若相等，查找成功。3.平方取中法平方取中法一個數的平方的中間幾位與這個數的一個數的平方的中間幾位與這個數的每一位都有關。利用這一特點，平方取每一位都有關。利用這一特點，平方取中法以鍵值平方的中間幾位作為散列地中法以鍵值平方的中間幾位作為散列地址。這一方法計算簡單且不需要事先掌址。這一方法計算簡單且不需要事先掌握鍵值的分布情況。又因取平方中能擴握鍵值的分布情況。又因取平方中能擴大鍵值差別，所得散列地址比較均勻。大鍵值差別，所得散列地址

47、比較均勻。4.4.基數轉換法基數轉換法將鍵值看成另一種進制的數再轉換成原來進將鍵值看成另一種進制的數再轉換成原來進制的數，然后選其中幾位作為散列地址。例如，制的數，然后選其中幾位作為散列地址。例如，對于十進制鍵值對于十進制鍵值210485210485，先把它看成是十三進，先把它看成是十三進制的數，并轉換為十進制數：制的數，并轉換為十進制數：21048521048513132 213135 5+1+113134 4+0+013133 3+4+413132 2+8+813+813+87719357719351010然后從中選取幾位作為散列地址。通常要求然后從中選取幾位作為散列地址。通常要求兩個基數

48、互素，且新基數比原基數大。兩個基數互素，且新基數比原基數大。5.5.隨機數法隨機數法選擇一個隨機函數選擇一個隨機函數randomrandom，以鍵值，以鍵值在該函數下的值作為散列地址：在該函數下的值作為散列地址：H(key)= random (key)H(key)= random (key)當各個鍵值的位數不同時采用此法當各個鍵值的位數不同時采用此法較好。較好。6.4.2 6.4.2 動態查找表在開散列表上的實現動態查找表在開散列表上的實現(拉鏈法拉鏈法) 采用散列技術需考慮的第二個主要問題是如采用散列技術需考慮的第二個主要問題是如何何解決解決“沖突沖突”。而處理沖突的方法與散列表。而處理沖突的方法與散列表本身的組織形式有關。按組織形式的不同，通本身的組織形式有關。按組織形式的不同，通常有兩類散列表：開散列表與閉散列表。一旦常有兩類散列表：開散列表與閉散列表。一旦選定了散列函數和散列表的組織形式，就可以選定了散列函數和散列表的組織形式，就可以確定相應的解決沖突的方法，進而可以給出動確定相應的解決沖突的方法，進而可以給出動態查找表的一個具體實現。態查找表的一個具體實現。 開散列表的組織方式如下。設選定的散列函開散列表的組織方式如下。設選定的散列函數為數為H ，H的值域的值域(即散列地址的集合即散列地址的集合)為為0.n-1。設置一個設置一個地址數組地址數組pointer