數(shù)據(jù)結(jié)構(gòu) 課件 第10章 查找

第10章查找總體要求：熟悉查找的定義和基本概念熟練掌握靜態(tài)查找、動態(tài)查找、哈希查找的算法核心技能點：各種查找方法應(yīng)用于實際問題的能力擴展技能點：各種查找方法C語言環(huán)境下的實現(xiàn)相關(guān)知識點：C語言數(shù)組的知識C語言結(jié)構(gòu)體的知識C語言函數(shù)的知識二叉樹的知識學(xué)習(xí)重點：靜態(tài)查找的折半查找和分塊查找動態(tài)查找的二叉樹查找哈希查找1查找（Searching）又稱為檢索，是指在某種數(shù)據(jù)結(jié)構(gòu)中找出滿足給定條件的結(jié)點。若找到滿足給定條件的結(jié)點，則查找成功；否則查找失敗。查找是數(shù)據(jù)結(jié)構(gòu)中很常用的基本操作，例如，在學(xué)生成績表中查找某位學(xué)生的成績；在圖書館的書目文件中查找某編號的圖書；在電話號碼簿中查找某用戶的電話號碼。選擇不同的數(shù)據(jù)結(jié)構(gòu)，查找的實現(xiàn)方法將不同，查找算法的好壞對查找過程影響很大。下面分別介紹。2第10章查找10.1靜態(tài)查找表10.1.1無序順序表的查找 順序查找(SequentialSearch)又稱為線性查找，是一種最簡單的查找方法。查找過程為：從線性表的一端開始，順序掃描線性表，依次將掃描到的結(jié)點關(guān)鍵字和給定值k相比較，若當(dāng)前掃描到的結(jié)點關(guān)鍵字與k相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于k的結(jié)點，則查找失敗。例10.1在關(guān)鍵字序列為{1，5，9，7，12，11，10，8，6，2，3}的線性表中查找關(guān)鍵字為8的元素。順序查找過程如圖10.1所示。34順序查找的線性表，用第2章線性表順序存儲的定義如下：#defineMaxsize100/*MaxSize線性表可能達到的最大長度*/TypedefintKeyType;typedefstruct{KeyTypekey;}DataType;/*根據(jù)需要還可以加入其它數(shù)據(jù)成員*/typedefstruct{DataTypelist[MaxSize]; intsize;}SeqList;

這里的KeyType和DataType可以是任何相應(yīng)的數(shù)據(jù)類型，如int，float及char等。5

順序查找的函數(shù)如下，其功能在線性表r中順序查找關(guān)鍵字為k的結(jié)點，若找到了，返回其位置i；若找不到，返回-1：/*順序查找*/intSeqSearch(SeqListS,DataTypex){inti=0; while(i<S.size&&S.list[i].key!=x.key)i++; if(S.list[i].key==x.key)returni; elsereturn-1;}voidmain(void){SeqListtest={{710,342,45,686,6,841,429,134,68,264},10}; DataTypex={687}; inti; if((i=SeqSearch(test,x))!=-1) printf("該數(shù)據(jù)元素位置為%d",i); elseprintf("查找失敗");}6算法分析:對于含有n=S.size個結(jié)點的線性表，結(jié)點的查找在等概率的前提下，即Pi=1/n成功的查找，平均查找長度為

7順序查找和我們后面將要討論到的其它查找算法相比，其缺點是平均查找長度較大，特別是當(dāng)n很大時，查找效率較低。速度較慢，平均查找長度為O（n）。然而，它有很大的優(yōu)點，算法簡單且適應(yīng)面廣。它對表的結(jié)構(gòu)無任何要求，無論記錄是否按關(guān)鍵字有序(若表中所有記錄的關(guān)鍵字滿足下列關(guān)系：r[i].key≤r[i+1].keyi=0,1,……,n-1則稱表中記錄按關(guān)鍵字有序)均可應(yīng)用。810.1.2有序順序表的查找以有序表表示靜態(tài)查找表時，查找函數(shù)可用折半查找來實現(xiàn)，折半查找(BinarySearch)的查找過程是：先確定待查記錄所在的范圍(區(qū)間)，然后逐步縮小范圍直到找到或找不到該記錄為止。也就是要求線性表中的結(jié)點必須已按關(guān)鍵字值的遞增或遞減順序排列。它首先把要查找紀錄的關(guān)鍵字x.key與中間位置結(jié)點的關(guān)鍵字相比較，這個中間結(jié)點把線性表分成了兩個子表，若比較結(jié)果相等則查找完成；若不相等，再根據(jù)x.key與該中間結(jié)點關(guān)鍵字的比較結(jié)果確定下一步查找哪個子表，這樣遞歸進行下去，直到找到滿足條件的結(jié)點或者該線性表中沒有這樣的結(jié)點。9

