Searching 查找運(yùn)算是計(jì)算機(jī)中最常用的操作課件

1、第九章. 查找 （Chapter 9. Searching) 查找運(yùn)算是計(jì)算機(jī)中最常用的操作之一。有人統(tǒng)計(jì)過(guò)，計(jì)算機(jī)大約有40%的運(yùn)算是與查找相關(guān)的。 數(shù)據(jù)元素（或記錄）的某個(gè)數(shù)據(jù)項(xiàng)，能用來(lái)標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。若能唯一的標(biāo)識(shí)一個(gè)數(shù)據(jù)元素， 則稱為主關(guān)鍵字（primary key），反之則為次關(guān)鍵字（secondary key）。關(guān)鍵字（key）查找表（search table）9.1 靜態(tài)表的查找查找（searching） 根據(jù)某個(gè)給定的值，在查找表中找尋關(guān)鍵字等于給定值的數(shù)據(jù)元素（或記錄）。若表中存在這樣的數(shù)據(jù)元素，則稱查找是成功的，查找結(jié)果即為查找到的數(shù)據(jù)元素；反之則稱查找是不成功的，此時(shí)查

2、找結(jié)果為空。 由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。表中的元素基本上是固定的，這類查找表稱為靜態(tài)查找表（static search table）；若在查找過(guò)程中將不存在的元素插入查找表中，則稱這類查找表為動(dòng)態(tài)查找表（dynamic search table）。 實(shí)際查找時(shí)，通常將給定值放在第 0 個(gè)記錄處，然后從后向前查找，直到找到所查記錄為止，找不到則返回結(jié)果 0。因?yàn)橛涗?0 像哨兵一樣看守著查找表下界，所以不會(huì)越界。typedef struct keytype key; . . . . . . elemtype;一、無(wú)序表的查找：查找表中的各元素（或記錄）的關(guān)鍵字的值是無(wú)序的。typ

3、edef struct elemtype * elem; int length; sstable;int seqsearch ( sstable R, keytype K ) R.elem0.key := K; for ( i = R.length ; R.elemi.key != K ; i - ) ; return i;查找表的長(zhǎng)度為 n：查找性能分析：平均查找長(zhǎng)度（average search length） 為了確定記錄在查找表中的位置，需與給定值比較的關(guān)鍵字的個(gè)數(shù)的期望值稱為平均查找長(zhǎng)度。在等概率情況下，順序查找有序表的平均查找長(zhǎng)度為： ASL成功 = （n+1) / 2 和 ASL

4、不成功 = （n+2) / 2 。有序表的查找比較好的方法是折半查找（binary search）： 將給定值與中間的記錄進(jìn)行比較，若找到則查找成功；否則若給定值比中間記錄小，則對(duì)前一半子表進(jìn)行折半查找，反之則對(duì)后一半子表進(jìn)行折半查找。若在查找過(guò)程中，遇到查找子表的上界小于下界，則表示查找失敗。int seqsearch ( sstable R, keytype K ) R.elem0.key := K; for ( i = R.length ; R.elemi.key K ; i - ) ; if (R.elemi.key=K) return i; else return 0;int bin

5、search ( sstable R , keytype K ) low = 1; high = R.length; while ( low K ) high = mid-1; else low = mid+1; return 0;查找性能分析： 折半查找每次只查表的一半，其所有記錄的查找路徑構(gòu)成一棵二叉樹，稱為折半查找樹（或判定樹），每次查找只走了該樹的一條分支，故平均查找長(zhǎng)度不超過(guò) log2n + 1。 有一組記錄的關(guān)鍵字為1，2，3，4，5，6，7，8，求其在等概率情況下查找成功的平均查找長(zhǎng)度： 例：42516378其查找樹如左圖所示：ASL成功 = = 21 / 8 。1*1+2*2+

6、3*4+4*18 有序表的查找也可用其它的查找方法，如費(fèi)波拉契查找（Fibonacci search）。 設(shè)查找表記錄數(shù)為某個(gè)費(fèi)波拉契數(shù)減一，即 n=Fu-1，則可將給定值與第Fu -1個(gè)記錄比較，若比其小，則在1 Fu -1-1 記錄間查找，否則在Fu -1+1 Fu-1記錄間查找 。如下圖所示：4251637 若有序表的關(guān)鍵字是均勻分布的，則還可用插值查找方法，其平均性能在記錄數(shù)較多時(shí)比折半查找好：將給定值先與第 i 個(gè)記錄比較，則 i = n。K- rL.keyrH.key- rL.key作 業(yè)25. 查找序列以帶頭結(jié)點(diǎn)的單鏈表表示，各結(jié)點(diǎn)中設(shè)一個(gè)訪問(wèn)頻度，初始值為 0，每次查找成功后該

