7查找7.1查找的概念與術(shù)語7.2順序查找與二分查找7.3二叉排序樹7.4平衡二叉樹7.5哈希查找7.6STL之set與map7.7在線題目求解學(xué)習(xí)目標(biāo)1.記憶和理解查找相關(guān)的基本概念和術(shù)語。2.熟練掌握順序查找、二分查找、二叉排序樹和哈希查找等查找的方法。3.重點(diǎn)掌握二分查找、二叉排序樹和哈希查找等查找算法的實(shí)現(xiàn)。4.能夠分析和評(píng)價(jià)查找算法的性能。5.學(xué)會(huì)運(yùn)用查找相關(guān)算法求解具體問題。7查找7.1查找的概念與術(shù)語由相同類型的數(shù)據(jù)元素（記錄）構(gòu)成的集合稱作查找表。查找表中的元素之間無明確的關(guān)系。關(guān)鍵字是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)某個(gè)數(shù)據(jù)元素。約定查找表中的關(guān)鍵字各不相同，因此每個(gè)關(guān)鍵字可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。查找是指在查找表中確定是否存在一個(gè)數(shù)據(jù)元素，該元素的關(guān)鍵字等于給定的某個(gè)值的過程。若在查找表中找到這樣的元素，則稱為查找成功；否則稱為查找失敗。7.1查找的概念與術(shù)語對(duì)查找表經(jīng)常進(jìn)行的操作如下：（1）查詢某個(gè)數(shù)據(jù)元素是否在查找表中；（2）在查找表中插入一個(gè)數(shù)據(jù)元素；（3）從查找表中刪除某個(gè)數(shù)據(jù)元素。根據(jù)是否對(duì)查找表進(jìn)行更新（插入或刪除），查找表可分為靜態(tài)查找表和動(dòng)態(tài)查找表。靜態(tài)查找表是指僅作查詢操作的查找表。動(dòng)態(tài)查找表是指在查詢之外還需進(jìn)行插入或刪除操作的查找表。也就是說，動(dòng)態(tài)查找表在查詢之后，還需將查找失敗的數(shù)據(jù)元素插入到查找表中；或者從查找表中刪除其指定的數(shù)據(jù)元素。7.1查找的概念與術(shù)語查找算法的平均查找長(zhǎng)度（AverageSearchLength，ASL）是指確定記錄在查找表中的位置所需與給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值，計(jì)算式為：

其中，n為查找表的表長(zhǎng)，Ci為找到該記錄時(shí)所作的比較次數(shù)，pi為查找表中查找第i個(gè)記錄的概率，且

。等概率情況下的ASL計(jì)算：7.2順序查找與二分查找順序查找和二分查找是針對(duì)靜態(tài)查找表的查找。順序查找基礎(chǔ)順序查找是指按從前往后（正向）或者從后往前（逆向）的順序在查找表中進(jìn)行查找，分別稱為正向順序查找和逆向順序查找。設(shè)關(guān)鍵字序列為(29,76,54,19,16,10,7,81,15,52)，對(duì)應(yīng)的靜態(tài)查找表（下標(biāo)從1開始用）如下：若對(duì)其進(jìn)行正向順序查找，則給定的待查找值（給定值）依次與下標(biāo)為1、2、3、……、10的關(guān)鍵字比較。若對(duì)其進(jìn)行逆向順序查找，則給定值依次與下標(biāo)為10、9、8、……、1的關(guān)鍵字比較。7.2順序查找與二分查找順序查找基礎(chǔ)靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)typedefintKeyType;structElemType{

//數(shù)據(jù)元素類型定義

KeyTypekey;

//關(guān)鍵字

//……

//其他屬性};structSSTable{

//靜態(tài)查找表類型定義

ElemType*elem;

//元素存儲(chǔ)空間基址，0號(hào)單元留空

intlength;

//表的長(zhǎng)度};7.2順序查找與二分查找順序查找算法實(shí)現(xiàn)正向順序查找算法//正向順序查找算法，在順序表ST中查找關(guān)鍵字等于e的元素//若找到，則返回該元素在表中的位置，否則返回0intSearch_Seq(SSTableST,KeyTypee){

intk=1;

while(k<=ST.length&&ST.elem[k].key!=e)k++;

if(k<=ST.length)returnk;

elsereturn0;}7.2順序查找與二分查找順序查找算法實(shí)現(xiàn)逆向順序查找時(shí)，從尾端往前查，并且初始時(shí)設(shè)置哨兵，即把待查找的關(guān)鍵字置于下標(biāo)為0的存儲(chǔ)單元，如此可以避免下標(biāo)越界的判斷。//逆向順序查找算法，在順序表ST中查找關(guān)鍵字等于e的元素//若找到，則返回該元素在表中的位置，否則返回0intSearch_Seq_Rev(SSTableST,KeyTypekey){

ST.elem[0].key=key;//設(shè)置哨兵

inti;

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

returni;

