查找在計(jì)算機(jī)信息處理.ppt課件

1、第八章 查找 查找在計(jì)算機(jī)信息處理、數(shù)據(jù)庫查詢等方面均有廣泛的應(yīng)用。查找算法的優(yōu)劣和能否針對(duì)不同要求來選用恰當(dāng)?shù)牟檎宜惴?，直接影響到查找效率。在一個(gè)數(shù)據(jù)集合中進(jìn)行查找所使用的方法與該數(shù)據(jù)集合的存儲(chǔ)結(jié)構(gòu)密切相關(guān)。查找的基本概念線性表的查找樹表的查找哈希表及其查找小結(jié) over查找的基本概念 查找就是在數(shù)據(jù)元素(記錄)集合中找出“滿足查找要求”的數(shù)據(jù)元素(記錄)。查找表(search table)- 指同一類型的記錄構(gòu)成的集合。關(guān)鍵字(key)-記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以識(shí)別、確定一個(gè)記錄。主關(guān)鍵字(primary key)-指查找表中能唯一地確定一個(gè)記錄的關(guān)鍵字。next次關(guān)鍵字(secon

2、dary key)-指查找表中能夠確定多個(gè)記錄的關(guān)鍵字。查找(searching)-給定一個(gè)確定的值，在查找表中確定一個(gè)記錄，其相應(yīng)的關(guān)鍵字等于給定值的操作。查找的結(jié)果有兩種：查找成功和查找失敗。查找表分為：靜態(tài)查找表和動(dòng)態(tài)查找表兩種。靜態(tài)查找表-指只查詢給定記錄是否存在于表中或檢索某個(gè)特定記錄的有關(guān)屬性。動(dòng)態(tài)查找表-除上之外，還可以對(duì)表進(jìn)行插入、刪除或修改操作。next基于比較的查找算法的執(zhí)行時(shí)間取決于給定值和關(guān)鍵字的比較次數(shù)，通常以比較次數(shù)的平均值作為衡量算法的依據(jù)，稱其為算法在查找成功時(shí)的平均查找長度(Average Search Length，簡記為ASL)。若查找表有n個(gè)記錄，則 其

3、中：pi位在查找表中查找第i個(gè)記錄的概率back線性表的查找說明：本節(jié)討論的是數(shù)組實(shí)現(xiàn)的順序表記錄結(jié)構(gòu)： typedef struct int key; NODE;順序表下的三種查找方法：順序查找折半查找分塊查找back順序查找(sequential search)方法：從順序表的一端開始，將給定值依次與數(shù)組中各個(gè)記錄的關(guān)鍵字進(jìn)行比較，若在表中找到某個(gè)記錄的key與給定值相等，則查找成功，返回記錄所在下標(biāo)；若查找失敗則給出失敗信息。適用：順序表中記錄的關(guān)鍵字無序的情況?；舅惴?-1改進(jìn)算法8-2性能分析back算法8-1 p163 int search(NODE a ,int n,int k

4、) int i=0; while (i=n) return -1; else return i; back順序查找的基本操作是關(guān)鍵字的比較。查找成功的最好情況是第一個(gè)記錄就是所查，比較一次即可；查找成功最壞的情況是第n個(gè)記錄符合要求，進(jìn)行n次比較。若查找概率相等，即pi=1/n，則順序查找成功的平均查找長度為：對(duì)算法8-2，查找不成功的比較次數(shù)為n+1，順序查找算法的時(shí)間復(fù)雜度為O(n)。back折半查找(binary search)(二分查找)適用：查找表中記錄關(guān)鍵字值有序。查找過程：(順序表記錄關(guān)鍵字升序排列)設(shè)low、mid、high指向表當(dāng)前待查范圍的下、中和上界。初始：給定查找值為k

