《數(shù)據(jù)結(jié)構(gòu)》課件第七章

第七章查找內(nèi)容提要線(xiàn)性查找（線(xiàn)性表結(jié)構(gòu)）無(wú)序表查找有序表查找索引順序表查找樹(shù)型查找（樹(shù)型結(jié)構(gòu)）哈希查找比較各種查找算法的時(shí)間、空間復(fù)雜度查找的相關(guān)概念（一）查找表：由同一類(lèi)型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。對(duì)表的基本操作：查詢(xún)某個(gè)“特定”的數(shù)據(jù)元素是否在表中檢索某個(gè)“特定”的數(shù)據(jù)元素的各種屬性在查找表中插入一個(gè)數(shù)據(jù)元素從查找表中刪除某個(gè)數(shù)據(jù)元素靜態(tài)查找表動(dòng)態(tài)查找表主關(guān)鍵字：數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素（或記錄）。次關(guān)鍵字：可以識(shí)別若干記錄的關(guān)鍵字。查找：按給定的某個(gè)值k，在查找表中查找關(guān)鍵字為給定值k的數(shù)據(jù)元素（或記錄）若表中存在這樣的元素，則查找成功，否則查找不成功，返回“空”。若關(guān)鍵字為主關(guān)鍵字，則查找結(jié)果是唯一的，若為次關(guān)鍵字，則可能得到多個(gè)查找結(jié)果。查找的相關(guān)概念（二）查找的方法取決于元素以何種關(guān)系組織在一起平均查找長(zhǎng)度：為確定記錄在查找表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的數(shù)學(xué)期望值稱(chēng)為在查找成功時(shí)的平均查找長(zhǎng)度（ASL）其中：Pi為查找表中第i個(gè)記錄的概率

Ci為查找成功時(shí)，和給定值已進(jìn)行過(guò)比較的關(guān)鍵字個(gè)數(shù)。Ci因查找過(guò)程不同而不同。線(xiàn)性查找（一）——無(wú)序表中的查找

以順序表或鏈表來(lái)表示靜態(tài)查找表。1.順序存儲(chǔ)結(jié)構(gòu)(數(shù)組)中的查找查找過(guò)程：從表中最后一個(gè)記錄開(kāi)始，逐個(gè)與給定值（關(guān)鍵字）進(jìn)行比較。順序查找的特點(diǎn)：方法簡(jiǎn)單對(duì)表的結(jié)構(gòu)無(wú)要求查找效率低，當(dāng)n較大時(shí)不宜采用T=O(n/2)最糟糕的情況:2n次比較，n次加1方法一從第一個(gè)元素找到第n個(gè)元素為止。T=O(n/2)最糟糕的情況:n+1次比較，n次減1，增加一個(gè)標(biāo)志位Key(0)方法一的改進(jìn)1.添加第0個(gè)元素，其值為K2.從第n個(gè)元素反向找，直到找到K為止。順序查找算法

intSearch_seq(SStableST,KeyTypekey){ST.elem[0].key=key;for(i=ST.length;key!=ST.elem[i].key;i--);Returni;}//監(jiān)視哨//從后往前查找無(wú)序表查找算法的性能分析平均查找長(zhǎng)度：在等概率的情況下P(i)=1/n查找成功時(shí)的平均查找長(zhǎng)度為(n+1)/2查找不成功時(shí)的比較次數(shù)(n+1)查找的平均時(shí)間復(fù)雜度O(n/2)典型：二分查找（折半查找）查找過(guò)程：例P219，算法P220線(xiàn)性查找（二）——有序表中的查找二分查找的特點(diǎn)：效率較高要求查找表有序只適合順序查找和建立后很少改動(dòng)而只需查找的表123456lowhighmidhigh=mid-1low=mid+1

mid=(low+high)/2當(dāng)low>high時(shí)結(jié)束查找【】折半查找法T=O(log2n)若要通過(guò)關(guān)鍵字之間的比較來(lái)實(shí)現(xiàn)查找，無(wú)論何算法和結(jié)構(gòu)，折半查找法的時(shí)間復(fù)雜度log2n已經(jīng)達(dá)到靜態(tài)查找的下界折半查找算法