//找不到時(shí)，i為0}7.2順序查找與二分查找順序查找性能分析正向順序查找，查找到第i個(gè)元素的比較次數(shù)Ci=i，等概率情況下，逆向順序查找，查找到第i個(gè)元素的比較次數(shù)Ci=n-i+1，等概率情況下，順序查找的時(shí)間復(fù)雜度為O(n)。7.2順序查找與二分查找二分查找基礎(chǔ)二分查找的前提是查找表采用順序存儲(chǔ)結(jié)構(gòu)，且按關(guān)鍵字有序。在二分查找過程中，每次取查找區(qū)間正中間位置的元素與待查找的給定值比較，從而使得查找區(qū)間不斷縮小一半，故也稱折半查找。二分查找的基本思想：設(shè)已按關(guān)鍵字升序排列的順序表ST的查找區(qū)間為[1..ST.length]，先計(jì)算正中間元素的下標(biāo)mid，再用其關(guān)鍵字與給定值x比較，分以下三種情況進(jìn)行處理：（1）若ST.elem[mid].key==x，則查找成功，結(jié)束查找；（2）若ST.elem[mid].key>x，則把查找區(qū)間縮小到表的前半部分，再繼續(xù)進(jìn)行二分查找；（3）若ST.elem[mid].key<x，則把查找區(qū)間縮小到表的后半部分，再繼續(xù)進(jìn)行二分查找。7.2順序查找與二分查找二分查找基礎(chǔ)例7.2.1二分查找的判定樹設(shè)關(guān)鍵字序列為(7,10,15,16,19,29,52,54,76,81)，要求畫出二分查找的判定樹，并計(jì)算等概率情況下，查找成功的ASL。二分查找的判定樹可用關(guān)鍵字或下標(biāo)描述等概率情況下查找成功的ASL=(1×1+2×2+3×4+4×3)/10=2.97.2順序查找與二分查找二分查找算法實(shí)現(xiàn)二分查找算法的實(shí)現(xiàn)方法設(shè)兩個(gè)指針（實(shí)際是下標(biāo)）low、high分別指向查找區(qū)間的左、右端點(diǎn)元素；計(jì)算中間位置的下標(biāo)mid=(low+high)/2；若待查找元素x等于mid所指元素的關(guān)鍵字ST.elem[mid].key，則查找成功；若x<ST.elem[mid].key，則到左半?yún)^(qū)間二分查找（high=mid-1）；若x>ST.elem[mid].key，則到右半?yún)^(qū)間二分查找（low=mid+1）。7.2順序查找與二分查找二分查找算法實(shí)現(xiàn)/*二分查找算法，在有序的順序表ST中，查找關(guān)鍵字等于給定值x的元素，

若找到則返回對(duì)應(yīng)的下標(biāo)，否則返回0*/intBinSearch(SSTableST,KeyTypex){

//二分查找

intlow=1;

//low指向查找區(qū)間的第一個(gè)元素

inthigh=ST.length;//high指向查找區(qū)間的最后一個(gè)元素

while(low<=high){//當(dāng)查找區(qū)間還有元素時(shí)循環(huán)

intmid=(low+high)/2;//計(jì)算中間位置的下標(biāo)

if(x==ST.elem[mid].key)//比較x和mid所指元素的關(guān)鍵字

returnmid;

//找到待查元素，則返回其下標(biāo)

elseif(x<ST.elem[mid].key)

high=mid-1;

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

else

low=mid+1;

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

}

return0;

//查找失敗，則返回0}7.2順序查找與二分查找二分查找性能分析表長(zhǎng)為n的二分查找的判定樹的深度和含有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度相同。設(shè)n=2h-1，等概率情況下，二分查找的ASL計(jì)算如下：二分查找的時(shí)間復(fù)雜度為O(log2n)。7.3二叉排序樹二叉排序樹基礎(chǔ)二叉排序樹也稱二叉搜索樹，它或?yàn)橐豢每諛洌蛘呤蔷哂腥缦绿匦缘亩鏄洌海?）若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的關(guān)鍵字值均小于根結(jié)點(diǎn)的關(guān)鍵字值；（2）若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的關(guān)鍵字值均大于根結(jié)點(diǎn)的關(guān)鍵字值；（3）它的左、右子樹也都分別是二叉排序樹。例如，右上圖為二叉排序樹，

右下圖為非二叉排序樹。二叉排序樹的中序遍歷序列是一個(gè)升序序列。7.3二叉排序樹二叉排序樹的查找算法二叉排序樹的查找的算法思想：若二叉排序樹為空，則查找失??；否則，（1）若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；（2）若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上按相同的方法進(jìn)行查找；（3）若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上按相同的方法進(jìn)行查找。例如，右圖中查找54，則將依次比較29、76、52、54，最終查找成功；若查找20，則將依次比較29、16、19，最終查找失敗7.3二叉排序樹二叉排序樹的查找算法在二叉排序樹的查找過程中，生成了一條查找路徑：（1）從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至找到關(guān)鍵字等于給定值的結(jié)點(diǎn)（查找成功）；（2）從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止（查找失?。?.3二叉排序樹二叉排序樹的查找算法結(jié)點(diǎn)類型typedefcharElemType;

//若改數(shù)據(jù)域類型，則把char改為相應(yīng)類型structBiTNode{

//結(jié)點(diǎn)結(jié)構(gòu)

ElemTypedata;

//

結(jié)點(diǎn)數(shù)據(jù)域

BiTNode*lchild,*rchild;//左、右孩子指針

//帶3個(gè)參數(shù)的構(gòu)造函數(shù)

BiTNode(ElemTypee,BiTNode*left,BiTNode*right){

data=e;

lchild=left;

rchild=right;

}

BiTNode(){}

//無參構(gòu)造函數(shù)};7.3二叉排序樹二叉排序樹的查找算法查找算法實(shí)現(xiàn)（遞歸法）//二叉排序樹的遞歸查找算法，查找成功后返回指向所找結(jié)點(diǎn)的指針，否則返回空指針BiTNode*SearchBST1(BiTNode*T,KeyTypekey){

if(T==NULL)returnT;//找到空指針，查找失敗

elseif(key==T->data)

//若key等于根結(jié)點(diǎn)的值，則查找成功

returnT;

elseif(key<T->data)

//若key小于根結(jié)點(diǎn)的值，則在左子樹中查找

returnSearchBST1(T->lchild,key);

else

//若key大于根結(jié)點(diǎn)的值，則在右子樹中查找

returnSearchBST1(T->rchild,key);}7.3二叉排序樹二叉排序樹的查找算法查找算法實(shí)現(xiàn)（迭代法）//二叉排序樹的迭代查找算法，查找成功后返回指向所找結(jié)點(diǎn)的指針，否則返回空指針BiTNode*SearchBST2(BiTNode*T,KeyTypekey){

while(T!=NULL){

//當(dāng)未找到空指針時(shí)循環(huán)

if(key==T->data)

//若key等于根結(jié)點(diǎn)的值，則查找成功

break;

elseif(key<T->data)//若key小于根結(jié)點(diǎn)的值，則在左子樹中查找

T=T->lchild;

else

//若key大于根結(jié)點(diǎn)的值，則在右子樹中查找

T=T->rchild;

}

