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

全國(guó)高等教育自學(xué)考試指定教材

計(jì)算機(jī)及應(yīng)用專(zhuān)業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第八章查找學(xué)習(xí)目標(biāo)理解查找的基本概念掌握順序查找、折半查找、索引順序查找方法的基本思想及實(shí)現(xiàn)過(guò)程，理解各種查找方法的適用條件理解二叉查找樹(shù)的概念，掌握二叉查找樹(shù)操作的定義及實(shí)現(xiàn)理解AVL樹(shù)的基本概念，掌握AVL樹(shù)基本操作的定義及實(shí)現(xiàn)理解B樹(shù)的概念，掌握插入及查找操作的定義及實(shí)現(xiàn)過(guò)程理解哈希方法中的基本概念，掌握哈希方法能夠?qū)Ω鞑檎曳椒ㄟM(jìn)行比較分析本章主要內(nèi)容查找的基本概念12樹(shù)形結(jié)構(gòu)的查找3順序表的查找哈希表及其查找4第一節(jié)查找的基本概念定義8.1設(shè)有一個(gè)集合T，其中有n個(gè)數(shù)據(jù)項(xiàng)，集合T及其中數(shù)據(jù)項(xiàng)的形式如下 T={(k0,I0),(k1,I1),…,(kn-1,In-1)} k0,k1,…,kn-1是互不相同的關(guān)鍵字值 Ij（0≤j≤n-1）是與關(guān)鍵字值kj相關(guān)的信息給定一個(gè)特定的關(guān)鍵字值K，查找問(wèn)題是在T中確定數(shù)據(jù)項(xiàng)(kj,Ij)，使得kj=K查找表中的數(shù)據(jù)項(xiàng)也稱(chēng)為記錄每個(gè)記錄至少包含一個(gè)關(guān)鍵字記錄中關(guān)鍵字的類(lèi)型可以是能夠進(jìn)行比較操作的任意類(lèi)型第二節(jié)順序表的查找順序查找方法初始時(shí)，將給定的關(guān)鍵字值K與表中第一個(gè)記錄的關(guān)鍵字值相比較，若兩個(gè)值相等則找到目標(biāo)，查找成功；否則將K與表中下一個(gè)記錄的關(guān)鍵字值繼續(xù)比較并判斷是否相等，依此類(lèi)推。如果直到最后一個(gè)記錄的關(guān)鍵字值與K都不相等，則表明所存儲(chǔ)的數(shù)據(jù)中沒(méi)有要查找的目標(biāo)，查找不成功順序表結(jié)構(gòu)順序表保存在一個(gè)數(shù)組中typedefintELEMType;typedefstruct{ ELEMTypeelement[maxSize]; intn; //實(shí)際的元素個(gè)數(shù)}searchList;typedefintposition;順序查找的算法查找的平均查找長(zhǎng)度為(n+1)/2不成功查找的查找次數(shù)為n折半查找方法當(dāng)數(shù)據(jù)按關(guān)鍵字有序存儲(chǔ)時(shí)，可以改進(jìn)順序查找方法折半查找也稱(chēng)為二分查找，其適用條件是數(shù)組中各個(gè)記錄按關(guān)鍵字有序排列，所以折半查找只適用于有序表折半查找并不從有序表的一端開(kāi)始查找，而是從中間開(kāi)始查找給定有序表1115182233456065828697使用折半查找方法查找22，給出查找過(guò)程初始時(shí)查找22的過(guò)程查找85的過(guò)程折半查找的具體算法效率折半查找的平均查找長(zhǎng)度可以用二叉樹(shù)進(jìn)行分析折半查找判定樹(shù)折半查找的平均查找長(zhǎng)度為logn索引順序查找索引順序查找又稱(chēng)為分塊查找，是結(jié)合了順序查找和二分查找特點(diǎn)的一種查找方法，適用于數(shù)據(jù)較多的情況將眾多的數(shù)據(jù)分成若干塊，即將大的查找池分為若干小的查找池每塊中的值可以有序，也可以無(wú)序，但塊與塊之間必須有序第1塊中的所有關(guān)鍵字都小于第2塊中的所有關(guān)鍵字第2塊中的所有關(guān)鍵字都小于第3塊中的所有關(guān)鍵字第i塊中的所有關(guān)鍵值都小于第i+1塊中的所有關(guān)鍵值分塊后，將每個(gè)塊中的最大關(guān)鍵字抽取出來(lái)，按塊的次序保存在一個(gè)一維數(shù)組中。這個(gè)一維數(shù)組稱(chēng)為索引表索引表是個(gè)有序表索引順序查找的基本思想首先查找索引表，確定要查找的關(guān)鍵字可能在哪個(gè)塊中索引表是有序表，所以查找索引表時(shí)可以使用折半查找，當(dāng)然如果索引表較小則也可以使用順序查找然后在確定的塊內(nèi)再進(jìn)行進(jìn)一步的查找在每個(gè)塊內(nèi)，通常使用順序查找。當(dāng)然，如果塊內(nèi)是有序的，也可以使用折半查找第三節(jié)樹(shù)形結(jié)構(gòu)的查找利用樹(shù)形結(jié)構(gòu)來(lái)存儲(chǔ)記錄這些方法不僅能達(dá)到較高的查找效率，也能較好地解決在查找表中插入和刪除記錄的問(wèn)題二叉查找樹(shù)定義8.2二叉查找樹(shù)（binarysearchtree，BST）或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)（1）若它的左子樹(shù)不空，則左子樹(shù)所有結(jié)點(diǎn)保存的記錄的關(guān)鍵字值均小于它的根結(jié)點(diǎn)保存的記錄的關(guān)鍵字值（2）若它的右子樹(shù)不空，則右子樹(shù)所有結(jié)點(diǎn)保存的記錄的關(guān)鍵字值均大于它的根結(jié)點(diǎn)保存的記錄的關(guān)鍵字值（3）它的左子樹(shù)、右子樹(shù)也都是二叉查找樹(shù)結(jié)點(diǎn)類(lèi)及二叉查找樹(shù)的定義typedefintELEMType;typedefstruct BNode //二叉查找樹(shù)結(jié)點(diǎn){ ELEMTypedata; //數(shù)據(jù)域 structBNode*left,*right; //指向左孩子、右孩子的指針}BstTNode;typedefBstTNode*BstTree;二叉查找樹(shù)的查找從根結(jié)點(diǎn)開(kāi)始，如果根結(jié)點(diǎn)的關(guān)鍵字等于查找目標(biāo)target，則查找成功如果目標(biāo)target小于根結(jié)點(diǎn)的關(guān)鍵字值，則在它的左子樹(shù)繼續(xù)查找如果目標(biāo)target大于根結(jié)點(diǎn)的關(guān)鍵字值，則在它的右子樹(shù)繼續(xù)查找依此類(lèi)推在BST中的查找，是沿著從根到葉結(jié)點(diǎn)的一條路徑向下查找，如果在路徑中某結(jié)點(diǎn)的關(guān)鍵字值與目標(biāo)相等，則查找成功，返回1；若遇到空指針則表示查找失敗，返回0，表示二叉查找樹(shù)中不存在查找目標(biāo)target示例在下面的二叉查找樹(shù)中，分別查找關(guān)鍵字為82和37二叉查找樹(shù)的查找算法采用遞歸程序方式二叉查找樹(shù)的查找算法采用迭代實(shí)現(xiàn)方式二叉查找樹(shù)的生成二叉查找樹(shù)的生成就是從空樹(shù)開(kāi)始依次將結(jié)點(diǎn)插入到樹(shù)中的過(guò)程若二叉查找樹(shù)為空，則新結(jié)點(diǎn)為二叉查找樹(shù)的根結(jié)點(diǎn)；若二叉查找樹(shù)非空，則比較新結(jié)點(diǎn)的關(guān)鍵字值和根結(jié)點(diǎn)的關(guān)鍵字值，若新結(jié)點(diǎn)關(guān)鍵字小于根結(jié)點(diǎn)關(guān)鍵字，則新結(jié)點(diǎn)插入到根的左子樹(shù)中，否則插入到根的右子樹(shù)中插入新結(jié)點(diǎn)的算法示例在如下的BST中依次插入關(guān)鍵字58和17示例從空樹(shù)開(kāi)始，依次插入關(guān)鍵字分別為h,a,r,d的結(jié)點(diǎn)，建立一棵二叉查找樹(shù)二叉查找樹(shù)的刪除假設(shè)要?jiǎng)h除的結(jié)點(diǎn)為x，它的雙親結(jié)點(diǎn)是f，不失一般性，設(shè)x為f的左孩子，分三種情況考慮x的度為0，即x為葉結(jié)點(diǎn)，此種情況最為簡(jiǎn)單，刪除該結(jié)點(diǎn)后，只須令f的左孩子指針為空即可x的度為1，即x只有左子樹(shù)LTree或只有右子樹(shù)RTree，刪除x結(jié)點(diǎn)后，只須令LTree或RTree直接成為其雙親結(jié)點(diǎn)f的左子樹(shù)即可。x的度為2，即x結(jié)點(diǎn)的左、右子樹(shù)均不空，這種情況比較復(fù)雜，可采用兩種辦法以x的直接前驅(qū)w來(lái)頂替它，再刪除w以x的直接后繼u來(lái)頂替它，再刪除u刪除示例分別刪除關(guān)鍵字45和60所在的結(jié)點(diǎn)同一組關(guān)鍵字，如果插入次序改變了，則可能會(huì)生成不同的二叉查找樹(shù)二叉查找樹(shù)的高度不僅決定了查找時(shí)最大的比較次數(shù)，也影響了平均查找長(zhǎng)度一般來(lái)說(shuō)，對(duì)于n個(gè)記錄，當(dāng)它們的關(guān)鍵字隨機(jī)出現(xiàn)時(shí)，所構(gòu)成的二叉查找樹(shù)還是比較均衡的。在這樣的二叉查找樹(shù)上進(jìn)行查找，其查找成功的平均查找長(zhǎng)度為O(logn)AVL樹(shù)兩位數(shù)學(xué)家Adel’son-Vel’skii和Landis在1962年提出了一種新的樹(shù)結(jié)構(gòu)在二叉查找樹(shù)的每個(gè)結(jié)點(diǎn)中增加一個(gè)標(biāo)記，稱(chēng)為平衡因子，定義為該結(jié)點(diǎn)左子樹(shù)的高度減去右子樹(shù)的高度當(dāng)每個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值不大于1時(shí)，稱(chēng)二叉查找樹(shù)為AVL樹(shù)AVL樹(shù)是平衡的，有的教材也稱(chēng)為平衡二叉樹(shù)樹(shù)定義8-3AVL樹(shù)或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉查找樹(shù)：（1）它的左子樹(shù)和右子樹(shù)都是AVL樹(shù)（2）它的左子樹(shù)和右子樹(shù)的高度之差的絕對(duì)值不大于1若二叉排序樹(shù)中所有結(jié)點(diǎn)的平衡因子均介于-1到+1之間時(shí)，稱(chēng)樹(shù)是平衡的，否則稱(chēng)為失平衡例8-12高度為4的AVL樹(shù)中，最少有多少個(gè)結(jié)點(diǎn)？解：有7個(gè)結(jié)點(diǎn)在所有等高的AVL樹(shù)中，滿足“除葉結(jié)點(diǎn)外，每個(gè)分支結(jié)點(diǎn)的平衡因子是-1或+1”條件的AVL樹(shù)所含的結(jié)點(diǎn)個(gè)數(shù)最少高度為0的AVL樹(shù)所含結(jié)點(diǎn)個(gè)數(shù)為0。高度為1的AVL樹(shù)僅含有1個(gè)結(jié)點(diǎn)。高度為2的AVL樹(shù)，一棵子樹(shù)的高度為1，另一棵子樹(shù)的高度為0，樹(shù)中含有的結(jié)點(diǎn)個(gè)數(shù)=1+0+1=2。依此類(lèi)推。AVL樹(shù)的查找AVL樹(shù)是滿足平衡條件的特殊二叉查找樹(shù)，AVL樹(shù)的查找過(guò)程與二叉查找樹(shù)的查找過(guò)程是一樣的AVL樹(shù)的插入從空樹(shù)開(kāi)始，向AVL樹(shù)中逐個(gè)插入關(guān)鍵字，生成AVL樹(shù)。每插入一個(gè)關(guān)鍵字，都要保證得到的樹(shù)是平衡的。將關(guān)鍵字插入AVL樹(shù)的過(guò)程分以下兩個(gè)步驟：①按照二叉查找樹(shù)的插入規(guī)則，將關(guān)鍵字插入到AVL樹(shù)中②如果得到的新樹(shù)是平衡的，則插入完成，否則進(jìn)行相應(yīng)的旋轉(zhuǎn)以恢復(fù)平衡共有四種旋轉(zhuǎn)稱(chēng)為RR型如果u插入在v右子結(jié)點(diǎn)的右子樹(shù)中（稱(chēng)為RR型），則進(jìn)行向左的單旋轉(zhuǎn)LL型旋轉(zhuǎn)RL型LR型雙旋轉(zhuǎn)例8-13將下列關(guān)鍵字添加到初始為空的AVL樹(shù)中，畫(huà)出生成樹(shù)的過(guò)程

70,80,90,20,10,50,60,40,30B樹(shù)定義8.3一棵m階B樹(shù)或者為空，或者為滿足下列性質(zhì)的m叉樹(shù)樹(shù)中每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)；根結(jié)點(diǎn)至少有兩棵子樹(shù)；除根結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)至少有