intSearch_bin(SStableST,KeyTypekey){Low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(key=ST.elem[mid].key)returnmidelseif(key<ST.elem[mid].key)high=mid-1elselow=mid+1;}Reutrn0;}//區(qū)間初值//找到中間元素//判斷查找元素的大致位置，在前半?yún)^(qū)還是后半?yún)^(qū)對(duì)索引表的要求：：按表中記錄的關(guān)鍵字分塊，其中第n塊的任一關(guān)鍵字均大于第n-1塊的任一關(guān)鍵字,每塊中的結(jié)點(diǎn)順序可以是無(wú)序的.對(duì)于索引表中的內(nèi)容，存放每塊的最大關(guān)鍵字，第一個(gè)記錄的物理位置以及最后一個(gè)記錄的物理位置。在某個(gè)索引指向的表中各元素不一定是有序的，但都小于該表索引的關(guān)鍵字.線(xiàn)性查找（三）——索引順序表查找索引順序表查找：分塊查找，順序查找的改進(jìn)查找過(guò)程：先確定待查記錄所在的塊，然后在塊中進(jìn)行順序查找。（塊中元素可以任意排列）分塊查找的特點(diǎn)：插入、刪除記錄比較容易增加了額外的存儲(chǔ)空間和運(yùn)算是順序查找的一種改進(jìn)適用于要求較快檢索且時(shí)需要?jiǎng)討B(tài)變化的情況樹(shù)型結(jié)構(gòu)查找二叉排序樹(shù)(二叉查找樹(shù))的查找(BST)二叉排序樹(shù)：或者是一棵空樹(shù)，或者具有以下性質(zhì)

1)若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值

2)若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值

3)它的左右子樹(shù)也分別是二叉排序樹(shù)4512533372410061907845125333724100619078查找過(guò)程若查找樹(shù)為空，查找失敗。若查找樹(shù)非空，將給定值k與查找樹(shù)的根結(jié)點(diǎn)關(guān)鍵字比較若相等，查找成功，結(jié)束查找過(guò)程；否則執(zhí)行如下：

當(dāng)給定值k小于根結(jié)點(diǎn)關(guān)鍵字時(shí)，查找將在以左子女為根的子樹(shù)上繼續(xù)進(jìn)行。當(dāng)給定值k大于根結(jié)點(diǎn)關(guān)鍵字時(shí)，查找將在以右子女為根的子樹(shù)上繼續(xù)進(jìn)行二叉排序樹(shù)的查找算法（遞歸）

BiTreeSearchBST(bitreeBT,KeyTypekey){If((!BT)||key==BT->data)return(BT);Elseif(key<BT->data)return(SearchBST(BT->lchild,key));Elsereturn(SearchBST(BT->rchild,key));}//若樹(shù)為空或者根為查找元素，查找結(jié)束//若關(guān)鍵字小于根結(jié)點(diǎn)，則在樹(shù)的左子樹(shù)上查找//若關(guān)鍵字大于根結(jié)點(diǎn)，則在樹(shù)的右子樹(shù)上查找45125333724100619078二叉排序樹(shù)的插入