例10.2在關(guān)鍵字有序序列{3，5，6，8，9，12，17，23，30，35，39，42}中采用折半查找法查找關(guān)鍵字為8的元素。 指針low和high分別指示待查元素所在范圍的下界和上界，指針mid指示區(qū)間的中間位置，即mid=(low+high)/2。在此例中，low和high的初值分別為0和11，即r[0~11]為待查范圍。 折半查找過程如圖10.2所示。1011圖10.2折半查找過程

折半查找的函數(shù)如下，其功能是在線性表S中二分查找關(guān)鍵字為x.key的結(jié)點，查找到了，返回其位置i；若找不到返回-1。/*折半查找*/intBinarySearch(SeqListS,DataTypex){ intlow=0,high=S.size-1;/*確定初始查找區(qū)間上下界*/ intmid; while(low<=high) {mid=(low+high)/2;/*確定初始查找區(qū)間中心位置*/ if(S.list[mid].key==x.key)returnmid;/*查找成功*/ elseif(S.list[mid].key<x.key)low=mid+1; elseif(S.list[mid].key>x.key)high=mid-1; } return-1;/*查找失敗*/}voidmain(void){ SeqListtest={{2,4,6,8,10,12},6}; DataTypex={6}; inti; if((i=BinarySearch(test,x))!=-1) printf("該數(shù)據(jù)元素位置為%d",i); elseprintf("查找失敗");}12算法分析：折半查找函數(shù)恰好是一條從判定樹的根到被查找結(jié)點的一條路徑，而比較的次數(shù)恰好是樹深。借助于二叉判定樹很容易求得折半查找的平均查找長度。設(shè)表長為n=S.size，樹深h=lb(n+1)，則平均查找長度為：13因此，折半查找法的平均查找長度為0（lbn），比順序查找速度快，與順序查找方法相比，折半查找的效率比順序查找高，但折半查找只能適用于有序表，需要對n個元素預(yù)先進行排序，僅限于順序存儲結(jié)構(gòu)（對線性鏈表無法進行折半查找）。10.1.3索引順序表的查找分塊查找又稱為索引順序查找，是順序查找的一種改進，其性能介于順序查找和折半查找之間。分塊查找把線性表分成若干塊，每一塊中的元素存儲順序是任意的，但塊與塊之間必須按關(guān)鍵字大小排序。即前一塊中的最大關(guān)鍵字小于(或大于)后一塊中的最小(或最大)關(guān)鍵字值。另外還需要建立一個索引表，索引表中的一項對應(yīng)線性表中的一塊，索引項由關(guān)鍵字域和鏈域組成，關(guān)鍵字域存放相應(yīng)塊的最大關(guān)鍵字，鏈域存放指向本塊第一個結(jié)點的指針。索引表按關(guān)鍵字值遞增(或遞減)順序排列。分塊查找的查找函數(shù)分為兩步進行:首先確定待查找的結(jié)點屬于哪一塊，即查找其所在的塊；然后在塊內(nèi)查找要查的結(jié)點。由于索引表是遞增有序的，采用折半查找時，塊內(nèi)元素個數(shù)較少，采用順序法在塊內(nèi)查找，不會對執(zhí)行速度有太大的影響。14例10.3