m/2

棵子樹(shù)；所有葉結(jié)點(diǎn)都出現(xiàn)在同一層上；所有結(jié)點(diǎn)都包含如下形式的數(shù)據(jù)：

（n,A0,K1,A1,K2,A2,…,Kn,An）其中n為關(guān)鍵字的個(gè)數(shù)Ki(i=1,2,…,n)為關(guān)鍵字，且滿足K1<K2<…<KnAi(i=0,1,…,n)為指向子樹(shù)根結(jié)點(diǎn)的指針，且對(duì)于i=1,2,…,n-1Ai所指子樹(shù)中全部結(jié)點(diǎn)的關(guān)鍵字均大于Ki而小于Ki+1A0所指子樹(shù)中全部結(jié)點(diǎn)的關(guān)鍵字均小于K1An所指子樹(shù)中全部結(jié)點(diǎn)的關(guān)鍵字均大于Kn對(duì)于葉結(jié)點(diǎn)，所有指針Ai皆為空。對(duì)于具有n個(gè)關(guān)鍵字的非葉結(jié)點(diǎn)，將有n+1棵子樹(shù)一棵3階(m=3)B樹(shù)每個(gè)結(jié)點(diǎn)中或者含有一個(gè)關(guān)鍵字，或者含有兩個(gè)關(guān)鍵字B樹(shù)的查找類(lèi)似二叉查找樹(shù)中的查找方法在如下的B樹(shù)中，分別查找關(guān)鍵字I和MB樹(shù)的建立建立B樹(shù)的過(guò)程，即是從空樹(shù)開(kāi)始逐個(gè)插入關(guān)鍵字的過(guò)程給定數(shù)據(jù)序列如下18,15,41,10,45,30,25,3,71,60,50,72依次插入到初始為空的5階B樹(shù)中第四節(jié)哈希表及其查找哈希方法使用的存儲(chǔ)結(jié)構(gòu)是數(shù)組，它采用特殊的機(jī)制存放數(shù)據(jù)哈希方法把關(guān)鍵字值映射到數(shù)組中的一個(gè)位置，這通過(guò)一個(gè)函數(shù)來(lái)實(shí)現(xiàn)，這個(gè)函數(shù)稱(chēng)為哈希函數(shù)，通常用H來(lái)表示存放記錄的數(shù)組稱(chēng)為哈希表，用T來(lái)表示哈希表中的一個(gè)位置也稱(chēng)為一個(gè)槽從數(shù)據(jù)存放到數(shù)據(jù)訪問(wèn)的整套機(jī)制稱(chēng)為哈希方法示例某個(gè)高校參加夏令營(yíng)的學(xué)生全部住在一棟宿舍大樓內(nèi)，該樓的樓層足夠高，樓中每層有足夠多的房間，每個(gè)房間內(nèi)只住一位學(xué)生為了便于管理和查詢(xún)，現(xiàn)以學(xué)生的姓名（假設(shè)不超過(guò)三個(gè)漢字）為關(guān)鍵字，以姓名的漢字筆劃數(shù)作為關(guān)鍵字的值，來(lái)決定他（她）所住的房間號(hào)，其中姓的筆劃數(shù)決定樓層號(hào)，名字的筆劃數(shù)決定本層的房間號(hào)又有一位名叫卞云的學(xué)生加入夏令營(yíng)，她的姓名編碼是404，可是404號(hào)房間已經(jīng)安排了學(xué)生王方，不能再住第二個(gè)人了。這就帶來(lái)了問(wèn)題，這種情況稱(chēng)為發(fā)生了“沖突”學(xué)生姓名房間號(hào)丁

