老師課件-第九章查找

第九章查找數(shù)據(jù)結(jié)構(gòu)9.1查找的基本概念9.2基于線性表的查找法9.3基于樹的查找法9.4散列表的查找—哈希法主要內(nèi)容列表：由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合，可利用任意數(shù)據(jù)結(jié)構(gòu)實現(xiàn)。關(guān)鍵碼：可以標(biāo)識一個記錄的某個數(shù)據(jù)項。鍵值：關(guān)鍵碼的值。主關(guān)鍵碼：可以唯一地標(biāo)識一個記錄的關(guān)鍵碼。次關(guān)鍵碼：不能唯一地標(biāo)識一個記錄的關(guān)鍵碼。50女李爽000525女齊梅000447女劉楠000325男張亮000238男王剛0001年齡性別姓名職工號1972年9月2003年7月1979年9月2003年7月1990年4月參加工作基本概念查找：在具有相同類型的記錄構(gòu)成的集合中找出滿足給定條件的記錄。查找的結(jié)果：若在查找集合中找到了與給定值相匹配的記錄，則稱查找成功；否則，稱查找失敗。50女李爽000525女齊梅000447女劉楠000325男張亮000238男王剛0001年齡性別姓名職工號1972年9月2003年7月1979年9月2003年7月1990年4月參加工作基本概念靜態(tài)查找：不涉及插入和刪除操作的查找。動態(tài)查找：涉及插入和刪除操作的查找。

靜態(tài)查找適用于：查找集合一經(jīng)生成，便只對其進行查找，而不進行插入和刪除操作，或經(jīng)過一段時間的查找之后，集中地進行插入和刪除等修改操作。動態(tài)查找適用于：查找與插入和刪除操作在同一個階段進行，例如當(dāng)查找成功時，要刪除查找到的記錄，當(dāng)查找不成功時，要插入被查找的記錄?；靖拍罹€性表：適用于靜態(tài)查找，主要采用順序查找技術(shù)、折半查找技術(shù)。樹

表：適用于動態(tài)查找，主要采用二叉排序樹的查找技術(shù)。散列表：靜態(tài)查找和動態(tài)查找均適用，主要采用散列技術(shù)。結(jié)構(gòu)線性表樹表散列表基本概念查找算法時間性能通過關(guān)鍵碼的比較次數(shù)來度量。關(guān)鍵碼的比較次數(shù)與哪些因素有關(guān)呢？⑴算法；⑵問題規(guī)模；⑶待查關(guān)鍵碼在查找集合中的位置；查找算法的時間復(fù)雜度是問題規(guī)模n

和待查關(guān)鍵碼在查找集合中的位置k

的函數(shù)，記為T(n，k)。同一查找集合、同一查找算法，關(guān)鍵碼的比較次數(shù)與哪些因素有關(guān)呢？基本概念平均查找長度：將查找算法進行的關(guān)鍵碼的比較次數(shù)的數(shù)學(xué)期望值定義為平均查找長度。計算公式為：

其中：n

：問題規(guī)模，查找集合中的記錄個數(shù)；

pi

：查找第i個記錄的概率；

ci

：查找第i個記錄所需的關(guān)鍵碼的比較次數(shù)。結(jié)論：ci取決于算法；pi與算法無關(guān)，取決于具體應(yīng)用。如果pi是已知的，則平均查找長度只是問題規(guī)模的函數(shù)。查找算法的性能ASL?==niiicp1基本思想：從線性表的一端向另一端逐個將關(guān)鍵碼與給定值進行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個表檢測完仍未找到與給定值相等的關(guān)鍵碼，則查找失敗，給出失敗信息。

101524612354098550123456789i例：查找key＝35iii

