第9章查找1.掌握順序查找、二分查找和分塊查找的方法。2.掌握二叉排序樹的相關運算和查找過程。3.理解平衡二叉樹的建樹方法。4.掌握哈希表的建立方法和查找過程。5.掌握各種查找方法在等概率下的平均查找長度的計算方法。學習要點基本概念

查找表：是由同一類型的數據元素構成的集合，由于“集合”中的數據元素之間存在著松散的關系，因此查找表是一種應用靈便的數據結構。

有關操作

查詢某個“特定的”數據元素是否在查找表中；

在查找表中插入一個數據元素；

從查找表中刪去某個數據元素。查找表的分類靜態查找表：僅作查詢和檢索操作的查找表。動態查找表：在查找過程中同時插入查找表中不存在的數據元素，或者從查找表中刪除已存在的某個數據元素。

關鍵字是數據元素中某個數據項的值，用以標識一個數據元素。若此關鍵字可以識別唯一的一個記錄，則稱之謂“主關鍵字”。若此關鍵字能識別若干記錄，則稱之謂“次關鍵字”。基本概念查找根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的數據元素。若查找表中存在這樣一個記錄，則稱“查找成功”，查找結果：給出整個記錄的信息，或指示該記錄在查找表中的位置；否則稱“查找不成功”，查找結果：給出“空記錄”或“空指針”。基本概念數據元素類型定義為：typedefstruct{KeyTypekey;//關鍵字域…//其他域}ElemType;基本概念9.1.1順序表的查找應用范圍：以順序表或線性鏈表表示的靜態查找表，表內元素之間無序。順序查找基本思想：從表中最后一個記錄開始，逐個進行記錄的關鍵字和給定值的比較，若某個記錄的關鍵字和給定值比較相等，則查找成功；若直至第一個記錄，其關鍵字和給定值比較都不等，則查找不成功。順序存儲結構的表示：

typedef

struct{

ElemType*elem;

intlength;}SSTable;9.1靜態查找表int

Search_Seq(StableST,KeyTypekey){//在順序表ST中順序查找其關鍵字等于key的數據元素

ST.elem[0].key=key;//哨兵

for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;//查找不成功時i為0}//Search_Seq免去查找過程中每一步都要檢測整個表是否查找完畢順序查找算法int

Search_Seq(StableST,KeyTypekey){//在順序表ST中順序查找其關鍵字等于key的數據元素

for(i=0;i<ST.length;++i)

if(ST.elem[i].key==key)returni;return(0);//查找不成功時i為0}//Search_Seq順序查找算法8012n-3n-2n-1nST.elem

key例1：在下表中查找key=8的結點?！?00100713iiiiiii查找不成功，i=08012n-3n-2n-1nST.elem

key例2：在下表中查找key=8的結點?！?00100813iii查找成功，i=n-2

舉例說明1n查找成功情況下：設每個結點的查找概率相等ASL＝∑(n-i+1)＝(n+1)/2i=1n

和給定值進行比較的關鍵字個數的期望值稱為查找成功時的平均查找長度。性能分析折半查找查找方式：每次將待查記錄所在區間縮小一半。適用條件：采用順序存儲結構的有序表。算法實現：設表長為n，low、high和mid分別指向待查元素所在區間的上界、下界和中點，k為給定值。

初始時，令low=1，high=n，mid=(low+high)/2。

讓k與mid指向的記錄比較若k==ST.elem[mid].key，查找成功；

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

若k>ST.elem[mid].key，則low=mid+1。重復上述操作，直至low>high時，查找失敗。9.1.2有序表的查找

舉例說明(1)low找key=215113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhighlow找key=705113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhigh

舉例說明(2)low5113219321437556664775880988109211midhighlow5113219321437556664775880988109211high

舉例說明(2)intSearch_bin(SStableST,KeyTypekey){//在有序表ST中折半查找關鍵字等于key的數據元素low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(EQ(ST.elem[mid].key,key)returnmid;elseif(LT(key,ST.elem[mid].key))high=mid-1;elselow=mid+1;}return0；}//Search_Bin折半查找算法判定樹：描述查找過程的二叉樹。有n個結點的判定樹的深度為log2n+1。

折半查找法在查找過程中進行的比較次數最多不超過log2n+1。其ASL=log2(n+1)-1。

折半查找的優點是比較的次數少，查找速度快，但前提是該表首先要進行排序，而排序是一種很費時運算，并且折半查找只適用于順序存儲的有序表，不適用于鏈表存儲的有序表。5619800521886413753792折半查找性能分析5113219321437556664775880988109211索引順序查找(分塊查找)

查找過程：將表分成幾塊，塊內無序，塊間有序；先確定待查記錄所在塊，再在塊內查找。適用條件：分塊有序表假設按元素關鍵字升序方式組織表中各塊，則要求第一塊中任一結點的關鍵字值都小于第二塊中所有結點的關鍵字值；第二塊中任一結點的關鍵字值都小于第三塊中所有結點的關鍵字值；如此類推。然后選擇每塊中的最大(或最小)關鍵字值組成索引表。索引表中的結點個數等于線性表被分割的塊數。9.1.4索引順序表的查找1234567891011121314151617182212138920

334244382448

6058745786532248861713索引表查38最大關鍵字起始地址表及其索引表LLASLwbbs+=其中：Lb是查找索引表確定所在塊的平均查找長度；

Lw是在塊中查找元素的平均查找長度。若將表長n為的表平均分成b塊，每塊含s個記錄，并設表中每個記錄的查找概率相等，則：用順序查找確定所在塊用折半查找確定所在塊ASLbs=1)(21ssn++ASLbs=2)1(log2ssn++分塊查找性能分析9.2動態查找表什么是二叉排序樹？或者是一棵空樹；或者是具有下列性質的二叉樹：1.若左子樹不空，則左子樹上所有結點值均小于根結點值；2.若右子樹不空，則右子樹上所有結點值均大于根結點值；3.根結點的左、右子樹也分別為二叉排序樹。45125333710024619078若二叉排序樹為空，則查找不成功；否則1.若給定值等于根結點的關鍵字，則查找成功；2.若給定值小于根結點的關鍵字，則繼續在左子樹上進行查找；3.若給定值大于根結點的關鍵字，則繼續在右子樹上進行查找。具體實現如下：BiTree

SearchBST(BiTree

T,KeyTypekey){if((!T)||(EQ(key,T->data.key))return(T);elseif(LT(key,T->data.key))returnSearchBST(T->lchild,key);elsereturnSearchBST(T->rchild,key);}二叉排序樹查找算法例如：在下圖中分別查找關鍵字值等于37，61和95過程。45125333710024619078從上述查找過程可見，在查找過程中，生成了一條查找路徑：1.從根結點出發，沿著左分支或右分支逐層向下直至關鍵字等于給定值的結點，表明查找成功。2.或者從根結點出發，沿著左分支或右分支逐層向下直至指針指向空樹為止，表明查找不成功。二叉排序樹查找過程基本思想：在每一步插入過程中，二叉排序樹中原有的結點位置均不動，只是將待插入的結點作為一個葉結點插入到適當的位置，使得樹中任何結點與其左、右子樹結點之間的關系仍然滿足二叉排序樹的性質，向二叉樹T插入一個新結點s的過程為：若T為空的二叉樹，則將新結點作為根結點插入。若新結點s的值等于二叉排序樹的根結點，說明該結點已存在，不需要插入。若將新結點s的值小于二叉排序樹T的根結點，則將s插入到T的左子樹中去。若新結點s的值大于二叉排序樹T的根結點，則將s插入到T的右子樹中去。二叉排序樹的插入操作是一個遞歸過程。二叉排序樹插入算法思想

StatusSearchBST(BiTree

T,KeyType

key,BiTree

f,BiTree&p)//若查找成功，則指針p指向該數據元素結點，返回TRUE，否則p指向查找路徑上訪問的最后一個結點并返回FALSE，f是指向T的雙親

{if(!T){p=f;returnFALSE;}elseif(EQ(key,T->data.key)){p=T;returnTRUE;}elseif(LT(key,T->data.key))returnSearchBST(T->lchild,key,T,p);elsereturnSearchBST(T->rchild,key,T,p);}具體實現(1)StatusInsertBST(BiTree&T,ElemTypee){if(!SearchBST(T,e.key,NULL,p)){s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;elseif(LT(e.key,p->data.key))p->lchild=s;elsep->rchild=s;returnTRUE;}elsereturnFALSE;}具體實現(2)2712從空樹出發，經過一系列的查找插入操作后，便可生成一棵二叉排序樹。例對于關鍵字序列{10，18，3，8，12，2，7}，構造一棵BST。101838注意：對于同樣的數據，輸入順序不同，建立起來的二叉排序樹的形態也不同。這直接影響到二叉排序樹的查找性能。如果輸入序列選得不好，會建立起一棵單支樹，使得二叉排序樹的高度達到最大，這樣必然會降低查找性能。建立二叉排序樹中序遍歷二叉排序樹便可得到一個關鍵字的有序序列，也就是說，一個無序序列可以通過構造一棵二叉排序樹而變成一個有序序列。對下圖所示的二叉排序進行中序遍歷，結果為(2，3，7，8，10，12，18)。每次插入的新結點都是二叉排序樹上新的葉子結點，不必移動其它結點，僅需修改某個結點的指針。這相當于在一個有序列上插入一個記錄而又不需要移動其他記錄。二叉排序樹既擁有折半查找的特性，又采用鏈式存儲。7212101838

結論和插入相反，刪除在查找成功之后進行，并且要求在刪除二叉排序樹上某個結點之后，仍然保持二叉排序樹的特性?？煞秩N情況討論：被刪除的結點是葉子；被刪除的結點只有左子樹或者只有右子樹；被刪除的結點既有左子樹，也有右子樹。二叉排序樹的刪除刪除葉子結點，只需將其雙親結點指向它的指針置為空，再釋放它即可。如：刪除關鍵字值為7的結點。1018381227刪除葉子結點刪除的結點只有左子樹或者只有右子樹，則使其雙親結點的相應指針域的值改為“指向被刪除結點的左子樹或右子樹”。如：(1)刪除關鍵字值為2的結點，它只有右子樹。(2)刪除關鍵字值為18的結點，它只有左子樹。1018581223刪除的結點只有左子樹或只有右子樹RQD中序遍歷：PL—D—R—Q

刪除后：PL—R—QPLRQPLRDQ中序遍歷：Q—R—PL—D

刪除后：Q—R—PLPLRQPLRQD中序遍歷：D—PR—R—Q

刪除后：PR—R—QPRRQPRRDQ中序遍歷：Q—R—D—PR

刪除后：Q—R—PRPRRQPR

具體解釋刪除葉結點和刪除的結點只有左子樹或者只有右子樹這兩種操作，可通過下面語句實現。if(!p->rchild){q=p;p=p->lchild;free(q);}elseif(!p->lchild){q=p;p=p->rchild;free(q);}1018581223p

具體實現方法一：首先將結點D的右子樹鏈接到其中序前驅結點(結點D的左子樹中“最右下”且右指針域為空的結點)的右指針域，然后把結點R(結點D的雙親結點)指向結點D的指針鏈接到結點D的左子樹上即可。RDQRRDRCCLQLGLGpfRQRRDRCCLQLGLGf該二叉排序樹的中序遍歷結果為：CL→C→QL→Q→GL→G→D→DR→R→RR刪除的結點既有左子樹又有右子樹方法二：把結點D的中序前驅結點G的值賦給結點D，因為該中序前驅結點G只有左子樹GL，然后將結點G的雙親結點的右指針鏈接到GL即可。RDQRRDRCCLQLGLGpfRGQRRDRCCLQLGLpf該二叉排序樹的中序遍歷結果為：CL→C→QL→Q→GL→G→D→DR→R→RR刪除的結點既有左子樹又有右子樹刪除的結點既有左子樹又有右子樹，可通過下面語句實現。q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;free(s);RDQRRDRCCLQLGLGpf

具體實現

BST上查找過程，是從根結點到所找到結點的一條路徑。與給定值比較次數等于該路徑長度+1，最大次數不超過樹的深度。但含有n個結點的BST卻不唯一。因此，含有n個結點的BST的ASL和樹的形態有關。最差情況是退化為單支樹，ASL=(n+1)/2(同順序查找)。最好情況與折半查找相同，與log2n成正比。12452453123793(45,24,53,12,37,93)2437455393(12,24,37,45,53,93)ASL(a)=(1+2+2+3+3+3)/6=14/6ASL(b)=(1+2+3+4+5+6)/6=21/6

查找分析平衡二叉樹是二叉排序樹的另一種形式，其特點為：樹中每個結點的左、右子樹高度之差的絕對值不大于1。若平衡因子定義為結點左子樹的高度減去右子樹的高度，則平衡二叉樹所有結點的平衡因子只可能是-1、0、1的二叉排序樹。例如：20210平衡樹非平衡樹-2-20-100101平衡二叉樹

采取的方法是在向平衡二叉樹插入結點時進行平衡化旋轉?；舅枷霝椋杭俣ㄏ蚱胶鈽洳迦胍粋€結點后破壞了其平衡性，則首先要找出唯一一棵最小不平衡子樹，然后再調整該子樹中有關結點之間的鏈接關系，使之成為一棵新的平衡二叉樹。最小不平衡子樹被調整為平衡子樹后，整個二叉排序樹又成為一棵平衡樹。

最小不平衡子樹是指離插入結點最近，且平衡因子絕對值大于1的祖先結點作為根的子樹。027511018410-110127511018410-211160構造平衡二叉樹的方法(1)單向右旋平衡處理(LL型)：新插入結點在A的左子樹根結點的左子樹上。A的平衡因子由1增至2，導致失衡。調整規則：將結點A的左孩子B向上旋轉成為新二叉樹的根，將結點A及其右子樹向右下旋轉成為結點B的右子樹，而結點B原來的右子樹BR則成為結點A的左子樹。(進行一次順時針旋轉)調整方法分四種情況h+1h-1ABARBRBLh-10+2+1hh-1ABARBRBL00具體實現：lc=p->lchild;p->lchild=lc->rchild;lc->rchild=p;p=lc;p(2)單向左旋平衡處理(RR型)：新插入結點在A的右子樹根結點的右子樹上。A的平衡因子由-1增至-2，導致失衡。調整規則：將結點A的右孩子B向上旋轉成為新二叉樹的根，將結點A及其左子樹向左下旋轉成為結點B的左子樹，而結點B原來的左子樹BL則成為結點A的右子樹。(進行一次逆時針旋轉)調整方法分四種情況-2hh-1h-1BABRBLAL-10-1h0BABRBLALh-10具體實現：rc=p->rchild;p->rchild=rc->lchild;rc->rchild=p;p=rc;p(3)先左后右平衡處理(LR型)：新插入結點在A的左子樹根結點的右子樹上。A的平衡因子由1增至2，導致失衡。調整規則：將A的左孩子的右子樹的根結點C旋轉到結點A的位置成為新二叉樹的根，將結點B及其左子樹向左下旋轉成為C的左子樹，而C結點原來的左子樹CL則作為結點B的右子樹；將結點A及其右子樹向右下旋轉成為結點C的右子樹，C結點原來的右子樹CR作為結點A的左子樹。(需進行兩次旋轉，先逆時針后順時針)調整方法分四種情況+2-1+1h-1ABARCLBLh-10CCRh-20h-1+1+2h-1CBARCLBLh-10CRh-2A+2h-10CBARCLBL0CRA-1將A的左孩子的右子樹的根結點C旋轉到結點A的位置成為新二叉樹的根，將結點B及其左子樹向左下旋轉成為C的左子樹，而C結點原來的左子樹CL則作為結點B的右子樹。(第一次逆時針旋轉)將結點A及其右子樹向右下旋轉成為結點C的右子樹，C結點原來的右子樹CR作為結點A的左子樹。(第二次順時針旋轉)調整過程調整方法分四種情況(4)先右后左平衡處理(RL型)：新插入結點在A的右子樹根結點的左子樹上。A的平衡因子由-1增至-2，導致失衡。調整規則：它與LR旋轉情況正好對稱的。調整實例假設一組數據對象為(40，28，16，56，50，32，30，63)，按次序插入每個對象生成一棵平衡二叉樹，根據插入過程指出每一步的調整類型：“單向左旋轉”、“單向右旋轉”、“先左后右旋轉”、“先右后左旋轉”、“無”。解釋：左子樹的左子樹上插入→“單向右旋轉”右子樹的右子樹上插入→“單向左旋轉”左子樹的右子樹上插入→“先左后右旋轉”右子樹的左子樹上插入→“先右后左旋轉”9.3哈希表9.3.1什么是哈希表？哈希查找：又叫散列查找，利用哈希函數進行查找的過程。其基本思想是在記錄的存儲地址和它的關鍵字之間建立一個確定的對應關系。這樣，不經過比較，一次存取就能得到所查元素的查找方法。哈希函數：在記錄的關鍵字與記錄的存儲地址之間建立的一種對應關系。按這種思想建立的表稱為哈希表。例假設有一批關鍵字序列18，75，60，43，54，90，46，給定散列函數H(k)=k%13，存貯區的內存地址從0到15，則可以得到每個關鍵字的散列地址為：

H(18)=18%13=5，H(75)=75%13=10，H(60)=60%13=8H(43)=43%13=4，H(54)=54%13=2，H(90)=90%13=12H(46)=46%13=7于是，根據散列地址，可以將上述7個關鍵字序列存貯到一個一維數組HT(散列表)中，具體表示為：90756046184354151413121110987654321

0HT其中HT就是散列存貯的表，稱為散列表。從散列表中查找一個元素相當方便，例如，查找75，只需計算出H(75)=75%13=10，則可以在HT[10]中找到75。舉例說明上面討論的散列表是一種理想的情形，即每一個關鍵字對應一個唯一的地址。但是有可能出現這樣的情形，兩個不同的關鍵字有可能對應同一個內存地址。這樣，將導致后放的關鍵字無法存貯，我們把這種現象叫做沖突(collision)。即key1≠key2，而f(key1)=f(key2)。在散列存貯中，沖突是很難避免的，除非構造出的散列函數為線性函數。散列函數選得比較差，則發生沖突的可能性越大。我們把相互發生沖突的關鍵字互稱為“同義詞”。

沖突問題1.直接定址法

可表示為H(key)=a*key+b，其中a、b均為常數。這種方法計算特別簡單，并且不會發生沖突，但當關鍵字分布不連續時，會出現很多空閑單元，將造成大量存貯單元的浪費。實際中使用此方法較少。例關鍵字集合為{100，300，500，700，800，900}，選取哈希函數為H(key)=key/100，則在哈希表中存放如下：

9.3.2哈希函數的構造方法01001230034500567007800890092.數字選擇法對關鍵字序列進行分析，取那些位上數字變化多的、頻率大的作為散列函數地址。例如，對如下的關鍵字序列：

43010

4681015355

43010

1701128352

43010

3720818350

430102690605351

．．．．．．通過對上述關鍵字序列分析，發現前5位相同，第6、8、10位上的數字變化多些，若規定地址取3位，則散列函數可取它的第6、8、10位。于是有：

H(430104681015355)＝480H(430101701128352)＝101H(430103620805351)＝328H(430102690605351)＝2969.3.2哈希函數的構造方法3.平方取中法取關鍵字平方后的中間幾位為散列函數地址。在選定散列函數時不一定知道關鍵字的全部信息，取其中哪幾位也不一定合適，而一個數平方后的中間幾位數和數的每一位都相關，因此，可以使用隨機分布的關鍵字得到函數地址。如圖，隨機給出一些關鍵字，并取平方后的第2到4位為函數地址。9.3.2哈希函數的構造方法關鍵字0100

(關鍵字)20010000函數地址010110012001210000144000021044011602061137040043105413703104.折疊法將關鍵字分割成位數相同的幾部分(最后一部分的位數可以不同)，然后取這幾部分的疊加和(舍去進位)作為散列函數地址，稱為折疊法。例如：假設關鍵字為某人身份證號碼430104681015355，則可以用4位為一組進行疊加，即有5355+8101+1046+430=14932，舍去高位，則有H(430104681015355)＝4932為該身份證關鍵字的散列函數地址。9.3.2哈希函數的構造方法5.除留余數法該方法是用關鍵字序列中的關鍵字k除以p(p是小于等于散列表長度m)所得余數作為散列函數的地址，即有H(k)＝k％p。

除留余數法計算簡單，適用范圍廣，是一種最常使用的方法。這種方法的關鍵是選取較理想的p值，使得每一個關鍵字通過該函數轉換后映射到散列空間上任一地址的概率都相等，從而盡可能減少發生沖突的可能性。

一般情形下，設散列表中允許的地址數為m，取一個不大于m，但最接近于或等于m的質數p。9.3.2哈希函數的構造方法由于散列存貯中選取的散列函數不是線性函數，故不可避免地會產生沖突，下面給出常見的解決沖突方法。1．開放定址法開放定址法就是從發生沖突的那個單元開始，按照一定的次序，從散列表中找出一個空閑的存儲單元，把發生沖突的待插入關鍵字存儲到該單元中，從而解決沖突的發生。9.3.3解決沖突的方法假設散列表的地址為0∽m-1，則散列表的長度為m。若一個關鍵字在地址d處發生沖突，則依次探查d+1，d+2，…，m-1(當達到表尾m-1時，又從0，1，2，….開始探查)等地址，直到找到一個空閑位置來裝沖突處的關鍵字，將這一種方法稱為線性探查法。探查下一位置的公式為di=(di-1+1)%m(1≤i≤m-1)，最后將沖突位置的關鍵字存入di地址中。線性探查法例給定序列為19，14，23，1，68，20，84，27，55，11，10，79，散到函數H(k)=k%13，散列表空間地址為0∽12，用線性探查法建立散列存貯結構。得到的散列表如下圖所示。

H(19)=19%13=6;H(14)=14%13=1;H(23)=23%13=10;H(1)=1%13=1;H(68)=68%13=3;H(20)=20%13=7;H(84)=84%13=6;H(27)=27%13=1;H(55)=55%13=3;H(11)=11%13=11;H(10)=10%13=10;H(79)=79%13=1;線性探查法012345678910111219142316820842755111079方法：構造若干個哈希函數，當發生沖突時，計算下一個哈希地址，直到沖突不再發生。即：Hi=Rhi(key)i=1,2,……,k其中：Rhi——不同的哈希函數