數(shù)據(jù)結(jié)構(gòu)與算法8

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

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

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

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

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

else low=mid+1; //在后半部分進(jìn)行折半查找

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

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

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

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

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

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