對于關(guān)鍵字序列為{8，20，13，17，40，42，45，32，49，58，50，52，67，70，78，80}的線性表采用分塊查找法查找關(guān)鍵字為50的元素。假定分塊索引和索引表如圖8.3(b)所示。15圖10.3塊表與索引

分塊查找過程是:先在索引表中采用二分查找法查找關(guān)鍵字50所在的塊，即在第3塊中，有4個元素，其關(guān)鍵字分別為49，58，50，52，在其中按順序查找法進行查找，找到第3個元素即總序號為11的元素是關(guān)鍵字為50的元素。索引表的定義如下:#defineMax10/*索引表最大長度*/TypedefintKeyType;typedefstruct{KeyTypekey; intlow，high;}indexItem;/*索引表元素*/typedefstruct{indexItemIndTable[Max];/*索引表*/IntIndLength;/*索引表長度*/}Index;/*索引表類型*/16分塊查找的函數(shù)省略，其功能是在線性表S中分塊查找x結(jié)點，若找到了，返回其位置i；若不找到，返回-1。 算法分析:分塊查找實際上進行了兩次查找，故整個算法的平均查找長度是兩次查找的平均查找長度之和。 假設(shè)有n個結(jié)點，分成kug塊，每塊有m個結(jié)點，即kug=n/m,每塊的查找概率為1/kug，塊內(nèi)每個結(jié)點的查找概率為1/m。

ASL≈lb(kug+1)-1+(m+1)/2 ≈lb(n/m+1)+m/2

分塊查找的優(yōu)點是:在線性表中插入或刪除一個元素時，只要找到相應(yīng)的塊，然后在該塊內(nèi)進行插入或刪除即可。由于塊內(nèi)元素個數(shù)相對較少，而且是任意存放的，所以插入或刪除比較容易，不需要移動大量的元素。1710.2動態(tài)查找表10.2.1二叉排序樹 二叉排序樹(BinarySortTree又記為BST)或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹：（1）若它的左子樹非空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；（2）若它的右子樹非空，則右子樹上所有結(jié)點的值均不小于它的根結(jié)點的值；（3）它的左、右子樹本身又各是一棵二叉排序樹。圖10.4所示的就是一棵二叉排序樹。1819圖10.4二叉排序樹示例

二叉排序樹又稱二叉查找樹，由上述定義的結(jié)構(gòu)特點，再結(jié)合圖10.4可以發(fā)現(xiàn)二叉樹的重要性質(zhì)：它的查找過程和次優(yōu)二叉樹類似，即當(dāng)二叉排序樹不空時，首先將給定值和根結(jié)點的關(guān)鍵字比較，若相等，則查找成功，否則將依據(jù)給定值和根結(jié)點的關(guān)鍵字之間的大小關(guān)系，分別在左子樹或右子樹上繼續(xù)進行查找。二叉排序樹用二叉鏈表來存儲，說明形式如下：typedefintKeyType;typedefstruct{ KeyTypekey;}DataType;typedefstructnode{ DataTypedata; structnode*leftChild; structnode*rightChild;}BiTreeNode;20二叉樹的構(gòu)造是通過依次輸入數(shù)據(jù)元素，并把它們插入到二叉樹的適當(dāng)位置上。具體的過程是：每讀入一個元素，建立一個新結(jié)點，若二叉排序樹非空，則將新結(jié)點的值與根結(jié)點的值相比較，如果小于根結(jié)點的值，則插入到左子樹中，否則插入到右子樹中；若二叉排序樹為空，則新結(jié)點作為二叉排序樹的根結(jié)點。21例如在圖10.4上插入關(guān)鍵字為55的過程:由于此時二叉樹非空，則將55與根結(jié)點50相比較，因為55>50；則應(yīng)將55插入到50的右子樹上，又因為50的右子樹非空，將55與右子樹的根70比較，固55<70，則55應(yīng)插入到70的左子樹中，依次類推，當(dāng)最后因55<65，且65的左子樹為空，將55作為65的左子樹插入到樹中。22整棵樹的構(gòu)造算法描述如下。BiTreeNode*BSTCreat(DataTypea[],intn)/*輸入一個數(shù)據(jù)元素序列，建立一棵二叉排序樹，endmark為輸入結(jié)束標志*/{inti;BiTreeNode*t;t=NULL;for(i=0;i<n;i++)BSTInsert(&t,a[i]);/*新結(jié)點插入*/return(t);}23例10.4

