第8章查找算法（4課時）8.3動態查找及其實現8.5應用實例8.1查找算法及常見查找算法比較8.4哈希查找及其實現8.2靜態查找及其實現目錄查找是指根據給定值從一個數據集合中搜索某個元素的過程。若某個元素的關鍵字值與給定值相等，則查找成功；否則查找失敗。本教材給出的代碼都是基于給定元素K進行查找，即將待查找數據集合中每一元素的關鍵字值與元素K的關鍵字值比較，若相等則查找成功。8.1查找算法及常見查找算法比較查找可以分為靜態查找和動態查找靜態查找只根據給定值在數據集合中按關鍵字查找匹配元素、訪問匹配元素的屬性，而不對數據集合進行插入元素、刪除元素等操作動態查找可能會在查找過程中向數據集合中插入一個新元素或從數據集合中刪除一個已有元素8.1查找算法及常見查找算法比較平均比較次數（也稱為平均查找長度，AverageSearchLength，簡寫為ASL）衡量查找算法性能優劣的標準其中，n是待查找數據集合中的元素數目，pi是查找第i個元素的概率，ci是找到第i個元素所需的比較次數。8.1查找算法及常見查找算法比較8.1查找算法及常見查找算法比較類別查找算法平均查找長度數據集合要求靜態查找順序查找(n+1)/2任何存儲結構，對數據集合無特別要求折半查找log2(n+1)-1數據集合采用順序表存儲結構，且數據集合中的元素是按關鍵字大小有序排列的分塊查找介于順序查找和折半查找之間除了待查找的數據集合外，還需建立一個索引表動態查找二叉排序樹查找O(log2n)采用二叉排序樹作為數據集合的存儲結構哈希查找哈希查找O(1)采用哈希表作為數據集合的存儲結構8.2靜態查找及其實現8.2.1順序查找.8.2.2折半查找8.2.3分塊查找順序查找的步驟按預先規定的順序依次將數據集合中每個元素的關鍵字與給定值進行比較，若某個元素的關鍵字與給定值相同，則查找成功；若遍歷所有元素后，仍沒有找到關鍵字與給定值相同的元素，則查找失敗。8.2靜態查找及其實現8.2.1順序查找【描述8-1】順序查找的算法描述。//根據給定元素K對R進行順序查找template<classT>intSeqSearch(TR[],intnSize,TK){ intnI; R[0]=K; //R[0]作為監視哨

for(nI=nSize;R[nI]!=K;nI--) //從表尾開始向前進行查找

; returnnI;//將匹配元素在數組中的下標返回，查找失敗則返回0}8.2靜態查找及其實現8.2.1順序查找折半查找（二分查找）要求數據集合采用順序表存儲結構，且數據集合中的元素是按關鍵字大小有序排列的。具體步驟為：對于包含n個元素的遞增數據集合R={R[1],R[2],…,R[n]}（R[i]≤R[i+1]），根據給定元素K進行折半查找，初始化待查找數據集合的下標起始位置low=1和結束位置high=n。計算中間元素下標(low+high)/2

，若R[mid]==K，則查找成功，折半查找算法結束；若R[mid]<K，則令low=mid+1；否則，若R[mid]>K，則令high=mid-1。若新的待查找數據集合不為空，即low≤high，則返回到上一步在新的數據集合（R[low],R[low+1],…,R[high]）上繼續進行折半查找；否則查找失敗。8.2靜態查找及其實現.8.2.2折半查找例如，對于一組具有關鍵字值{17,22,28,30,37,43,56,70}的數據元素集合{R1,R2,…,R8}，分別根據給定值k=56和k=25進行折半查找，其過程如圖8-1（a）和（b）所示。8.2靜態查找及其實現.8.2.2折半查找【描述8-2】折半查找的算法描述。//根據給定元素K對R進行折半查找template<classT>intBinSearch(TR[],intnSize,TK){ intlow=1,high=nSize,mid; while(low<=high) { mid=(low+high)/2; if(R[mid]==K) returnmid; //查找成功，返回匹配元素下標

elseif(R[mid]>K) high=mid-1; //在前半部分進行折半查找