5、，low=0，high=n-1，mid=比較，若k=amid.key，成功；若kamid.key，令low=mid+1，繼續(xù)查找；比較，若lowhigh，重復(fù)執(zhí)行，否則查找完畢，若無滿足記錄則查找失敗。next搜索成功的例子 搜索失敗的例子next例8-1 順序表8,11,18,28,45,55,63,80，用折半查找的方法查找55和22的記錄。查找55過程：初始low=0,high=7,mid=(0+7)/2=3 下標(biāo) 0 1 2 3 4 5 6 7 low mid high 比較,(k=55)(amid.key=28),令low=mid+1=4,high=7,mid=(4+7)/2=5 下

6、標(biāo) 0 1 2 3 4 5 6 7 low mid high 比較,(k=55)=(amid.key=55),查找成功,返回5811182845556380811182845556380next算法8-3 p166 int Binary_Search(NODE a ,int n,int k) int low=0,high=n-1,mid; while (low=high) mid=(low+high)/2; if (amid.key=k) return mid; else if (amid.keyk) low=mid+1; eles high=mid-1; return -1; next折半查

7、找過程可用一棵二叉樹表示： 樹中每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于查找表中一個(gè)記錄，結(jié)點(diǎn)值為相應(yīng)記錄在查找表中的位置值，根結(jié)點(diǎn)值是查找表中間元素下標(biāo)； 左子樹結(jié)點(diǎn)是key中間元素的右子表，右子樹的根結(jié)點(diǎn)是右子表的中間元素的下標(biāo) 依此類推得到相應(yīng)的判定樹。next從有序表構(gòu)造出的判定樹next在等概率條件下，可求得成功查找的平均查找長度。 例：上圖ASL=(1+2*2+3*4+4*2)/9=25/93當(dāng)查找成功時(shí)，最好情況是比較1次。查到每個(gè)記錄的比較次數(shù)=該結(jié)點(diǎn)在判定樹中的深度。折半查找算法的時(shí)間復(fù)雜度為O(log2n)。back分塊查找(索引順序查找)是順序查找的一種改進(jìn)，在分塊查找時(shí)，把表內(nèi)記錄按某種屬性分成

8、n(1)個(gè)塊(子表)，且塊間有序，即后一塊中所有記錄key值前一塊重所有記錄key值，而塊內(nèi)key值可以無序。建立一相應(yīng)“索引表”，由若干索引記錄組成，每個(gè)索引記錄對(duì)應(yīng)一個(gè)塊。索引記錄包括兩個(gè)數(shù)據(jù)項(xiàng)：對(duì)應(yīng)塊內(nèi)最大key值和塊中第一個(gè)記錄位置的地址指針。next分塊查找的步驟：對(duì)索引表進(jìn)行查找以確定給定值所在的塊，因?yàn)樗饕碛行?，可用順序查找或折半查找；在確定的塊中查找給定的值，塊內(nèi)不一定有序，所以一般用順序查找。 例：子表數(shù)據(jù)分開存儲(chǔ)next例8-2 線性表16,22,5,11,66,38,62,88,1009個(gè)元素，用分塊查找法查找66的數(shù)據(jù)元素。 索引表 塊內(nèi)最大關(guān)鍵字值 塊的起始地址 下

9、標(biāo) 0 1 2 3 4 5 6 7 8 線性表分為3塊，每塊3個(gè)元素。給定值k=66，與索引表中各塊內(nèi)最大key值比較，100k62，可判定在第三塊中查找，直至成功或失敗。1662100036165112238626688100back樹表的查找樹表查找是指查找表用二叉樹表示，存儲(chǔ)結(jié)構(gòu)采用二叉鏈表，鏈表中每個(gè)結(jié)點(diǎn)對(duì)應(yīng)查找表中一個(gè)記錄。二叉排序樹的定義二叉排序樹的查找二叉排序樹的插入和刪除back二叉排序樹(binary sort tree)的定義或者是一棵空樹，或者具有下列性質(zhì)的二叉樹：若它的左子樹非空，則在左子樹的所有結(jié)點(diǎn)的值都小于它的根結(jié)點(diǎn)的值；若它的右子樹非空，則在右子樹的所有結(jié)點(diǎn)的值都