查找不成功時(shí)，將新結(jié)點(diǎn)與當(dāng)前結(jié)點(diǎn)做比較，若小于，則插入當(dāng)前結(jié)點(diǎn)的左子樹(shù)，否則插入右子樹(shù)。直到插入到合適的位置為止。45125333724100619078插入的結(jié)點(diǎn)一定是新添加的葉子結(jié)點(diǎn)生成一棵二叉排序樹(shù)就是在空二叉樹(shù)的基礎(chǔ)上逐個(gè)插入結(jié)點(diǎn)的過(guò)程二叉排序樹(shù)上結(jié)點(diǎn)P的刪除1)如果P是葉子結(jié)點(diǎn)：則直接刪除,修改其雙親指針即可。2)如果P只含有一個(gè)兒子結(jié)點(diǎn)，則用該兒子來(lái)取代P。3)如果刪除的點(diǎn)左右子樹(shù)均不為空；二叉排序樹(shù)(BST)的特點(diǎn)中序遍歷BST可以得到一個(gè)有序序列在BST上插入一個(gè)結(jié)點(diǎn)時(shí)，不必移動(dòng)其他結(jié)點(diǎn)，僅需改變某個(gè)結(jié)點(diǎn)的指針（插入的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)）BST有類(lèi)似于折半查找的特性，又采用了鏈?zhǔn)酱鎯?chǔ)，適合要經(jīng)常進(jìn)行查找、刪除、插入的有序表。折半查找長(zhǎng)度為n的表的判定樹(shù)是唯一的,而含有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)不是唯一的.(平衡二叉樹(shù)是最好的選擇)平衡二叉樹(shù)（AVL樹(shù)）概念：它或者是一棵空樹(shù)，或者具有下列性質(zhì)的二叉樹(shù)：對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)引入一個(gè)平衡因子，其值為該結(jié)點(diǎn)左子樹(shù)的深度減去右子樹(shù)的深度。平衡二叉樹(shù)的左右子樹(shù)都是平衡二叉樹(shù)，且每個(gè)結(jié)點(diǎn)的平衡因子絕對(duì)值不超過(guò)1。平衡二叉樹(shù)的葉子節(jié)點(diǎn)都在最底下的兩層。ABCD-1010ABCDEF20-1010性能好，查找方便是不是哈希表與其他查找表的區(qū)別：其他查找表查找方法建立在“比較”的基礎(chǔ)上，查找的效率依賴(lài)于查找過(guò)程中所進(jìn)行的比較次數(shù)；哈希表是將記錄的存儲(chǔ)位置與它的關(guān)鍵字之間建立一個(gè)唯一確定的對(duì)應(yīng)關(guān)系。沖突：哈希函數(shù)是一個(gè)壓縮的映象，因而不可避免的產(chǎn)生沖突。不同的關(guān)鍵字可能得到同一哈希地址（同義詞），這種現(xiàn)象就是沖突。哈希表：根據(jù)設(shè)定的哈希函數(shù)和處理沖突的方法將一組關(guān)鍵字映像到一個(gè)有限的連續(xù)的地址集上。哈希查找哈希表的構(gòu)造好的哈希函數(shù)的標(biāo)準(zhǔn)：簡(jiǎn)單、均勻（使沖突最小化）常用的構(gòu)造方法：直接定址法：H(key)=key或H(key)=a*key+b

特點(diǎn)分析：不同的關(guān)鍵字不會(huì)產(chǎn)生沖突，空間浪費(fèi)大除留余數(shù)法：H(key)=keymodP(P的選擇很重要）P的選取為小于或等于散列表長(zhǎng)度m的某個(gè)最大素?cái)?shù)比較好折疊法：將關(guān)鍵字自左向右分為為數(shù)相等的幾部分，最后一部分位數(shù)可以短些，然后將這些部分疊加求和，并按哈希表表長(zhǎng)取后幾位作為哈希地址。（移位法和間接疊加）

特點(diǎn)分析：適合用于位數(shù)較多且各位分布較均勻的情況隨機(jī)數(shù)法：關(guān)鍵字長(zhǎng)度不等時(shí)采用解決沖突的方法：為發(fā)生沖突的關(guān)鍵字的記錄找到另一個(gè)空的哈希地址。開(kāi)放定址法★：當(dāng)發(fā)生沖突后，就去尋找下一個(gè)空的哈希地址，只要哈希表足夠大，（可循環(huán)查找）空的哈希地址總能找到，并將數(shù)據(jù)元素存入。線(xiàn)性探測(cè)法：Hi=(Hash(key)+di)modm(di=1,2,3…m-1)二次探測(cè)法：Hi=(Hash(key)+di)modm(di=12，-12，22，…j2，)m是表長(zhǎng)線(xiàn)性探測(cè)簡(jiǎn)單能探查整個(gè)表的空間，但容易產(chǎn)生堆積；二次探查簡(jiǎn)單、不容易產(chǎn)生堆積。但不易探查整個(gè)空間鏈地址法：將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一單鏈表中的方法。再哈希法：建立一個(gè)公共溢出區(qū)哈希表的查找

