數(shù)據(jù)結(jié)構(gòu)（第2版）（C語言實(shí)現(xiàn)）課件：查找

查找

本書在第2章至第6章中已經(jīng)介紹了各種線性和非線性的數(shù)據(jù)結(jié)構(gòu)，在這一章將討論另一種在實(shí)際應(yīng)用中大量使用的重要技術(shù)──查找。在計(jì)算機(jī)處理非數(shù)值問題時(shí)，查找是一種經(jīng)常使用和非常重要的操作。本章主要介紹查找的基本概念、靜態(tài)查找、動(dòng)態(tài)查找、哈希表及查找。

本章重點(diǎn)和難點(diǎn)：

1、折半查找

2、索引順序表的查找

3、二叉排序樹和平衡二叉樹

4、B-樹

5、哈希表的構(gòu)造與查找7.1查找的基本概念

關(guān)鍵字(key)與主關(guān)鍵字(primarykey)：數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值。如果該關(guān)鍵字可以將所有的數(shù)據(jù)元素區(qū)別開來，也就是說可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素，則該關(guān)鍵字被稱為主關(guān)鍵字，否則被稱為次關(guān)鍵字(secondarykey)。特別地，如果數(shù)據(jù)元素只有一個(gè)數(shù)據(jù)項(xiàng)，則數(shù)據(jù)元素的值即是關(guān)鍵字。查找表(searchtable)：是由同一種類型的數(shù)據(jù)元素構(gòu)成的集合。查找表中的數(shù)據(jù)元素是完全松散的，數(shù)據(jù)元素之間沒有直接的聯(lián)系。7.1查找的基本概念

查找(searching)：根據(jù)關(guān)鍵字在特定的查找表中找到一個(gè)與給定關(guān)鍵字相同的數(shù)據(jù)元素的操作。如果在表中找到相應(yīng)的數(shù)據(jù)元素，則稱查找是成功的，否則，稱查找是失敗的。例如，表7.1中為學(xué)生學(xué)籍信息，如果要查找入學(xué)年份為“2008年”并且姓名是“劉華平”的學(xué)生，則可以先利用姓名將記錄定位（如果有重名的），然后在入學(xué)年份中查找為“2008”的記錄。表7.1學(xué)生學(xué)籍信息表7.1查找的基本概念

關(guān)鍵字（Key）與主關(guān)鍵字（PrimaryKey）：數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值。如果該關(guān)鍵字可以將所有的數(shù)據(jù)元素區(qū)別開來，也就是說可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素，則該關(guān)鍵字被稱為主關(guān)鍵字，否則被稱為次關(guān)鍵字。特別地，如果數(shù)據(jù)元素只有一個(gè)數(shù)據(jù)項(xiàng)，則數(shù)據(jù)元素的值即是關(guān)鍵字。

靜態(tài)查找（StaticSearchTable）：指的是僅僅在數(shù)據(jù)元素集合中查找是否存在與關(guān)鍵字相等的數(shù)據(jù)元素。在靜態(tài)查找過程中的存儲(chǔ)結(jié)構(gòu)稱為靜態(tài)查找表。

動(dòng)態(tài)查找（DynamicSearchTable）：在查找過程中，同時(shí)在數(shù)據(jù)元素集合中插入數(shù)據(jù)元素，或者在數(shù)據(jù)元素集合中刪除某個(gè)數(shù)據(jù)元素，這樣的查找稱為動(dòng)態(tài)查找。動(dòng)態(tài)查找過程中所使用的存儲(chǔ)結(jié)構(gòu)稱為動(dòng)態(tài)查找表。7.1查找的基本概念

平均查找長(zhǎng)度(averagesearchlength)：是指在查找過程中，需要比較關(guān)鍵字的平均次數(shù)，它是衡量查找算法的效率標(biāo)準(zhǔn)。平均查找長(zhǎng)度的數(shù)學(xué)定義為：ASL=。其中，Pi表示查找表中第i個(gè)數(shù)據(jù)元素的概率，Ci表示在找到第i個(gè)數(shù)據(jù)元素時(shí)，與關(guān)鍵字比較的次數(shù)。

7.2靜態(tài)查找7.2.1順序表的查找順序表的存儲(chǔ)結(jié)構(gòu)如下。

#defineMaxSize100typedefstruct{KeyTypekey;}DataType;typedefstruct{DataTypelist[MaxSize];intlength;}SSTable;7.2靜態(tài)查找順序表的查找算法描述如下：intSeqSearch(SSTableS,DataTypex)/*在順序表中查找關(guān)鍵字為x的元素，如果找到返回該元素在表中的位置，否則返回0*/{inti=0;while(i<S.length&&S.list[i].key!=x.key)/*從順序表的第一個(gè)元素開始比較*/i++;if(S.list[i].key==x.key)returni+1;elsereturn0;}7.2靜態(tài)查找以上算法也可以通過設(shè)置監(jiān)視哨的方法實(shí)現(xiàn)，其算法描述如下：intSeqSearch2(SSTableS,DataTypex)/*設(shè)置監(jiān)視哨S.list[0]，在順序表中查找關(guān)鍵字為x的元素，如果找到返回該元素在表中的位置，否則返回0*/{inti=S.length;S.list[0].key=x.key; /*將關(guān)鍵字存放在第0號(hào)位置，防止越界*/while(S.list[i].key!=x.key)/*從順序表的最后一個(gè)元素開始向前比較*/i--;returni;}7.2靜態(tài)查找下面分析帶監(jiān)視哨查找算法的效率。假設(shè)表中有n個(gè)數(shù)據(jù)元素，且數(shù)據(jù)元素在表中的出現(xiàn)的概率都相等即，則順序表在查找成功時(shí)的平均查找長(zhǎng)度為：

即查找成功時(shí)平均比較次數(shù)約為表長(zhǎng)的一半。在查找失敗時(shí)，即要查找的元素沒有在表中，則每次比較都需要進(jìn)行n+1次。7.2靜態(tài)查找7.2.2有序順序表的查找所謂有序順序表，就是順序表中的元素是以關(guān)鍵字進(jìn)行有序排列的。對(duì)于有序順序表的查找有兩種方法：順序查找和折半查找。

1．順序查找有序順序表的順序查找算法與順序表的查找算法類似。在通常情況下，無須比較表中的所有元素。如果要查找的元素在表中，則返回該元素的序號(hào)，否則返回0。7.2靜態(tài)查找intSeqSearch2(SSTableS,DataTypex)/*設(shè)置監(jiān)視哨S.list[0]，在有序順序表中查找關(guān)鍵字為x的元素，如果找到返回該元素在表中的位置，否則返回0*/{inti=S.length;S.list[0].key=x.key;/*將關(guān)鍵字存放在第0號(hào)位置，防止越界*/while(S.list[i].key>x.key) /*從有序順序表的最后一個(gè)元素開始向前比較*/

i--;if(S.list[i].key==x.key)

returni;return0;}7.2靜態(tài)查找

