數(shù)據(jù)結(jié)構(gòu)第9章

第九章查找重點：掌握順序查找、折半查找、二叉排序樹上查找以及散列表上查找的基本思想和算法實現(xiàn)。難點：二叉排序樹的刪除算法及B-樹上的插入和刪除算法。相關(guān)定義----查找表查找表(SearchTable)定義：由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。

“集合”中的數(shù)據(jù)元素之間存在著完全松散的關(guān)系查找表是一種非常靈便的數(shù)據(jù)結(jié)構(gòu)操作查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；檢索某個“特定的”數(shù)據(jù)元素的各種屬性；相關(guān)定義----查找表及其分類操作在查找表中插入一個數(shù)據(jù)元素；從查找表中刪去某個數(shù)據(jù)元素。查找表的分類靜態(tài)查找表：僅作查詢和檢索操作的查找表。動態(tài)查找表：在查詢過程中同時插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個數(shù)據(jù)元素。相關(guān)定義----關(guān)鍵字關(guān)鍵字定義：是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用以標識（識別）一個數(shù)據(jù)元素（或記錄）。若此關(guān)鍵字可以唯一地標識一個記錄，則稱之為主關(guān)鍵字；若此關(guān)鍵字能識別若干記錄，則稱之為次關(guān)鍵字。相關(guān)定義----查找查找定義：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。

若查找表中存在這樣一個記錄，則稱查找是成功的，此時查找結(jié)果為給出整個記錄的信息，或指示該記錄在查找表中的位置；

