全國高等教育自學考試指定教材

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

70,80,90,20,10,50,60,40,30B樹定義8.3一棵m階B樹或者為空，或者為滿足下列性質的m叉樹樹中每個結點至多有m棵子樹；根結點至少有兩棵子樹；除根結點之外，每個結點至少有

m/2

棵子樹；所有葉結點都出現在同一層上；所有結點都包含如下形式的數據：

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

一201于

立305王

方404田小華536劉力文624李中元744┆┆哈希方法需要解決的問題有兩個選擇什么樣的哈希函數當有沖突發生時，如何解決沒有“沖突”的哈希函數稱為完美哈希函數哈希函數的構造方法構造哈希函數時通常考慮的因素有計算哈希函數所需要的時間關鍵字的長度哈希表的大小關鍵字的分布情況記錄的查找頻率構造哈希函數的基本原則是算法簡單，運算量小均勻分布，減少沖突直接定址法哈希函數是關鍵字值的線性函數，H(k)=k或H(k)=a

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

135+1

134+0

133+4

132+8

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