已知一關(guān)鍵字序列為{402552102880}，則問生成的二叉排序樹？如圖8.5所示:24圖10.5二叉排序樹的構(gòu)造過程由此可以看出：二叉排序樹的形態(tài)完全由一個輸入序列決定，一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列。若輸入序列為10，25，28，40，52，80則所對應(yīng)的二叉排序樹為單支樹。見圖10.625圖10.6單支二叉排序樹

此外，從圖10.5的二叉排序樹構(gòu)造過程還可以看出，每次插入的新結(jié)點都是作二叉排序樹的葉子結(jié)點，在插入過程中不需要移動其它元素，只需改變某個結(jié)點的指針由空變?yōu)榉强占纯?，所以二叉排序樹結(jié)構(gòu)適合于元素的經(jīng)常插入，那么如何在二叉排序樹上刪除一個結(jié)點呢?在二叉排序樹中刪除一個結(jié)點，不能把以該結(jié)點為根的子樹都有刪去，只能刪除這個結(jié)點并仍就保證二叉排序樹的特性，也就是說刪除二叉排序樹上一個結(jié)點相當(dāng)于刪除有序序列中的一個元素。26

假設(shè)在二叉排序樹上被刪除結(jié)點為p(p指針指向被刪除結(jié)點)，f為其雙親結(jié)點，則刪除結(jié)點P的過程分三種情況討論：（1）若P結(jié)點為葉子結(jié)點，即p->leftChild及P->rightChild均為空，則由于刪去葉子結(jié)點后不破壞整棵樹的結(jié)構(gòu)，因此，只需修改P結(jié)點的雙親結(jié)點指針。即：

f->leftChild(或f->rightChild)=NULL；（2）若P結(jié)點只有左子樹或者只有右子樹，此時只需將P的左子樹或右子樹直接成為雙親f的左子樹(或右子樹)。即

f->leftChild(或f->rightChild)=p->leftChild； 或f->leftChild(或f->rightChild)=p->rightChild；（3）若p結(jié)點的左，右子樹均不空，此時不能象上面那樣簡單處理，刪除p結(jié)點時應(yīng)考慮將p的左子樹、右子樹連接到適當(dāng)?shù)奈恢茫⒈ＷC二叉排序樹的特牲。方法是令p的中序前趨結(jié)點s結(jié)點代替p結(jié)點，然后刪除s結(jié)點。27查找p結(jié)點中序前趨結(jié)點的操作為：q=p；s=p->leftChild；whiles->rchild!=NULLdo{q=s；s=s->rightChild；}

因為二叉排序樹可以看成是一個有序表，在二叉排序樹中左子樹上所有結(jié)點的關(guān)鍵字均小于根結(jié)點的關(guān)鍵字，右子樹上所有結(jié)點的關(guān)鍵字均大于或等于根結(jié)點的關(guān)鍵字，所以在二叉排序樹上進行查找與折半查找類似。 查找過程為：若二叉排序樹非空，將給定值與根結(jié)點值相比較，若相等，則查找成功；若不等，則當(dāng)根結(jié)點值大于給定值時，到根的左子樹中查找，否則在根的右子樹中查找。28/*BST查找算法*/intBSTSearch(BiTreeNode*t,DataTypex)/*在t所指的二叉排序樹中查找x記錄*/{ BiTreeNode*p; if(t!=NULL) {p=t; while(p!=NULL) {if(p->data.key==x.key)return1; if(x.key>p->data.key)p=p->rightChild; elsep=p->leftChild; } }return0;}29可見，在二叉排序樹上查找其關(guān)鍵字等于給定值的結(jié)點的過程，恰是走了一條從根結(jié)點到該結(jié)點的路徑的過程，和給定值比較的關(guān)鍵字個數(shù)等于路徑長度加1。二叉排序數(shù)的平均查找長度為:而圖10.4同樣結(jié)點的單支的二叉排序樹，平均查找長度為：30