設(shè)表中的元素個(gè)數(shù)為n且要查找的數(shù)據(jù)元素在表中出現(xiàn)的概率相等即為，則有序順序表在查找成功時(shí)的平均查找長(zhǎng)度為：

即查找成功時(shí)平均比較次數(shù)約為表長(zhǎng)的一半。在查找失敗時(shí)，即要查找的元素沒有在表中，則有序順序表在查找失敗時(shí)的平均查找長(zhǎng)度為：7.2靜態(tài)查找2．折半查找折半查找（binarysearch）又稱為二分查找，這種查找算法要求待查找的元素序列必須是從小到大排列的有序序列。折半查找的算法描述如下：將待查找元素與表中間的元素進(jìn)行比較，如果兩者相等，則說明查找成功；否則利用中間位置將表分成兩部分，如果待查找元素小于中間位置的元素值，則繼續(xù)與前一個(gè)子表的中間位置元素進(jìn)行比較；否則與后一個(gè)子表的中間位置元素進(jìn)行比較。不斷重復(fù)以上操作，直到找到與待查找元素相等的元素，表明查找成功。如果子表變?yōu)榭毡?，表明查找失敗?.2靜態(tài)查找

例如，一個(gè)有序順序表為（9，23，26，32，36，47，56，63，79，81）,如果要查找56。利用以上折半查找思想，折半查找的過程如圖11.1所示。其中，圖中l(wèi)ow和high表示兩個(gè)指針，分別指向待查找元素的下界和上界，指針mid指向low和high的中間位置，即mid=(low+high)/2。7.2靜態(tài)查找折半查找的算法描述如下。intBinarySearch(SSTableS,DataTypex)/*在有序順序表中折半查找關(guān)鍵字為x的元素，如果找到返回該元素在表中的位置，否則返回0*/{ intlow,high,mid; low=0,high=S.length-1; /*設(shè)置待查找元素范圍的下界和上界*/ while(low<=high) { mid=(low+high)/2; if(S.list[mid].key==x.key) /*如果找到元素，則返回該元素所在的位置*/ returnmid+1; elseif(S.list[mid].key<x.key) /*如果mid所指示的元素小于關(guān)鍵字，則修改low指針*/ low=mid+1; elseif(S.list[mid].key>x.key) /*如果mid所指示的元素大于關(guān)鍵字，則修改high指針*/ high=mid-1; } return0;}7.2靜態(tài)查找

用折半查找算法查找關(guān)鍵字56的元素時(shí)，需要比較的次數(shù)為4個(gè)。從圖7.1中可以看出，查找元素36時(shí)需要比較1次，查找元素63時(shí)需要比較2次，查找元素47時(shí)需要比較3次，查找56需要比較4次。整個(gè)查找過程可以用圖7.2所示的二叉判定樹來表示。。7.2靜態(tài)查找對(duì)于具有n個(gè)結(jié)點(diǎn)的有序表剛好能夠構(gòu)成一個(gè)深度為h的滿二叉樹，則有h=。二叉樹中第i層的結(jié)點(diǎn)個(gè)數(shù)是2i-1，假設(shè)表中每個(gè)元素的查找概率相等，即Pi=。則有序表的折半查找成功時(shí)的平均查找長(zhǎng)度為：

查找失敗時(shí)，有序表的折半查找失敗時(shí)的平均查找長(zhǎng)度為：7.2靜態(tài)查找7.2.3索引順序表的查找當(dāng)順序表中的數(shù)據(jù)量非常大時(shí)，無論使用前述哪種查找算法都需要很長(zhǎng)的時(shí)間，此時(shí)提高查找效率的一個(gè)常用方法就是在順序表中建立索引表。建立索引表的方法是將順序表分為幾個(gè)單元，然后分別為這幾個(gè)單元建立一個(gè)索引，我們把原來的順序表稱為主表，提供索引的表稱為索引表。索引表中只存放主表中要查找的數(shù)據(jù)元素的主關(guān)鍵字和索引信息。圖7.3是一個(gè)主表和一個(gè)按關(guān)鍵字建立的索引表結(jié)構(gòu)圖。7.2靜態(tài)查找因索引表中的元素的關(guān)鍵字是有序的，故在確定元素所在主表的單元時(shí)，既可采用順序查找法也可采用折半查找法，但對(duì)于主表，只能采用順序法查找。索引順序表的平均查找長(zhǎng)度可以表示為：ASL=Lindex+Lunit。其中，Lindex是索引表的平均查找長(zhǎng)度，Lunit是單元中元素的平均查找長(zhǎng)度。假設(shè)主表中的元素個(gè)數(shù)為n，并將該主表平均分為b個(gè)單元，且每個(gè)單元有s個(gè)元素，即b=n/s。如果表中的元素查找概率相等，則每個(gè)單元中元素的查找概率就是1/s，主表中每個(gè)單元的查找概率是1/b。如果用順序查找法查找索引表中的元素，則索引順序表查找成功時(shí)的平均查找長(zhǎng)度為：ASL成功=。7.2靜態(tài)查找

當(dāng)然，如果主表中每個(gè)單元中的元素個(gè)數(shù)是不相等的時(shí)候，就需要在索引表中增加一項(xiàng)，即用來存儲(chǔ)主表中每個(gè)單元元素的個(gè)數(shù)。將這種利用索引表示的順序表稱為不等長(zhǎng)索引順序表。例如，一個(gè)不等長(zhǎng)的索引表如圖7.4所示。7.3動(dòng)態(tài)查找7.3.1二叉排序樹二叉排序樹也稱為二叉查找樹。二叉排序樹的查找是一種常用的動(dòng)態(tài)查找方法。

1．什么是二叉排序樹所謂二叉排序樹（binarysorttree），或者是一棵空二叉樹，或者二叉樹具有以下性質(zhì)：（1）如果二叉樹的左子樹不為空，則左子樹上的每一個(gè)結(jié)點(diǎn)的值均小于其對(duì)應(yīng)根結(jié)點(diǎn)的值；（2）如果二叉樹的右子樹不為空，則右子樹上的每一個(gè)結(jié)點(diǎn)的值均大于其對(duì)應(yīng)根結(jié)點(diǎn)的值；（3）該二叉樹的左子樹和右子樹也滿足性質(zhì)（1）和（2），即左子樹和右子樹也是一棵二叉排序樹。7.3動(dòng)態(tài)查找一棵二叉排序樹如圖7.5所示。