returnT;

//返回指向所找到結(jié)點(diǎn)的指針或NULL}7.3二叉排序樹二叉排序樹的插入算法根據(jù)動(dòng)態(tài)查找表的定義，“插入”操作在查找不成功時(shí)才進(jìn)行。若二叉排序樹為空樹，則新插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié)點(diǎn)，其插入位置在按上述查找算法進(jìn)行查找的過程得到。也就是說，若在二叉排序樹的查找過程中找到空指針，則該空指針?biāo)谖恢眉礊椴迦胛恢谩?.3二叉排序樹二叉排序樹的插入算法插入算法實(shí)現(xiàn)（遞歸法）//二叉排序樹的遞歸插入算法，在以T為根的二叉排序樹中插入關(guān)鍵字為e的結(jié)點(diǎn)voidInsertBST1(BiTNode*&T,KeyTypee){

if(!T)

//若為空樹，則創(chuàng)建結(jié)點(diǎn)

T=newBiTNode(e,NULL,NULL);

elseif(e<T->data)

//往左子樹插入

InsertBST1(T->lchild,e);

elseif(e>T->data)

//往右子樹插入

InsertBST1(T->rchild,e);}7.3二叉排序樹二叉排序樹的插入算法插入算法實(shí)現(xiàn)（迭代法）//二叉排序樹的迭代插入算法，在以T為根的二叉排序樹中插入關(guān)鍵字為e的結(jié)點(diǎn)voidInsertBST2(BiTNode*&T,KeyTypee){

if(!T){

//空樹

T=newBiTNode(e,NULL,NULL);return;

}

BiTNode*p=T;

while(true){

//p將一直移動(dòng)到插入位置的父結(jié)點(diǎn)位置

if(e<p->data&&p->lchild)//往左子樹找插入位置

p=p->lchild;

elseif(e>p->data&&p->rchild)//往右子樹找插入位置

p=p->rchild;

else

//找到或者p的左、右指針之一為空指針

break;

}7.3二叉排序樹二叉排序樹的插入算法插入算法實(shí)現(xiàn)（迭代法）

//離開循環(huán)只有找到或未找到2種情況（p不會(huì)為空）

if(e<p->data)

p->lchild=newBiTNode(e,NULL,NULL);

elseif(e>p->data)

p->rchild=newBiTNode(e,NULL,NULL);}7.3二叉排序樹二叉排序樹的創(chuàng)建創(chuàng)建二叉排序樹實(shí)際上是一個(gè)不斷調(diào)用插入算法的過程，可以逐個(gè)輸入關(guān)鍵字并調(diào)用插入算法創(chuàng)建二叉排序樹。例7.3.1二叉排序樹的創(chuàng)建請(qǐng)按給定的關(guān)鍵字序列(29,76,54,16,19,15,7,10,81,52)創(chuàng)建二叉排序樹，并求等概率情況下的ASL。按照關(guān)鍵字序列中關(guān)鍵字出現(xiàn)的順序，依次調(diào)用插入算法把結(jié)點(diǎn)插入到一棵初始為空樹的二叉排序樹中，最終結(jié)果如右圖。等概率情況下，ASL=(1×1+2×2+3×4+4×2+5×1)/10=3。7.3二叉排序樹二叉排序樹的刪除算法刪除在查找成功之后進(jìn)行，并且要求在刪除二叉排序樹上某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹的特性。在二叉排序樹中刪除結(jié)點(diǎn)可分三種情況討論：（1）被刪除的結(jié)點(diǎn)是葉子；（2）被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹；（3）被刪除的結(jié)點(diǎn)既有左子樹，又有右子樹。7.3二叉排序樹二叉排序樹的刪除算法若被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)，則直接刪去即可；若考慮算法實(shí)現(xiàn)，則只需把待刪結(jié)點(diǎn)的父結(jié)點(diǎn)中的相應(yīng)指針域的值改為空指針即可。例如，對(duì)下圖（左）所示的二叉排序樹，若分別刪去結(jié)點(diǎn)10和52，則所得結(jié)果分別如下圖（中）、下圖（右）所示。7.3二叉排序樹二叉排序樹的刪除算法若被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹，則把其左子樹或右子樹作為其父結(jié)點(diǎn)的相應(yīng)子樹；若考慮算法實(shí)現(xiàn)，則其父結(jié)點(diǎn)的相應(yīng)指針域的值改為待刪結(jié)點(diǎn)的左孩子指針或右孩子指針。例如，對(duì)下圖（左）所示的二叉排序樹，若分別刪去結(jié)點(diǎn)54和7，則所得結(jié)果分別如下圖（中）、下圖（右）所示。7.3二叉排序樹二叉排序樹的刪除算法若被刪除的結(jié)點(diǎn)既有左子樹又有右子樹，則用其中序遍歷的前驅(qū)或后繼替代待刪結(jié)點(diǎn)，然后再刪除用來替代待刪結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)；若考慮算法實(shí)現(xiàn)，則可先找到待刪結(jié)點(diǎn)的中序遍歷的前驅(qū)（或后繼）并替代之，然后再刪除該前驅(qū)（或后繼）結(jié)點(diǎn)。例如，對(duì)下圖（左）所示的二叉排序樹，若刪去結(jié)點(diǎn)29時(shí)分別以中序遍歷的前驅(qū)19或后繼52替代，則所得結(jié)果分別如下圖（中）、下圖（右）所示。7.3二叉排序樹二叉排序樹的刪除算法刪除二叉排序樹中一個(gè)結(jié)點(diǎn)的算法//從二叉排序樹中刪除p所指結(jié)點(diǎn)，并重接它的左子樹或右子樹voidDeleteNode(BiTNode*&p){

BiTNode*q,*s;

if(!p->rchild){

q=p;

//

右子樹為空樹

p=p->lchild;

deleteq;

}

elseif(!p->lchild){

q=p;

//

左子樹為空樹

p=p->rchild;

deleteq;

}7.3二叉排序樹二叉排序樹的刪除算法