10、大于等于根結(jié)點(diǎn)的值；左右子樹也分別是一棵二叉排序樹。簡而言之，二叉排序樹每個(gè)結(jié)點(diǎn)的值都大于它的左子樹上的所有結(jié)點(diǎn)的值，而小于等于它的右子樹上所有結(jié)點(diǎn)的值。對(duì)二叉排序樹進(jìn)行中序遍歷即可得到從小到大的有序序列。back二叉排序樹的查找具體做法： 當(dāng)二叉排序樹非空時(shí)，將給定值k與根的key比較，若相等則表示查找成功；否則，若kkey != k) if (kkey) p=p-left; else p=p-right; if (!p) break; return p; back二叉排序樹的插入和刪除按照一定規(guī)則在二叉排序樹上插入、刪除結(jié)點(diǎn)仍能保持二叉排序樹的性質(zhì)。只要解決了插入問題，也就解決了建樹過程，

11、因?yàn)榻溥^程就是從空樹開始逐次插入新結(jié)點(diǎn)的過程。用二叉排序樹插入算法生成的二叉排序樹，其形狀、高度不僅依賴于關(guān)鍵字值的大小和數(shù)量，還與記錄輸入的先后次序有關(guān)系。next插入的具體做法： 動(dòng)態(tài)生成一新結(jié)點(diǎn)p，若二叉排序樹root為空，則作為根結(jié)點(diǎn)插入；若非空，則比較，若p-keykey則插入左子樹，否則插入右子樹。在左或右子樹上進(jìn)行同樣的操作，實(shí)際是一個(gè)遞歸的過程。最后p的插入位置是二叉排序樹中某結(jié)點(diǎn)的空指針位置。新結(jié)點(diǎn)p是作為葉結(jié)點(diǎn)插入，所以新結(jié)點(diǎn)插入時(shí)其左右子指針均為NULL。next算法8-5 二叉排序樹中插入新結(jié)點(diǎn)的非遞歸算法 p170-171 #include #include #de