從圖7.5中可以看出，圖中的每個(gè)結(jié)點(diǎn)的值都大于其所有左子樹結(jié)點(diǎn)的值，而小于其所有右子樹中結(jié)點(diǎn)的值。如果要查找與二叉樹中某個(gè)關(guān)鍵字相等的結(jié)點(diǎn)，可以從根結(jié)點(diǎn)開始，與給定的關(guān)鍵字比較，如果相等，則查找成功。如果給定的關(guān)鍵字小于根結(jié)點(diǎn)的值，則在該根結(jié)點(diǎn)的左子樹中查找。如果給定的關(guān)鍵字大于根結(jié)點(diǎn)的值，則在該根結(jié)點(diǎn)的右子樹中查找。7.3動(dòng)態(tài)查找

2．查找算法采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的二叉排序樹的類型定義如下：

typedefstructNode{DataTypedata;structNode*lchild,*rchild;}BiTreeNode,*BiTree;7.3動(dòng)態(tài)查找BiTreeBSTSearch(BiTreeT,DataTypex)/*二叉排序樹的查找，如果找到元素x，則返回指向結(jié)點(diǎn)的指針，否則返回NULL*/{ BiTreeNode*p; if(T!=NULL) /*如果二叉排序樹不為空*/ { p=T; while(p!=NULL) { if(p->data.key==x.key)/*找到則返回指向該結(jié)點(diǎn)的指針*/ returnp; elseif(x.key<p->data.key)/*如果關(guān)鍵字小于p指向的結(jié)點(diǎn)的值，則在左子樹中查找*/ p=p->lchild; else p=p->rchild; /*如果關(guān)鍵字大于p指向的結(jié)點(diǎn)的值，則在右子樹中查找*/ } }returnNULL;}7.3動(dòng)態(tài)查找

在二叉排序樹的查找過程中，查找某個(gè)結(jié)點(diǎn)的過程正好是走了從根結(jié)點(diǎn)到要查找結(jié)點(diǎn)的路徑，其比較的次數(shù)正好是路徑長(zhǎng)度+1，這類似于折半查找，與折半查找不同的是由n個(gè)結(jié)點(diǎn)構(gòu)成的判定樹是唯一的，而由n個(gè)結(jié)點(diǎn)構(gòu)成的二叉排序樹則不唯一。例如，圖7.6為兩棵二叉排序樹，其元素的關(guān)鍵字序列分別是{57，21，71，12，51，67，76}和{12，21，51，57，67，71，76}。7.3動(dòng)態(tài)查找2．二叉排序樹的插入二叉排序樹的結(jié)構(gòu)不是一次生成的，而是在查找的過程中，當(dāng)樹中不存在關(guān)鍵字等于給定值的結(jié)點(diǎn)時(shí)再進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子結(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。二叉排序樹的插入操作過程其實(shí)就是二叉排序樹的建立過程。在算法的實(shí)現(xiàn)過程中，需要設(shè)置一個(gè)指向下一個(gè)要訪問結(jié)點(diǎn)的雙親結(jié)點(diǎn)指針parent，記下前驅(qū)結(jié)點(diǎn)的位置，以便在查找失敗時(shí)進(jìn)行插入操作。7.3動(dòng)態(tài)查找intBSTInsert(BiTree*T,DataTypex)/*二叉排序樹的插入操作，如果樹中不存在元素x，則將x插入到正確的位置并返回1，否則返回0*/{ BiTreeNode*p,*cur,*parent=NULL; cur=*T; while(cur!=NULL) { if(cur->data.key==x.key) /*二叉樹中存在元素為x的結(jié)點(diǎn)，則返回0*/ return0; parent=cur; /*parent指向cur的前驅(qū)結(jié)點(diǎn)*/ if(x.key<cur->data.key) /*如果關(guān)鍵字小于p指向的結(jié)點(diǎn)的值，則在左子樹中查找*/ cur=cur->lchild; else cur=cur->rchild; /*如果關(guān)鍵字大于p指向的結(jié)點(diǎn)的值，則在右子樹中查找*/ }7.3動(dòng)態(tài)查找p=(BiTreeNode*)malloc(sizeof(BiTreeNode)); /*生成結(jié)點(diǎn)*/ if(!p) exit(-1); p->data=x; p->lchild=NULL; p->rchild=NULL; if(!parent) /*如果二叉樹為空，則第一結(jié)點(diǎn)成為根結(jié)點(diǎn)*/ *T=p; elseif(x.key<parent->data.key) /*如果關(guān)鍵字小于parent指向的結(jié)點(diǎn)，則將x成為parent的左孩子*/ parent->lchild=p; else/*如果關(guān)鍵字大于parent指向的結(jié)點(diǎn)，則將x成為parent的右孩子*/ parent->rchild=p; return1; }

對(duì)于一個(gè)關(guān)鍵字序列{37，32，35，62，82，95，73，12，5}，根據(jù)二叉排序樹的插入算法思想，插入過程如圖7.7所示。7.3動(dòng)態(tài)查找7.3動(dòng)態(tài)查找3．二叉排序樹的刪除如何在二叉樹排序樹中刪除一個(gè)結(jié)點(diǎn)呢？假設(shè)要?jiǎng)h除的結(jié)點(diǎn)由指針s指示，指針p指向s的雙親結(jié)點(diǎn)，設(shè)s為p的左孩子結(jié)點(diǎn)。刪除一個(gè)結(jié)點(diǎn)分為3種情況討論。刪除情形如圖7.8所示。（1）如果s指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)，其左子樹和右子樹為空，刪除葉子結(jié)點(diǎn)不會(huì)影響到樹的結(jié)構(gòu)特性，因此只需要修改p的指針即可。（2）如果s指向的結(jié)點(diǎn)只有左子樹或只有右子樹，在刪除了結(jié)點(diǎn)*s后，只需要將s的左子樹sL或右子樹sR作為p的左孩子即p->lchild=s->lchild或p->lchid=s->rchild。（3）若s存在左子樹和右子樹，在刪除結(jié)點(diǎn)T之前，二叉排序樹的中序序列為{…QLQ…XLXYLYTTRP…}，因此，在刪除了結(jié)點(diǎn)S之后，使該二叉樹仍然保持原來的性質(zhì)不變的調(diào)整方法有兩種：（1）使結(jié)點(diǎn)T的左子樹作為結(jié)點(diǎn)P的左子樹，結(jié)點(diǎn)T的右子樹作為結(jié)點(diǎn)Y的右子樹。（2）使結(jié)點(diǎn)T的直接前驅(qū)取代結(jié)點(diǎn)T，并刪除T的直接前驅(qū)結(jié)點(diǎn)Y，然后令結(jié)點(diǎn)Y原來的左子樹作為結(jié)點(diǎn)X的右子樹。如圖7.8所示。7.3動(dòng)態(tài)查找二叉排序樹的刪除操作算法描述如下。intBSTDelete(BiTree*T,DataTypex)/*在二叉排序樹T中存在值為x的數(shù)據(jù)元素時(shí)，刪除該數(shù)據(jù)元素結(jié)點(diǎn)，并返回1，否則返回0*/{ if(!*T) /*如果不存在值為x的數(shù)據(jù)元素，則返回0*/ return0; else { if(x.key==(*T)->data.key)/*如果找到值為x的數(shù)據(jù)元素，則刪除該結(jié)點(diǎn)*/ DeleteNode(T); elseif((*T)->data.key>x.key) /*如果當(dāng)前元素值大于x的值，則在該結(jié)點(diǎn)的左子樹中查找并刪除之*/ BSTDelete(&(*T)->lchild,x); else /*如果當(dāng)前元素值小于x的值，則在該結(jié)點(diǎn)的右子樹中查找并刪除之*/ BSTDelete(&(*T)->rchild,x); return1; }}7.3動(dòng)態(tài)查找voidDeleteNode(BiTree*s)/*從二叉排序樹中刪除結(jié)點(diǎn)s，并使該二叉排序樹性質(zhì)不變*/{ BiTreeq,x,y; if(!(*s)->rchild) /*如果s的右子樹為空，重接左子樹*/ { q=*s; *s=(*s)->lchild; free(q); } elseif(!(*s)->lchild) /*如果s的左子樹為空，重接右子樹*/ { q=*s; *s=(*s)->rchild; free(q); }7.3動(dòng)態(tài)查找7.3動(dòng)態(tài)查找 else /*如果s的左、右子樹都存在，則使s的直接前驅(qū)結(jié)點(diǎn)代替s，并使其直接前驅(qū)結(jié)點(diǎn)的左子樹成為其雙親結(jié)點(diǎn)的右子樹結(jié)點(diǎn)*/ { x=*s; y=(*s)->lchild; while(y->rchild) /*查找s的直接前驅(qū)結(jié)點(diǎn)，y為s的直接前驅(qū)結(jié)點(diǎn)，x為y的雙親結(jié)點(diǎn)*/ { x=y; y=y->rchild; } (*s)->data=y->data; /*結(jié)點(diǎn)s被y取代*/ if(x!=*s) /*如果結(jié)點(diǎn)s的左孩子結(jié)點(diǎn)存在右子樹*/ x->rchild=y->lchild;/*使y的左子樹成為x的右子樹*/ else /*如果結(jié)點(diǎn)s的左孩子結(jié)點(diǎn)不存在右子樹*/ x->lchild=y->lchild; /*使y的左子樹成為x的左子樹*/ free(y); }}5．二叉排序樹應(yīng)用舉例