最壞的情況下，二叉排序樹變?yōu)閱沃?，最好的情況是二叉排序樹比較均勻。二叉排序樹的性能與折半查找相差不大，但二叉排序樹對于結(jié)點的插入和刪除十分方便，因此對于經(jīng)常進行插入、刪除和查找運算的表，應(yīng)采用二叉排序樹。10.2.2平衡二叉樹

平衡二叉樹(BalancedBinaryTree)又稱AVL樹。它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。二叉樹上結(jié)點的平衡因子定義為該結(jié)點的左子樹的深度減去它的右子樹的深度。因此，平衡二叉樹上所有結(jié)點的平衡因子為-1、0或1中的一個值，只要二叉樹上有一個結(jié)點的平衡因子的絕對值大于1，則該二叉樹就是不平衡的。圖10.7（a）、(b)分別給出了二棵平衡二叉樹和二棵不平衡二叉樹，樹中結(jié)點內(nèi)的數(shù)字是該結(jié)點的平衡因子。3132

圖10.7平衡二叉樹和不平衡二叉樹（a）平衡二叉樹（b）不平衡二叉樹由上節(jié)得知，二叉排序樹形態(tài)均勻時查找性能才能最好，而形態(tài)為單支樹時其查找性能與順序查找相同，因此，我們希望在初始時及在有元素變動時的二叉排序樹都是平衡二叉樹，那么如何使構(gòu)成的二叉排序樹成為平衡樹呢？ 例如，輸入關(guān)鍵字序列為（15，20，35，80，50），構(gòu)造一棵二叉排序樹。⑴輸入15，15作為根結(jié)點，見圖10.8(a)。⑵輸入20，20作為15的右子樹，見圖10.8(b)，此時仍為平衡樹。⑶輸入35，35作為20的右子樹，見圖10.8(c)，此時結(jié)點15的平衡因子是-2，該樹為非平衡樹，必須進行調(diào)整。顯然要進行逆時針右轉(zhuǎn)，該20作為根結(jié)點，見圖10.8(d)，此時又是一棵平衡二叉樹。⑷輸入80，80作為35的右子樹，見圖10.8(e)，此時樹為一棵平衡二叉樹。⑸輸入50，50作為80的左子樹，見圖10.8(f)，由于樹中又出現(xiàn)有絕對值大于1的平衡因子，所以必須進行調(diào)整。先將50作為35的右子樹，80作為50的右子樹，見圖10.8（g），然后令50作為20的右子樹，35和80分別作50的左、右子樹，見圖10.8(h)。3334圖10.8平衡二叉樹的構(gòu)造示例可見保持二叉樹為平衡二叉樹的基本思想是：每當(dāng)對二叉排序樹插入一個結(jié)點時，首先檢查是否因插入而破壞了樹的平衡，若是，則找出其中最小的不平衡樹，在保持二叉排序樹的特性情況下，調(diào)整最小不平衡子樹中結(jié)點之間的關(guān)系，以達到新的平衡。離插入結(jié)點最近、且以平衡因子的絕對值大于1的結(jié)點作根的子樹被稱為最小平衡樹。失去平衡后調(diào)整規(guī)律可歸納為四種情況：①LL型平衡旋轉(zhuǎn)；②RR型平衡旋轉(zhuǎn)；③LR型平衡旋轉(zhuǎn)；④RL型平衡旋轉(zhuǎn)。平衡二叉排序樹上的查找與二叉排序樹中的查找相同，由于平衡二叉樹的的形態(tài)不再變?yōu)閱沃涞那樾?，且比較均勻，故在AVL樹上查找的時間復(fù)雜度為O(lbn)。由于在動態(tài)平衡的過程中所進行的調(diào)整操作仍需花費不少時間，因此AVL樹的使用要視具體情況而定。3510.3哈希表及其查找10.3.1哈希表與哈希函數(shù)在前面討論的各種結(jié)構(gòu)（線性表、樹等）中，記錄在結(jié)構(gòu)中的相對位置是隨機的，和記錄的關(guān)鍵字之間不存在確定的關(guān)系。因此，在結(jié)構(gòu)中查找記錄時需進行一系列和關(guān)鍵字的比較。這一類查找方法建立在“比較”的基礎(chǔ)上。在順序查找時，比較的結(jié)果為“=”與“≠”兩種可能；在折半查找、二叉排序樹查找時，比較的結(jié)果為“<”、“=”和“>“三種可能。查找的效率依賴于查找過程中所進行的比較次數(shù)。36理想的情況是希望不經(jīng)過任何比較，一次存取便能得到所查記錄，那就必須在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系H，使每個關(guān)鍵字和結(jié)構(gòu)中一個惟一的存儲位置相對應(yīng)。因而在查找時，只要根據(jù)這個對應(yīng)關(guān)系H找到給定值k的像H(k)。若結(jié)構(gòu)中存在關(guān)鍵字和k相等的記錄，則必定在H(k)的存儲位置上，由此，不需要進行比較便可直接取得所查記錄。在此，我們稱這個對應(yīng)關(guān)系H為哈希（Hash）函數(shù)，按這個理想建立的表為哈希表。37舉一個哈希表的最簡單的例子。假設(shè)要建立一張全國30個地區(qū)的各民族人口統(tǒng)計表，每個地區(qū)為一個記錄，記錄的各數(shù)據(jù)項為：編號地區(qū)名總?cè)丝跐h族回族……38顯然，可以用一個一維數(shù)組c[30]來存放這張表，其中c[i]是編號為i的地區(qū)的人口情況。編號i便為記錄的關(guān)鍵字，由它唯一確定記錄的存儲位置c[i]。例如：假設(shè)北京市的編號為1，則若要查看北京市的各民族人口，只要取出c[1]的記錄即可。假如把這個數(shù)組看成是哈希表，則哈希函數(shù)H(key)=key。然而很多情況下的哈希函數(shù)并不如此簡單。不能簡單地取哈希函數(shù)H(key)=key，而是首先要將它們轉(zhuǎn)化為數(shù)字，有時還要作些簡單的處理。例如有這樣的哈希函數(shù)：取關(guān)鍵字中第一個字母在字母表中的序號作為哈希函數(shù)。例如：BEIJING的哈希函數(shù)值為字母‘B’在字母表中的序號，等于2。TIANJIN的哈希函數(shù)數(shù)值為字母“T”在字母表中的序號，等于‘20’。KeyBEIJING（北京）TIANJIN（天津）SHANGHAI（上海）HEBEI（河北）HENAN（河南）SHANDONG（山東）SHANXI（山西）SICHAN（四川）F(key)022019080819191939表10.1簡單的哈希函數(shù)示例從這個例子可見：⑴哈希函數(shù)是一個映象，因此哈希函數(shù)的給定很靈活，只要使得任何關(guān)鍵字由此所得的哈希函數(shù)值都落在表長允許范圍之內(nèi)即可；⑵對不同的關(guān)鍵字可能得到同一哈希地址，即key1≠key2，而H(key1)=H(key2)，這種現(xiàn)象稱為沖突（Collision）。綜上所述，可如下描述哈希表：根據(jù)設(shè)定的哈希函數(shù)H(key)和處理沖突的方法將一組關(guān)鍵字映象到一個有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“象”作為記錄在表中的存儲位置，這種表便稱為哈希表，這一映象過程稱為哈希表或散列，所得存儲位置稱哈希地址或散列地址。下面分別就哈希函數(shù)和處理沖突的方法進行討論。4010.3.2構(gòu)造哈希函數(shù)的常用方法構(gòu)造哈希函數(shù)的方法很多，如何構(gòu)造一個“好”的哈希函數(shù)是有很強的技術(shù)性和實踐性的問題。這里的“好”指的是哈希函數(shù)的構(gòu)造比較簡單，并且用此哈希函數(shù)產(chǎn)生的映象所發(fā)生沖突的可能性最小，換向話說，一個好的哈希函數(shù)能將給定的數(shù)據(jù)集合均勻地映射到所給定的地址區(qū)間中。我們知道，關(guān)鍵字可以惟一地對應(yīng)一個記錄，因此，在構(gòu)造哈希函數(shù)時，應(yīng)盡可能地使關(guān)鍵字的各個成分都對它的哈希地址產(chǎn)生影響。下面介紹幾種常用的構(gòu)造哈希函數(shù)的方法。41直接地址法