一201于

立305王

方404田小華536劉力文624李中元744┆┆哈希方法需要解決的問(wèn)題有兩個(gè)選擇什么樣的哈希函數(shù)當(dāng)有沖突發(fā)生時(shí)，如何解決沒(méi)有“沖突”的哈希函數(shù)稱(chēng)為完美哈希函數(shù)哈希函數(shù)的構(gòu)造方法構(gòu)造哈希函數(shù)時(shí)通常考慮的因素有計(jì)算哈希函數(shù)所需要的時(shí)間關(guān)鍵字的長(zhǎng)度哈希表的大小關(guān)鍵字的分布情況記錄的查找頻率構(gòu)造哈希函數(shù)的基本原則是算法簡(jiǎn)單，運(yùn)算量小均勻分布，減少?zèng)_突直接定址法哈希函數(shù)是關(guān)鍵字值的線性函數(shù)，H(k)=k或H(k)=a

k+b，其中a、b為常數(shù)設(shè)要統(tǒng)計(jì)某地區(qū)從1949年到2000年每年的出生人數(shù)，此時(shí)年份為關(guān)鍵字。H(k)=k-1949即可，其中k為年份數(shù)平方取中法一個(gè)數(shù)自乘后，乘積的中間幾位既能反映原數(shù)低位的情況，也能反映原數(shù)高位的情況關(guān)鍵字機(jī)內(nèi)代碼機(jī)內(nèi)代碼的平方數(shù)哈希地址ABCBCDCDEXYZ┆010203020304030405242526┆01041012090412252416092446402558818860676┆410225446886┆折疊法折疊法是另一類(lèi)處理多位關(guān)鍵字的方法。當(dāng)關(guān)鍵字的位數(shù)較多，遠(yuǎn)超過(guò)哈希表地址的范圍時(shí)，可將關(guān)鍵字分割為位數(shù)相等的幾段，然后將各段疊加，疊加后將最高位的進(jìn)位舍去，所得結(jié)果即為哈希地址關(guān)鍵字值k=123203241712，將k按三位分段為123,203,241,712。相加并去掉進(jìn)位得到哈希地址為279也可以間隔地讓分段后的數(shù)反轉(zhuǎn)再相加基數(shù)轉(zhuǎn)換法將關(guān)鍵字值先看成另一種進(jìn)制的數(shù)，然后轉(zhuǎn)換成原來(lái)進(jìn)制的數(shù)（例如十進(jìn)制），再選其中的幾位作為哈希地址如十進(jìn)制的關(guān)鍵字值210485，把它看成十三進(jìn)制的數(shù)后，再轉(zhuǎn)換成十進(jìn)制數(shù) 21048513=2