【例7.1】給定一組元素序列{37,32,35,62,82,95,73,12,5}，利用二叉排序樹的插入算法創(chuàng)建一棵二叉排序樹，然后查找元素值為73的元素，并刪除元素32，然后以中序序列輸出該元素序列。7.3動(dòng)態(tài)查找7.3.2平衡二叉樹若二叉排序樹的深度為n，在最壞的情況下平均查找長(zhǎng)度為n。因此，為了減小二叉排序樹的查找次數(shù)，需要對(duì)二叉樹排序樹進(jìn)行平衡化處理，平衡化處理得到的二叉樹稱為平衡二叉樹。

1．什么是平衡二叉樹平衡二叉樹（balancedbinarytree）又稱為AVL樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對(duì)值不超過1。7.3動(dòng)態(tài)查找若將二叉樹中結(jié)點(diǎn)的平衡因子BF（balancefactor）定義為結(jié)點(diǎn)的左子樹的深度減去右子樹的深度，則平衡二叉樹中每個(gè)結(jié)點(diǎn)的平衡因子只可能是-1、0和1。如圖7.12所示為兩棵平衡二叉樹，結(jié)點(diǎn)的右邊表示平衡因子，因?yàn)樵摱鏄浼仁嵌媾判驑溆质瞧胶鈽洌虼?，該二叉樹稱為平衡二叉排序樹。只要二叉樹上有一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則該二叉樹就是不平衡的。如圖7.11所示為兩棵不平衡的二叉樹。7.3動(dòng)態(tài)查找2．二叉排序樹的平衡處理在二叉排序樹中插入一個(gè)新結(jié)點(diǎn)后，如何保證該二叉樹是平衡二叉排序樹呢？設(shè)有一個(gè)關(guān)鍵字序列{7，36，45，78，65}，依照此關(guān)鍵字序列建立二叉排序樹，且使該二叉排序樹是平衡二叉排序樹。初始時(shí)，二叉樹為空樹，因此是平衡二叉樹。插入結(jié)點(diǎn)7和36后，該二叉樹依然是平衡的，結(jié)點(diǎn)7和結(jié)點(diǎn)36的平衡因子分別為-1和0。當(dāng)插入結(jié)點(diǎn)45后，結(jié)點(diǎn)7的平衡因子變?yōu)?2，二叉樹變?yōu)椴黄胶猓@需要進(jìn)行調(diào)整。以結(jié)點(diǎn)36為軸進(jìn)行逆時(shí)針旋轉(zhuǎn)，將二叉樹變?yōu)橐?6為根，各個(gè)結(jié)點(diǎn)的平衡因子都為0，二叉樹恢復(fù)了平衡。7.3動(dòng)態(tài)查找

繼續(xù)插入結(jié)點(diǎn)76，二叉樹仍然是平衡的。當(dāng)插入結(jié)點(diǎn)65時(shí)，該二叉樹失去了平衡，如果仍然按照上述方法僅僅以結(jié)點(diǎn)45為軸進(jìn)行旋轉(zhuǎn)，就會(huì)失去二叉排序樹的性質(zhì)。為了保持二叉排序樹的性質(zhì)，又要保證該二叉樹是平衡的，需要進(jìn)行兩次調(diào)整：先以結(jié)點(diǎn)76為軸進(jìn)行順時(shí)針旋轉(zhuǎn)，然后以結(jié)點(diǎn)65為軸進(jìn)行逆時(shí)針旋轉(zhuǎn)。7.3動(dòng)態(tài)查找

