《數(shù)據(jù)結(jié)構(gòu)》課件-第8章 查找技術(shù)

數(shù)據(jù)構(gòu)C語言描述結(jié)第8章

查找技術(shù)第8章查找技術(shù)知識目標(biāo)：理解查找和平均查找長度的概念掌握靜態(tài)表查找的方法：順序查找、折半查找和分塊查找掌握動態(tài)表查找方法，二叉排序樹的基本操作掌握哈希表組織方式，哈希函數(shù)的構(gòu)造、解決沖突的方法及哈希表的查找操作技能目標(biāo)：能應(yīng)用靜態(tài)表、動態(tài)表和哈希表的理論設(shè)計(jì)算法，解決實(shí)際問題8.4散列表的查找技術(shù)8.1概述8.2線性表的查找技術(shù)8.3樹表的查找技術(shù)8.5案例實(shí)現(xiàn)——查找綜合練習(xí)查找的基本概念關(guān)鍵碼：可以標(biāo)識一個(gè)記錄的某個(gè)數(shù)據(jù)項(xiàng)。鍵值：關(guān)鍵碼的值。主關(guān)鍵碼：可以唯一地標(biāo)識一個(gè)記錄的關(guān)鍵碼。次關(guān)鍵碼：不能唯一地標(biāo)識一個(gè)記錄的關(guān)鍵碼。50女李爽000525女齊梅000447女劉楠000325男張亮000238男王剛0001年齡性別姓名職工號1972.92003.71979.92003.71990.4工作時(shí)間8.1概述查找的基本概念查找

：在具有相同類型的記錄構(gòu)成的集合中找出滿足給定條件的記錄。給定的查找條件可能是多種多樣的，為便于討論，把查找條件限制為“匹配”，即查找關(guān)鍵碼等于給定值的記錄。查找的結(jié)果：若在查找集合中找到了與給定值相匹配的記錄，則稱查找成功；否則，稱查找失敗。8.1概述靜態(tài)查找：不涉及插入和刪除操作的查找。動態(tài)查找：涉及插入和刪除操作的查找。

查找的基本概念靜態(tài)查找適用于：查找集合一經(jīng)生成，便只對其進(jìn)行查找，而不進(jìn)行插入和刪除操作，或經(jīng)過一段時(shí)間的查找之后，集中地進(jìn)行插入和刪除等修改操作；動態(tài)查找適用于：查找與插入和刪除操作在同一個(gè)階段進(jìn)行，例如當(dāng)查找成功時(shí)，要刪除查找到的記錄，當(dāng)查找不成功時(shí)，要插入被查找的記錄。8.1概述查找的基本概念查找結(jié)構(gòu)：面向查找操作的數(shù)據(jù)結(jié)構(gòu)，即查找基于的數(shù)據(jù)結(jié)構(gòu)。查找結(jié)構(gòu)查找方法集合中元素之間不存在明顯的組織規(guī)律，不便查找。集合線性表樹表散列表8.1概述本章討論的查找結(jié)構(gòu)：線性表：適用于靜態(tài)查找，主要采用順序查找和折半查找技術(shù)。樹表：適用于動態(tài)查找，主要采用二叉排序樹的查找技術(shù)。散列表：靜態(tài)查找和動態(tài)查找均適用，主要采用散列技術(shù)。查找結(jié)構(gòu)：面向查找操作的數(shù)據(jù)結(jié)構(gòu)，即查找基于的數(shù)據(jù)結(jié)構(gòu)。查找的基本概念8.1概述算法本身及問題規(guī)模；待查關(guān)鍵碼在檢索集合中的位置。8.1概述查找算法的性能查找算法時(shí)間性能通過關(guān)鍵碼的比較次數(shù)來度量。關(guān)鍵碼的比較次數(shù)與哪些因素有關(guān)呢？查找算法的性能查找算法時(shí)間性能通過關(guān)鍵碼的比較次數(shù)來度量。關(guān)鍵碼的比較次數(shù)與哪些因素有關(guān)呢？平均查找長度：將查找算法進(jìn)行的關(guān)鍵碼的比較次數(shù)的數(shù)學(xué)期望值定義為平均查找長度，即：其中：n：問題規(guī)模，查找集合中的記錄個(gè)數(shù)； pi：查找第i個(gè)記錄的概率； ci：查找第i個(gè)記錄所需的關(guān)鍵碼的比較次數(shù)。ASL∑==niiicp18.1概述順序查找技術(shù)折半查找技術(shù)8.2線性表的查找技術(shù)基本思想：從線性表的一端向另一端逐個(gè)將關(guān)鍵碼與給定值進(jìn)行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個(gè)表檢測完仍未找到與給定值相等的關(guān)鍵碼，則查找失敗，給出失敗信息。101524612354098550123456789i例：查找k＝35iii順序查找（線性查找）8.2線性表的查找技術(shù)順序查找（線性查找）intSeqSearch1(intr[],intn,intk)//數(shù)組r[1]~r[n]存放查找集合{i=n;while(i>0&&r[i]!=k)i--;returni;}8.2線性表的查找技術(shù)基本思想：設(shè)置“哨兵”。哨兵就是待查值，將它放在查找方向的盡頭處，免去了在查找過程中每一次比較后都要判斷查找位置是否越界，從而提高查找速度。改進(jìn)的順序查找101524612354098550123456789i例：查找k＝35iii哨兵35查找方向8.2線性表的查找技術(shù)改進(jìn)的順序查找101524612354098550123456789iii25查找方向iiiiiii基本思想：設(shè)置“哨兵”。哨兵就是待查值，將它放在查找方向的盡頭處，免去了在查找過程中每一次比較后都要判斷查找位置是否越界，從而提高查找速度。例：查找k＝258.2線性表的查找技術(shù)intSeqSearch2(intr[],intn,intk)//數(shù)組r[1]~r[n]存放查找集合{r[0]=k;i=n;while(r[i]!=k)i--;returni;}

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