靜態(tài)查找表——順序表的查找以順序表或線性鏈表表示靜態(tài)查找表typedefstruct{keyTypekey;//關(guān)鍵字域

……//其它屬性域}ElemType;typedefstruct{ElemType*elem;intlength;}SSTable;intSearch(SSTableST,KeyTypekey){for(i=ST.length;i>0&&ST.elem[i].key!=key;--i);returni;}

順序查找法(線性查找)基本思想：設(shè)置“哨兵”。哨兵就是所要查找的值，將它放在查找方向的盡頭處，免去了在查找過程中每一次比較后都要判斷查找位置是否越界，從而提高查找速度。

101524612354098550123456789i例：查找k＝35iii哨兵35查找方向

改進的順序查找法intSearch(SSTableST,KeyTypekey){ST.elem[0].key=key;for(i=ST.length;ST.elem[i].key!=key;--i);returni;}

改進的順序查找法

列表長度為n，查找第i個數(shù)據(jù)元素時需進行n-i+1次比較，即ci=n-i+1。又假設(shè)查找每個數(shù)據(jù)元素的概率相等，即pi=1/n。

平均查找長度較大，特別是當(dāng)待查找集合中元素較多時，查找效率較低。順序查找的缺點：算法簡單而且使用面廣。對表中記錄的存儲沒有任何要求，順序存儲和鏈接存儲均可；對表中記錄的有序性也沒有要求，無論記錄是否按關(guān)鍵碼有序均可。順序查找的優(yōu)點：

順序查找法的優(yōu)缺點使用條件：

在有序表中，取中間元素作為比較對象，1、若給定值與中間記錄的關(guān)鍵字相等，則查找成功；2、若給定值小于中間記錄的關(guān)鍵字，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；3、若給定值大于中間記錄的關(guān)鍵字，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程，直到查找成功，或所查找的區(qū)域無記錄（low>high），查找失敗。

有序表的查找——折半查找

線性表中的記錄必須按關(guān)鍵字有序；必須采用順序存儲?；舅枷耄豪翰檎抑禐?4的記錄的過程：012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=2

mid=1

31>1418>147<14low=2mid=2

14=14例：查找值為22的記錄的過程：012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=4

mid=5

31>2218<2223>22low=4mid=4

21<22low=5low>highintSearch_Bin(SSTableST,KeyTypekey){low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(key==ST.elem[mid].key)returnmid;elseif(key<ST.elem[mid].key)high=mid-1;elselow=mid+1;}return0;}

折半查找的算法折半查找成功時的平均查找長度為：ASLbs＝i=1nPiCi＝n1j=1nj×2j-1＝nn+1log2(n+1)-1優(yōu)點：

比較次數(shù)少，查找速度快，平均性能好。缺點：

要求待查的表為有序表。

折半查找的性能分析動態(tài)查找表：結(jié)構(gòu)本身是在查找過程中動態(tài)生成的，即對于給定值key，若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回，否則插入關(guān)鍵字等于key的記錄。動態(tài)查找表二叉排序樹平衡二叉樹B樹

動態(tài)查找表二叉排序樹(二叉查找樹)：或者是一棵空的二叉樹，或者是具有下列性質(zhì)的二叉樹：⑴若它的左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；⑵若它的右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；⑶它的左右子樹也都是二叉排序樹。二叉排序樹的定義采用的是遞歸方法。

二叉排序樹二叉排序樹非二叉排序樹6390554258104567837063605582581045678370中序遍歷二叉排序樹可以得到一個關(guān)鍵碼有序序列。

二叉排序樹typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;

二叉排序樹—存儲結(jié)構(gòu)通常，取二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu)。在二叉排序樹中查找給定值的過程是：⑴若二叉排序樹是空樹，則查找失?。?2)若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；(3)若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進行查找；(4)若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進行查找。