else{

//

左右子樹均不空

q=p;

s=p->lchild;

while(s->rchild){

q=s;

//s指向被刪結(jié)點(diǎn)前驅(qū)

s=s->rchild;

}

p->data=s->data;

if(q!=p)

//意味著原來的s有右子樹

q->rchild=s->lchild;

//重接q的右子樹

else

q->lchild=s->lchild;

//重接q的左子樹

deletes;

}}7.3二叉排序樹二叉排序樹的刪除算法

在二叉排序樹中查找關(guān)鍵字為給定值key的結(jié)點(diǎn)并刪除該結(jié)點(diǎn)的算法思想：若找不到（查找過程中遇到空樹），則返回false；若找到（key等于某結(jié)點(diǎn)的關(guān)鍵字），則調(diào)用DeleteNode算法刪除該結(jié)點(diǎn)并返回true；否則，若key小于該結(jié)點(diǎn)的關(guān)鍵字，則在其左子樹中按相同的方法繼續(xù)查找，若key大于該結(jié)點(diǎn)的關(guān)鍵字，則在其右子樹中按相同的方法繼續(xù)查找。7.3二叉排序樹二叉排序樹的刪除算法//若T中存在關(guān)鍵字等于key的元素，則刪除該結(jié)點(diǎn)并返回true，否則返回falseboolDeleteBST(BiTNode*&T,KeyTypekey){if(!T)returnfalse;//不存在關(guān)鍵字等于key的元素if(key==T->data){//找到關(guān)鍵字等于key的結(jié)點(diǎn)DeleteNode(T);returntrue;}elseif(key<T->data)returnDeleteBST(T->lchild,key);//在左子樹中進(jìn)行查找elsereturnDeleteBST(T->rchild,key);//在右子樹中進(jìn)行查找}7.3二叉排序樹二叉排序樹的性能分析隨機(jī)情況下，n個(gè)結(jié)點(diǎn)的二叉排序樹的平均查找長(zhǎng)度與O(log2n)同數(shù)量級(jí)。注意，由值相同的n個(gè)關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長(zhǎng)度的值不同，甚至可能差別很大。例如，關(guān)鍵字序列(3,1,2,5,4)、(1,2,3,4,5)所構(gòu)造的二叉排序樹分別如下圖（左）、下圖（右），ASL分別為2.2和3。n個(gè)結(jié)點(diǎn)的二叉排序樹查找的最壞時(shí)間復(fù)雜度為O(n)7.4平衡二叉樹平衡二叉樹基礎(chǔ)平衡二叉樹，也稱AVL樹，是另一種形式的二叉排序樹，其特點(diǎn)是樹中每個(gè)結(jié)點(diǎn)的左、右子樹深度之差的絕對(duì)值不大于1。樹中某結(jié)點(diǎn)的左、右子樹深度之差稱為該結(jié)點(diǎn)的平衡因子。平衡二叉樹本身是一棵二叉排序樹，故它的查找與二叉排序樹完全相同。但其查找的最壞時(shí)間復(fù)雜度為O(log2n)。平衡二叉樹非平衡二叉樹7.4平衡二叉樹平衡二叉樹基礎(chǔ)構(gòu)造平衡二叉樹的方法與創(chuàng)建二叉排序樹類似，但每插入一個(gè)新結(jié)點(diǎn)都要檢查是否會(huì)使得該樹“失衡”，即檢查是否出現(xiàn)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，若出現(xiàn)這種情況，則需根據(jù)所插入結(jié)點(diǎn)的類型（LL、RR、LR、RL）進(jìn)行平衡旋轉(zhuǎn)。7.4平衡二叉樹平衡二叉樹基礎(chǔ)例7.4.1平衡二叉樹的構(gòu)造根據(jù)關(guān)鍵字序列(5,4,2,8,6,9,0,1)構(gòu)造平衡二叉樹。7.4平衡二叉樹構(gòu)造平衡二叉樹的一般方法設(shè)A是最靠近新插入結(jié)點(diǎn)的失衡結(jié)點(diǎn)（平衡因子絕對(duì)值大于1），則失衡后進(jìn)行調(diào)整的平衡處理方法可歸納為如下四種情況：（1）LL型：在A的左子樹根結(jié)點(diǎn)的左子樹上插入結(jié)點(diǎn)，如下圖（左）所示；采用單向右旋平衡處理，如下圖（右）所示。7.4平衡二叉樹構(gòu)造平衡二叉樹的一般方法（2）RR型：在A的右子樹根結(jié)點(diǎn)的右子樹上插入結(jié)點(diǎn)，如下圖（左）所示；采用單向左旋平衡處理，如下圖（右）所示。7.4平衡二叉樹構(gòu)造平衡二叉樹的一般方法（3）LR型：在A的左子樹根結(jié)點(diǎn)的右子樹上插入結(jié)點(diǎn)，如下圖（左）所示；采用先左后右的雙向旋轉(zhuǎn)平衡處理：先向左旋轉(zhuǎn)，如下圖（中）所示，再向右旋轉(zhuǎn)，如下圖（右）所示。7.4平衡二叉樹構(gòu)造平衡二叉樹的一般方法（4）RL型：在A的右子樹根結(jié)點(diǎn)的左子樹上插入結(jié)點(diǎn)，如下圖（左）所示；采用先右后左的雙向旋轉(zhuǎn)平衡處理：先向右旋轉(zhuǎn)，如下圖（中）所示，再左向旋轉(zhuǎn)，如下圖（右）所示。7.5哈希查找哈希查找基礎(chǔ)對(duì)于頻繁使用的查找表，期待ASL等于0。若預(yù)先知道所查關(guān)鍵字在表中的位置，則不需要與任何關(guān)鍵字比較即可直接找到該關(guān)鍵字。如此，要求表中的記錄位置和其關(guān)鍵字之間存在一種確定的關(guān)系。例如，若要求以學(xué)號(hào)為關(guān)鍵字為1000名新生（學(xué)號(hào)取值范圍為xx000~xx999）建立一張查找表，則可以下標(biāo)為0~999的順序表表示之，取學(xué)號(hào)的后三位為地址，從而不需要經(jīng)過比較便可直接從順序表中找到待查關(guān)鍵字。7.5哈希查找哈希查找基礎(chǔ)哈希函數(shù)是在關(guān)鍵字key與其記錄在表中的存儲(chǔ)位置p之間建立的一個(gè)函數(shù)關(guān)系H，使得p=H(key)。其中，p稱為關(guān)鍵字key的哈希地址。根據(jù)哈希函數(shù)H(key)和所選用的處理沖突的方法構(gòu)造所得的查找表稱為哈希表（HashTable）。若哈希表以一維數(shù)組表示，則哈希地址是指該數(shù)組的下標(biāo)。7.5哈希查找哈希查找基礎(chǔ)例7.5.1哈希表的構(gòu)造設(shè)哈希函數(shù)H(key)=(key的第一個(gè)字母-'A'+1)/2，要求根據(jù)關(guān)鍵字序列(Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dai)構(gòu)造哈希表。因H(key)的最大值為13，故可設(shè)哈希表長(zhǎng)為14；計(jì)算可得關(guān)鍵字序列的哈希地址序列為(13,