else low=mid+1; //在后半部分進行折半查找

} return0; //查找失敗}8.2靜態查找及其實現.8.2.2折半查找分塊查找，又稱索引順序查找，它是順序查找的一種改進算法性能和對待查找數據集合的要求均介于順序查找和折半查找之間除了待查找的數據集合外，還需建立一個索引表待查數據集合與索引表的關系將包含n個元素的待查找數據集合均勻分為b塊（即b個子集合），前b-1塊中元素數目s=n/b，最后一塊中元素數目小于等于s。分塊后塊內元素可以無序，但塊間必須有序，這里假設塊間為遞增排列，即第i+1塊中的任一元素大于第i塊中的任一元素（i<b）。構造一個包含b個元素的索引表，用于記錄每塊的起始位置和最大元素值。8.2靜態查找及其實現8.2.3分塊查找8.2靜態查找及其實現分塊查找算法的具體步驟在索引表中查找，確定待查找元素在哪一塊，由于索引表有序，因此可以使用二分查找算法。在已確定的塊中，進行順序查找。8.2.3分塊查找8.3動態查找及其實現若待查找的數據集合在查找過程中會動態變化，則這樣的查找過程稱為動態查找。動態查找的數據集合通常采用樹型存儲結構，主要有二叉排序樹、平衡二叉樹、紅黑樹、B樹等，這里僅介紹二叉排序樹及基于二叉排序樹的動態查找。8.3動態查找及其實現8.3.1二叉排序樹的定義8.3.3二叉排序樹的查找8.3.2二叉排序樹的生成8.3動態查找及其實現二叉排序樹，又稱二叉查找樹，它或者是一棵空樹，或者是具有如下性質的二叉樹：若它的左子樹非空，則左子樹上所有結點的值均小于根結點的值。若它的右子樹非空，則右子樹上所有結點的值均大于根結點的值。左、右子樹也分別是二叉排序樹。8.3.1二叉排序樹的定義8.3動態查找及其實現8.3.2二叉排序樹的生成8.3動態查找及其實現8.3.2二叉排序樹的生成8.3動態查找及其實現【描述8-6】以遞歸方式實現的二叉排序樹查找的算法描述。template<classT>LinkedNode<T>*SearchBST(LinkedNode<T>*pRoot,TK){ LinkedBinTree<T>btree; Tx; if(pRoot==NULL) //若子樹為空，則查找失敗

returnNULL; btree.GetNodeValue(pRoot,x); if(K==x) //若K等于根結點的值，則查找成功

returnpRoot; elseif(K<x)//若K小于根結點的值，則在左子樹中繼續進行二叉排序樹的查找

returnSearchBST(btree.GetLeftChild(pRoot),K); else //否則，若K大于根結點的值，則在右子樹中繼續進行二叉排序樹的查找

returnSearchBST(btree.GetRightChild(pRoot),K);}8.3.3二叉排序樹的查找8.3動態查找及其實現【例8-1】基于描述8-4至描述8-7中二叉排序樹的C++實現代碼，完成如下操作：創建一個包含整型元素43、56、37、28、17、39、22的二叉排序樹，并顯示二叉排序樹中的所有元素。根據給定值在二叉排序樹中進行查找，若查找成功則輸出找到的元素值，否則輸出“查找失敗”。8.3.3二叉排序樹的查找8.4哈希查找及其實現前面學習的查找算法的查找效率取決于比較的次數。哈希查找采用了一種截然不同的方式，它的思想類似于7.6節學習的分配排序，即直接根據待查找元素的值確定該元素所在的位置。哈希查找利用哈希表（又稱散列表）作為待查找數據集合的存儲結構，與前面學習的查找算法相比，哈希查找具有更高的效率。8.4.1哈希表8.4.2哈希函數8.4哈希查找及其實現8.4.3沖突的處理方法哈希表是線性表的一種重要存儲方式，數據元素自身的值決定了它的存儲位置。哈希表的基本思想確定一函數h，對于關鍵字值是k的元素，以k為自變量計算函數值h(k)，這個函數值被解釋為一片連續存儲空間中的一個地址（即數組中的一個下標值），元素即被存入到這個地址中。8.4哈希查找及其實現8.4.1哈希表例如，對于具有關鍵字值{43,56,37,28,16,30,22}的數據集合R={R1,R2,…,R7}，假設選取的哈希函數為h(k)=k%11，元素存儲在一維數組中，則可得到圖8-7所示的哈希表。8.4哈希查找及其實現8.4.1哈希表8.4哈希查找及其實現常用的哈希函數構造方法除余法數字分析法折疊法平方取中法8.4.2哈希函數開放定址法8.4哈希查找及其實現8.4.3沖突的處理方法拉鏈法8.4哈希查找及其實現8.4.3沖突的處理方法

【例8-2】基于描述8-8中哈希表類的C++實現代碼，完成如下操作：創建一個包含整型元素43、56、37、28、17、39、22的哈希表（其哈希函數為h(x)=x%11），并顯示哈希表中的所有元素。根據給定值在哈希表中進行哈希查找，若查找成功則輸出找到的元素值，否則輸出“查找失敗”。8.4哈希查找及其實現8.4.3沖突的處理方法

編寫學生信息管理程序，要求可以按學號、姓名或成績對學生信息查找。求解思路：在實際中，通常需要按照不同關鍵字對數據集合中的元素進行查找。例如，可以按學號、姓名、成績等查找學生。若是使用順序查找，則只存儲一份學生信息就可以，占