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

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

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

; returnnI;//將匹配元素在數(shù)組中的下標(biāo)返回，查找失敗則返回0}8.2靜態(tài)查找及其實(shí)現(xiàn)8.2.1順序查找折半查找（二分查找）要求數(shù)據(jù)集合采用順序表存儲(chǔ)結(jié)構(gòu)，且數(shù)據(jù)集合中的元素是按關(guān)鍵字大小有序排列的。具體步驟為：對(duì)于包含n個(gè)元素的遞增數(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。計(jì)算中間元素下標(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)查找及其實(shí)現(xiàn).8.2.2折半查找例如，對(duì)于一組具有關(guān)鍵字值{17,22,28,30,37,43,56,70}的數(shù)據(jù)元素集合{R1,R2,…,R8}，分別根據(jù)給定值k=56和k=25進(jìn)行折半查找，其過(guò)程如圖8-1（a）和（b）所示。8.2靜態(tài)查找及其實(shí)現(xiàn).8.2.2折半查找【描述8-2】折半查找的算法描述。//根據(jù)給定元素K對(duì)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)查找及其實(shí)現(xiàn).8.2.2折半查找分塊查找，又稱索引順序查找，它是順序查找的一種改進(jìn)算法性能和對(duì)待查找數(shù)據(jù)集合的要求均介于順序查找和折半查找之間除了待查找的數(shù)據(jù)集合外，還需建立一個(gè)索引表待查數(shù)據(jù)集合與索引表的關(guān)系將包含n個(gè)元素的待查找數(shù)據(jù)集合均勻分為b塊（即b個(gè)子集合），前b-1塊中元素?cái)?shù)目s=n/b，最后一塊中元素?cái)?shù)目小于等于s。分塊后塊內(nèi)元素可以無(wú)序，但塊間必須有序，這里假設(shè)塊間為遞增排列，即第i+1塊中的任一元素大于第i塊中的任一元素（i<b）。構(gòu)造一個(gè)包含b個(gè)元素的索引表，用于記錄每塊的起始位置和最大元素值。8.2靜態(tài)查找及其實(shí)現(xiàn)8.2.3分塊查找8.2靜態(tài)查找及其實(shí)現(xiàn)分塊查找算法的具體步驟在索引表中查找，確定待查找元素在哪一塊，由于索引表有序，因此可以使用二分查找算法。在已確定的塊中，進(jìn)行順序查找。8.2.3分塊查找8.3動(dòng)態(tài)查找及其實(shí)現(xiàn)若待查找的數(shù)據(jù)集合在查找過(guò)程中會(huì)動(dòng)態(tài)變化，則這樣的查找過(guò)程稱為動(dòng)態(tài)查找。動(dòng)態(tài)查找的數(shù)據(jù)集合通常采用樹(shù)型存儲(chǔ)結(jié)構(gòu)，主要有二叉排序樹(shù)、平衡二叉樹(shù)、紅黑樹(shù)、B樹(shù)等，這里僅介紹二叉排序樹(shù)及基于二叉排序樹(shù)的動(dòng)態(tài)查找。8.3動(dòng)態(tài)查找及其實(shí)現(xiàn)8.3.1二叉排序樹(shù)的定義8.3.3二叉排序樹(shù)的查找8.3.2二叉排序樹(shù)的生成8.3動(dòng)態(tài)查找及其實(shí)現(xiàn)二叉排序樹(shù)，又稱二叉查找樹(shù)，它或者是一棵空樹(shù)，或者是具有如下性質(zhì)的二叉樹(shù)：若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值。若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。左、右子樹(shù)也分別是二叉排序樹(shù)。8.3.1二叉排序樹(shù)的定義8.3動(dòng)態(tài)查找及其實(shí)現(xiàn)8.3.2二叉排序樹(shù)的生成8.3動(dòng)態(tài)查找及其實(shí)現(xiàn)8.3.2二叉排序樹(shù)的生成8.3動(dòng)態(tài)查找及其實(shí)現(xiàn)【描述8-6】以遞歸方式實(shí)現(xiàn)的二叉排序樹(shù)查找的算法描述。template<classT>LinkedNode<T>*SearchBST(LinkedNode<T>*pRoot,TK){ LinkedBinTree<T>btree; Tx; if(pRoot==NULL) //若子樹(shù)為空，則查找失敗

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

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

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

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

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

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