7、結(jié)點(diǎn)頻度值增加 1。試給出算法，在每次查找后查找序列均按訪問(wèn)頻度從大到小排列。 查找效率最高即平均查找長(zhǎng)度最小，根據(jù)前面所學(xué)知識(shí)，我們可以給出有序表在非等概率情況下應(yīng)遵循的兩個(gè)原則：1、最先訪問(wèn)的結(jié)點(diǎn)應(yīng)是訪問(wèn)概率最大的結(jié)點(diǎn)；2、每次訪問(wèn)應(yīng)使結(jié)點(diǎn)兩邊尚未訪問(wèn)的結(jié)點(diǎn)的被訪概 率之和盡可能相等。三、靜態(tài)樹表的查找： 前面介紹的有序表查找都是在“等概率”情況下的，若在非等概率情況下應(yīng)該怎樣查找才能使查找效率更高了？ 這樣的樹稱為靜態(tài)最優(yōu)查找樹（static optimal search tree），構(gòu)造這樣一棵樹的時(shí)間代價(jià)太大，亦即時(shí)間復(fù)雜度很大，因此我們通常是構(gòu)造次優(yōu)查找樹（nearly optim

8、al search tree），構(gòu)造它的時(shí)間代價(jià)遠(yuǎn)遠(yuǎn)低于構(gòu)造最優(yōu)查找樹，但查找性能只比最優(yōu)查找樹差1%2%，很少差3%以上。 這兩個(gè)原則可用一句話來(lái)表示，即判定樹為帶權(quán)內(nèi)路徑長(zhǎng)度之和最小的二叉樹，亦即： PH = wihi 最小，其中 n 為有序表長(zhǎng)度，hi 為第 i 個(gè)結(jié)點(diǎn)在判定樹上的層次數(shù)，wi = cpi，c 為某個(gè)常數(shù)，pii =1n為第 i 個(gè)結(jié)點(diǎn)的查找概率。次優(yōu)查找樹的構(gòu)造： 設(shè)有序表每個(gè)記錄的權(quán)值為 wl,wl+1,wh，第一個(gè)應(yīng)訪問(wèn)的結(jié)點(diǎn)號(hào)為 i ，則有：pi = wj - wj 最小，即 pi = Min pj 再分別對(duì) rl,rl+1,ri-1 和 ri+1,ri+2,rh

9、 分別構(gòu)造次優(yōu)查找樹。j =i +1j =lhi - lljh為便于計(jì)算，引入累計(jì)權(quán)值swi=wj，并設(shè)wl-1=swl-1=0，則：j=liwjj =i +1hwjj =li -1swi-1 - swl-1 =swh - swi =pi = | swh + swl-1 - swi - swi-1 |35689311013最大關(guān)鍵字起始地址索引表231611356283125194157689375886913245678910111213141516順序表9.2 動(dòng)態(tài)表的查找一、二叉排序樹： 二叉排序樹（binary sort tree）或者為空樹，或者為這樣一棵樹：根結(jié)點(diǎn)的左子樹的所有結(jié)點(diǎn)

10、的關(guān)鍵字值均比根結(jié)點(diǎn)的關(guān)鍵字值?。桓Y(jié)點(diǎn)的右子樹的所有結(jié)點(diǎn)的關(guān)鍵字值均比根結(jié)點(diǎn)的關(guān)鍵字值大；根結(jié)點(diǎn)的左右子樹也是二叉排序樹。 二叉排序樹是動(dòng)態(tài)查找樹，即在查找時(shí)將未找到的給定值的記錄插入到查找樹中，查找樹是動(dòng)態(tài)生成的。 54 32 25 9 94 73 68有查找請(qǐng)求 54、32、54、25、73、25、94、68、32、73、9，查找結(jié)果如下：例：查找失敗查找失敗查找成功查找失敗查找失敗查找成功查找失敗查找失敗查找成功查找成功查找失敗二叉排序樹的查找：若當(dāng)前結(jié)點(diǎn)指針為空或當(dāng)前結(jié)點(diǎn)為所找結(jié)點(diǎn)則返回當(dāng)前指針；若當(dāng)前結(jié)點(diǎn)關(guān)鍵字值比給定值大則繼續(xù)查找當(dāng)前結(jié)點(diǎn)的左子樹；否則就繼續(xù)查找當(dāng)前結(jié)點(diǎn)的右子樹。

