1、 8.1 基本概念與術(shù)語 8.2 靜態(tài)查找表 8.3 動態(tài)查找表 8.4 哈希表查找 8.5 小結(jié)與習(xí)題第八章 查找1 8.1 基本概念與術(shù)語 第八章 查找1本章主要內(nèi)容本章主要學(xué)習(xí)靜態(tài)查找和動態(tài)查找方法。靜態(tài)查找包括順序查找、二分查找和分塊索引查找等，動態(tài)查找包括二叉排序樹、B樹等。作為重點內(nèi)容本章還介紹了哈希查找及相關(guān)知識。查找是數(shù)據(jù)結(jié)構(gòu)中的重要操作，好的查找方法會大大提高執(zhí)行效率。通過本章學(xué)習(xí)，應(yīng)掌握以下內(nèi)容： 查找的有關(guān)概念； 靜態(tài)查找； 動態(tài)查找； 哈希查找。 2本章主要內(nèi)容本章主要學(xué)習(xí)靜態(tài)查找和動態(tài)查找方法。靜態(tài)查找包括 查找就是指在給定的一組數(shù)據(jù)中對某個數(shù)值進(jìn)行查詢的過程。 關(guān)鍵

2、字是數(shù)據(jù)元素（或記錄）中某個項或組合項的數(shù)值，它可以標(biāo)識一個數(shù)據(jù)元素或記錄。 主關(guān)鍵字將能唯一確定一個數(shù)據(jù)元素（或記錄）的關(guān)鍵字。 查找表是由具有相同類型的數(shù)據(jù)元素（或記錄）組成的集合。分為靜態(tài)查找表和動態(tài)查找表兩大類。 如果查找表中能夠找到滿足條件的記錄，稱為查找成功，否則稱為查找不成功。8.1 基本概念與術(shù)語3 查找就是指在給定的一組數(shù)據(jù)中對某個數(shù)值進(jìn)行查詢的 靜態(tài)查找表：在對查找表進(jìn)行操作時，不改變表的結(jié)構(gòu)，只進(jìn)行查找操作； 動態(tài)查找表：在對查找表進(jìn)行操作時，可以改變該查找表的結(jié)構(gòu)，既可以進(jìn)行查找操作，又可以進(jìn)行插入、刪除等操作。8.2 靜態(tài)查找表8.2.1 靜態(tài)查找表結(jié)構(gòu) 靜態(tài)查找表是

3、由數(shù)據(jù)元素組成的線性表。其存儲結(jié)構(gòu)分為順序存儲和鏈?zhǔn)酱鎯煞N?？梢杂庙樞虮砘蚓€性鏈表來表示靜態(tài)查找表。4 靜態(tài)查找表：在對查找表進(jìn)行操作時，不改變表的8.2.1 靜態(tài)查找表結(jié)構(gòu) typedef int KeyType; typedef struct KeyType key; ElemType; typedef struct ElemType elemMAXSIZE+1； int length； SST； typedef struct NODE ElemType data；/* 結(jié)點的數(shù)據(jù)域 */ struct NODE *next；/*指針域 */ NodeType； 靜態(tài)查找表的順序存儲結(jié)構(gòu)