否則稱查找不成功，此時查找結(jié)果可給出一個空記錄或空指針。相關(guān)定義----類型定義typedefstruct{KeyTypekey; //關(guān)鍵字域

…… //其它域}ElemType;根據(jù)具體的關(guān)鍵字類型,定義用于比較的、帶參的宏#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))#defineEQ(a,b)(!strcmp((a),(b)))#defineLT(a,b)(strcmp((a),(b))<0)#defineLQ(a,b)(strcmp((a),(b))<=0)原型：externintstrcmp(constchar*s1,constchar*s2);

用法：#include<string.h>功能：比較字符串s1和s2。

說明：當s1<s2時，返回值<0當s1=s2時，返回值=0當s1>s2時，返回值>09.1.1順序查找查找表結(jié)構(gòu)：以順序表或線性鏈表表示基本思想：從一端開始向另一端，逐個進行記錄的關(guān)鍵字和給定值的比較，若某個記錄的關(guān)鍵字和給定值比較相等，則查找成功；反之，若直至另一端，其關(guān)鍵字和給定值比較都不等，則表明表中沒有所查記錄，查找不成功。

查找成功示例：

(34,44,43,12,53,55,73,64,77)，key=64

查找不成功示例：

(34,44,43,12,53,55,73,64,77)，key=889.1.1順序查找對順序表的順序查找typedefstruct{ElemType*elem;//數(shù)據(jù)元素存儲空間基址

intlength; //表長度}SSTable;i01234567891011

513192137566475808892找6464監(jiān)視哨iiii比較次數(shù)=5比較次數(shù)：查找第n個元素：1查找第n-1個元素：2……….查找第1個元素：n查找第i個元素：n+1-i查找失敗：n+1查找過程：從表的一端開始逐個進行記錄的關(guān)鍵字和給定值的比較。例如：9.1.1順序查找9.1.1順序查找對順序表的順序查找

intSearch_Seq(SSTableST,KeyTypekey)

{

//在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。

//若找到，則函數(shù)值為該元素在表中的位置，否則為0。

ST.elem[0].key

=key;

//“哨兵”

//從后往前找

for(i=ST.length;ST.elem[i].key!=key;--i);

returni;

//找不到時，i為0

}//Search_Seq

哨兵的作用：免去查找過程中每一步都要檢測整個表是否查找完畢。

上述順序查找表的查找算法簡單，但平均查找長度較大，特別不適用于表長較大的查找表。若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進行。9.1.2有序表的查找----折半查找1.設表長為n，low、high和mid分別指向待查元素所在區(qū)間的下界上界和中點,key為給定值。

2.初始時，令

low=1,high=n,mid=(low+high)/2

讓key與mid指向的記錄比較

若key==ST[mid].key，查找成功

若key<ST[mid].key，則high=mid-1

若key>ST[mid].key，則low=mid+1

3.重復上述操作，直至low>high時，查找失敗。9.1.2有序表的查找-折半查找折半查找(二分查找)查找表結(jié)構(gòu)：有序表基本思想：查找區(qū)間逐步縮小(折半)

查找成功示例：

123456789

(12,33,40,45,53,55,64,66,77)，key=64

low指示查找區(qū)間的下界;

high指示查找區(qū)間的上界;

mid=(low+high)/2

。9.1.2有序表的查找-折半查找lowhighmidlowlowmidmid9.1.2有序表的查找-折半查找基本思想：查找區(qū)間逐步縮小(折半)

查找不成功示例：

123456789

(12,33,40,45,53,55,64,66,77)，key=68lowhighmidlowlowmidmidlowlowmidmidlowlowmidmidhighhigh9.1.2有序表的查找-折半查找intSearch_Bin(SSTableST,KeyTypekey){low=1;high=ST.length;

//置區(qū)間初值

while(low<=high){mid=(low+high)/2;if(EQ(key,ST.elem[mid].key))returnmid;

//找到待查元素

elseif(LT(key,ST.elem[mid].key))high=mid-1;

//繼續(xù)在前半?yún)^(qū)間進行查找

elselow=mid+1;

//繼續(xù)在后半?yún)^(qū)間進行查找

}return0;

//順序表中不存在待查元素}//Search_Bin9.1.2有序表的查找-折半查找性能分析判定樹：折半查找的查找過程可以用二叉樹描述。n=ST.length=10時，判定樹的形態(tài)為：

52816397410查找成功時的ASL=該結(jié)點在判定樹中的層次判定樹的形態(tài)與n直接相關(guān)，與關(guān)鍵字的取值無關(guān)查找不成功時練習：畫出對長度為12的有序表進行折半查找的判定樹9.1.2有序表的查找-折半查找第九章查找9.1順序查找9.2動態(tài)查找表9.3哈希表9.2.1二叉排序樹----定義二叉排序樹(二叉查找樹)

BinarySort/SearchTree定義(遞歸)：或者是一棵空樹，或者是具有如下特性的二叉樹：若它的左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；若它的右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；它的左、右子樹也分別是二叉排序樹。503080209010854035252388例如:是二叉排序樹。66不9.2.1二叉排序樹----定義通常，取二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu)。typedefstruct

BiTNode

{//結(jié)點結(jié)構(gòu)

TElemTypedata;structBiTNode*lchild,*rchild;

//左右孩子指針}BiTNode,*BiTree;9.2.1二叉排序樹----定義1）若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；2）若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進行查找；3）若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進行查找。否則若二叉排序樹為空，則查找不成功；9.2.1-二叉排序樹:查找算法50308020908540358832例如:二叉排序樹查找關(guān)鍵字==50,505035,503040355090,50809095,9.2.1-二叉排序樹:查找算法從上述查找過程可見，在查找過程中，生成了一條查找路徑:

從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點;或者

從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止。

——查找成功——查找不成功9.2.1-二叉排序樹:查找算法9.2.1二叉排序樹----插入二叉排序樹的插入新插入的結(jié)點一定是一個新添加的葉子結(jié)點，并且是查找不成功時查找路徑上訪問的最后一個結(jié)點的左孩子或右孩子結(jié)點。示例：從空樹出發(fā)，待插的關(guān)鍵字序列為33,44,23,46,12,37334423461237中序遍歷二叉排序樹可得到一個關(guān)鍵字的有序序列。該例中，中序遍歷結(jié)果為：12,23,33,37,44,46

若從一棵空樹出發(fā)，經(jīng)過一系列的查找插入操作之后，可生成一棵二叉樹。且對其進行中序遍歷可得到一個關(guān)鍵字的有序序列。這說明一個無序序列可通過構(gòu)造一棵二叉排序樹而變成一棵有序序列。

9.2.1-二叉排序樹:改進的查找算法503080209010854035252388中序序列為：1020232530354050808588909.2.1-二叉排序樹:改進的查找算法9.2.1二叉排序樹----刪除二叉排序樹的刪除假設被刪結(jié)點為*p，其雙親結(jié)點為*f，*p為葉子結(jié)點：刪去*p，并修改*f的孩子域。*p只有左子樹PL或只有右子樹PR：令PL或PR直接成為*f的子樹334423461237464633442346124544464546459.2.1二叉排序樹----刪除二叉排序樹的刪除*p的左子樹PL和右子樹PR均不為空33442346123744405048353846504833231237403538方法1：PL

接替*p成為*f的子樹，PR成為PL最右下結(jié)點(中序遍歷PL所得序列的最后一個結(jié)點)的右子樹。40這種方法可能會導致二叉排序樹高度的增長！本例中高度：564846509.2.1二叉排序樹----刪除二叉排序樹的刪除*p的左子樹PL和右子樹PR均不為空334423461237444050483538332312方法2：與方法1對稱，PR接替*p成為*f的子樹，PL成為PR最左下結(jié)點(中序遍歷PR所得序列的最前一個結(jié)點)的左子樹。46374035389.2.1二叉排序樹----刪除二叉排序樹的刪除*p的左子樹PL和右子樹PR均不為空方法3、令*p的中序遍歷的直接前驅(qū)替代*p，再從二叉排序樹中刪去它的直接前驅(qū)。這種方法不會導致二叉排序樹高度的增長！本例中高度：55刪除時，如何不增長樹的高度？334423461237444050483538404038383344234612374440504835389.2.1二叉排序樹----刪除二叉排序樹的刪除*p的左子樹PL和右子樹PR均不為空方法4：與方法3對稱，令*p的中序遍歷的直接后繼替代*p，再從二叉排序樹中刪去它的直接后繼。334423461244504837403538464648504850334423461237444050483538334423461237444050483538334423461237444050483538404038389.2.1二叉排序樹----刪除算法9.2.1二叉排序樹----性能分析二叉排序樹的查找分析與給定值比較的關(guān)鍵字個數(shù)不超過二叉排序樹的深度示例：從空樹出發(fā)，待插的關(guān)鍵字序列為33,44,23,46,12,37334423461237二叉排序樹的形態(tài)與關(guān)鍵字的插入次序直接相關(guān)！如：將上例的關(guān)鍵字插入次序調(diào)整為：

12,23,33,44,37,46122333374446查找成功且各記錄的查找概率相等時

ASL(a)=(1+2*2+3*3)/6=14/6查找成功且各記錄的查找概率相等時ASL(b)=(1+2+3+4+5*2)/6=20/69.2.1二叉排序樹----性能分析9.2.1二叉排序樹----性能分析對給定序列建立二叉排序樹，若左右子樹均勻分布，則其查找過程類似于有序表的折半查找。但若給定序列原本有序，則建立的二叉排序樹就蛻化為單鏈表，其查找效率和順序查找一樣。第九章查找9.1順序查找9.2動態(tài)查找表9.3哈希表9.3哈希表9.3.1什么是哈希表9.3.2哈希函數(shù)的構(gòu)造方法9.3.3處理沖突的方法9.3.4哈希表的查找及其分析9.3.1什么是哈希表9.1和9.2節(jié)討論的各查找方法記錄在查找表中的位置和它的關(guān)鍵字之間不存在確定的關(guān)系；查找是建立在比較的基礎上(給定值vs.表中的關(guān)鍵字）查找效率依賴于查找過程中所進行的比較次數(shù)如何一次存取便能得到所查記錄？記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應關(guān)系H，以H(key)作為關(guān)鍵字為key的記錄在表中的位置，稱這個對應關(guān)系H為哈希(Hash)函數(shù)。9.3.1什么是哈希表例：30個地區(qū)的各民族人口統(tǒng)計表編號地區(qū)名總?cè)丝跐h族回族…1北京2上海┆┆以編號作關(guān)鍵字，構(gòu)造哈希函數(shù)：H(key)=keyH(1)=1H(2)=2以地區(qū)名作關(guān)鍵字，取地區(qū)名的第一個拼音字母的序號作哈希函數(shù)：H(Beijing)=2H(Shanghai)=19H(Shenyang)=199.3.1什么是哈希表哈希函數(shù)是一個映象，哈希函數(shù)的設定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長允許的范圍之內(nèi)即可；沖突：key1≠key2，但H(key1)=H(key2)的現(xiàn)象

具有相同哈希函數(shù)值的關(guān)鍵字稱做同義詞。根據(jù)設定的哈希函數(shù)

H(key)和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“象”作為記錄在表中的存儲位置，這種表便稱為哈希表，這一映象過程稱為哈希造表或散列，所得存儲位置稱哈希地址或散列地址。9.3.2哈希函數(shù)的構(gòu)造方法直接定址法哈希函數(shù)為關(guān)鍵字的線性函數(shù)，即

H(key)=key或者H(key)=a·key+b此法僅適合于：地址集合的大小==關(guān)鍵字集合的大小，其中a和b為常數(shù)；例：解放后出生的人口調(diào)查表H(key)=key-1948地址010203…22…年份194919501951…1970…人數(shù)…………15000…┆9.3.2哈希函數(shù)的構(gòu)造方法數(shù)字分析法關(guān)鍵字是以r為基的數(shù)，且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則取關(guān)鍵字的若干數(shù)位組成哈希地址。例：有80個記錄，關(guān)鍵字為8位十進制數(shù)，哈希地址為2位十進制數(shù)8134653281372242813874228130136781322817813389678136853781419355…..分析：只取8只取1只取3、4只取2、7、5數(shù)字分布近乎隨機所以：取任意兩位，或兩位與另兩位的疊加作哈希地址9.3.2哈希函數(shù)的構(gòu)造方法平方取中法取關(guān)鍵字平方后的中間幾位作為哈希地址求“關(guān)鍵字平方”的目的是“擴大差別”，同時平方值的中間幾位數(shù)和關(guān)鍵字的每一位都相關(guān)。9.3.2哈希函數(shù)的構(gòu)造方法(4)折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同)，然后取它們的疊加和(舍去進位)為哈希地址。移位疊加：將分割后的幾部分低位對齊相加；間界疊加：從一端沿分割界來回折迭，然后對齊相加。例：關(guān)鍵字為0442205864，哈希地址分別為586442200410088H(key)=0088移位疊加5864022404

6092H(key)=6092間界疊加9.3.2哈希函數(shù)的構(gòu)造方法除留余數(shù)法H(key)=keyMODp,p≤mp為質(zhì)數(shù)或不包含小于20的質(zhì)因子的合數(shù)

為什么？例：給定一組關(guān)鍵字為:12,39,18,24,33,21，若取p=9,則它們對應的哈希函數(shù)值將為:

3,3,0,6,6,3

可見，若p中含質(zhì)因子3,則所有含質(zhì)因子3的關(guān)鍵字均映射到“3的倍數(shù)”的地址上，從而增加了“沖突”的可能。

注意：p最好選取小于或等于表長m的最大素數(shù)。如表長為20，那么p選19，若表長為25，則p可選23，…。表長m與模p的關(guān)系可按下表對應：

m=8，16，32，64，128，256，512，1024，…

p=7，13，31，61，127，251，503，1019，…9.3.3處理沖突的方法“處理沖突”的實際含義是：

為產(chǎn)生沖突的地址尋找下一個哈希地址。處理沖突的方法

開放定址法、鏈地址法、再哈希法、建立公共溢出區(qū)開放定址法為產(chǎn)生沖突的地址H(key)求得一個地址序列：

H0,H1,H2,…,Hs1≤s≤m-1Hi=(H(key)+di)MODm，其中：i=1,2,…,s H(key)為哈希函數(shù); m為哈希表長; di為增量序列；9.3.3處理沖突的方法開放定址法對增量di的三種取法：線性探測再散列

di=c×i，最簡單的情況c=1平方探測再散列

di=12,-12,22,-22,…,隨機探測再散列

di

是一偽隨機數(shù)序列二次聚集：在處理同義詞的沖突過程中又添加了非同義詞的沖突，這種現(xiàn)象稱作“二次聚集”。9.3.3處理沖突的方法開放定址法例:給定關(guān)鍵字集合構(gòu)造哈希表

{19,01,23,14,55,68,11,82,36}設定哈希函數(shù)H(key)=keyMOD11(表長=11)若采用線性探測再散列處理沖突若采用二次探測再散列處理沖突012345678910191011232141551683116822365012345678910191011232141551684113821362二次探測會降低“二次聚集”發(fā)生的概率9.3.3處理沖突的方法鏈地址法將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中例:關(guān)鍵字