對于關(guān)鍵字是整數(shù)類型的數(shù)據(jù)，直接地址法的哈希函數(shù)H直接利用關(guān)鍵字求得哈希地址。

H(ki)=aki+b(a，b為常量)

在使用時，為了使哈希地址與存儲空間吻合，可以調(diào)整a和b。例如，取H(ki)=ki+10.

直接地址法的特點是：哈希函數(shù)簡單，并且對于不同的關(guān)鍵字不會產(chǎn)生沖突。但在實際問題中，由于關(guān)鍵字集中的元素很少是連續(xù)的，用該方法產(chǎn)生的哈希表會造成空間的大量浪費。因此，這種方法很少使用。42數(shù)字分析法 數(shù)字分析法是假設(shè)有一組關(guān)鍵字，每個關(guān)鍵字由幾位數(shù)字組成，如k1k2k3…kn。數(shù)字分析法是從中提取數(shù)字分布比較均勻的若干位作為哈希地址。 例如，對于關(guān)鍵字k1到k8的序列{100011211，100011322，100011413，100011556，100011613，100011756，100011822，100011911}，可以取第6位和第7位作為哈希地址，即：H（k1）=12，H（k2）=13，H（k3）=14，H（k4）=15，H（k5）=16，H（k6）=17，H（k7）=18，H（k8）=19。43平方取中法 平方取中法是取關(guān)鍵字平方的中間幾位作為散列地址的方法，具體取多少位視實際情況而定。即：