4、定義靜態(tài)查找表的鏈?zhǔn)酱鎯Y(jié)構(gòu)定義58.2.1 靜態(tài)查找表結(jié)構(gòu) typedef in8.2.2 順序查找 順序查找又稱線性查找，它思路簡單、容易實現(xiàn)，是一種最基本的查找方法。其查找過程為：從查找表的一端開始，逐個進(jìn)行關(guān)鍵字與查找值的比較，若某個記錄的關(guān)鍵字值與給定值相等，則查找成功，給出數(shù)據(jù)元素在查找表中的位置；若將整個表查找完，仍未找到與給定值相同的關(guān)鍵字，則查找失敗，給出提示信息。68.2.2 順序查找6【算法8.1】順序查找int Search_Seq(SST ST，KeyType x) ST.elem0.key=x; /*設(shè)置監(jiān)護(hù)哨*/ i=ST.length; while(ST.ele

5、mi.key!=x) i-; /*返回找到記錄的下標(biāo)或者0(查找不成功) */ return i; /*Search_Seq*/ 將查找過程中給定值和關(guān)鍵字比較的次數(shù)稱為查找長度。通常用平均查找長度ASL來衡量查找算法的優(yōu)劣。算法分析：7【算法8.1】順序查找 將查找過程中給定值和關(guān) 平均查找長度：在查找成功時，平均查找長度ASL是指為確定數(shù)據(jù)元素在表中位置所進(jìn)行關(guān)鍵字比較次數(shù)的期望值。對一個含n個數(shù)據(jù)元素的表，查找成功時 ASL=Pi*Ci ni=1 Pi為表中第i個數(shù)據(jù)元素的查找概率，Ci為表中第i個數(shù)據(jù)元素的關(guān)鍵字與給定值x相等時，需要比較的次數(shù)。 設(shè)查找表長度為n，查找元素x和表中第i

6、個元素關(guān)鍵字相等時，需要比較的次數(shù)為n-i+1，則平均查找長度為：ASL=Pi*（n-i+1） ni=18 平均查找長度：在查找成功時，平均查找長度ASL是指 設(shè)查找表中各元素的查找概率相等，即 Pi=1/n，則上面的式子表示為： ni=1ASL=（n-i+1）= 當(dāng)查找成功時，順序查找的時間復(fù)雜度就是O(n)。 當(dāng)查找失敗時，關(guān)鍵字與給定值的比較次數(shù)總是n+1次。8.2.3二分查找 二分查找，也稱為折半查找，是對有序表進(jìn)行的一種高效率的線性查找。有序表是指數(shù)據(jù)元素按給定的關(guān)鍵字已經(jīng)是升序（或者是降序）的查找表。9 設(shè)查找表中各元素的查找概率相等，即 Pi=1/n 假設(shè)各記錄的關(guān)鍵字是由小到大

7、排序的，算法的實現(xiàn)過程為：在待查找的有序表中，將中間元素首先與給定值進(jìn)行比較，若相等，則表示查找成功；若給定值小于中間元素的關(guān)鍵字，則在左邊的區(qū)域中繼續(xù)查找；若給定值大于中間元素的關(guān)鍵字，則在右邊的區(qū)域中繼續(xù)查找。重復(fù)上述過程，直到查找成功或者查找失敗，查找的過程隨之結(jié)束。 例在給定的序列A=6，13，17，20，24，28，30，36，39，44，48，51，55中查找給定值13和52這兩個數(shù)據(jù)。 查找關(guān)鍵字為13的過程10 假設(shè)各記錄的關(guān)鍵字是由小到大排序的，算法 6131720242830363944485155第一次 low=1 mid=7 high=13因x30，下一步繼續(xù)在左半?yún)^(qū)查

8、找，即： 0 1 2 3 4 5 6 7 8 9 10 11 12 13第二次 low=1 mid=3 high=6因x6，下一步繼續(xù)在右半?yún)^(qū)查找。此時，low=2,high=2 ,mid=(2+2)/2=2。由于x=13,查找成功，所找到的記錄序號為2。 查找關(guān)鍵字為52的過程第一次 low=1 mid=7 high=13因x30，下一步繼續(xù)在右半?yún)^(qū)查找，即： 0 1 2 3 4 5 6 7 8 9 10 11 12 13第二次 low=8 mid=10 high=13 因x44，下一步繼續(xù)在右半?yún)^(qū)查找，即： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 613172024