二叉排序樹的查找50308020908540358832例如:二叉排序樹查找關(guān)鍵字==50,505035,503040355090,50809095,BitTreeSearchBST(BiTreeT,KeyTypekey){

if((!T)||(key==T->data.key))return(T);

else

if(key<T->data.key

)return(SearchBST(T->lchild,key));

elsereturn(SearchBST(T->rchild,key));}二叉排序樹的查找二叉排序樹的查找性能分析由序列{3,1,2,5,4}得到二叉排序樹：由序列{1,2,3,4,5}得到二叉排序樹：ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.21234531254二叉排序樹的查找性能分析由此可見，在二叉排序樹上進行查找時的平均查找長度和二叉排序樹的形態(tài)有關(guān)。最壞情況：二叉排序樹是通過把一個有序表的n個結(jié)點一次插入生成的，由此得到的二叉排序樹為一顆深度為n的單支樹，它的平均查找長度和單鏈表上的順序查找相同，也是(n+1)/2。最好情況：二叉排序樹在生成過程中，樹的形態(tài)比較均勻，即樹中各結(jié)點的左右子樹的深度差距不大的樹，此時他的平均查找長度大約是log2n。1、若二叉排序樹是空樹，結(jié)點s成為二叉排序樹的根；2、若二叉樹排序樹非空，則將s的關(guān)鍵字值key與二叉樹排序樹的根進行比較，①如果s的值等于根結(jié)點的值，則停止插入；②如果s的值小于根結(jié)點的值，則將s插入左子樹；③如果s的值大于根結(jié)點的值，則將s插入右子樹。插入一個關(guān)鍵字值為key的結(jié)點s，插入的方法：

二叉排序樹的插入6355905870985563root∧9058∧∧70∧∧98∧∧sroot∧

二叉排序樹的插入

給定一個元素序列，可以利用插入算法創(chuàng)建一棵二叉排序樹。將二叉排序樹初始化為一棵空樹，然后逐個讀入元素，每讀入一個元素，就建立一個新的結(jié)點插入到當(dāng)前已生成的二叉排序樹中，即調(diào)用上述二叉排序樹的插入算法將新結(jié)點插入。直到所有結(jié)點插入完成，二叉排序樹就構(gòu)造完成了。分析：若二叉排序樹為空樹，則新插入的結(jié)點為新的根結(jié)點；否則，新插入的結(jié)點必為一個新的葉子結(jié)點，其插入位置由查找過程得到。

二叉排序樹的構(gòu)造從空的二叉排序樹開始，依次插入一個個結(jié)點。例：關(guān)鍵碼集合為

{63，90，70，55，58}7.3樹表的查找技術(shù)6355905870

二叉排序樹的構(gòu)造1、關(guān)鍵字的輸入順序為：45,24,53,12,28,90，構(gòu)造二叉排序樹4524531228902、關(guān)鍵字的輸入順序為：24,53,

90,

12,

28,

45

，構(gòu)造二叉排序樹241228539045結(jié)論：對同樣一組數(shù)據(jù)元素，如果輸入的順序不同，則所建的二叉樹形態(tài)也不同。一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列;每次插入的新結(jié)點都是二叉排序樹上新的葉子結(jié)點;找到插入位置后，不必移動其它結(jié)點，僅需修改某個結(jié)點的指針；在左子樹/右子樹的查找過程與在整棵樹上查找過程相同；新插入的結(jié)點沒有破壞原有結(jié)點之間的關(guān)系。小結(jié)：

二叉排序樹的構(gòu)造二叉排序樹的刪除

在二叉排序樹上刪除某個結(jié)點之后，仍然保持二叉排序樹的特性。分三種情況討論：被刪除的結(jié)點是葉子；被刪除的結(jié)點只有左子樹或者只有右子樹；被刪除的結(jié)點既有左子樹，也有右子樹。

二叉排序樹的刪除1.若結(jié)點p是葉子，則直接刪除結(jié)點p；2.若p結(jié)點只有左子樹，或只有右子樹，則因為該結(jié)點只有左子樹或只有右子樹，也就是說，其后繼只有一個分支。刪除該結(jié)點時，只要將被刪除結(jié)點的唯一后繼（左子樹或右子樹）直接鏈接到被刪除結(jié)點的位置即可。3.若結(jié)點p的左右子樹均不空：首先找到p結(jié)點在中序序列中的直接前驅(qū)s結(jié)點，然后用s結(jié)點的值，替代p結(jié)點的值，再將s結(jié)點刪除,因為s的右指針一定為空，所以只要把s的左孩子鏈接到s結(jié)點本身的位置即可。

二叉排序樹的刪除50308020403590858832（2）被刪除的結(jié)點只有左子樹或者只有右子樹