135+1

134+0

133+4

132+8

13+5=77193210然后從中選幾位作為哈希地址即可通常要求兩個(gè)基數(shù)互素，且新基數(shù)要比原基數(shù)大除留余數(shù)法設(shè)給出關(guān)鍵字值為k，哈希表長(zhǎng)度為m，則設(shè)計(jì)哈希函數(shù)為： H(k)=kmodp其中p為小于等于m的某個(gè)正整數(shù)。理論分析和試驗(yàn)結(jié)果均證明，p應(yīng)取小于等于表長(zhǎng)m的最大素?cái)?shù)處理沖突的方法給定一個(gè)哈希函數(shù)H和兩個(gè)關(guān)鍵字k1、k2，如果H(k1)=b=H(k2)，其中b是哈希表中的一個(gè)位置，則稱(chēng)k1和k2在哈希函數(shù)H下對(duì)于b有沖突有兩種處理方法一類(lèi)稱(chēng)為開(kāi)放地址法，也叫閉哈希法另一類(lèi)稱(chēng)為鏈地址法，也叫開(kāi)哈希法開(kāi)放地址法這一類(lèi)解決沖突的精髓是如何得到下一個(gè)空閑地址。最常用的是如下兩種確定探測(cè)序列的方式線性探測(cè)法二次探測(cè)法線性探測(cè)法假設(shè)哈希表長(zhǎng)度為m，地址為0～m-1，哈希函數(shù)為H(k)。求下一地址的公式是 di+1=(di+1)modm其中d1=H(k)這個(gè)方法的思想是從哈希地址基位置H(k)出發(fā)，依次探查后面一個(gè)位置、后面二個(gè)位置、…去尋找空閑地址。當(dāng)?shù)竭_(dá)哈希表位置m-1時(shí)，再返回到哈希表頭繼續(xù)探查。即將哈希表看成是循環(huán)的在這個(gè)探查過(guò)程中，如果哈希表不滿，則一定能夠找到一個(gè)空位置，將記錄放入哈希表中如果轉(zhuǎn)了一圈又回到基位置d1，仍未找到空閑位置，則表明哈希表已滿二次探測(cè)法用二次探測(cè)法解決沖突時(shí)，求下一空閑地址的公式是： d2i=(d1+i2)modm d2i+1=(d1-i2)modm (i=1,2,…)其中d1=H(k)這個(gè)方法的基本思想是以哈希地址基位置H(k)為中心，跳躍式地向兩邊搜索下一地址。即探查的地址序列為；d1+12,d1-12,d1+22,d1-22,d1+32,d1-32,…仍是將哈希表看成是循環(huán)的，而且是雙向循環(huán)的。即如果下標(biāo)變大越過(guò)表尾，則返回表頭繼續(xù)；如果下標(biāo)變小越過(guò)表頭，則返回表尾繼續(xù)二次探測(cè)法因?yàn)槭翘S式地查找空閑地址，有可能不能遍歷哈希表中的所有位置。所以即使哈希表不滿，也可能找不到空閑位置有研究表明，當(dāng)哈希表的表長(zhǎng)為素?cái)?shù)，且