H(Ki)=“Ki的平方的中間幾位” 這也是一種常用的較好的設(shè)計哈希函數(shù)的方法。關(guān)鍵字平方后使得它的中間幾位和組成關(guān)鍵字的多位值均有關(guān)，從而使哈希地址的分布更為均勻，減少了發(fā)生沖突的可能性。44

折疊法 折疊法是首先把關(guān)鍵字分割成位數(shù)相同的幾段（最后一段的位數(shù)可少一些），段的位數(shù)取決于哈希地址的位數(shù)，由實際情況而定，然后將它們的疊加和（舍去最高進位）作為哈希地址的方法。 與平方取中法類似，折疊法也使得關(guān)鍵字的各位值都對哈希地址產(chǎn)生影響。45除留余數(shù)法 除留余數(shù)法是用關(guān)鍵字ki除以一個合適的不大于哈希表長度的正整數(shù)p，所得余數(shù)作為哈希地址的方法。對應(yīng)的哈希函數(shù)H（

ki）為：

H(ki)=ki%p

這里的%表示求余數(shù)運算，用該方法產(chǎn)生的哈希函數(shù)的好壞取決于p值的選取。實踐證明，當(dāng)p取小于哈希表長的最大質(zhì)數(shù)時，產(chǎn)生的哈希函數(shù)較好。 除留余數(shù)法是一種簡單而行之有效的構(gòu)造哈希函數(shù)的方法。4610.3.3解決沖突的主要方法

正如前面所講過的,在實際問題中,無論怎樣構(gòu)造哈希函數(shù)，沖突是不可避免的。通常用的處理沖突的方法有下列幾種。1.開放地址法 開放地址法又分為線性探測再散列、二次探測再散列和偽隨機探測再散列。 假設(shè)哈希表空間為T[M]，哈希函數(shù)為H(ki)，dj為第次求得的地址。 線性探測再散列解決沖突求“下一個”地址公式為：