9、2830363944485155 613172024283036394448515512因x6，下一步繼續(xù)在右半?yún)^(qū)查找。此時，low=2,high第三次 low=11 high=13 mid=12因x51，下一步繼續(xù)在右半?yún)^(qū)查找，即： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 第四次 low=mid=high=13因xhigh，所以查找失敗。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 6131720242830363944485155 613172024283036394448515513第三次 【算法8.2】二分查找int Search_Bin (

10、SST ST，KeyType x)low=1；high=ST.length； while(low=high) /* 區(qū)間條件判斷 */ /* 當(dāng)區(qū)間下限不高于上限時，進(jìn)行比較測試 */ mid=(low+high)/2； /* 取中點 */ if(xST.elemmid.key) low=mid+1； /* 查找區(qū)間縮小到右邊區(qū)域 */ else return mid; return ERROR;14【算法8.2】二分查找14算法分析：對于有序查找表，可采用建立二叉樹的方法：將表的中間元素作為二叉樹的根結(jié)點，比中間值小的所有結(jié)點全部在二叉樹的左子樹中，比中間值大的所有結(jié)點全部在二叉樹的右子樹中

11、。按照這種思路建立的二叉樹稱為判定二叉樹。如圖所示。513928176445530244836132015算法分析：5139281764455302448361320時間復(fù)雜度：該算法的時間復(fù)雜度取決于該二叉樹中從根結(jié)點到該查找元素所在的結(jié)點的路徑上與中間結(jié)點的比較次數(shù)，即該元素結(jié)點在樹中的所在的層數(shù)。對于n個結(jié)點的判定樹，樹高為h，則有2h-1-1n2h-1，即h-1key) return p; /*查找結(jié)束*/ else if(xkey) f=p;p=p-lchild;/*在左子樹上查找*/ else f=p;p=p-rchild; /*在右子樹上查找*/ return NULL; 29【