8,

9,

6,

11,

1,

4,

12,

2)，可構(gòu)造哈希表如下：若添加關(guān)鍵字Zhou，則產(chǎn)生沖突，該如何處理？7.5哈希查找哈希查找基礎(chǔ)沖突是指不同的關(guān)鍵字按哈希函數(shù)得到相同的哈希地址，即key1≠key2，而有H(key1)=H(key2)。哈希函數(shù)值相同的關(guān)鍵字（或元素）稱為同義詞。對(duì)于key1≠key2，若有H(key1)=H(key2)，則key1和key2互為同義詞。哈希函數(shù)是一個(gè)壓縮映象，在一般情況下，很容易產(chǎn)生沖突現(xiàn)象。在構(gòu)造哈希表時(shí)，除了需要選擇一個(gè)“好”（盡可能少產(chǎn)生沖突）的哈希函數(shù)之外；還需要找到一種“處理沖突”的方法。實(shí)際上，很難找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)，盡可能減少?zèng)_突。7.5哈希查找哈希查找基礎(chǔ)構(gòu)造哈希函數(shù)的方法構(gòu)造哈希函數(shù)的方法很多。對(duì)于數(shù)字型的關(guān)鍵字，可用下列構(gòu)造方法：（1）數(shù)字分析法：分析關(guān)鍵字提取數(shù)字分布比較均勻的若干位作為哈希地址；（2）平方取中法：對(duì)關(guān)鍵字求平方后取中間的幾位（或其組合）作為哈希地址；（3）折疊法：將關(guān)鍵字分割成位數(shù)相同（最后一部分可不同）的若干部分并疊加（可用移位疊加或邊界疊加）求和（舍去進(jìn)位）作為哈希地址；（4）除留余數(shù)法：用關(guān)鍵字除以某個(gè)數(shù)的余數(shù)作為哈希地址。7.5哈希查找哈希查找基礎(chǔ)（4）除留余數(shù)法設(shè)哈希表中允許的地址數(shù)（表長(zhǎng)）為m，除留余數(shù)法通常取一個(gè)不大于m，但最接近于或等于m的p作為除數(shù)，利用下面的哈希函數(shù)把關(guān)鍵字key轉(zhuǎn)換成哈希地址Hash(key)。

Hash(key)=key%p,p≤m直接用上式得到的哈希地址只能是0~p-1，若p<m，則p,…,m-1這些地址是不可能用哈希函數(shù)計(jì)算出來的，它們只可能在處理沖突時(shí)用到。通常，要求p是質(zhì)數(shù)（素?cái)?shù)）且不接近2的冪，否則，可能會(huì)增加沖突。7.5哈希查找哈希查找基礎(chǔ)對(duì)于非數(shù)字型關(guān)鍵字，需先對(duì)其進(jìn)行數(shù)字化處理。兩個(gè)經(jīng)典的字符串哈希函數(shù)unsignedintHash1(strings){

unsignedinth=0;

for(inti=0;i<s.size();i++){

h=31*h+s[i];

}

returnh%MaxN;}7.5哈希查找哈希查找基礎(chǔ)兩個(gè)經(jīng)典的字符串哈希函數(shù)unsignedintHash2(strings){

unsignedinth=0;

for(inti=0;i<s.size();i++){

h=(h<<4)+s[i];

unsignedintg=h&0Xf0000000L;

if(g)h^=g>>24;

h&=~g;

}

returnh%MaxN;}7.5哈希查找哈希查找之處理沖突在哈希查找中沖突通常不可避免。處理沖突的含義是為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址。處理沖突常用的兩種方法是開放定址法和鏈地址法。開放定址法

為產(chǎn)生沖突的地址H(key)求得一個(gè)地址序列：H0,H1,H2,…,Hs(1≤s≤m-1)，其中，m為哈希表的表長(zhǎng)，H0=H(key)，

Hi=(H(key)+di)%m,i=1,2,…,s

對(duì)增量di有三種取法，對(duì)應(yīng)線性探測(cè)法、平方探測(cè)法（二次探測(cè)法）、隨機(jī)探測(cè)法等三種探測(cè)方法。7.5哈希查找哈希查找之處理沖突之開放定址法（1）線性探測(cè)法di=i,i=1,2,…,m-1（2）平方探測(cè)法di=12,-12,22,-22,…,k2,-k2,k≤m/2（3）隨機(jī)探測(cè)法隨機(jī)探測(cè)的增量di是一組偽隨機(jī)數(shù)列。7.5哈希查找哈希查找之處理沖突之開放定址法例7.5.2基于線性探測(cè)的哈希表構(gòu)造

關(guān)鍵字序列(19,1,23,14,55,68,11,82,36)，哈希函數(shù)H(key)=key%11，表長(zhǎng)為11，采用線性探測(cè)法處理沖突，要求構(gòu)造哈希表，并求等概率情況下查找成功的ASL。等概率情況下查找成功的ASL=(4×1+2×2+3+5+6)/9=22/97.5哈希查找哈希查找之處理沖突之開放定址法例7.5.3基于二次探測(cè)的哈希表構(gòu)造