通過上述平衡化處理，我們得出一個(gè)結(jié)論：通過讓插入點(diǎn)最近的祖先結(jié)點(diǎn)恢復(fù)平衡，從而使上一層祖先結(jié)點(diǎn)恢復(fù)平衡。因此，為了使二叉排序樹恢復(fù)平衡，需要從離插入點(diǎn)最近的結(jié)點(diǎn)開始調(diào)整。平衡化二叉排序樹可分為以下4種情形。（1）LL型。LL型是指在離插入點(diǎn)最近的失衡結(jié)點(diǎn)的左子樹的左子樹中插入結(jié)點(diǎn)，導(dǎo)致二叉排序樹失去平衡。如圖7.13所示。距離插入點(diǎn)最近的失衡結(jié)點(diǎn)為A，插入新結(jié)點(diǎn)X后，結(jié)點(diǎn)A的平衡因子由1變?yōu)?，該二叉排序樹失去平衡。為了使二叉樹恢復(fù)平衡且保持二叉排序樹的性質(zhì)不變，可以使結(jié)點(diǎn)A作為結(jié)點(diǎn)B的右子樹，結(jié)點(diǎn)B的右子樹作為結(jié)點(diǎn)A的左子樹。這樣就恢復(fù)了該二叉排序樹的平衡，這相當(dāng)于以結(jié)點(diǎn)B為軸，對(duì)結(jié)點(diǎn)A進(jìn)行順時(shí)針旋轉(zhuǎn)。7.3動(dòng)態(tài)查找

為平衡二叉排序樹的每個(gè)結(jié)點(diǎn)增加一個(gè)域bf，用來表示對(duì)應(yīng)結(jié)點(diǎn)的平衡因子。平衡二叉排序樹的類型如下：

typedefstructBSTNode /*平衡二叉排序樹的類型定義*/{ DataTypedata; intbf; /*結(jié)點(diǎn)的平衡因子*/ structBSTNode*lchild,*rchild;/*左、右孩子指針*/}BSTNode,*BSTree;7.3動(dòng)態(tài)查找

對(duì)LL型二叉排序樹的平衡化處理代碼如下：

BSTreeb; b=p->lchild; /*lc指向p的左子樹的根結(jié)點(diǎn)*/ p->lchild=b->rchild; /*將lc的右子樹作為p的左子樹*/ b->rchild=p; p->bf=b->bf=0; /*修改平衡因子*/7.3動(dòng)態(tài)查找

（2）LR型。LR型是指在離插入點(diǎn)最近的失衡結(jié)點(diǎn)的左子樹的右子樹中插入結(jié)點(diǎn)，導(dǎo)致二叉排序樹失去平衡。如圖7.14所示。這相當(dāng)于以結(jié)點(diǎn)B為軸，對(duì)結(jié)點(diǎn)C先做了一次逆時(shí)針旋轉(zhuǎn)；然后以結(jié)點(diǎn)C為軸對(duì)結(jié)點(diǎn)A做了一次順時(shí)針旋轉(zhuǎn)。7.3動(dòng)態(tài)查找7.3動(dòng)態(tài)查找

（3）RL型。RL型是指在離插入點(diǎn)最近的失衡結(jié)點(diǎn)的右子樹的左子樹中插入結(jié)點(diǎn)，導(dǎo)致二叉排序樹失去平衡。如圖7.15所示。這相當(dāng)于以結(jié)點(diǎn)B為軸，對(duì)結(jié)點(diǎn)C先做了一次順時(shí)針旋轉(zhuǎn)；然后以結(jié)點(diǎn)C為軸對(duì)結(jié)點(diǎn)A做了一次逆時(shí)針旋轉(zhuǎn)。7.3動(dòng)態(tài)查找（4）RR型。RR型是指在離插入點(diǎn)最近的失衡結(jié)點(diǎn)的右子樹的右子樹中插入結(jié)點(diǎn)，導(dǎo)致二叉排序樹失去平衡。如圖7.16所示。這相當(dāng)于以結(jié)點(diǎn)B為軸，對(duì)結(jié)點(diǎn)A做了一次逆時(shí)針旋轉(zhuǎn)。7.3動(dòng)態(tài)查找