12、算法8.3】二叉排序樹的查找29【算法8.4】二叉排序樹的建立BTNode *BST_Insert(BTNode *t,int x)/*在二叉排序樹上執(zhí)行插入操作*/ BTNode *s,*p=BST_search(t,x); if(p=NULL) s=(BTNode *)malloc(sizeof(BTNode); s-key=x; s-lchild=s-rchild=NULL; if(t=NULL) t=s; else if(xkey) f-lchild=s; /*生成左孩子*/ else f-rchild=s; /*生成右孩子*/ return t; 30【算法8.4】二叉排序樹的建立3

13、08.3.3平衡二叉樹（AVL樹）平衡二叉樹(Balanced Binary Tree)指的是形態(tài)勻稱的二叉樹，其定義是一個遞歸過程：它或是一棵空樹，或者是具有下列性質(zhì)的二叉排序樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹高度之差的絕對值不超過12200548549607701000318.3.3平衡二叉樹（AVL樹）它或是一棵空樹，或者是具有下 對于非平衡二叉排序樹，希望通過適當(dāng)調(diào)整，使其成為平衡二叉樹，設(shè)A結(jié)點為失去平衡的最小子樹根結(jié)點，對該子樹進(jìn)行平衡化調(diào)整歸納起來有以下四種情況：1.LL型平衡旋轉(zhuǎn) 當(dāng)在A的左子樹上插入結(jié)點，使A的平衡因子由1增至2而

14、失去平衡，因此需要進(jìn)行一次順時針旋轉(zhuǎn)操作。如圖8-9(a)所示。AB1插入前，平衡AB2C插入結(jié)點，失去平衡AB0C順時針旋轉(zhuǎn)后，平衡32 對于非平衡二叉排序樹，希望通過適當(dāng)調(diào)整，使其成為平衡二叉樹2.RR型平衡旋轉(zhuǎn) 由于在A的右子樹上插入結(jié)點，使A的平衡因子由-1增至-2而失去平衡，因此需要進(jìn)行一次逆時針旋轉(zhuǎn)操作。如圖所示。 AB-1插入前平衡AB-2C插入結(jié)點失去平衡CB0A逆時針旋轉(zhuǎn)后平衡332.RR型平衡旋轉(zhuǎn) AB-1插入前AB-2C插入結(jié)點CB03.LR型平衡旋轉(zhuǎn)由于在A的左子樹的右子樹上插入結(jié)點，使A的平衡因子由1增至2而失去平衡，因此需要進(jìn)行兩次旋轉(zhuǎn)（先逆時針旋轉(zhuǎn)，再順時針旋轉(zhuǎn)）

15、操作。如圖8-9(c)所示。AB1插入前平衡AC0B順時針旋轉(zhuǎn)使其平衡AB2C插入結(jié)點失去平衡AC2以C為軸逆時針旋轉(zhuǎn)B343.LR型平衡旋轉(zhuǎn)AB1插入前AC0B順時針旋轉(zhuǎn)AB2C插入4.RL型平衡旋轉(zhuǎn)由于在A的右子樹的左子樹上插入結(jié)點，使A的平衡因子由-1增至-2而失去平衡，因此需要進(jìn)行兩次旋轉(zhuǎn)（先順時針旋轉(zhuǎn)，再逆時針旋轉(zhuǎn)）操作。如圖8-9(d)所示。-1插入前平衡ABAB-2CBC0A插入結(jié)點失去平衡逆時針旋轉(zhuǎn)使平衡AC-2以C為軸順時針旋轉(zhuǎn)B354.RL型平衡旋轉(zhuǎn)-1插入前ABAB-2CBC0A插入結(jié)點逆【例8-4】設(shè)有數(shù)據(jù)序列63，90，70，55，67，42，98，試用這組數(shù)建立平衡

16、二叉排序樹，如圖8-10所示。636390639070709063709063557090635567709063556742 (e) (f) (g) 失去平衡36【例8-4】設(shè)有數(shù)據(jù)序列63，90，70，55，67，42 (h) 調(diào)整平衡 (i) 結(jié)束67906355704267906355704298平衡二叉樹的查找分析： 在查找過程中將給定值進(jìn)行比較的關(guān)鍵字個數(shù)不超過樹的深度。因此，在平衡樹上進(jìn)行查找的時間復(fù)雜度為O(log2n)。(等概率的提前下進(jìn)行的)37 (h) 調(diào)整平衡 8.3.4 B樹如果查找需要在外存儲器上進(jìn)行，需要使用外部查找方法。1.B樹的定義 一棵m階的B樹，或者為空樹

17、，或為滿足下列特性的m叉樹： 樹中每個結(jié)點至多有m棵子樹； 除非根結(jié)點為葉子結(jié)點，否則至少有兩棵子樹； 除根結(jié)點之外的所有非終端結(jié)點至少有m/2 棵子樹； 所有的非終端結(jié)點中包含以下信息數(shù)據(jù)： （n，A0，K1，A1，K2，Kn，An）388.3.4 B樹1.B樹的定義38其中：Ki（i=1,2,n）為關(guān)鍵字，且KiKi+1，Ai為指向子樹根結(jié)點的指針(i=0,1,n)，且指針Ai-1所指子樹中所有結(jié)點的關(guān)鍵字均小于Ki (i=1,2,n)，An所指子樹中所有結(jié)點的關(guān)鍵字均大于Kn， m/2 1nm 1 ，n為關(guān)鍵字的個數(shù)。 所有的葉子結(jié)點都出現(xiàn)在同一層次上，并且不帶信息。1L2DG3OSW3

18、ABC2EF2HK2MN3PQR3TUV3XYZ圖8-11 一棵5階的B-樹39其中：Ki（i=1,2,n）為關(guān)鍵字，且KiKi+12B樹基本操作 B樹的基本操作也是查找、插入和刪除等操作。現(xiàn)以B樹查找為例做簡單介紹。B樹的查找類似二叉排序樹的查找，所不同的是B樹每個結(jié)點上是多關(guān)鍵字的有序表，在到達(dá)某個結(jié)點時，先在有序表中查找，若找到，則查找成功；否則，按照對應(yīng)的指針信息指向的子樹中去查找，當(dāng)?shù)竭_(dá)葉子結(jié)點時，則說明樹中沒有對應(yīng)的關(guān)鍵字，查找失敗。 可見，B樹上進(jìn)行查找的過程是一個順指針查找結(jié)點和在結(jié)點的關(guān)鍵字中進(jìn)行查找交叉進(jìn)行的過程。402B樹基本操作 可見，B樹上進(jìn)行查找的過程是一個順指針查