關(guān)鍵字序列(14,9,1,23,55,20,84,27)，哈希函數(shù)H(key)=key%7，表長(zhǎng)為10，采用二次探測(cè)法處理沖突，要求構(gòu)造哈希表，并求等概率情況下查找成功的ASL。等概率情況下查找成功的ASL=(1×4+2×2+3×2)/8=7/47.5哈希查找哈希查找之處理沖突之開放定址法例7.5.4哈希表的構(gòu)造及其ASL與填充因子

已知關(guān)鍵字序列(19,14,23,1,68,20,84,27,55,11,10,79)，哈希表長(zhǎng)為14，哈希函數(shù)H(key)=key%13。用線性探測(cè)法處理沖突，構(gòu)造哈希表，求等概率情況下查找成功與查找不成功的平均查找長(zhǎng)度及哈希表的填充因子。7.5哈希查找哈希查找之處理沖突之開放定址法例7.5.4哈希表的構(gòu)造及其ASL與填充因子

等概率情況下查找成功的ASLsuccess=1/12×(1×6+2+3×3+4+9)=2.5等概率情況下查找不成功的平均查找長(zhǎng)度=1/13×(1+2+3+4+5+6+7+8+9+10+11+12+13)=7填充因子=12/14=6/7設(shè)記錄數(shù)為n，表長(zhǎng)為m，對(duì)于線性探測(cè)法，找到空位表示查找失敗，比較次數(shù)Ci包含找到空位的那一次比較。7.5哈希查找哈希查找之處理沖突之鏈地址法鏈地址法將所有哈希地址相同的記錄都鏈接在同一鏈表中。鏈地址法對(duì)應(yīng)的哈希表類似于圖的鄰接表，包含兩部分，即表頭結(jié)點(diǎn)表和邊表；表頭結(jié)點(diǎn)表是一個(gè)指針數(shù)組，每個(gè)元素指向一個(gè)鏈表；邊表中的每個(gè)鏈表由哈希地址相同的記錄鏈接而成。例7.5.5基于鏈地址法的哈希表構(gòu)造

已知關(guān)鍵字序列(19,14,23,68,20,84,27,55,11,30,79,48)，用鏈地址法處理沖突，哈希函數(shù)H(key)=key%7。構(gòu)造哈希表，求等概率情況下查找成功與查找不成功的平均查找長(zhǎng)度及哈希表的填充因子。7.5哈希查找哈希查找之處理沖突之鏈地址法例7.5.5基于鏈地址法的哈希表構(gòu)造等概率情況下，查找成功的平均查找長(zhǎng)度ASLsuccess=(1×5+2×4+3×2+4)/12=23/12查找失敗的平均查找長(zhǎng)度ASLunsuccess=1/7×(1×2+2×1+3×2+4+5)=19/7填充因子α=12/7。對(duì)于鏈地址法，找到空指針表示查找失敗，比較次數(shù)包含找到空指針的那一次比較7.5哈希查找哈希查找之處理沖突從以上例子可見，哈希查找的ASL實(shí)際上并不等于零。決定哈希查找ASL的因素主要包括：（1）選用的哈希函數(shù)；（2）選用的處理沖突的方法；（3）哈希表飽和的程度，以填充因子衡量。哈希查找的ASL是處理沖突方法和填充因子的函數(shù)。用哈希表構(gòu)造查找表時(shí)，可以選擇一個(gè)適當(dāng)?shù)奶畛湟蜃?，使得ASL限定在某個(gè)范圍內(nèi)。7.5哈希查找哈希查找的算法實(shí)現(xiàn)哈希查找的主要算法是查找算法和插入算法。哈希查找的查找算法思想：對(duì)于給定值k，計(jì)算哈希地址p=H(k)；若p地址為空，則查找失??；若地址p上記錄的關(guān)鍵字等于k，則查找成功，否則求下一地址Hi(k)，直至Hi(k)為空（查找失敗），或地址Hi(k)上記錄的關(guān)鍵字等于k（查找成功）。對(duì)于地址為空（空位），采用開放定址法時(shí)可預(yù)設(shè)關(guān)鍵字為特殊值（如-1）來表示，而采用鏈地址法時(shí)可用空指針NULL表示。哈希查找的插入算法思想：對(duì)于給定值k，先在哈希表中查找，若找到關(guān)鍵字k則無需插入，否則把關(guān)鍵字為k的記錄插入到查找過程中得到的空位上。7.5哈希查找哈希查找的算法實(shí)現(xiàn)基于開放地址法的算法實(shí)現(xiàn)constintMaxSize=101;

//最大的表長(zhǎng)，除留余數(shù)法的除數(shù)typedefintKeyType;

//關(guān)鍵字類型typedefintInfoType;

//其他字段類型structElemType{

//元素結(jié)構(gòu)

KeyTypekey;

//關(guān)鍵字

InfoTypeinfo;

//其他信息};constintSPECIAL=-1;

//關(guān)鍵字設(shè)為特殊值-1表示地址為空intHash(intkey);

//哈希函數(shù)，除留余數(shù)法intNextPos(intp);

//線性探測(cè)求一個(gè)地址7.5哈希查找哈希查找的算法實(shí)現(xiàn)基于開放地址法的算法實(shí)現(xiàn)structHashTable{

//哈希表結(jié)構(gòu)

ElemType*elem;

//哈希表

intcount;

//當(dāng)前數(shù)據(jù)元素個(gè)數(shù)