11、二叉排序樹的插入：先用給定值查找二叉排序樹，查找成功則返回所找結(jié)點(diǎn)指針；否則在找不到時(shí)的葉結(jié)點(diǎn)的左子樹或右子樹處插入給定值記錄。（新插入的結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)）二叉排序樹的刪除：若將刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)，直接刪除即可；若將刪除的結(jié)點(diǎn)只有左子樹或只有右子樹，則可用左孩子或右孩子直接替換將要?jiǎng)h除結(jié)點(diǎn)位置；若將刪除的結(jié)點(diǎn)左、右子樹均存在，則可用將要?jiǎng)h除結(jié)點(diǎn)左子樹的最右結(jié)點(diǎn)（關(guān)鍵字值最大的結(jié)點(diǎn)）替換將要?jiǎng)h除結(jié)點(diǎn)，用替換結(jié)點(diǎn)的左子樹（若存在）替換“替換結(jié)點(diǎn)”。二叉排序樹的查找分析：ASL與二叉排序樹的高度有關(guān)。由于二叉排序樹是根據(jù)查找請(qǐng)求序列建立的，因此很可能退化成為線性表（什么情況下？），如何解決這一問(wèn)

12、題呢？二、平衡二叉樹： 平衡二叉樹（balanced binary tree) 又稱 AVL樹(G. M. Adelson-Velskii & Y. M. Landis. An algorithm for the organization of information. Soviet Math. Dokl., 3:1259-1262, 1962.) ，它具有如下性質(zhì)：或者為空樹，或者根結(jié)點(diǎn)的左、右子樹也均為平衡二叉樹，且左、右子樹的樹高之差的絕對(duì)值不超過(guò)1。平衡因子（balance factor）：結(jié)點(diǎn)的左子樹高度減去右子樹高度的值稱為該結(jié)點(diǎn)的平衡因子。因此平衡二叉樹也可以這樣定義：平衡二叉樹

13、是所有結(jié)點(diǎn)的平衡因子的絕對(duì)值均小于2的二叉樹。我們談?wù)摰钠胶舛鏄淦鋵?shí)是平衡二叉排序樹。平衡二叉樹的插入：平衡二叉樹插入時(shí)分為四種類型：LL型、LR型、RL型和RR型。 1、將新的結(jié)點(diǎn)插入在平衡二叉樹中，沿著剛插入的結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑修改所經(jīng)過(guò)結(jié)點(diǎn)的平衡因子，直到找到某結(jié)點(diǎn)A 的 平衡因子為 2 或修改完根結(jié)點(diǎn)的平衡因子后仍為平衡二叉樹。 2、若結(jié)點(diǎn)A 的平衡因子為2 ，則需進(jìn)行調(diào)整，設(shè) A 的兒子和孫子（剛經(jīng)過(guò)的結(jié)點(diǎn)）分別為 B 和 C，則有： A B C A C BLR0-12000 A B CRL0 1-2 B C A000 A B C A B CLL012000 A B C C B A

14、RR0-1-2000# JAN FEB APR AUG MAR JUN MAY JUL JAN FEB MAR APR MAY JUN JUL AUG SEP OCT 有一組關(guān)鍵字序列JAN、FEB、MAR、APR、MAY、JUN、JUL、AUG、SEP、OCT、NOV、DEC，以此建立 AVL 樹。 例：LR AUG0 APR-1 FEB2 OCT0 SEP1 MAY-2 SEP OCT JAN FEB MAR APR MAY JUN JUL AUG NOV DEC NOV SEP OCT JAN FEB MAR APR MAY JUN JUL AUGRLRR OCT1 MAR-1 JAN-

15、2含有 n 個(gè)關(guān)鍵字的平衡二叉樹的最大深度為多少？平衡二叉樹的查找分析： 用 Nh 表示深度為 h 的平衡二叉樹含有的最少結(jié)點(diǎn)數(shù)，則：N0 = 0、N1 = 1、N2 = 2、Nh = Nh -1 + Nh -2 + 1 = h+2/5-1，其中 = （1 +5 ）/ 2，則含有 n 個(gè)結(jié)點(diǎn)的平衡二叉樹的最大深度為 log(5 ( n + 1) - 2，因此，平衡二叉樹查找的時(shí)間復(fù)雜度為 O ( log n )。三、B 樹 B 樹是一種平衡的多路查找樹，主要應(yīng)用在文件系統(tǒng)中。一棵 m 階的 B 樹，或?yàn)榭諛?，或?yàn)闈M足下列特性的 m 叉樹： 1、樹中每個(gè)結(jié)點(diǎn)最多有 m 棵子樹； 2、若根結(jié)點(diǎn)不是