19、8.4 哈希表查找8.4.1 哈希表與哈希方法前面介紹的查找算法基本上都是建立在“比較”的基礎(chǔ)上。而數(shù)據(jù)元素的存儲位置與關(guān)鍵字之間不存在確定的關(guān)系，查找效率由每次比較縮小的查找范圍決定。哈希表（Hash）是由哈希函數(shù)生成的表示關(guān)鍵字與存儲位置之間關(guān)系的表。哈希函數(shù)是一個以關(guān)鍵字值為自變量，在關(guān)鍵字值與記錄存儲位置之間建立確定關(guān)系的函數(shù)。哈希函數(shù)的值，就是指定關(guān)鍵字對應(yīng)的存儲地址。418.4 哈希表查找8.4.1 哈希表與哈希方法哈希表（Ha【例8-5】 設(shè)有11個記錄的關(guān)鍵字，其值分別為 6，37，12，21，69，31，16，33，41，13，51。選取關(guān)鍵字與記錄位置間的函數(shù)為 Hash(

20、key)=key % 11建立的哈希查找表如下：331213693716651413121 對于n個數(shù)據(jù)元素的集合，總能找到關(guān)鍵字與存放地址一一對應(yīng)的函數(shù)。但當(dāng)key1key2，而Hash(key1)=Hash(key2)時，即將不同的關(guān)鍵字映射到同一個哈希地址上，這種現(xiàn)象稱為沖突，映射到同一哈希地址上的關(guān)鍵字稱為同義詞?？梢哉f，沖突是不可能避免的，只能盡可能減少。因此選取適當(dāng)?shù)墓：瘮?shù)很關(guān)鍵。42【例8-5】 設(shè)有11個記錄的關(guān)鍵字，其值分別為 6，37，8.4.2 常用的哈希函數(shù)1.直接定址法 Hash(key)=a*key+b (a、b為常數(shù))直接地址法取關(guān)鍵字的某個線性函數(shù)值為哈希地址

21、?！纠?-6】 解放后，某農(nóng)作物年產(chǎn)量(單位：噸)序列為下表：1950年1951年1952年1953年1954年1955年160萬240萬360萬540萬810萬1006萬若選取哈希函數(shù)： Hash(key)= key-1950，其中key取“年份”，則建立的哈希查找表如下：01234519501951195219531954 1955160240360540810 1006 438.4.2 常用的哈希函數(shù)【例8-6】 解放后，某農(nóng)作物年產(chǎn)2.除留余數(shù)法 Hash(key)=key % p (p是一個整數(shù))即取關(guān)鍵字除以p的余數(shù)作為哈希地址。使用除留余數(shù)法，選取合適的p很重要，若哈希表表長為m

22、，一般選取pm的質(zhì)數(shù)?！纠?-7】 關(guān)鍵字集合為34，21，78，52，16，46，33，構(gòu)造哈希函數(shù)。選取哈希函數(shù)為 Hash(key)=key%7，則存放如下：21781652463334 0 1 2 3 4 5 6442.除留余數(shù)法【例8-7】 關(guān)鍵字集合為34，21，78，3.數(shù)字分析法 設(shè)關(guān)鍵字集合中，每個關(guān)鍵字均由m位組成，每位上可能有r種不同的符號。 數(shù)字分析法根據(jù)r種不同的符號，在各位上的分布情況，選取某幾位，組合成哈希地址。所選的位應(yīng)使各種符號在該位上出現(xiàn)的頻率大致相同。【例8-8】 有一組關(guān)鍵字如下： 2 7 4 0 3 6 4 2 7 6 1 4 8 7 2 7 5 2