HashTable(intn=MaxSize){

//構(gòu)造函數(shù)

count=0;

elem=newElemType[n];

for(inti=0;i<n;i++){

elem[i].key=-1;

elem[i].info=0;

}

}};7.5哈希查找哈希查找的算法實(shí)現(xiàn)基于開放地址法的算法實(shí)現(xiàn)/*查找算法，在哈希表ht中查找關(guān)鍵字為k的元素，若查找成功，以p指示待查記錄在表中位置，并返回true；否則，以p指示插入位置，并返回false*/boolSearchHash(HashTableht,KeyTypek,int&p){

p=Hash(k);

//利用Hash函數(shù)求得哈希地址

//當(dāng)未找到待找關(guān)鍵字且未找到空位時(shí)循環(huán)

while(ht.elem[p].key!=SPECIAL&&ht.elem[p].key!=k){

p=NextPos(p);

//求得下一探測(cè)地址p

}

if(ht.elem[p].key==k)

//查找成功，p返回待查記錄位置

returntrue;

else

returnfalse;//查找不成功，p返回的是插入位置}7.5哈希查找哈希查找的算法實(shí)現(xiàn)基于開放地址法的算法實(shí)現(xiàn)//插入算法，查找不成功時(shí)插入e，并返回true；查找成功返回falseboolInsertHash(HashTable&ht,ElemTypee){

intp;

if(SearchHash(ht,e.key,p)==true)

returnfalse;

//表中已有與e有相同關(guān)鍵字的記錄

else{

ht.elem[p]=e;

//插入記錄e

ht.count++;

returntrue;

}}7.5哈希查找哈希查找的算法實(shí)現(xiàn)基于開放地址法的算法實(shí)現(xiàn)intHash(intkey){

//哈希函數(shù)，除留余數(shù)法

returnkey%MaxSize;}

intNextPos(intp){

//線性探測(cè)求一個(gè)地址

return(p+1)%MaxSize;}7.5哈希查找哈希查找的算法實(shí)現(xiàn)基于鏈地址法的算法實(shí)現(xiàn)constintMaxSize=101;

//最大的表長(zhǎng)，除留余數(shù)法的除數(shù)

structNode{

//鏈表結(jié)點(diǎn)結(jié)構(gòu)

intkey;

//關(guān)鍵字

Node*next;

//指針域

Node(intk,Node*p){

//構(gòu)造函數(shù)

key=k,next=p;

}};7.5哈希查找哈希查找的算法實(shí)現(xiàn)基于鏈地址法的算法實(shí)現(xiàn)structHTable{

//表結(jié)構(gòu)

Node**elem;

//存放哈希表（指針數(shù)組）首地址

intlength;

//元素個(gè)數(shù)

HTable(intn=MaxSize){

//構(gòu)造函數(shù)

length=0;

elem=newNode*[n];

for(inti=0;i<n;i++)elem[i]=NULL;

}};intHash(intkey){

//哈希函數(shù)，除留余數(shù)法

returnkey%MaxSize;}7.5哈希查找哈希查找的算法實(shí)現(xiàn)基于鏈地址法的算法實(shí)現(xiàn)//鏈地址法的查找算法，在哈希表ht中查找k，若查找成功，指針p指向所查記錄，//否則，p為空指針boolSearchHash(HTableht,intk,Node*&p){

intq=Hash(k);

//利用Hash函數(shù)求得哈希地址

p=ht.elem[q];

//p指向下標(biāo)q對(duì)應(yīng)的鏈表

while(p!=NULL&&p->key!=k){

//在p所指鏈表中查找k

p=p->next;

}

if(p!=NULL)returntrue;

elsereturnfalse;}7.5哈希查找哈希查找的算法實(shí)現(xiàn)基于鏈地址法的算法實(shí)現(xiàn)//鏈地址法的插入算法，在哈希表ht中若不存在關(guān)鍵字k，則插入boolInsertHash(HTable&ht,intk){

intp=Hash(k);

//利用Hash函數(shù)求得哈希地址

if(ht.elem[p]==NULL){

//在頭部插入

ht.elem[p]=newNode(k,NULL);returntrue;

}

Node*p1=ht.elem[p],*p2;

while(p1!=NULL){

//使p2指向鏈表的最后一個(gè)結(jié)點(diǎn)

if(p1->key==k)returnfalse;

p2=p1,p1=p1->next;

}

p2->next=newNode(k,NULL);//插在鏈表尾部

returntrue;}7.6STL之set與mapSTL中查找相關(guān)的容器集合set、映射map、多重集合multiset、多重映射multimapset、multiset的頭文件為setmap、multimap的頭文件為map。STL之set和map均默認(rèn)按關(guān)鍵字升序排序。STL之setSTL之set中的元素具有唯一性。STL之set的常用方法如表7-1所示。7.6STL之set與mapSTL之set7.6STL之set與mapSTL之set通過set_union、set_intersection、set_difference等系統(tǒng)函數(shù)（頭文件為algorithm），可以方便的實(shí)現(xiàn)集合的并、交、差等操作。#include<iostream>#include<set>#include<algorithm>usingnamespacestd;voidOutputSet(set<int>st);intmain(){

inti,t,m,n;

set<int>Sa,Sb,Su,Si,Sd;

cin>>m>>n;

for(i=0;i<m;i++){

//建立集合Sa

cin>>t;

Sa.insert(t);

}7.6STL之set與mapSTL之set

for(i=0;i<n;i++){

//建立集合Sb

cin>>t;

Sb.insert(t);

}

//set_intersection求交集，set_union求并集、set_difference求差集

set_intersection(Sa.begin(),Sa.end(),Sb.begin(),Sb.end(),

inserter(Si,Si.begin()));

OutputSet(Si);

//輸出集合中的元素

set_union(Sa.begin(),Sa.end(),Sb.begin(),Sb.end(),

inserter(Su,Su.begin()));

OutputSet(Su);

set_difference(Sa.begin(),Sa.end(),Sb.begin(),Sb.end(),

inserter(Sd,Sd.begin()));

OutputSet(Sd);