12、fine MAX 5 Bnode *btInsert(int x,Bnode *root); void main( ) int i,aMAX=60,40,70,20,80; Bnode *root=NULL; for(i=0;ikey=x; p-left=p-right=NULL; if (!root) root=p; return p; q=root; while (!flag) if (q-key x) if (q-left) q=q-left; else q-left=p; flag=1; else if (q-right) q=q-right; else q-right=p; flag

13、=1; return root; next在二叉排序樹上刪除一個(gè)結(jié)點(diǎn)p，分四種情況：若p是葉結(jié)點(diǎn)，直接刪除即可；若p只有右子樹沒有左子樹，直接將其右子樹的根結(jié)點(diǎn)放到被刪位置上即可；若p只有左子樹沒有右子樹，直接將其左子樹的根結(jié)點(diǎn)放到被刪位置上即可；若p既有左右子樹，找p右子樹key最小結(jié)點(diǎn)s，用s取代p的位置，用s右子樹的根結(jié)點(diǎn)取代s的位置。二叉排序樹的平均查找長度為O(log2n)。二叉排序樹適用于經(jīng)常要進(jìn)行插入刪除操作的查找表。back哈希(Hash)表及其查找指通過待查記錄的key進(jìn)行相應(yīng)的計(jì)算就能找到要查找記錄的方法。這需要在待查記錄的key與該記錄的存儲(chǔ)位置之間建立確定的對(duì)應(yīng)關(guān)系。哈

14、希表的基本概念哈希函數(shù)的構(gòu)造方法處理沖突的方法back哈希函數(shù)-p174 是記錄的關(guān)鍵字值與該記錄的存儲(chǔ)地址之間所構(gòu)造的對(duì)應(yīng)關(guān)系。哈希表-p174 是用來存放查找表中記錄序列的表，每一個(gè)記錄的存儲(chǔ)位置是以該記錄的關(guān)鍵字為自變量，由相應(yīng)哈希函數(shù)計(jì)算所得到的函數(shù)值。要保證哈希表查找能正確操作，必須保證記錄的存放規(guī)則和查找規(guī)則一致，即是用相同的哈希函數(shù)。next例子：將關(guān)鍵字序列8,10,14,21存儲(chǔ)到編號(hào)為0到4的表長為5的哈希表中，哈希函數(shù)為H(Ki)=Ki mod 5，Ki是關(guān)鍵字值。哈希表結(jié)構(gòu)如： 0 1 2 3 4沖突(collision)-p174 指不同的關(guān)鍵字值具有相同的哈希地址。

15、同義詞(synonym)-p174 指對(duì)應(yīng)一個(gè)哈希函數(shù)具有相同函數(shù)值的的關(guān)鍵字。1021814back哈希函數(shù)的構(gòu)造方法 哈希函數(shù)的構(gòu)造，與key長度、哈希表大小、key的實(shí)際取值狀況等多種因素有關(guān)。直接定址法： 當(dāng)key是正數(shù)時(shí)，取key本身或者它的某個(gè)線性函數(shù)作為它的哈希地址，即： H(K)=K 或者 H(K)=ak+b (a、b為常數(shù)) 該方法簡單，key取值不同時(shí)不會(huì)產(chǎn)生沖突，但是，它要求散列地址空間的大小與關(guān)鍵碼集合的大小相同。若key分布不連續(xù)則哈希表會(huì)造成空間大量浪費(fèi)。實(shí)際少用。next例：有一組關(guān)鍵碼942148,941269,940527,941630, 941805,941

16、558,942047,940001。 散列函數(shù)為Hash(key)=key940000 則有 Hash(942148)=2148 Hash(941269)=1269 Hash(940527)=527 Hash(941630)=1630 Hash(941805)=1805 Hash(941558)=1558 Hash(942047)=2047 Hash(940001)=1 可以按計(jì)算出的地址存放記錄。next平方取中法：一種較好的方法 先計(jì)算key的平方值，再取其平方值的中間若干位作為哈希地址，即： H(K)=“K的平方值的中間幾位” key平方后其中間幾位和組成key的各位均有關(guān)系，使得哈希地

17、址的分布較為均勻，減少了發(fā)生沖突的可能。其所取的位數(shù)取決于哈希表的長度。 例：K1=11052501,K2=11052502,計(jì)算出K12=122157778355001,K22=122157800460004,取左起第7到第9位作為哈希地址。next除留余數(shù)法：最簡單最常用的方法 選一個(gè)合適的不大于哈希表長度的正整數(shù)P，用P去除關(guān)鍵字K，得到余數(shù)作為哈希地址，即：H(K)= K mod P 這樣可以保證哈希函數(shù)的值在有效地址空間之內(nèi)。該方法的好壞取決于P值得選擇，當(dāng)P取小于哈希表長度的最大質(zhì)數(shù)時(shí)，產(chǎn)生的哈希函數(shù)比較好。next 例：有一個(gè)關(guān)鍵碼key=962148，散列表大小 m=25，即H

18、T25。取質(zhì)數(shù)p=23。散列函數(shù) hash(key)=key%p。則散列地址為 hash(962148)=962148%23=12。 可以按計(jì)算出的地址存放記錄。 需要注意的是，使用上面的散列函數(shù)計(jì)算出來的地址范圍是0到22，因此，從23到24這幾個(gè)散列地址實(shí)際上在一開始是不可能用散列函數(shù)計(jì)算出來的，只可能在處理溢出時(shí)達(dá)到這些地址。next數(shù)字分析法： 設(shè)key有d位，對(duì)各個(gè)key的每位進(jìn)行分析，選取key中取值較均勻的若干位作為哈希地址。 計(jì)算key中符號(hào)分布的均勻度 k的公式： 其中， 表示第i個(gè)符號(hào)在第k位上出現(xiàn)的次數(shù)，n/r表示各種符號(hào)在n個(gè)數(shù)中均勻出現(xiàn)的期望值。計(jì)算出的k值越小，表明

19、在該位(第k位)各種符號(hào)分布得越均勻。 next若散列表地址范圍有3位數(shù)字,取各關(guān)鍵碼的位做為記錄的散列地址。也可以把第和第位相加，舍去進(jìn)位位，變成一位數(shù)，與第位合起來作為散列地址。還有其它方法。 9 4 2 1 4 8位， 1 = 510.60 9 4 1 2 6 9位， 2 = 510.60 9 4 0 5 2 7位， 3 = 110.60 9 4 1 6 3 0位， 4 = 110.60 9 4 1 8 0 5位， 5 = 110.60 9 4 1 5 5 8位， 6 = 110.60 9 4 2 0 4 7 9 4 0 0 0 1 next 數(shù)字分析法僅適用于事先明確知道表中所有關(guān)鍵碼

20、每一位數(shù)值的分布情況，它完全依賴于關(guān)鍵碼集合。如果換一個(gè)關(guān)鍵碼集合，選擇哪幾位要重新決定。隨即數(shù)法：適用于key長度不等的情況 取key的隨機(jī)函數(shù)作為它的哈希地址，即： H(K)=random(K) 其中random( )為取隨機(jī)數(shù)的函數(shù)。back處理沖突的方法 在實(shí)際應(yīng)用中，不論選擇何種哈希函數(shù)，都不可能完全避免沖突。下面介紹兩種處理沖突的方法：鏈地址法開放地址法鏈地址法這種方法是把具有相同哈希地址的key的值存放在一個(gè)鏈表中，哈希表中的每個(gè)單元所存放的不是key的值，而是相應(yīng)單鏈表的指針。例：給出一組表項(xiàng)關(guān)鍵碼Burke,Ekers,Broad,Blum,Attlee,Alton, Hec

21、ht,Ederly 。 散列函數(shù)為：Hash(x)ord(x)ord(A)。next 用哈希函數(shù)計(jì)算可得： Hash(Burke)=1 Hash(Ekers)=4 Hash(Broad)=1 Hash(Blum)=1 Hash(Attlee)=0 Hash(Hecht)=7 Hash(Alton)=0Hash(Ederly)=4 散列表為 HT0.25，m=26。 采用鏈地址發(fā)法處理沖突，則上述關(guān)鍵碼在散列表中的散列位置如圖所示。nextnext該方法適合于沖突現(xiàn)象比較嚴(yán)重的情況，能夠較好解決溢出問題，也很容易實(shí)現(xiàn)插入和刪除操組。不足，除了哈希表的存儲(chǔ)空間外，還增加了鏈域空間。如果哈希函數(shù)的均勻性較差，會(huì)造成存儲(chǔ)單元的浪費(fèi)。back開放地址法開放地址法是在沖突發(fā)生時(shí)，按照某種方法繼續(xù)探測(cè)表中其它存儲(chǔ)單元，直到找到空位置為止。如： Hi(K)=(H(K)+di)mod m(i=1,2,3,k(km-1) 其中Hi(K)為在探測(cè)到的地址， H(K)為關(guān)鍵字K的直接哈希地址，m為哈希表長，di為再探測(cè)時(shí)的地址增量。next首先計(jì)算key的直接哈希地址H(K)，若該單元已被占用則繼續(xù)探測(cè)地址為H(K)+d1單元，若也被占用，再繼續(xù)探測(cè)地址為H(K)+d2單元，直到發(fā)現(xiàn)某個(gè)單元為空，停止探