[r1………rmid-1]rmid[rmid+1………rn]如果k<rmid如果k>rmid查找左半?yún)^(qū)查找右半?yún)^(qū)kmid=(1+n)/28.2線性表的查找技術(shù)例：查找值為14的記錄的過程：012345678910111213

7141821232931353842464952low=1high=13mid=7high=6mid=3high=2

mid=131>1418>147<14low=2mid=214=148.2線性表的查找技術(shù)low=1high=13mid=7high=6mid=3high=4mid=531>2218<2223>22low=4mid=421<22low=5low>high例：查找值為22的記錄的過程：012345678910111213

71418212329313538424649528.2線性表的查找技術(shù)intBinSearch1(intr[],intn,intk){//數(shù)組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線性表的查找技術(shù)intBinSearch2(intr[],intlow,inthigh,intk){//數(shù)組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線性表的查找技術(shù)折半查找判定樹

判定樹：折半查找的過程可以用二叉樹來描述，樹中的每個(gè)結(jié)點(diǎn)對應(yīng)有序表中的一個(gè)記錄，結(jié)點(diǎn)的值為該記錄在表中的位置。通常稱這個(gè)描述折半查找過程的二叉樹為折半查找判定樹，簡稱判定樹。8.2線性表的查找技術(shù)(1)當(dāng)n=0時(shí)，折半查找判定樹為空；(2)當(dāng)n＞0時(shí)，折半查找判定樹的根結(jié)點(diǎn)是有序表中序號為mid=(n+1)/2的記錄，根結(jié)點(diǎn)的左子樹是與有序表r[1]~r[mid-1]相對應(yīng)的折半查找判定樹，根結(jié)點(diǎn)的右子樹是與r[mid+1]~r[n]相對應(yīng)的折半查找判定樹。判定樹的構(gòu)造方法8.2線性表的查找技術(shù)－11－22－33－44－510－1111－9－108－97－85－66－7內(nèi)部結(jié)點(diǎn)外部結(jié)點(diǎn)3691011784512判定樹的構(gòu)造方法8.2線性表的查找技術(shù)判定樹的構(gòu)造方法8.2線性表的查找技術(shù)具有n個(gè)結(jié)點(diǎn)的折半查找判定樹的深度為查找成功：在表中查找任一記錄的過程，即是折半查找判定樹中從根結(jié)點(diǎn)到該記錄結(jié)點(diǎn)的路徑，給定值的比較次數(shù)等于該記錄結(jié)點(diǎn)在樹中的層數(shù)。查找不成功：查找失敗的過程就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑，和給定值進(jìn)行的關(guān)鍵碼的比較次數(shù)等于該路徑上內(nèi)部結(jié)點(diǎn)的個(gè)數(shù)。。??1log2+n折半查找性能分析

8.2線性表的查找技術(shù)1234567891011513192137566475808892平均查找長度ASL=(1*1+2*2+3*4+4*4)/11=3－11－22－33－44－510－1111－9－108－97－85－66－73691011784512折半查找性能分析

8.2線性表的查找技術(shù)折半查找假設(shè)在有序表A[0…19]中進(jìn)行二分查找，比較一次查找成功的結(jié)點(diǎn)數(shù)為______，比較二次查找成功的結(jié)點(diǎn)數(shù)為______，比較三次查找成功的結(jié)點(diǎn)數(shù)為______，比較四次查找成功的結(jié)點(diǎn)數(shù)為______，比較五次查找成功的結(jié)點(diǎn)數(shù)為______，平均查找長度為______。124853.7ASL=(1*1+2*2+3*4+4*8+5*5)/20=74/20優(yōu)點(diǎn)：比較次數(shù)少，查找速度快，平均性能好；缺點(diǎn)：由于折半查找的適用前提是有序表，并且必須是順序存儲，在數(shù)據(jù)集頻繁執(zhí)行插入和刪除操作時(shí)，需要O(n)的時(shí)間來維護(hù)表的有序性，并且需要移動大量元素，因而折半查找一般僅適用于靜態(tài)查找。折半查找的優(yōu)缺點(diǎn)

8.2線性表的查找技術(shù)樹結(jié)構(gòu)的查找法又稱為樹表查找法，是利用特定的樹結(jié)構(gòu)將查找表組織成有序表，并在表上實(shí)現(xiàn)查找、插入和刪除運(yùn)算。基于樹結(jié)構(gòu)的查找表本身是在查找過程中動態(tài)生成的，因此樹結(jié)構(gòu)的查找可用于動態(tài)查找表的表示和實(shí)現(xiàn)。二叉排序樹平衡二叉排序樹8.3樹表的查找技術(shù)二叉排序樹二叉排序樹（也稱二叉查找樹）：或者是一棵空的二叉樹，或者是具有下列性質(zhì)的二叉樹：若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；它的左右子樹也都是二叉排序樹。二叉排序樹的定義采用的是遞歸方法8.3樹表的查找技術(shù)二叉排序樹非二叉排序樹6390554258104567837063605582581045678370二叉排序樹8.3樹表的查找技術(shù)思考：對二叉排序樹進(jìn)行中序遍歷，會有什么發(fā)現(xiàn)？中序遍歷二叉排序樹可以得到一個(gè)按關(guān)鍵碼有序的序列，這也是二叉排序樹的名稱之由來。因此，二叉排序樹是記錄之間滿足一定次序關(guān)系的二叉樹。構(gòu)造二叉排序樹的目的是排序嗎？構(gòu)造二叉排序樹的目的并非是為了排序，而是用它來加速查找。因?yàn)樵谝粋€(gè)有序的數(shù)據(jù)集上進(jìn)行查找通常比在無序的數(shù)據(jù)集上的查找速度快。8.3樹表的查找技術(shù)以二叉鏈表形式存儲，C語言描述如下：typedefstructBiTNode{ElemTypedata;/*關(guān)鍵字的值*/structBiTNode*lchild,*rchild;/*左右指針*/}BiTNode,*BiTree;二叉排序樹的存儲結(jié)構(gòu)8.3樹表的查找技術(shù)已知一個(gè)關(guān)鍵字值為key的結(jié)點(diǎn)s，若將其插入到二叉排序樹中，只要保證插入后仍符合二叉排序樹的定義即可。若二叉排序樹是空樹，則key成為二叉排序樹的根；若二叉排序樹非空，則將key與二叉排序樹的根進(jìn)行比較：如果key的值等于根結(jié)點(diǎn)的值，則停止插入；如果key的值小于根結(jié)點(diǎn)的值，則將key插入左子樹；如果key的值大于根結(jié)點(diǎn)的值，則將key插入右子樹。二叉排序樹的插入8.3樹表的查找技術(shù)例：插入值為98的結(jié)點(diǎn)6355905870985563root∧9058∧∧70∧∧98∧∧sroot∧8.3樹表的查找技術(shù)從空的二叉排序樹開始，依次插入一個(gè)個(gè)結(jié)點(diǎn)。例：關(guān)鍵碼集合為{63，90，70，55，58}，二叉排序樹的構(gòu)造過程為：6355905870二叉排序樹的構(gòu)造8.3樹表的查找技術(shù)一個(gè)無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個(gè)有序序列；每次插入的新結(jié)點(diǎn)都是二叉排序樹上新的葉子結(jié)點(diǎn)；找到插入位置后，不必移動其它結(jié)點(diǎn)，僅需修改某個(gè)結(jié)點(diǎn)的指針；在左子樹/右子樹的查找過程與在整棵樹上查找過程相同；新插入的結(jié)點(diǎn)沒有破壞原有結(jié)點(diǎn)之間的關(guān)系。小結(jié)：8.3樹表的查找技術(shù)在二叉排序樹上刪除某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹的特性。分三種情況討論：被刪除的結(jié)點(diǎn)是葉子；被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹；被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹。二叉排序樹的刪除8.3樹表的查找技術(shù)情況1——被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)50302080908588403532503020809085403532操作：將雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為空。8.3樹表的查找技術(shù)操作：將雙親結(jié)點(diǎn)的相應(yīng)指針域的值指向被刪除結(jié)點(diǎn)的左子樹（或右子樹）。50302080908588403532503020908588403532情況2——被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹8.3樹表的查找技術(shù)操作：以其左子樹中的最大值結(jié)點(diǎn)（或右子樹中的最小值結(jié)點(diǎn)）替代之，然后再刪除該結(jié)點(diǎn)。50302080908588403532403020809085883532情況3——被刪除的結(jié)點(diǎn)既有左子樹也有右子樹8.3樹表的查找技術(shù)1.若結(jié)點(diǎn)p是葉子，則直接刪除結(jié)點(diǎn)p；2.若結(jié)點(diǎn)p只有左子樹，則只需重接p的左子樹；若結(jié)點(diǎn)p只有右子樹，則只需重接p的右子樹；3.若結(jié)點(diǎn)p的左右子樹均不空，則3.1查找結(jié)點(diǎn)p的右子樹上的最左下結(jié)點(diǎn)s及其雙親結(jié)點(diǎn)par；3.2將結(jié)點(diǎn)s數(shù)據(jù)域替換到被刪結(jié)點(diǎn)p的數(shù)據(jù)域；3.3若結(jié)點(diǎn)p的右孩子無左子樹，則將s的右子樹接到par的右子樹上；否則，將s的右子樹接到結(jié)點(diǎn)par的左子樹上；3.4刪除結(jié)點(diǎn)s；二叉排序樹的刪除算法——偽代碼8.3樹表的查找技術(shù)在二叉排序樹中查找給定值k的過程是：若root是空樹，則查找失??；若k＝root->data，則查找成功；否則若k＜root->data，則在root的左子樹上查找；否則在root的右子樹上查找。上述過程一直持續(xù)到k被找到或者待查找的子樹為空，如果待查找的子樹為空，則查找失敗。二叉排序樹的查找效率在于只需查找二個(gè)子樹之一。二叉排序樹的查找8.3樹表的查找技術(shù)例：在二叉排序樹中查找關(guān)鍵字值為35，95的過程：5030208090858840353250302080908588403532二叉排序樹的查找8.3樹表的查找技術(shù)BiNode*BiSortTree::SearchBST(BiNode<int>*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樹表的查找技術(shù)由序列{3,1,2,5,4}得到二叉排序樹：由序列{1,2,3,4,5}得到二叉排序樹：ASL=（1+2+3+4+5）/5=3ASL=（1+2*2+3*2）/5=2.2二叉排序樹的查找性能取決于二叉排序樹的形狀，在O(log2n)和O(n)之間。1234531254二叉排序樹的查找性能分析8.3樹表的查找技術(shù)課堂練習(xí)已知一組關(guān)鍵字{9,15,3,8,12,2,

7,

3}畫出其二叉排序樹的生成過程。9321587312{10,

18,

3,

8,

12,

2,

7,

3}平衡二叉樹：或者是一棵空的二叉排序樹，或者是具有下列性質(zhì)的二叉排序樹：⑴根結(jié)點(diǎn)的左子樹和右子樹的深度最多相差1;⑵

根結(jié)點(diǎn)的左子樹和右子樹也都是平衡二叉樹。

平衡因子：結(jié)點(diǎn)的平衡因子是該結(jié)點(diǎn)的左子樹的深度與右子樹的深度之差。

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

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

8.3樹表的查找技術(shù)108791291012876平衡二叉樹——RR型8.3樹表的查找技術(shù)插入前插入后，調(diào)整前調(diào)整后A-1BLhBRh0ALhBXA-2BLhBRh0ALhBBALhBLh0BRh+1AX0插入后，調(diào)整前先順時(shí)針旋轉(zhuǎn)

再逆時(shí)針旋轉(zhuǎn)8.3樹表的查找技術(shù)平衡二叉樹——LR型A2CLh-1BLh-1ARhBCCRh-1XXACLh-1CBCRh-1ARhBLhARhCACRh-1BCLh-1X0-10BLh插入后，調(diào)整前先順時(shí)針旋轉(zhuǎn)

再逆時(shí)針旋轉(zhuǎn)8.3樹表的查找技術(shù)平衡二叉樹——RL型XACLh-1BRhCBCRh-1ALhA-2CLh-1BRh1ALhBCCRh-1XBRhCBCRh-1AALhCLh-1X001課堂練習(xí)：設(shè)有關(guān)鍵碼序列{5,4,2,8,6,9}，構(gòu)造平衡樹5428.3樹表的查找技術(shù)LL型42586864256842585642課堂練習(xí)：設(shè)有關(guān)鍵碼序列{5,4,2,8,6,9}，構(gòu)造平衡樹8.3樹表的查找技術(shù)RL型旋轉(zhuǎn)1次RL型旋轉(zhuǎn)2次856429RR型8465298.3樹表的查找技術(shù)課堂練習(xí)：設(shè)有關(guān)鍵碼序列{5,4,2,8,6,9}，構(gòu)造平衡樹散列的基本思想：在記錄的存儲地址和它的關(guān)鍵碼之間建立一個(gè)確定的對應(yīng)關(guān)系。這樣，不經(jīng)過比較，一次讀取就能得到所查元素的查找方法。關(guān)鍵碼集合kiriH(ki)…………H8.4散列表的查找技術(shù)概述散列表：采用散列技術(shù)將記錄存儲在一塊連續(xù)的存儲空間中，這塊連續(xù)的存儲空間稱為散列表。散列表數(shù)組8.4散列表的查找技術(shù)概述關(guān)鍵碼集合kiriH(ki)…………H散列函數(shù)：將關(guān)鍵碼映射為散列表中適當(dāng)存儲位置的函數(shù)。散列函數(shù)8.4散列表的查找技術(shù)概述散列表數(shù)組關(guān)鍵碼集合kiriH(ki)…………H散列地址：由散列函數(shù)所得的存儲地址。散列地址下標(biāo)8.4散列表的查找技術(shù)概述散列表數(shù)組關(guān)鍵碼集合kiriH(ki)…………H散列技術(shù)僅僅是一種查找技術(shù)嗎？散列既是一種查找技術(shù)，也是一種存儲技術(shù)。散列只是通過記錄的關(guān)鍵碼定位該記錄，沒有完整地表達(dá)記錄之間的邏輯關(guān)系，所以，散列主要是面向查找的存儲結(jié)構(gòu)。散列是一種完整的存儲結(jié)構(gòu)嗎？8.4散列表的查找技術(shù)概述散列技術(shù)一般不適用于允許多個(gè)記錄有同樣關(guān)鍵碼的情況。散列方法也不適用于范圍查找，換言之，在散列表中，我們不可能找到最大或最小關(guān)鍵碼的記錄，也不可能找到在某一范圍內(nèi)的記錄。散列技術(shù)適合于哪種類型的查找？散列技術(shù)最適合回答的問題是：如果有的話，哪個(gè)記錄的關(guān)鍵碼等于待查值。8.4散列表的查找技術(shù)概述散列技術(shù)的關(guān)鍵問題：(1)散列函數(shù)的設(shè)計(jì)。如何設(shè)計(jì)一個(gè)簡單、均勻、存儲利用率高的散列函數(shù)。(2)沖突的處理。如何采取合適的處理沖突方法來解決沖突。8.4散列表的查找技術(shù)概述沖突：對于兩個(gè)不同關(guān)鍵碼ki≠kj，有H(ki)＝H(kj)，即兩個(gè)不同的記錄需要存放在同一個(gè)存儲位置,ki和kj相對于H稱做同義詞。

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

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

1470147014散列地址56494235282114關(guān)鍵碼如何選取合適的p，產(chǎn)生較少同義詞？例：p＝21＝3×78.4散列表的查找技術(shù)散列函數(shù)——除留余數(shù)法一般情況下，選p為小于或等于表長（最好接近表長）的最小素?cái)?shù)或不包含小于20質(zhì)因子的合數(shù)。除留余數(shù)法是一種最簡單、也是最常用的構(gòu)造散列函數(shù)的方法，并且不要求事先知道關(guān)鍵碼的分布。適用情況？8.4散列表的查找技術(shù)散列函數(shù)——除留余數(shù)法根據(jù)關(guān)鍵碼在各個(gè)位上的分布情況，選取分布比較均勻的若干位組成散列地址。例：關(guān)鍵碼為8位十進(jìn)制數(shù)，散列地址為2位十進(jìn)制數(shù)81346