23、4 9 6 2 7 5 5 4 7 0 2 7 5 7 3 0 5 分析：第1、2位均是“2和7”，第3位也只有“ 4、5、6”，因此，這幾位不能用，余下四位分布較均勻，可作為哈希地址選用。453.數(shù)字分析法【例8-8】 有一組關(guān)鍵字如下： 分析4. 平方取中法對關(guān)鍵字平方后，按哈希表大小，取中間的若干位作為哈希地址?！纠?-9】設(shè)有如下關(guān)鍵字序列0100，0110，1010，1001，0111，采用平方取中法建立哈希表。 關(guān)鍵字 平方 取值 0100 0010000 100 0110 0012100 121 1010 1020100 201 1001 1002001 020 0111 001

24、2321 123則該關(guān)鍵字序列對應(yīng)的地址值分別為100，121，201，020，123。464. 平方取中法 關(guān)鍵字 8.4.3 處理沖突的方法1. 開放定址法：當(dāng)由關(guān)鍵字得到的哈希地址發(fā)生了沖突，即該地址已經(jīng)存放了某數(shù)據(jù)元素時，就自動尋找下一個空的內(nèi)存地址，只要哈希表足夠大，總能找到一個位置，將數(shù)據(jù)元素存入。 (1) 線性探測法 Hi=(Hash(key)+di) % m ( 1i m )其中：Hash(key)為哈希函數(shù)，m為哈希表長度，di 為增量序列 1，2，m-1，且di=i【例8-11】關(guān)鍵字集為 47，7，29，11，16，92，22，8，3，哈希表表長為11， Hash(key

25、)=key % 11，用線性探測法處理沖突，如下所示： 0 1 2 3 4 5 6 7 8 9 10112247921637298 478.4.3 處理沖突的方法 (1) 線性探測法【例8-11】 存儲元素47、7后，再存儲29時，Hash(29)=7，哈希地址上沖突，由H1=(Hash(29)+1) % 11=8，哈希地址8為空，將29存入； 線性探測法可能使第i個哈希地址的同義詞存入第i+1個哈希地址，這樣本應(yīng)存入第i+1個哈希地址的元素變成了第i+2個哈希地址的同義詞，因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率。 可采用二次探測法，或雙哈希函數(shù)探測法，以改善

26、“堆積”問題。 0 1 2 3 4 5 6 7 8 9 10112247921637298 48 存儲元素47、7后，再存儲29時，Hash( (2) 二次探測法 Hi=(Hash(key)di) mod m其中：Hash(key)為哈希函數(shù)，m為哈希表長度，通常取m為4k+3的質(zhì)數(shù)，di 為增量序列 12，-12，22，-22，q2，-q2且q(m-1)/2 當(dāng)對例8-11使用二次探測法處理沖突時，如果已經(jīng)將前8個數(shù)都存入相應(yīng)的位置，其結(jié)果如下所示： 0 1 2 3 4 5 6 7 8 9 1011223479216 7298 當(dāng)存入最后一個元素3時，Hash(3)=3，哈希地址上沖突，由H1=(Hash(3)+12) mod 11=4，仍然沖突；H2=(Hash(3)-12) mod 11=2找到空的哈希地址，將元素3存入該位置。49 (2) 二次探測法 當(dāng)對例8-11使用二次探測法處 (3) 雙哈希函數(shù)探測法 Hi=(Hash(key)+i*ReHash(key) % m (i=1,2,，m-1) 其中： Hash(key)，ReHash(key)是兩個哈希函數(shù)，m為哈希表長度，其方法是：先用第一個函數(shù)Hash(key)對關(guān)鍵字計算哈希地址，一旦產(chǎn)生地址沖突，再用第二個函數(shù)ReHash(key)確定移動的步長因子，最后，通過步長因