d1=H(ki) dj=(dj-1+j)%M（j=2,3…） 二次探測再散列解決沖突求“下一個”地址公式為：47d1=H(ki)dj=(dj-1+(-1)jj2)%M（j=2,3…）隨機探測再散列解決沖突求“下一次”地址公式為：d1=H(ki)dj=(dj-1+R)%M其中，R為隨機數(shù)序列。例10.5使用的哈希函數(shù)為：H(ki)=3ki%11并采用開放地址法處理沖突，其求下一個地址的函數(shù)為：d1=H(Ki)dj=(dj-1+(7ki%10)+1)%11(j=2,3,……)48試在0～10的散列地址空間中對關(guān)鍵字序列（22，41，53，46，30，13，01，67）構(gòu)造哈希表，求等概率情況下查找成功的平均查找長度，并設(shè)計構(gòu)造哈希表的完整函數(shù)。 本題的哈希表構(gòu)造過程如下： ⑴H（22）=3*22%11=0 ⑵H（41）=3*41%11=2 ⑶H（53）=3*53%11=5 ⑷H（46）=3*46%11=6 ⑸H（30）=3*30%11=2（沖突）

d1=H(30)=2 d2=(2+(7*30%10)+1)%11=3

⑹H(13)=3*13%11=6（沖突）

d1=H(13)=6 d2=(6+(7*13%10)+1)%11=849⑺H（1）=3*1%11=3（沖突）

d1=H(1)=3 d2=(3+(1*7%10)+1)%11=0(沖突) d3=(0+(1*7%10)+1)%11=8(沖突) d4=(8+(1*7%10)+1)%11=5(沖突) d5=(5+(1*7%10)+1)%11=2(沖突) d6=(2+(1*7%10)+1)%11=10⑻H(67)=3*67%11=3(沖突) d1=H(67)=3 d2=(3+(7*67%10)+1)%11=2(沖突) d3=(2+(7*67%10)+1)%11=1查找成功的平均查找長度為：ASL=（1*4+2*2+3*1+6*1）*(1/8)=2.125502.再哈希法 再哈希法的基本思想是：當(dāng)發(fā)生沖突時，再用另一個哈希函數(shù)來得到另一個哈希地址，直到?jīng)_突不再發(fā)生。即Hi=RHi(key)（i=1,2,3,…k）

RHi均是不同的哈希函數(shù)，這種方法不易產(chǎn)生“聚集”但增加了計算的時間。3.鏈地址法 鏈地址法的基本思想是：將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。假設(shè)某哈希函數(shù)產(chǎn)生的哈希地址在區(qū)間[0,m-1]上，鏈表結(jié)點的結(jié)構(gòu)類型定義如下：51typedefstructNode{ DataTypedata; structNode*next;}SLNode;

則設(shè)立一個指向鏈表類型SLNode的指針型向量SLNode*chainhash[m]； 其每個分量的初始狀態(tài)都是空指針。凡哈希地址為i的記錄都插入到頭指針為chainhash[i]的鏈表中。在鏈表中的插入位置可以在表頭或表尾，也可以在中間，以保持同義詞在同一線性鏈表中按關(guān)鍵字有序。52本章小結(jié)

查找（Searching），是指在某種數(shù)據(jù)結(jié)構(gòu)中找出滿足給定條件的結(jié)點。若找到滿足給定條件的結(jié)點，則查找成功；否則查找失敗。查找是數(shù)據(jù)結(jié)構(gòu)中很常用的基本操作，根據(jù)選擇存儲結(jié)構(gòu)的不同，查找方法可分為：靜態(tài)查找表、動態(tài)查找表、哈希表查找。掌握靜態(tài)查找表的關(guān)鍵是數(shù)據(jù)分布特征，正確選擇順序查找，折半查找和索引查找。掌握動態(tài)查找表的關(guān)鍵是二叉排序樹的構(gòu)成和如何維持二叉排序樹的平衡。掌握哈希表查找的關(guān)鍵是如何合理的構(gòu)造哈希函數(shù)和解決沖突的方法。53習(xí)題一、填空題1.順序查找法的平均查找長度為

；二分查找法的平均查找長度為

；分塊查