5

3

281372

2

4281387

4

2281301

3

6781322

8

1781338

9

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

253463587

+05──────1308

移位疊加

253364587+50──────1254

間界疊加適用情況:關(guān)鍵碼位數(shù)很多，事先不知道關(guān)鍵碼的分布。8.4散列表的查找技術(shù)散列函數(shù)——折疊法由關(guān)鍵碼得到的散列地址一旦產(chǎn)生了沖突，就去尋找下一個(gè)空的散列地址，并將記錄存入。如何尋找下一個(gè)空的散列地址?（1）線性探測法（2）二次探測法（3）隨機(jī)探測法8.4散列表的查找技術(shù)處理沖突的方法——開放定址法當(dāng)發(fā)生沖突時(shí)，從沖突位置的下一個(gè)位置起，依次尋找空的散列地址。對于鍵值key，設(shè)H(key)=d，閉散列表的長度為m，則發(fā)生沖突時(shí)，尋找下一個(gè)散列地址的公式為：

Hi=(H(key)＋di)%m（di=1，2，…，m-1）用開放定址法處理沖突得到的散列表叫閉散列表。8.4散列表的查找技術(shù)處理沖突的方法——線性探測法例：關(guān)鍵碼集合為{47,7,29,11,16,92,22,8,3}，散列表表長為11，散列函數(shù)為H(key)=keymod11，用線性探測法處理沖突，則散列表為：47729111692292222883333堆積：在處理沖突的過程中出現(xiàn)的非同義詞之間對同一個(gè)散列地址爭奪的現(xiàn)象。0123456789108.4散列表的查找技術(shù)處理沖突的方法——線性探測法當(dāng)發(fā)生沖突時(shí)，尋找下一個(gè)散列地址的公式為：Hi=(H(key)＋d