綜上以上4種情形，在平衡二叉排序樹中插入一個(gè)結(jié)點(diǎn)e后，若仍需保持二叉排序樹平衡的算法描述如下：（1）若平衡二叉排序樹是空樹，則插入的結(jié)點(diǎn)e作為根結(jié)點(diǎn)，并使該樹的深度增1；（2）若二叉樹中已存在與結(jié)點(diǎn)e的關(guān)鍵字相等的結(jié)點(diǎn)，則無須插入；（3）若結(jié)點(diǎn)e的關(guān)鍵字小于要插入位置的結(jié)點(diǎn)的關(guān)鍵字，則將e插入到該結(jié)點(diǎn)的左子樹位置，并使該結(jié)點(diǎn)的左子樹高度增1，同時(shí)修改該結(jié)點(diǎn)的平衡因子；如果該結(jié)點(diǎn)的平衡因子絕對(duì)值大于1，則需要進(jìn)行平衡化處理；（4）若結(jié)點(diǎn)e的關(guān)鍵字大于要插入位置的結(jié)點(diǎn)的關(guān)鍵字，則將e插入到該結(jié)點(diǎn)的右子樹位置，并將該結(jié)點(diǎn)的右子樹高度增1，同時(shí)修改該結(jié)點(diǎn)的平衡因子；如果該結(jié)點(diǎn)的平衡因子絕對(duì)值大于1，則進(jìn)行平衡化處理。7.3動(dòng)態(tài)查找1．LL型的平衡處理對(duì)于LL型的失去平衡的情形，只需要對(duì)離插入點(diǎn)最近的失衡結(jié)點(diǎn)進(jìn)行一次順時(shí)針旋轉(zhuǎn)處理即可。其算法實(shí)現(xiàn)如下。voidRightRotate(BSTree*p)/*對(duì)以*p為根的二叉排序樹進(jìn)行右旋，處理之后p指向新的根結(jié)點(diǎn)，即旋轉(zhuǎn)處理之前的左子樹的根結(jié)點(diǎn)*/{ BSTreelc; lc=(*p)->lchild; /*lc指向p的左子樹的根結(jié)點(diǎn)*/ (*p)->lchild=lc->rchild; /*將lc的右子樹作為p的左子樹*/ lc->rchild=*p; (*p)->bf=lc->bf=0; *p=lc; /*p指向新的根結(jié)點(diǎn)*/}7.3動(dòng)態(tài)查找2．LR型的平衡處理對(duì)于LR型的失去平衡的情形，需要進(jìn)行兩次旋轉(zhuǎn)處理：先進(jìn)行一次逆時(shí)針旋轉(zhuǎn)，然后再進(jìn)行一次順時(shí)針旋轉(zhuǎn)處理。其算法實(shí)現(xiàn)如下。7.3動(dòng)態(tài)查找3．RL型的平衡處理對(duì)于RL型的失去平衡的情形，需要進(jìn)行兩次旋轉(zhuǎn)處理：先進(jìn)行一次順時(shí)針旋轉(zhuǎn)，然后再進(jìn)行一次逆時(shí)針旋轉(zhuǎn)處理。其算法實(shí)現(xiàn)如下。7.3動(dòng)態(tài)查找4．RR型的平衡處理對(duì)于RR型的失去平衡的情形，只需要對(duì)離插入點(diǎn)最近的失衡結(jié)點(diǎn)進(jìn)行一次逆時(shí)針旋轉(zhuǎn)處理即可。算法實(shí)現(xiàn)如下。voidLeftRotate(BSTree*p)/*對(duì)以*p為根的二叉排序樹進(jìn)行左旋，處理之后p指向新的根結(jié)點(diǎn)，即旋轉(zhuǎn)處理之前的右子樹的根結(jié)點(diǎn)*/{ BSTreerc; rc=(*p)->rchild; /*rc指向p的右子樹的根結(jié)點(diǎn)*/ (*p)->rchild=rc->lchild;/*將rc的左子樹作為p的右子樹*/ rc->lchild=*p; *p=rc; /*p指向新的根結(jié)點(diǎn)*/}7.3.3紅黑樹紅黑二叉查找樹（red-blackBST），簡(jiǎn)稱紅黑樹，顧名思義，它也是一種二叉查找樹，在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示結(jié)點(diǎn)的顏色，可以是紅或黑。紅黑樹是一種接近平衡的二叉樹。1．紅黑樹的定義紅黑樹是一棵具有以下特點(diǎn)的二叉查找樹：（1）每個(gè)結(jié)點(diǎn)不是紅色，就是黑色；（2）根結(jié)點(diǎn)的顏色為黑色；（3）葉子結(jié)點(diǎn)是空節(jié)點(diǎn)且為黑色；（4）若一個(gè)結(jié)點(diǎn)是紅色的，則孩子結(jié)點(diǎn)一定是黑色的，即從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑中，不存在連續(xù)的紅色結(jié)點(diǎn)；（5）從任何一個(gè)結(jié)點(diǎn)出發(fā)到葉子結(jié)點(diǎn)的路徑上，包含相同數(shù)目的黑色結(jié)點(diǎn)。2．紅黑樹的基本運(yùn)算1）紅黑樹的插入紅黑樹的插入也是在葉子結(jié)點(diǎn)處進(jìn)行，插入的新結(jié)點(diǎn)作為紅黑樹的葉子結(jié)點(diǎn)。插入的結(jié)點(diǎn)被著色為紅色，然后以二叉排序樹的插入方法插入到紅黑樹中。假設(shè)插入的結(jié)點(diǎn)為T，其雙親結(jié)點(diǎn)P為紅色的，則P的雙親結(jié)點(diǎn)是黑色的。插入結(jié)點(diǎn)后，可分為兩種情況進(jìn)行調(diào)整。（1）T的雙親結(jié)點(diǎn)P的兄弟結(jié)點(diǎn)U是黑色的情況如圖7-18(b)所示。圖中的a、b、c、d、e分別表示相應(yīng)的子樹。（2）T的雙親結(jié)點(diǎn)P的兄弟結(jié)點(diǎn)U是紅色的情況若T的雙親結(jié)點(diǎn)P的兄弟結(jié)點(diǎn)U是紅色時(shí)，不能再通過簡(jiǎn)單的一次旋轉(zhuǎn)或兩次旋轉(zhuǎn)，調(diào)整兩個(gè)結(jié)點(diǎn)的顏色來恢復(fù)原有紅黑樹的性質(zhì)了。插入的結(jié)點(diǎn)T為紅色，當(dāng)雙親結(jié)點(diǎn)P也為紅色時(shí)，則P的雙親結(jié)點(diǎn)G為黑色。若P的兄弟結(jié)點(diǎn)U為紅色，這需要重新對(duì)紅黑樹進(jìn)行著色，即將G著色為紅色，P和U著色為黑色。如圖7.21所示。2）紅黑樹的刪除與插入操作一樣，在刪除了紅黑樹中的結(jié)點(diǎn)后，仍要使紅黑樹保持原有性質(zhì)不變。如果刪除的是葉子結(jié)點(diǎn)，刪除的結(jié)點(diǎn)可能為紅色或者黑色，若刪除的是紅色結(jié)點(diǎn)，由于刪除該結(jié)點(diǎn)不會(huì)影響到分支結(jié)點(diǎn)的數(shù)量，則直接刪除即可。如果刪除的是黑色結(jié)點(diǎn)，則需要進(jìn)行調(diào)整操作。（1）D的兄弟結(jié)點(diǎn)S為黑色，且S至少有一個(gè)孩子結(jié)點(diǎn)是紅色。（2）D的兄弟結(jié)點(diǎn)S為黑色，且S的兩個(gè)孩子結(jié)點(diǎn)也是黑色的。（3）D的兄弟結(jié)點(diǎn)為紅色結(jié)點(diǎn)。7.4B-樹與B+樹7.4.1B-樹與二叉排序樹類似，B-樹是一種特殊的m叉動(dòng)態(tài)查找樹。下面介紹B-樹的結(jié)構(gòu)與查找算法。

1．什么是B-樹

B-是一種平衡的多路查找樹，也稱為m路（叉）查找樹，它在文件系統(tǒng)中很有用。一棵m路（階）B-樹或者是一棵空樹，或者是滿足以下性質(zhì)的m叉樹：（1）任何一個(gè)結(jié)點(diǎn)最多有m棵子樹；（2）或者是根結(jié)點(diǎn)或者是葉子結(jié)點(diǎn)，或者至少有兩棵子樹；（3）除根結(jié)點(diǎn)外，所有非終端結(jié)點(diǎn)至少有棵子樹；（4）所有的非終端結(jié)點(diǎn)的結(jié)構(gòu)如下：7.4B-樹與B+樹

其中，n為結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)，-1≤n≤m-1，Pi為指向子樹根結(jié)點(diǎn)的指針，并且Pi指向子樹的每個(gè)結(jié)點(diǎn)關(guān)鍵字都小于Ki+1(i=0,1,…,n-1)。（5）所有葉子結(jié)點(diǎn)處于同一層次上，且不帶信息（可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在）。例如，一棵深度為4的4階的B-樹如圖7.17所示。7.4B-樹與B+樹2．B-樹的查找

B-樹的查找其實(shí)是對(duì)二叉排序樹查找的擴(kuò)展，與二叉排序樹不同的地方是，B-樹中每個(gè)結(jié)點(diǎn)有不止一棵子樹。在B-樹中查找某個(gè)結(jié)點(diǎn)時(shí)，需要先判斷要查找的結(jié)點(diǎn)在哪棵子樹上，然后在結(jié)點(diǎn)中逐個(gè)查找目標(biāo)結(jié)點(diǎn)。B-樹的類型描述如下：