16、葉子結(jié)點(diǎn)，則最少有兩棵子樹；3、除根之外的所有非終端結(jié)點(diǎn)最少有 m / 2 棵子樹；4、所有非終端結(jié)點(diǎn)包含 （n,A0,K1,A1,K2,Kn,An）信息數(shù)據(jù)； 5、所有葉子結(jié)點(diǎn)在同一層上，且不帶信息。 其中n為結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)，Ai為指向子樹的指針，Ki為關(guān)鍵字。B 的查找： B 樹是一棵平衡的多路排序樹，只是每個(gè)結(jié)點(diǎn)的關(guān)鍵字不只一個(gè)，因此整棵樹的查找方法與二叉排序樹的查找相似，只需對(duì)每個(gè)結(jié)點(diǎn)內(nèi)部實(shí)行順序查找。 具有 N 個(gè)關(guān)鍵字的 B 樹深度不超過(guò) ( log m / 2 ( N+1 ) / 2 ) + 1。2、被刪關(guān)鍵字所在結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù) = m / 2 - 1 ，而與該結(jié)點(diǎn)相鄰的兄弟

17、結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù) m / 2 ，則需將其兄弟結(jié)點(diǎn)中靠近該結(jié)點(diǎn)的關(guān)鍵字上移至父母結(jié)點(diǎn)中，再?gòu)母改附Y(jié)點(diǎn)中下移一個(gè)緊挨剛才上移關(guān)鍵字的關(guān)鍵字到該結(jié)點(diǎn)中，然后從該結(jié)點(diǎn)中刪去該關(guān)鍵字即可；3、被刪關(guān)鍵字所在結(jié)點(diǎn)及其相鄰的兄弟結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)均等于 m / 2 - 1，設(shè)其父母結(jié)點(diǎn)指向其兄弟結(jié)點(diǎn)的指針為 Ai ，則從該結(jié)點(diǎn)中刪除該關(guān)鍵字后，將該結(jié)點(diǎn)中剩余的關(guān)鍵字和父母結(jié)點(diǎn)中的 Ki 關(guān)鍵字一起合并到其右兄弟（無(wú)右兄弟則為左兄弟）結(jié)點(diǎn)中即可。四、B + 樹： B+ 樹是B 樹的變形，廣泛應(yīng)用在文件系統(tǒng)中，特別是數(shù)據(jù)庫(kù)的 VSAM 文件系統(tǒng)中。一棵 m 階 B+ 樹與一棵 m 階 B 樹的不同之處在：1、有

18、n 棵子樹的結(jié)點(diǎn)中有 n 個(gè)關(guān)鍵字； 2、所有葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息及指向這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)以關(guān)鍵字大小自小至大順序鏈接；3、所有非終端結(jié)點(diǎn)可以看成是索引部分，其中只含有其子樹中最大（或最小）關(guān)鍵字。 其實(shí) B+ 樹已不是一棵真正意義上的樹型結(jié)構(gòu)了，其終端結(jié)點(diǎn)已連成了線性有序表。 鍵樹（key tree）又稱數(shù)字查找樹（digital search tree），它的每個(gè)結(jié)點(diǎn)只包含組成關(guān)鍵字的字符或數(shù)字。鍵樹主要用來(lái)存儲(chǔ)一些關(guān)鍵字表或標(biāo)識(shí)符表，有利于這些關(guān)鍵字的查找。 鍵樹的常用存儲(chǔ)方式有兩種： 1、孩子兄弟的二叉樹表示法（雙鏈樹）； 2、多重鏈表表示法（Trie 樹）。

19、五、鍵樹：作 業(yè)27. 試從空樹開始，按以下順序向2-3樹中插入關(guān)鍵字建樹：20，30，50，52，60，68，70。如果此后再刪去50和68，畫出每一步執(zhí)行后的狀態(tài)。9.3 散列表查找 前面所介紹的查找方法的查找效率各不相同，且相適應(yīng)的查找表也不一樣，但都有一個(gè)共性，即平均查找長(zhǎng)度不會(huì)為 1。那么有沒(méi)有辦法使平均查找長(zhǎng)度等于 1，即一次查找成功呢？ 散列表（Hash table）的查找就是為了解決這個(gè)問(wèn)題而提出的。 散列表是如此構(gòu)造的：給定一個(gè)線性表空間，選取一 個(gè)自變量為關(guān)鍵字的映射函數(shù)，其函數(shù)值為關(guān)鍵字在線性表空間中的存儲(chǔ)位置，關(guān)鍵字經(jīng)該函數(shù)映射后即可存儲(chǔ)到線性表空間中；查找時(shí)也用相同的