計(jì)算出哈希地址h(K)，若表中該單元的值為空，則查找失敗。否則比較關(guān)鍵字，若和K相等，則返回成功；否則按建表時(shí)設(shè)定的處理沖突方法尋找，反復(fù)下去，直到出現(xiàn)紅色字體的情況為止裝填因子a=表中填入的記錄數(shù)哈希表的長(zhǎng)度裝填因子越大，沖突可能性越大思考寫(xiě)一算法，在有序表中插入一元素，保持表的有序性，并上機(jī)實(shí)現(xiàn)。（二分法）將序列13，15，22，8，34，19，21插到一個(gè)初始為空的哈希表中，哈希表的裝填因子為0.7，哈希函數(shù)采用H(x)=1+(x%7),沖突時(shí)用線(xiàn)性探測(cè)法解決沖突,試構(gòu)造這個(gè)哈希表（哈希表地址從1開(kāi)始）。

解H(13)=7H(15)=2H(22)=2(沖突）H(8)=2(沖突）H(34)=7（沖突）H(19)=6H(21)=1解決沖突：H1(22)=（H（22）+1）%10=3H1（8）=（H（8）+1）%10=3（仍沖突）H2（8）=（H（8）+2）%10=4H1（34）=（H（34）+1）%10=8123456789102115228191334已知裝填因子，可求得哈希表長(zhǎng)度：長(zhǎng)度為7/0.7=10例題設(shè)數(shù)據(jù)序列為D={13，28，72，5，16，8，7，9，34}，請(qǐng)用D組織一個(gè)哈希表，哈希函數(shù)是H（K）=Kmod7，哈希表長(zhǎng)度為11個(gè)單元，起始地址為0，要求分別用線(xiàn)性探測(cè)方法和二次探測(cè)方法來(lái)解決沖突。解：H（13）=6；

H（28）=0；

H（72）=2；

H（5）=5；

H（16）=2（沖突）H1(16)=(H(16)+1)MOD11=3H（8）=1；

H（7）=0；（沖突）H1(7)=(H(7)+1)MOD11=1(沖突)H2(7)=(H(7)+2)MOD11=2(沖突)H3(7)=(H(7)+3)MOD11=3(沖突)

H4(7)=(H(7)+4)MOD11=4H(9)=2(沖突)H1(9)=(H(9)+1)MOD11=3(沖突)H2(9)=(H(9)+2)MOD11=4(沖突)H3(9)=(H(9)+3)MOD11=5(沖突)H4(9)=(H(9)+4)MOD11=6(沖突)H5(9)=(H(9)+5)MOD11=7H(34)=6(沖突)H1(34)=(H(34)+1)MOD11=7(沖突)H2(34)=(H(34)+2)MOD11=8線(xiàn)性探測(cè)后的哈希表二次探測(cè)的結(jié)果如下H1（16）=（H（16）+1）mod11=3；H1（7）=（H（7）+1）mod11=1；（仍沖突）H2（7）=（H（7）-1）mod11=10；H1（9）=（H（9）+1）mod11=3；（仍沖突）H2（9）=（H（9）-1）mod11=1；（仍沖突）H3（9）=（H（9）+4）mod11=6；（仍沖突）H4（9）=（H（9）-4）mod11=9；H1（34）=（H（34）+1）mod11=70123456789102887216513349701234567891028872167513934思考畫(huà)出長(zhǎng)度為10的有序表折半查找的一棵判定樹(shù)，并求等概率時(shí)查找成功的平均查找長(zhǎng)度補(bǔ)充下面的算法，使之完整。該算法已知一個(gè)r[1..n]的n個(gè)記錄的遞增