#definem4 /*B-樹的階數(shù)*/typedefstructBTNode /*B-樹類型定義*/{ intkeynum; /*每個(gè)結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)*/ structBTNode*parent; /*指向雙親結(jié)點(diǎn)*/ KeyTypedata[m+1]; /*結(jié)點(diǎn)中關(guān)鍵字信息*/ structBTNode*ptr[m+1]; /*指針向量*/}BTNode,*BTree;7.4B-樹與B+樹3．B-樹的插入操作在B-樹上插入結(jié)點(diǎn)與在二叉樹上插入結(jié)點(diǎn)類似，都是插入前后，保證B-樹仍然是一棵排序樹，即結(jié)點(diǎn)左子樹中每個(gè)結(jié)點(diǎn)的關(guān)鍵字小于根結(jié)點(diǎn)的關(guān)鍵字，右子樹結(jié)點(diǎn)的關(guān)鍵字大于根結(jié)點(diǎn)的關(guān)鍵字。但由于B-樹結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)必須≥-1，因此每次插入一個(gè)關(guān)鍵字不是在樹中添加一個(gè)葉子結(jié)點(diǎn)，而是首先在最低層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字，若該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)不超過m-1，則插入完成，否則對(duì)該結(jié)點(diǎn)進(jìn)行分裂。7.4B-樹與B+樹

例如，圖7.18為一棵3階的B-樹（省略了葉子結(jié)點(diǎn)），當(dāng)給定一棵B-樹的階之后，就確定了這棵樹的最少子樹個(gè)數(shù)為和最多子樹個(gè)數(shù)，確定了每個(gè)結(jié)點(diǎn)要求最少1個(gè)關(guān)鍵字，最多2個(gè)關(guān)鍵字。插入關(guān)鍵字42：首先需要從根結(jié)點(diǎn)開始，確定關(guān)鍵字42應(yīng)插入的位置應(yīng)該是結(jié)點(diǎn)E。因?yàn)椴迦牒蠼Y(jié)點(diǎn)E中的關(guān)鍵字個(gè)數(shù)大于1（-1）小于2（m-1），所以插入成功。插入后B-樹如圖7.19所示。。7.4B-樹與B+樹插入關(guān)鍵字25：插入關(guān)鍵字78：7.4B-樹與B+樹

此時(shí)，結(jié)點(diǎn)C的關(guān)鍵字個(gè)數(shù)大于2，因此，需要將結(jié)點(diǎn)C進(jìn)行分裂為兩個(gè)結(jié)點(diǎn)。將中間的關(guān)鍵字73插入到雙親結(jié)點(diǎn)A中，關(guān)鍵字83保留在C中，關(guān)鍵字67被插入到新結(jié)點(diǎn)C’中，并使關(guān)鍵字56的右指針指向結(jié)點(diǎn)C’，關(guān)鍵字73的右指針指向結(jié)點(diǎn)C。結(jié)點(diǎn)C的分裂過程如圖8.22所示。插入關(guān)鍵字43：7.4B-樹與B+樹

此時(shí)，結(jié)點(diǎn)B中的關(guān)鍵字個(gè)數(shù)大于2，需要進(jìn)一步分解結(jié)點(diǎn)B，其中關(guān)鍵字32被插入到雙親結(jié)點(diǎn)A中，關(guān)鍵字24被保留在結(jié)點(diǎn)B中，關(guān)鍵字32被插入到新結(jié)點(diǎn)B’中，關(guān)鍵字24的左、右指針分別指向結(jié)點(diǎn)D和D’，關(guān)鍵字32的左、右指針分別指向結(jié)點(diǎn)E和E’。結(jié)點(diǎn)B被分裂的過程如圖7.25所示。。結(jié)點(diǎn)A被分裂的過程如圖7.26所示。7.4B-樹與B+樹4．B-樹的刪除操作

B-樹的刪除操作可分為3種情況：（1）要?jiǎng)h除的關(guān)鍵字所在結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)大于等于，則只需要將關(guān)鍵字Ki和對(duì)應(yīng)的指針Pi從該結(jié)點(diǎn)中刪除即可。因?yàn)閯h除該關(guān)鍵字后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)仍然不小于-1。例如，圖7.27顯示了從結(jié)點(diǎn)E中刪除關(guān)鍵字35的情形。7.4B-樹與B+樹

（2）被刪除的關(guān)鍵字所在結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)等于，而與該結(jié)點(diǎn)相鄰的的右兄弟（或左兄弟）結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)大于-1，則刪除關(guān)鍵字后，需要將其兄弟結(jié)點(diǎn)中最小（或最大）的關(guān)鍵字上移至雙親結(jié)點(diǎn)中，將雙親結(jié)點(diǎn)中小于（或大于）且緊靠該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在的結(jié)點(diǎn)中。例如，將關(guān)鍵字89刪除后，需要將關(guān)鍵字73向上移動(dòng)到雙親結(jié)點(diǎn)C中，并將關(guān)鍵字83下移到結(jié)點(diǎn)H中，得到如圖7.28所示的B-樹。7.4B-樹與B+樹

（3）被刪除的關(guān)鍵字所在結(jié)點(diǎn)和其相鄰的兄弟結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)均等于

，假設(shè)該結(jié)點(diǎn)有右兄弟，且其右兄弟結(jié)點(diǎn)地址由雙親結(jié)點(diǎn)中的指針Pi所指，則在刪除關(guān)鍵字之后，它所在的結(jié)點(diǎn)中剩余的關(guān)鍵字和指針，加上雙親結(jié)點(diǎn)中的關(guān)鍵字Ki一起，合并到Pi所指的兄弟結(jié)點(diǎn)中。若沒有右兄弟結(jié)點(diǎn)，則合并至左兄弟結(jié)點(diǎn)中。例如，將關(guān)鍵字83刪除后，需要將關(guān)鍵字83的左兄弟結(jié)點(diǎn)的關(guān)鍵字69與其雙親結(jié)點(diǎn)中的關(guān)鍵字73合并到一起，得到如圖7.29所示的B-樹。7.4B-樹與B+樹7.4.2B+樹