其雙親結(jié)點的相應(yīng)指針域的值改為“指向被刪除結(jié)點的左子樹或右子樹”。被刪關(guān)鍵字=3580503080209085883532（3）被刪除的結(jié)點既有左子樹，也有右子樹4040以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點被刪關(guān)鍵字=50StatusDeleteBST(BiTree&T,KeyTypekey){if(!T)returnFALSE;else{if(key==T->data.key){Delete(T);returnTRUE;} elseif(key<T->data.key)DeleteBST(T->lchild,key);elseDeleteBST(T->rchild,key);}}平衡二叉樹：或者是一棵空的二叉排序樹，或者是具有下列性質(zhì)的二叉排序樹：⑴根結(jié)點的左子樹和右子樹的深度最多相差1;⑵根結(jié)點的左子樹和右子樹也都是平衡二叉樹。平衡因子：結(jié)點的平衡因子是該結(jié)點的左子樹的深度與右子樹的深度之差。在平衡二叉樹中，結(jié)點的平衡因子可以是1，0，-1。

平衡二叉樹548254821

平衡樹非平衡樹在平衡樹中，結(jié)點的平衡因子可以是1，0，-1。結(jié)點的平衡因子＝HL-HR

平衡二叉樹最小不平衡子樹：

在平衡二叉樹的構(gòu)造過程中，以距離插入結(jié)點最近的、且平衡因子絕對值大于1的祖先結(jié)點為根的子樹。542814

最小不平衡子樹

在構(gòu)造二叉排序樹的過程中，每插入一個結(jié)點時，首先檢查是否因插入新結(jié)點而破壞了樹的平衡性，若是，則找出最小不平衡子樹，在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點之間的鏈接關(guān)系，進行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。

平衡二叉樹構(gòu)造【基本思想】

設(shè)結(jié)點A為最小不平衡子樹的根結(jié)點，則失去平衡后進行調(diào)整的規(guī)律可歸納為下列四種情況：

1.LL型：由于在A的左子樹根結(jié)點B的左子樹上插入結(jié)點，A的平衡因子由1變?yōu)?。

2.RR型：由于在A的右子樹根結(jié)點B的右子樹上插入結(jié)點，A的平衡因子由-1變?yōu)?2。

3.LR型：由于在A的左子樹根結(jié)點B的右子樹上插入結(jié)點，A的平衡因子由1變?yōu)?。

4.RL型：由于在A的右子樹根結(jié)點B的左子樹上插入結(jié)點，A的平衡因子由1變?yōu)?。

平衡二叉樹的調(diào)整插入前插入后、調(diào)整前順時針平衡二叉樹——LL型A1BLhBRh0ARhBh2BLhBRh1ARABXh+1BLhARBRh00BAX

以B為軸，對A做了一次順時針旋轉(zhuǎn)，即將A改為B的右孩子，B原來的右孩子改為A的左孩子61→2例:LL型

108791291012876平衡二叉樹——RR型插入前插入后，調(diào)整前逆時針A-1BLhBRh0ALhBXA-2BLhBRh-1ALhBBALhBLh0BRh+1AX0

以B為軸，對A做了一次逆時針旋轉(zhuǎn)，即將A改為B的左孩子，B原來的左孩子改為A的右孩子插入后，調(diào)整前先逆時針旋轉(zhuǎn)再順時針旋轉(zhuǎn)A2CLh-1BLh-1ARhBCCRh-1XXACLh-1CBCRh-1ARhBLhARhCACRh-1BCLh-1X0-10BLh平衡二叉樹——LR型1、將B改為其右子樹根結(jié)點C的左孩子，而C原來的左孩子改為B的右孩子，相當(dāng)于以C為軸，對B作了一次逆時針旋轉(zhuǎn)；

2、將A改為C的右孩子，C原來的右孩子改為A的左孩子，相當(dāng)于以C為軸，對A進行了一次順時針旋轉(zhuǎn)。插入后，調(diào)整前先順時針旋轉(zhuǎn)再逆時針旋轉(zhuǎn)XACLh-1BRhCBCRh-1ALhA-2CLh-1BRh1ALhBCCRh-1XBRhCBCRh-1AALhCLh-1X001平衡二叉樹——RL型1、將B改為其左子樹根結(jié)點C的右孩子，而C原來的右孩子改為B的左孩子，相當(dāng)于以C為軸，對B作了一次順時針旋轉(zhuǎn)；