return0;}7.6STL之set與mapSTL之setvoidOutputSet(set<int>st){

//遍歷集合

set<int>::iteratorit;

for(it=st.begin();it!=st.end();it++){

if(it!=st.begin())cout<<"";

cout<<*it;

}

cout<<endl;}7.6STL之set與mapSTL之mapSTL之map建立“關(guān)鍵字-值”對(duì)（屬于命名空間std中定義的pair結(jié)構(gòu)體類型，成員first對(duì)應(yīng)“關(guān)鍵字”，成員second對(duì)應(yīng)“值”）。map能夠根據(jù)關(guān)鍵字快速查找記錄，查找的時(shí)間復(fù)雜度基本是O(log2n)，對(duì)于1000個(gè)記錄，最多查找10次，對(duì)于1000000個(gè)記錄，最多查找20次。STL之map默認(rèn)按關(guān)鍵字升序排序。map的常用方法如表7-2所示。7.6STL之set與mapSTL之map7.6STL之set與mapSTL之mapmap的簡(jiǎn)單使用代碼示例#include<iostream>#include<map>usingnamespacestd;intmain(){

map<string,int>myMap;

//定義map

map<string,int>::iteratorit;

//定義遍歷map的迭代器

strings,res="";

while(cin>>s){

myMap[s]++;

//把s插入map中，值m[s]增1

}

//遍歷map

for(it=myMap.begin();it!=myMap.end();it++){

cout<<it->first<<""<<it->second<<endl;

}7.6STL之set與mapSTL之map

//在map中找值最大的關(guān)鍵字，輸出該關(guān)鍵字及其值

intmax=0;

for(it=myMap.begin();it!=myMap.end();it++){

if(it->second>max){

res=it->first;

max=it->second;

}

}

cout<<res<<""<<max<<endl;

return0;}7.7在線題目求解例7.7.1判斷是否二叉排序樹

根據(jù)帶虛結(jié)點(diǎn)的先序序列建立二叉樹，然后判斷其是否為二叉排序樹。輸入:

測(cè)試數(shù)據(jù)有多組，處理到文件尾。每組測(cè)試數(shù)據(jù)在一行中輸入一個(gè)數(shù)字字符串（不含'0'且長(zhǎng)度不超過20），表示二叉樹的先序遍歷序列，其中字符'*'表示虛結(jié)點(diǎn)（對(duì)應(yīng)的子樹為空）。輸出:

對(duì)于每組測(cè)試，輸出是否二叉排序樹的判定結(jié)果，是輸出“YES”，否則輸出“NO”。引號(hào)不必輸出。輸入樣例:56**87***54**87***輸出樣例:NOYES解析：用帶虛結(jié)點(diǎn)的先序遍歷序列創(chuàng)建二叉樹可以使用5.4節(jié)的CreateBiTree算法，判斷是否二叉排序樹可以利用其特性—二叉排序樹的中序遍歷序列是一個(gè)升序序列。7.7在線題目求解例7.7.1判斷是否二叉排序樹//用帶虛結(jié)點(diǎn)的先序遍歷序列創(chuàng)建二叉樹BiTNode*CreateBiTree(string&s){

if(s[0]=='*'){

s=s.substr(1);

returnNULL;

}

BiTNode*p=newBiTNode;

p->data=s[0];//處理根節(jié)點(diǎn)

s=s.substr(1);

p->lchild=CreateBiTree(s);//處理左子樹

p->rchild=CreateBiTree(s);

//處理右子樹

returnp;}structBiTNode{//結(jié)點(diǎn)結(jié)構(gòu)

chardata;

BiTNode*lchild,*rchild;};7.7在線題目求解例7.7.1判斷是否二叉排序樹boolInOrderCheck(BiTNode*T,int&x){

//中序遍歷

if(T==NULL)returntrue;

InOrderCheck(T->lchild,x);

if(T->data<=x)returnfalse;

x=T->data;

InOrderCheck(T->rchild,x);

returntrue;}7.7在線題目求解例7.7.1判斷是否二叉排序樹#include<iostream>#include<string>usingnamespacestd;intmain(){

strings;

while(cin>>s){

BiTNode*root=CreateBiTree(s);

intt=0;

boolflag=InOrderCheck(root,t);

if(flag==true)cout<<"YES"<<endl;

elsecout<<"NO"<<endl;

}

return0;}7.7在線題目求解例7.7.2二叉排序樹的遍歷

建立二叉排序樹，先序遍歷之，并按升序輸出該二叉排序樹中大于給定值x的所有結(jié)點(diǎn)的數(shù)據(jù)。輸入:

測(cè)試數(shù)據(jù)有多組，處理到文件尾。每組測(cè)試數(shù)據(jù)第一行輸入兩個(gè)整數(shù)n（1<n<100）和x，第二行輸入n個(gè)整數(shù)。輸出:

對(duì)于每組測(cè)試，先在第一行輸出所建立二叉排序樹的先序遍歷序列，再在第二行按升序輸出該二叉排序樹中大于給定值x的結(jié)點(diǎn)數(shù)據(jù)（測(cè)試數(shù)據(jù)保證至少存在一個(gè)結(jié)果），每?jī)蓚€(gè)數(shù)據(jù)之間留一個(gè)空格。x7.7在線題目求解例7.7.2二叉排序樹的遍歷輸入樣例:45587410312345678910輸出樣例:5487781234567891045678910解析：調(diào)用二叉排序樹插入算法Insert創(chuàng)建二叉排序樹，然后先序遍歷之。因“二叉排序樹的中序遍歷序列是一個(gè)升序序列”，故可在中序遍歷過程中判斷結(jié)點(diǎn)數(shù)據(jù)是否大于x，是則輸出。7.7在線題目求解例7.7.2二叉排序樹的遍歷#include<iostream>usingnamespacestd;

structBstNode{

intdata;

BstNode*lchild,*rchild;

BstNode(intd,BstNode*l,BstNode*r){

data=d,lchild=l,rchild=r;

}

BstNode(){}};7.7在線題目求解例7.7.2二叉排序樹的遍歷intcnt,x;//中序遍歷二叉排序樹，輸出大于x的數(shù)據(jù)voidInorder(BstNode*T){

if(T==NULL)return;

Inorder(T->lchild);

if(T->data>x){

cnt++;

if(cnt>1)cout<<"";

cout<<T->data;

}

Inorder(T->rchild);}7.7在線題目求解例7.7.2二叉排序樹的遍歷voidInsert(BstNode*&T,inte){

/