B+樹是B-樹的一種變型樹。一棵m階的B+樹和m階的B-樹的差異在于：（1）有n棵子樹的結(jié)點(diǎn)必有n個(gè)關(guān)鍵字，即關(guān)鍵字個(gè)數(shù)與結(jié)點(diǎn)的子樹個(gè)數(shù)相等；（2）所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小從小到大順序鏈接。（3）所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹（根結(jié)點(diǎn)）中的最大（或最?。╆P(guān)鍵字。7.5哈希表7.5.1什么是哈希表如何在查找元素的過程中，不與給定的關(guān)鍵字進(jìn)行比較，就能確定所查找元素的存放位置。這就需要在元素的關(guān)鍵字與元素的存儲(chǔ)位置之間建立起一種對(duì)應(yīng)關(guān)系，使得元素的關(guān)鍵字與唯一的存儲(chǔ)位置對(duì)應(yīng)。有了這種對(duì)應(yīng)關(guān)系，在查找某個(gè)元素時(shí)，只需要利用這種確定的對(duì)應(yīng)關(guān)系，由給定的關(guān)鍵字就可以直接找到該元素。用key表示元素的關(guān)鍵字，f表示對(duì)應(yīng)關(guān)系，則f(key)表示元素的存儲(chǔ)地址，將這種對(duì)應(yīng)關(guān)系f稱為哈希函數(shù)，利用哈希函數(shù)可以建立哈希表。哈希表也稱為散列函數(shù)。表7.2哈希表示例7.5哈希表7.5.2哈希函數(shù)的構(gòu)造方法構(gòu)造哈希函數(shù)的目的主要是使哈希地址盡可能地均勻分布以減少或避免產(chǎn)生沖突、使計(jì)算方法盡可能地簡(jiǎn)便以提高運(yùn)算效率。哈希函數(shù)的構(gòu)造方法主要有以下幾種：

1．直接定址法

2．平方取中法

3．折疊法折疊法是將元素平均分割為若干等份，最后一個(gè)部分如果不夠可以空缺，然后將這幾個(gè)等份疊加求和作為哈希地址。這種方法主要用在元素的位數(shù)特別多且每一個(gè)元素的位數(shù)分布大體相當(dāng)?shù)那闆r。例如，給定一個(gè)元素為23478245983，可以按照3位將該元素分割為幾個(gè)部分，其折疊計(jì)算過程如下：7.5哈希表4．除留余數(shù)法通過對(duì)元素取余，將得到的余數(shù)作為哈希地址。設(shè)哈希表長(zhǎng)為m，p為小于等于m的最大質(zhì)數(shù)，則哈希函數(shù)為h(key)=key%p。例如，給定一組關(guān)鍵字{75，150，123，183，230，56，37，91}，設(shè)哈希表長(zhǎng)m為14，取p=13則這組關(guān)鍵字的哈希地址存儲(chǔ)情況為7.5哈希表7.5.3處理沖突的方法處理沖突的方法常用的主要有：開放定址法、再哈希法和鏈地址法。

1．開放定址法開放定址法是解決沖突比較常用的方法。開放定址法就是利用哈希表中的空地址存儲(chǔ)產(chǎn)生沖突的關(guān)鍵字。當(dāng)沖突發(fā)生時(shí)，按照下列公式處理沖突：

hi=(h(key)+di)%m,其中i=1,2,…,m-1

其中，h(key)為哈希函數(shù)，m為哈希表長(zhǎng)，di為地址增量。地址增量di可以以下三種方法獲得：（1）線性探測(cè)再散列：在沖突發(fā)生時(shí)，地址增量di依次取1,2,…,m-1自然數(shù)列，即di=1,2,…,m-1;

（2）二次探測(cè)再散列：在沖突發(fā)生時(shí)，地址增量di依次取自然數(shù)的平方，即di=12，-12，22，-22,…,k2，-k2。（3）偽隨機(jī)數(shù)再散列：在沖突發(fā)生時(shí)，地址增量di依次取隨機(jī)數(shù)序列。7.5哈希表

例如，在長(zhǎng)度為14的哈希表中，在將關(guān)鍵字183，123，230，91存放在哈希表中的情況如圖7.31所示。

當(dāng)要插入關(guān)鍵字149時(shí)，由哈希函數(shù)h(149)=149%13=6，而單元6已經(jīng)存在關(guān)鍵字，產(chǎn)生沖突，利用線性探測(cè)再散列法解決沖突，即h1=(6+1)%14=7，將149存儲(chǔ)在單元7中。如圖7.32所示。當(dāng)要插入元素227時(shí)，7.5哈希表2．再哈希法再哈希法就是在沖突發(fā)生時(shí)，利用另外一個(gè)哈希函數(shù)再次求哈希函數(shù)的地址，直到?jīng)_突不再發(fā)生為止.3．鏈地址法鏈地址法就是將具有相同散列地址的關(guān)鍵字用一個(gè)線性鏈表存儲(chǔ)起來。每個(gè)線性鏈表設(shè)置一個(gè)頭指針指向該鏈表。鏈地址法的存儲(chǔ)表示類似于圖的鄰接表表示。在每一個(gè)鏈表中，所有的元素都是按照關(guān)鍵字有序排列。鏈地址法的主要優(yōu)點(diǎn)是在哈希表中增加元素和刪除元素方便。7.5哈希表

例如，一組關(guān)鍵字序列{23，35，12，56，123，39，342，90，78，110}，按照哈希函數(shù)h(key)=key%13和鏈地址法處理沖突，其哈希表如圖7.35所示。。7.5哈希表7.5.4哈希表查找與分析在哈希查找過程中，查找效率的高低除了與解決沖突的方法有關(guān)外，在處理沖突方法相同的情況下，其平均查找時(shí)間還依賴于哈希表的裝填因子，哈希表的裝填因子定義為：

裝填因子越小，表中填入的記錄就越小，發(fā)生沖突的可能性就會(huì)越小；反之，表中已填入的記錄越多，再繼續(xù)填充記錄時(shí)，發(fā)生沖突的可能性就越大，則查找時(shí)進(jìn)行關(guān)鍵字查找的比較次數(shù)就會(huì)越多。7.5哈希表7.5.5哈希表應(yīng)用舉例

【例7.2】將關(guān)鍵字序列(7,8,30,11,18,9,14)散列存儲(chǔ)在散列表中，散列表的存儲(chǔ)空間是一個(gè)下標(biāo)從0開始的一維數(shù)組，散列函數(shù)為H(key)=(key*3)MOD7，處理沖突采用線性探測(cè)再散列法，要求裝填因子為0.7。

（1）請(qǐng)畫出構(gòu)造的散列表。

（2）分別計(jì)算等概率情況下查找成功和查找失敗時(shí)的平均查找長(zhǎng)度。

【分析】（1）由題目已知條件裝填因子=0.7，可得到表長(zhǎng)m為10。根據(jù)散列函數(shù)H(key)=(key*3)MOD7和處理沖突方法構(gòu)造哈希表。對(duì)于關(guān)鍵字7，H(7)=7*3%7=0對(duì)于關(guān)鍵字8，H(8)=8*3%7=3對(duì)于關(guān)鍵字30，H(30)=30*3%7=6對(duì)于關(guān)鍵字11，H(11)=11*3%7=57.5哈希