2、將A改為C的左孩子，C原來的左孩子改為A的右孩子，相當(dāng)于以C為軸，對A進行了一次逆時針旋轉(zhuǎn)。課堂練習(xí)：設(shè)有關(guān)鍵碼序列{5,4,2,8,6,9}，構(gòu)造平衡樹542LL型42586864256842585642課堂練習(xí)：設(shè)有關(guān)鍵碼序列{5,4,2,8,6,9}，構(gòu)造平衡樹RL型旋轉(zhuǎn)1次RL型旋轉(zhuǎn)2次856429RR型846529課堂練習(xí)：設(shè)有關(guān)鍵碼序列{5,4,2,8,6,9}，構(gòu)造平衡樹例：設(shè)序列{20，35，40，15，30，25}，構(gòu)造平衡樹。203540352040153025352040153025202515354030354030202515例：設(shè)序列{20，35，40，15，30，25}，構(gòu)造平衡樹。（1）查找應(yīng)插位置，同時記錄離插入位置最近的可能失衡結(jié)點A（A的平衡因子不等于0）。（2）插入新結(jié)點S，并修改從A到S路徑上各結(jié)點的平衡因子。（3）根據(jù)A、B的平衡因子，判斷是否失衡以及失衡類型，并做相應(yīng)處理。

平衡二叉樹的調(diào)整

綜上所述，在一個平衡二叉排序樹上插入一個新結(jié)點S時，主要包括以下三步：查找操作要完成什么任務(wù)？待查值k確定k在存儲結(jié)構(gòu)中的位置

散列表的查找—哈希表若以下標(biāo)為000~999的順序表表示之。例如：為每年招收的1000名新生建立一張查找表，其關(guān)鍵字為學(xué)號，其值的范圍為xx000~xx999(前兩位為年份)。

則查找過程可以簡單進行：取給定值（學(xué)號）的后三位，不需要經(jīng)過比較便可直接從順序表中找到待查關(guān)鍵字。哈希法：又稱散列法、雜湊法以及關(guān)鍵字地址計算法等，相應(yīng)的表稱為哈希表。哈希法的基本思想：首先在元素的關(guān)鍵字k和元素的存儲位置p之間建立一個對應(yīng)關(guān)系H，使得p=H(k)，H稱為哈希函數(shù)。創(chuàng)建哈希表時，把關(guān)鍵字為k的元素直接存入地址為H(k)的單元；以后當(dāng)查找關(guān)鍵字為k的元素時，再利用哈希函數(shù)計算出該元素的存儲位置p=H(k)，從而達到按關(guān)鍵字直接存取元素的目的。

散列表的查找—哈希表設(shè)計哈希函數(shù)一般應(yīng)遵循以下原則：⑴計算簡單。哈希函數(shù)不應(yīng)該有很大的計算量，否則會降低查找效率。⑵函數(shù)值即哈希地址分布均勻。函數(shù)值要盡量均勻散布在地址空間，這樣才能保證存儲空間的有效利用并減少沖突。沖突：對于兩個不同關(guān)鍵碼ki≠kj，有H(ki)＝H(kj)，即兩個不同的記錄需要存放在同一個存儲位置，ki和kj相對于f稱做同義詞。

哈希函數(shù)的構(gòu)造【直接定址法】散列函數(shù)是關(guān)鍵碼的線性函數(shù)，即：H(key)=a

key+b（a，b為常數(shù)）例：關(guān)鍵碼集合為{10,30,50,70,80,90}，選取的散列函數(shù)為H(key)=key/10，則散列表為：0123456789103050708090適用情況？事先知道關(guān)鍵碼，關(guān)鍵碼集合不是很大且連續(xù)性較好。

哈希函數(shù)的構(gòu)造方法H(key)=keymodp