第8章查找技術

數據結構與算法作者：胡明王紅梅出版社：電子工業(yè)出版社郵箱：wanghm@第8章查找技術本章的主要內容是:查找的基本概念線性表的查找技術樹表的查找技術散列表的查找技術查找的基本概念關鍵碼：可以標識一個記錄的某個數據項。鍵值：關鍵碼的值。主關鍵碼：可以唯一地標識一個記錄的關鍵碼。

次關鍵碼：不能唯一地標識一個記錄的關鍵碼。8.1概述50女李爽000525女齊梅000447女劉楠000325男張亮000238男王剛0001年齡性別姓名職工號1972.92003.71979.92003.71990.4工作時間查找的基本概念查找

：在具有相同類型的記錄構成的集合中找出滿足給定條件的記錄。

給定的查找條件可能是多種多樣的，為便于討論，把查找條件限制為“匹配”，即查找關鍵碼等于給定值的記錄。

8.1概述查找的結果：若在查找集合中找到了與給定值相匹配的記錄，則稱查找成功；否則，稱查找失敗。

靜態(tài)查找：不涉及插入和刪除操作的查找。動態(tài)查找：涉及插入和刪除操作的查找。

8.1概述查找的基本概念靜態(tài)查找適用于：查找集合一經生成，便只對其進行查找，而不進行插入和刪除操作，或經過一段時間的查找之后，集中地進行插入和刪除等修改操作；動態(tài)查找適用于：查找與插入和刪除操作在同一個階段進行，例如當查找成功時，要刪除查找到的記錄，當查找不成功時，要插入被查找的記錄。8.1概述查找的基本概念查找結構：面向查找操作的數據結構，即查找基于的數據結構。查找結構

查找方法

集合中元素之間不存在明顯的組織規(guī)律，不便查找。集合

線性表

樹表

散列表

本章討論的查找結構：線性表：適用于靜態(tài)查找，主要采用順序查找技術和折半查找技術。樹表：適用于動態(tài)查找，主要采用二叉排序樹的查找技術。散列表：靜態(tài)查找和動態(tài)查找均適用，主要采用散列技術。

8.1概述查找結構：面向查找操作的數據結構，即查找基于的數據結構。查找的基本概念查找算法的性能

查找算法時間性能通過關鍵碼的比較次數來度量。8.1概述關鍵碼的比較次數與哪些因素有關呢？平均查找長度：將查找算法進行的關鍵碼的比較次數的數學期望值定義為平均查找長度，即：其中：n：問題規(guī)模，查找集合中的記錄個數；

pi：查找第i個記錄的概率；ci：查找第i個記錄所需的關鍵碼的比較次數。ASL?==niiicp1查找算法的性能

查找算法時間性能通過關鍵碼的比較次數來度量。8.1概述關鍵碼的比較次數與哪些因素有關呢？平均查找長度：將查找算法進行的關鍵碼的比較次數的數學期望值定義為平均查找長度，即：ASL?==niiicp1ci取決于算法；pi與算法無關，取決于具體應用。如果pi是已知的，則平均查找長度只是問題規(guī)模的函數。順序查找（線性查找）基本思想：從線性表的一端向另一端逐個將關鍵碼與給定值進行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個表檢測完仍未找到與給定值相等的關鍵碼，則查找失敗，給出失敗信息。

101524612354098550123456789i8.2線性表的查找技術例：查找k＝35iii順序查找（線性查找）8.2線性表的查找技術intSeqSearch1(intr[],intn,intk)//數組r[1]~r[n]存放查找集合{i=n;while(i>0&&r[i]!=k)i--;returni;}基本思想：設置“哨兵”。哨兵就是待查值，將它放在查找方向的盡頭處，免去了在查找過程中每一次比較后都要判斷查找位置是否越界，從而提高查找速度。

8.2線性表的查找技術改進的順序查找101524612354098550123456789i例：查找k＝35iii哨兵35查找方向基本思想：設置“哨兵”。哨兵就是待查值，將它放在查找方向的盡頭處，免去了在查找過程中每一次比較后都要判斷查找位置是否越界，從而提高查找速度。

8.2線性表的查找技術改進的順序查找101524612354098550123456789i例：查找k＝25ii25查找方向iiiiiiiintSeqSearch2(intr[],intn,intk)//數組r[1]~r[n]存放查找集合{r[0]=k;i=n;while(r[i]!=k)i--;returni;}8.2線性表的查找技術改進的順序查找