20、方法即可找到該記錄。 該線性表空間即稱為散列表（也叫哈稀表），所選取的函數(shù)稱為散列函數(shù)（Hash function），得到的函數(shù)值稱為散列地址，得到散列地址的過(guò)程稱為哈稀造表或散列。理論上散列表查找成功的平均查找長(zhǎng)度 ASL成功 = 1。 但實(shí)際上經(jīng)常會(huì)遇見這樣的情況：不同的兩個(gè)關(guān)鍵字經(jīng)過(guò)散列函數(shù)運(yùn)算后所得到的散列地址相同，這種現(xiàn)象稱為沖突（collision），而產(chǎn)生沖突的兩個(gè)關(guān)鍵字對(duì)該散列函數(shù)而言稱為同義詞（synonym）。 我們應(yīng)盡可能選取沖突少的散列函數(shù)，但不能完全避免沖突的產(chǎn)生，而有了沖突就需要找相應(yīng)的解決辦法。 構(gòu)造散列函數(shù)的方法很多，原則是希望構(gòu)造的散列函數(shù)是均勻的（unifo

21、rm），亦即經(jīng)散列函數(shù)映象到地址集合中的任何一個(gè)地址的概率是相等的，這樣做能盡可能減少?zèng)_突。散列函數(shù)的構(gòu)造方法：最常用的散列函數(shù)構(gòu)造方法有以下幾種：1、直接定址法：H( key ) = a * key + b， a、b為常數(shù)；2、數(shù)字分析法：分析關(guān)鍵字，找出其中幾位數(shù)字作散列地址；3、平方取中法：關(guān)鍵字平方后中間幾位數(shù)字與所有數(shù)字相關(guān)，可選取來(lái)作為散列地址；4、折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分相疊加作為散列地址；5、除留余數(shù)法：H( key ) = key MOD p， pm，m 為比散列表長(zhǎng)度小的數(shù)；6、偽隨機(jī)數(shù)法：選取一個(gè)用關(guān)鍵字作為種子的偽隨機(jī)數(shù)發(fā)生器生成散列地址。 與構(gòu)造散列函數(shù)

22、一樣，解決沖突的方法也很多，原則是盡可能避免產(chǎn)生二次聚集的情況不同散列地址的記錄間因解決沖突而產(chǎn)生新的沖突的現(xiàn)象。解決沖突的方法：最常用的解決沖突方法有以下幾種：1、開放定址法：Hi =(H(key) + di) MOD m, i = 1,2, k (km)；其中 H(key) 為散列函數(shù)，m 為散列表長(zhǎng)，di 為增量序列，取值為：、 di =1,2,m-1，稱為線性探測(cè)（linear probing）再散列； 、 di = 12, -12,22, -22,k2 ( km/2 )，稱為二次探測(cè)（quadratic probing）再散列； 、 di = 偽隨機(jī)數(shù)，稱為偽隨機(jī)探測(cè)（random

23、probing）再散列；2、再散列法：Hi =RHi(key), i =1,2,k，RHi為不同的散列函數(shù)；3、鏈地址法：散列表設(shè)立指針，將所有散列地址為此位置的關(guān)鍵字記錄用單鏈表形式存儲(chǔ)起來(lái)；4、公共溢出區(qū)法：建立公共溢出區(qū)，將所有發(fā)生沖突的關(guān)鍵字記錄存儲(chǔ)到公共溢出區(qū)中去。散列函數(shù)的查找及分析： 散列表的查找過(guò)程與散列表的建立過(guò)程相同：利用建表時(shí)的散列函數(shù)和解決沖突的方法，逐步去進(jìn)行查找，直到找到該記錄或找不到該記錄（該單元為空或空指針）為止。 因此，在刪除記錄時(shí)，不是將該位置置為空，而是將其置為“被刪除”，否則查找鏈就會(huì)斷。 一般的，關(guān)鍵字?jǐn)?shù)目一定，散列表空間越大，沖突相對(duì)越少。裝填因子（load factor）： = 表中填入的記錄數(shù)散列表長(zhǎng)度 即越小，發(fā)生沖突的可能性就越??； 越大，發(fā)生沖突的可能性就越大。理論上查找成功的平均查找長(zhǎng)度為：線性探測(cè)再散列： ASL ( 1 + 1 / ( 1 - ) / 2鏈地址： ASL 1 + / 2理論上查找不成功的平均查找長(zhǎng)度為：線