ASL==?=niicp1?+-=niiinp1)1(i=(n+1)/2=O(n)平均查找長度較大，特別是當待查找集合中元素較多時，查找效率較低。8.2線性表的查找技術順序查找的缺點：對表中記錄的存儲沒有任何要求，順序存儲和鏈接存儲均可；對表中記錄的有序性也沒有要求，無論記錄是否按關鍵碼有序均可。順序查找的優(yōu)點：算法簡單而且使用面廣。折半查找使用條件：線性表中的記錄必須按關鍵碼有序；必須采用順序存儲?；舅枷耄涸谟行虮碇?，取中間記錄作為比較對象，若給定值與中間記錄的關鍵碼相等，則查找成功；若給定值小于中間記錄的關鍵碼，則在中間記錄的左半區(qū)繼續(xù)查找；若給定值大于中間記錄的關鍵碼，則在中間記錄的右半區(qū)繼續(xù)查找。不斷重復上述過程，直到查找成功，或所查找的區(qū)域無記錄，查找失敗。8.2線性表的查找技術折半查找的基本思想8.2線性表的查找技術

[r1………rmid-1]rmid[rmid+1………rn]如果k<rmid如果k>rmid查找左半區(qū)查找右半區(qū)k（mid=(1+n)/2）例：查找值為14的記錄的過程：

012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=2

mid=1

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

14=148.2線性表的查找技術例：查找值為22的記錄的過程：

012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=4

mid=5

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

21<228.2線性表的查找技術low=5low>highintBinSearch1(intr[],intn,intk){//數組r[1]~r[n]存放查找集合low=1;high=n;while(low<=high){mid=(low+high)/2;if(k<r[mid])high=mid-1;elseif(k>r[mid])low=mid+1;elsereturnmid;}return0;}8.2線性表的查找技術折半查找——非遞歸算法intBinSearch2(intr[],intlow,inthigh,intk){//數組r[1]~r[n]存放查找集合if(low>high)return0;

else{mid=(low+high)/2;if(k<r[mid])returnBinSearch2(r,low,mid-1,k);elseif(k>r[mid])returnBinSearch2(r,mid+1,high,k);elsereturnmid;}}8.2線性表的查找技術折半查找——遞歸算法折半查找判定樹

判定樹：折半查找的過程可以用二叉樹來描述，樹中的每個結點對應有序表中的一個記錄，結點的值為該記錄在表中的位置。通常稱這個描述折半查找過程的二叉樹為折半查找判定樹，簡稱判定樹。8.2線性表的查找技術⑴當n=0時，折半查找判定樹為空；⑵當n＞0時，折半查找判定樹的根結點是有序表中序號為mid=(n+1)/2的記錄，根結點的左子樹是與有序表r[1]~r[mid-1]相對應的折半查找判定樹，根結點的右子樹是與r[mid+1]~r[n]相對應的折半查找判定樹。

8.2線性表的查找技術判定樹的構造方法8.2線性表的查找技術－11－22－33－44－510－1111－9－108－97－85－66－7內部結點外部結點3691011784512判定樹的構造方法具有n個結點的折半查找判定樹的深度為

查找成功：在表中查找任一記錄的過程，即是折半查找判定樹中從根結點到該記錄結點的路徑，和給定值的比較次數等于該記錄結點在樹中的層數。查找不成功：查找失敗的過程就是走了一條從根結點到外部結點的路徑，和給定值進行的關鍵碼的比較次數等于該路徑上內部結點的個數。8.2線性表的查找技術。??1log2+n折半查找性能分析

分塊查找35…20…8…52…40…61…65…88…76…第1塊文件關鍵碼其他數據項第2塊第3塊353613883索引表最大值塊長塊首地址有序8.2線性表的查找技術分塊查找（也稱為索引順序查找），分兩步進行：⑴在索引表中確定待查關鍵碼所在的塊；⑵在相應塊中查找待查關鍵碼。索引表查找順序查找折半查找塊內查找——順序查找分塊查找8.2線性表的查找技術設有n個記錄的文件分為m個塊，每個塊均為t個記錄，則n=m×t。設Lb為查找索引表確定關鍵碼所在塊的平均查找長度，Lw為在塊內查找關鍵碼的平均查找長度，則分塊查找的平均查找長度為：

ASL=Lb+Lw若采用順序查找對索引表進行查找，則分塊查找的平均查找長度為：

ASL=Lb+Lw=當t取時，ASL取最小值+1。nn分塊查找8.2線性表的查找技術二叉排序樹二叉排序樹（也稱二叉查找樹）：或者是一棵空的二叉樹，或者是具有下列性質的二叉樹：⑴若它的左子樹不空，則左子樹上所有結點的值均小于根結點的值；⑵若它的右子樹不空，則右子樹上所有結點的值均大于根結點的值；⑶它的左右子樹也都是二叉排序樹。8.3樹表的查找技術二叉排序樹的定義采用的是遞歸方法。二叉排序樹非二叉排序樹二叉排序樹8.3樹表的查找技術6390554258104567837063605582581045678370中序遍歷二叉排序樹可以得到一個按關鍵碼有序的序列二叉排序樹的存儲結構以二叉鏈表形式存儲，類聲明如下：classBiSortTree{

public:BiSortTree(inta[],intn);~BiSortTree();voidInsertBST(BiNode<int>*root,BiNode<int>*s);voidDeleteBST(BiNode<int>*p,BiNode<int>*f);BiNode<int>*SearchBST(BiNode<int>*root,intk);private:

BiNode*root;};8.3樹表的查找技術二叉排序樹的插入分析：若二叉排序樹為空樹，則新插入的結點為新的根結點；否則，新插入的結點必為一個新的葉子結點，其插入位置由查找過程得到。8.3樹表的查找技術voidInsertBST(BiNode*root,BiNode*s);例：插入值為98的結點8.3樹表的查找技術6355905870985563root∧9058∧∧70∧∧98∧∧sroot∧voidInsertBST(BiNode*root,BiNode*s){if(root==NULL)root=s;elseif(s->data<root->data)InsertBST(root->lchild,s);elseInsertBST(root->rchild,s);}8.3樹表的查找技術二叉排序樹的插入算法二叉排序樹的構造從空的二叉排序樹開始，依次插入一個個結點。例：關鍵碼集合為{63，90，70，55，58}，二叉排序樹的構造過程為：

8.3樹表的查找技術6355905870BiNode*Creat(intr[],intn){for(i=0;i<n;i++){s=(BiNode*)malloc(sizeof(BiNode));s->data=r[i];s->lchild=s->rchild=NULL;InsertBST(root,s);}returnroot;}8.3樹表的查找技術二叉排序樹的構造算法一個無序序列可以通過構造一棵二叉排序樹而變成一個有序序列;每次插入的新結點都是二叉排序樹上新的葉子結點;找到插入位置后，不必移動其它結點，僅需修改某個結點的指針；在左子樹/右子樹的查找過程與在整棵樹上查找過程相同；新插入的結點沒有破壞原有結點之間的關系。小結：8.3樹表的查找技術二叉排序樹的刪除在二叉排序樹上刪除某個結點之后，仍然保持二叉排序樹的特性。分三種情況討論：被刪除的結點是葉子；被刪除的結點只有左子樹或者只有右子樹；被刪除的結點既有左子樹，也有右子樹。8.3樹表的查找技術情況1——被刪除的結點是葉子結點8.3樹表的查找技術50302080908588403532503020809085403532操作：將雙親結點中相應指針域的值改為空。情況2——被刪除的結點只有左子樹或者只有右子樹操作：將雙親結點的相應指針域的值指向被刪除結點的左子樹（或右子樹）。8.3樹表的查找技術50302080908588403532503020908588403532情況3——被刪除的結點既有左子樹也有右子樹操作：以其左子樹中的最大值結點（或右子樹中的最小值結點）替代之，然后再刪除該結點。8.3樹表的查找技術503020809085884035324030208090858835321.若結點p是葉子，則直接刪除結點p；2.若結點p只有左子樹，則只需重接p的左子樹；若結點p只有右子樹，則只需重接p的右子樹；3.若結點p的左右子樹均不空，則3.1查找結點p的右子樹上的最左下結點s及其雙親結點par；3.2將結點s數據域替換到被刪結點p的數據域；3.3若結點p的右孩子無左子樹，則將s的右子樹接到par的右子樹上；否則，將s的右子樹接到結點par的左子樹上；3.4刪除結點s；8.3樹表的查找技術二叉排序樹的刪除算法——偽代碼二叉排序樹的查找在二叉排序樹中查找給定值k的過程是：

⑴若root是空樹，則查找失??；⑵若k＝root->data，則查找成功；否則⑶若k＜root->data，則在root的左子樹上查找；否則⑷在root的右子樹上查找。上述過程一直持續(xù)到k被找到或者待查找的子樹為空，如果待查找的子樹為空，則查找失敗。二叉排序樹的查找效率在于只需查找二個子樹之一。8.3樹表的查找技術例：在二叉排序樹中查找關鍵字值為35，95的過程：8.3樹表的查找技術50302080908588403532二叉排序樹的查找50302080908588403532BiNode*SearchBST(BiNode*root,intk){if(root==NULL)

returnNULL；elseif(root->data==k)

returnroot;elseif(k<root->data)

returnSearchBST(root->lchild,k);elsereturnSearchBST(root->rchild,k);}8.3樹表的查找技術二叉排序樹的查找二叉排序樹的查找性能分析由序列{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.2二叉排序樹的查找性能取決于二叉排序樹的形狀，在O(log2n)和O(n)之間。

8.3樹表的查找技術1234531254平衡二叉樹：或者是一棵空的二叉排序樹，或者是具有下列性質的二叉排序樹：⑴根結點的左子樹和右子樹的深度最多相差1;⑵

根結點的左子樹和右子樹也都是平衡二叉樹。

平衡因子：結點的平衡因子是該結點的左子樹的深度與右子樹的深度之差。

平衡二叉樹8.3樹表的查找技術548254821是平衡樹非平衡樹8.3散列表的查找技術平衡二叉樹在平衡樹中，結點的平衡因子可以是1，0，-1。結點的平衡因子＝HL-HR最小不平衡子樹：在平衡二叉樹的構造過程中，以距離插入結點最近的、且平衡因子的絕對值大于1的結點為根的子樹。

8.3樹表的查找技術542814平衡二叉樹構造平衡二叉樹的基本思想：每插入一個結點，（1）從插入結點開始向上計算各結點的平衡因子，如果某結點平衡因子的絕對值超過1，則說明插入操作破壞了二叉排序樹的平衡性，需要進行平衡調整；否則繼續(xù)執(zhí)行插入操作。（2）如果二叉排序樹不平衡，則找出最小不平衡子樹的根結點，根據新插入結點與最小不平衡子樹根結點之間的關系判斷調整類型。（3）根據調整類型進行相應的調整，使之成為新的平衡子樹。8.3樹表的查找技術平衡二叉樹例：設序列{20，35，40，15，30，25}，構造平衡樹。2035408.3樹表的查找技術352040153025例：設序列{20，35，40，15，30，25}，構造平衡樹。8.3樹表的查找技術352040153025202515354030354030202515設結點A為最小不平衡子樹的根結點，對該子樹進行平衡調整歸納起來有以下四種情況：1.LL型2.RR型3.LR型4.RL型8.3樹表的查找技術平衡二叉樹插入前插入后，調整前調整后8.3樹表的查找技術平衡二叉樹——LL型A1BLhBRh0ARhBh2BLhBRh1ARABXh+1BLhARBRh00BAX旋轉：扁擔原理；沖突：旋轉優(yōu)先61→2例:LL型

8.3樹表的查找技術108791291012876平衡二叉樹——RR型8.3樹表的查找技術插入前插入后，調整前調整后A-1BLhBRh0ALhBXA-2BLhBRh0ALhBBALhBLh0BRh+1AX0插入后，調整前先順時針旋轉

再逆時針旋轉8.3樹表的查找技術平衡二叉樹——LR型A2CLh-1BLh-1ARhBCCRh-1XXACLh-1CBCRh-1ARhBLhARhCACRh-1BCLh-1X0-10BLh插入后，調整前先順時針旋轉

再逆時針旋轉8.3樹表的查找技術平衡二叉樹——RL型XACLh-1BRhCBCRh-1ALhA-2CLh-1BRh1ALhBCCRh-1XBRhCBCRh-1AALhCLh-1X001課堂練習：設有關鍵碼序列{5,4,2,8,6,9}，構造平衡樹5428.3樹表的查找技術LL型42586864256842585642課堂練習：設有關鍵碼序列{5,4,2,8,6,9}，構造平衡樹8.3樹表的查找技術RL型旋轉1次RL型旋轉2次856429RR型8465298.3樹表的查找技術課堂練習：設有關鍵碼序列{5,4,2,8,6,9}，構造平衡樹所有非終端結點都包含以下數據：（n，A0，K1，A1，K2，…，Kn，An）其中，n（m/2

1≤n≤m

1）為關鍵碼的個數；Ki（1≤i≤n）為關鍵碼，且Ki＜Ki+1（1≤i≤n-1）；Ai（0≤i≤n）為指向子樹根結點的指針，且指針Ai所指子樹中所有結點的關鍵碼均小于Ki+1大于Ki。B樹的定義8.3樹表的查找技術1181

111

271

393475364199FFFFFFFFFFFF243781

35B樹示例葉子結點查找失敗的結點終端結點在同一層上外結點指針包含其子女結點的塊號8.3樹表的查找技術18331223304810152021243145475052B樹——查找操作2118<21<3321<23比較次數不超過樹的深度。8.3樹表的查找技術B樹——插入操作新記錄將插入到相應的葉子結點中。18331223304810152021243145475052葉子結點只包含1個記錄插入新記錄

148.3樹表的查找技術B樹——插入操作新記錄將插入到相應的葉子結點中。葉子結點只包含1個記錄插入新記錄

18331223304815202124314547505210148.3樹表的查找技術B樹——插入操作新記錄將插入到相應的葉子結點中。18331223304810152021243145475052葉子結點只包含2個記錄插入新記錄，分裂－提升

558.3樹表的查找技術B樹——插入操作新記錄將插入到相應的葉子結點中。1833122330481015202124314547505255葉子結點只包含2個記錄插入新記錄，分裂－提升

插入8.3樹表的查找技術B樹——插入操作新記錄將插入到相應的葉子結點中。1833122330481015202124314547葉子結點只包含2個記錄插入新記錄，分裂－提升

分裂5055528.3樹表的查找技術B樹——插入操作新記錄將插入到相應的葉子結點中。18331223301015202124314547葉子結點只包含2個記錄插入新記錄，分裂－提升

提升505548528.3樹表的查找技術18331223304810152021243145475052B樹——刪除操作情況1：從包含2個記錄的葉子結點刪除1個記錄。解決方法：直接刪除這個記錄。8.3樹表的查找技術1833122330481015243145475052B樹——刪除操作情況1：從包含2個記錄的葉子結點刪除1個記錄。解決方法：直接刪除這個記錄。218.3樹表的查找技術18331223304810152021243145475052B樹——刪除操作情況2：從包含1個記錄的葉子結點中刪除這個記錄。解決方法：向兄弟結點借一個記錄，同時修改雙親結點的記錄。8.3樹表的查找技術183312213048101520233145475052B樹——刪除操作情況2：從包含1個記錄的葉子結點中刪除這個記錄。解決方法：向兄弟結點借一個記錄，同時修改雙親結點的記錄。8.3樹表的查找技術183312213048101520233145475052B樹——刪除操作情況2：從包含1個記錄的葉子結點中刪除這個記錄。解決方法：兄弟結點不夠借，需要合并相鄰結點，并影響雙親結點。8.3樹表的查找技術1833122021481015303145475052B樹——刪除操作情況2：從包含1個記錄的葉子結點中刪除這個記錄。解決方法：兄弟結點不夠借，需要合并相鄰結點，并影響雙親結點。8.3樹表的查找技術1833122021481015303145475052B樹——刪除操作情況2：從包含1個記錄的葉子結點中刪除這個記錄。解決方法：兄弟結點不夠借，需要合并相鄰結點，并影響雙親結點。8.3樹表的查找技術202148333145475052B樹——刪除操作情況2：從包含1個記錄的葉子結點中刪除這個記錄。10121830解決方法：兄弟結點不夠借，需要合并相鄰結點，并影響雙親結點。8.3樹表的查找技術48333045475052B樹——刪除操作情況2：從包含1個記錄的葉子結點中刪除這個記錄。解決方法：兄弟結點不夠借，需要合并相鄰結點，并影響雙親結點，這可能減少樹的高度。25208.3樹表的查找技術B樹——刪除操作情況2：從包含1個記錄的葉子結點中刪除這個記錄。解決方法：兄弟結點不夠借，需要合并相鄰結點，并影響雙親結點，這可能減少樹的高度。4547505233482025B樹的優(yōu)點：能夠以相對較低的代價保持樹高平衡。8.3樹表的查找技術B樹——刪除操作情況3：從內部結點刪除一個記錄。解決方法：將被刪除記錄用右邊子樹中的最小關鍵碼Y代替（Y一定在某個葉子結點中），然后再刪除Y。183312233048101520212431454750528.3樹表的查找技術B樹——刪除操作情況3：從內部結點刪除一個記錄。解決方法：將被刪除記錄用右邊子樹中的最小關鍵碼Y代替（Y一定在某個葉子結點中），然后再刪除Y。2033122330481015212431454750528.3樹表的查找技術B+樹的定義m階B＋樹是滿足下列特性的樹：⑴含有m個關鍵碼，每一個關鍵碼對應一棵子樹。⑵關鍵碼Ki是它所對應的子樹的根結點中的最大（或最?。╆P鍵碼。⑶所有終端結點中包含了全部關鍵碼信息，以及指向關鍵碼記錄的指針。⑷

所有終端結點按關鍵碼的大小鏈在一起，形成單鏈表，并設置頭指針。

8.3樹表的查找技術LB+樹示例509020506080901216202630505560627080828690內部結點只存儲關鍵碼終端結點存儲記錄引導查找8.3樹表的查找技術8.4散列表的查找技術順序查找、折半查找、二叉排序樹查找等。這些查找技術都是通過一系列的給定值與關鍵碼的比較，查找效率依賴于查找過程中進行的給定值與關鍵碼的比較次數。查找操作要完成什么任務？待查值k確定k在存儲結構中的位置我們學過哪些查找技術？這些查找技術的共性？在存儲位置和關鍵碼之間建立一個確定的對應關系能否不用比較，通過關鍵碼直接確定存儲位置？概述散列的基本思想：在記錄的存儲地址和它的關鍵碼之間建立一個確定的對應關系。這樣，不經過比較，一次讀取就能得到所查元素的查找方法。關鍵碼集合kiriH(ki)…………H8.4散列表的查找技術散列表：采用散列技術將記錄存儲在一塊連續(xù)的存儲空間中，這塊連續(xù)的存儲空間稱為散列表。概述關鍵碼集合kiriH(ki)…………H散列表數組8.4散列表的查找技術散列函數：將關鍵碼映射為散列表中適當存儲位置的函數。概述散列表關鍵碼集合kiriH(ki)…………H散列函數數組8.4散列表的查找技術散列地址：由散列函數所得的存儲地址。概述散列表關鍵碼集合kiriH(ki)…………H散列函數散列地址下標數組8.4散列表的查找技術概述散列技術僅僅是一種查找技術嗎？散列既是一種查找技術，也是一種存儲技術。散列只是通過記錄的關鍵碼定位該記錄，沒有完整地表達記錄之間的邏輯關系，所以，散列主要是面向查找的存儲結構。散列是一種完整的存儲結構嗎？8.4散列表的查找技術散列技術一般不適用于允許多個記錄有同樣關鍵碼的情況。散列方法也不適用于范圍查找，換言之，在散列表中，我們不可能找到最大或最小關鍵碼的記錄，也不可能找到在某一范圍內的記錄。概述散列技術適合于哪種類型的查找？散列技術最適合回答的問題是：如果有的話，哪個記錄的關鍵碼等于待查值。8.4散列表的查找技術散列技術的關鍵問題：⑴散列函數的設計。如何設計一個簡單、均勻、存儲利用率高的散列函數。⑵沖突的處理。如何采取合適的處理沖突方法來解決沖突。概述8.4散列表的查找技術沖突：對于兩個不同關鍵碼ki≠kj，有H(ki)＝H(kj)，即兩個不同的記錄需要存放在同一個存儲位置,ki和kj相對于H稱做同義詞。

概述關鍵碼集合kiri…………H(ki)kjH(kj)8.4散列表的查找技術散列函數設計散列函數一般應遵循以下原則：⑴計算簡單。散列函數不應該有很大的計算量，否則會降低查找效率。⑵函數值即散列地址分布均勻。函數值要盡量均勻散布在地址空間，這樣才能保證存儲空間的有效利用并減少沖突。8.4散列表的查找技術散列函數——直接定址法散列函數是關鍵碼的線性函數，即：H(key)=a

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

散列函數——除留余數法1470147014散列地址56494235282114關鍵碼如何選取合適的p，產生較少同義詞？例：p＝21＝3×78.4散列表的查找技術散列函數——除留余數法一般情況下，選p為小于或等于表長（最好接近表長）的最小素數或不包含小于20質因子的合數。

除留余數法是一種最簡單、也是最常用的構造散列函數的方法，并且不要求事先知道關鍵碼的分布。適用情況？8.4散列表的查找技術根據關鍵碼在各個位上的分布情況，選取分布比較均勻的若干位組成散列地址。

例：關鍵碼為8位十進制數，散列地址為2位十進制數81346

5

3

281372

2

4281387

4

2281301

3

6781322

8

1781338

9

67①②③④⑤⑥⑦⑧散列函數——數字分析法8.4散列表的查找技術適用情況:能預先估計出全部關鍵碼的每一位上各種數字出現(xiàn)的頻度，不同的關鍵碼集合需要重新分析。散列函數——數字分析法8.4散列表的查找技術對關鍵碼平方后，按散列表大小，取中間的若干位作為散列地址（平方后截?。?。散列函數——平方取中法事先不知道關鍵碼的分布且關鍵碼的位數不是很大。適用情況:例：散列地址為2位，則關鍵碼123的散列地址為：(1234)2＝15227568.4散列表的查找技術將關鍵碼從左到右分割成位數相等的幾部分，將這幾部分疊加求和，取后幾位作為散列地址。散列函數——折疊法例：設關鍵碼為25346358705，散列地址為三位。

253463587

+05───1308

移位疊加

253364587+50───1254

間界疊加適用情況:關鍵碼位數很多，事先不知道關鍵碼的分布。8.4散列表的查找技術處理沖突的方法——開放定址法由關鍵碼得到的散列地址一旦產生了沖突，就去尋找下一個空的散列地址，并將記錄存入。如何尋找下一個空的散列地址?（1）線性探測法（2）二次探測法（3）隨機探測法8.4散列表的查找技術線性探測法當發(fā)生沖突時，從沖突位置的下一個位置起，依次尋找空的散列地址。

對于鍵值key，設H(key)=d，閉散列表的長度為m，則發(fā)生沖突時，尋找下一個散列地址的公式為：

Hi=(H(key)＋di)%m

（di=1，2，…，m-1）

用開放定址法處理沖突得到的散列表叫閉散列表。8.4散列表的查找技術例：關鍵碼集合為{47,7,29,11,16,92,22,8,3}，散列表表長為11，散列函數為H(key)=keymod11，用線性探測法處理沖突，則散列表為：47729111692292222883333堆積：在處理沖突的過程中出現(xiàn)的非同義詞之間對同一個散列地址爭奪的現(xiàn)象。線性探測法0123456789108.4散列表的查找技術在線性探測法構造的散列表中查找算法——偽代碼1.計算散列地址j;2.若ht[j]等于k，則查找成功，返回記錄在散列表中的下標；否則執(zhí)行第3步；3.若ht[j]為空或整個散列表探測一遍，則查找失敗，轉4；否則，j指向下一單元，轉2；4.若整個散列表探測一遍，則表滿，拋出溢出異常；否則，將待查值插入；8.4散列表的查找技術intHashSearch1(intht[],intm,intk){j=H(k);//計算散列地址if(ht[j]==k)returnj;//沒有發(fā)生沖突，比較一次查找成功elseif(ht[j]==Empty){ht[j]=k;return0;}//查找不成功，插入i=(j+1)%m;//設置探測的起始下標while(ht[i]!=Empty&&i!=j){if(ht[i]==k)returni;//發(fā)生沖突，比較若干次查找成功elsei=(i+1)%m;//向后探測一個位置}if(i==j){printf("溢出");exit(-1);}else{ht[i]=k;return0;}//查找不成功，插入}在線性探測法構造的散列表中查找算法8.4散列表的查找技術二次探測法當發(fā)生沖突時，尋找下一個散列地址的公式為：Hi=(H(ke