數(shù)據(jù)結(jié)構(gòu)查找方法及原理

【數(shù)據(jù)結(jié)構(gòu)】查找：線性表的查找2010-09-0313:01:26|分類：數(shù)據(jù)結(jié)構(gòu)|字號(hào)大中小訂閱本章簡(jiǎn)介由于查找運(yùn)算的使用頻率很高，幾乎在任何一個(gè)計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件中都會(huì)涉及到，所以當(dāng)問題所涉及的數(shù)據(jù)量相當(dāng)大時(shí)，查找方法的效率就顯得格外重要。在一些實(shí)時(shí)查詢系統(tǒng)中尤其如此。因此，本章將系統(tǒng)地討論各種查找方法，并通過對(duì)它們的效率分析來比較各種查找方法的優(yōu)劣。查找的基本概念1、 査找表和査找—般，假定被查找的對(duì)象是由一組結(jié)點(diǎn)組成的表(Table)或文件，而每個(gè)結(jié)點(diǎn)則由若干個(gè)數(shù)據(jù)項(xiàng)組成。并假設(shè)每個(gè)結(jié)點(diǎn)都有一個(gè)能惟一標(biāo)識(shí)該結(jié)點(diǎn)的關(guān)鍵字。查找(Searching)的定義是：給定一個(gè)值K,在含有n個(gè)結(jié)點(diǎn)的表中找出關(guān)鍵字等于給定值K的結(jié)點(diǎn)。若找到，則查找成功，返回該結(jié)點(diǎn)的信息或該結(jié)點(diǎn)在表中的位置；否則查找失敗，返回相關(guān)的指示信息。2、 查找表的數(shù)據(jù)結(jié)構(gòu)表示(1)動(dòng)態(tài)查找表和靜態(tài)查找表若在查找的同時(shí)對(duì)表做修改操作(如插入和刪除)，則相應(yīng)的表稱之為動(dòng)態(tài)查找表。否則稱之為靜態(tài)查找表。(2)內(nèi)查找和外查找和排序類似，查找也有內(nèi)查找和外查找之分。若整個(gè)查找過程都在內(nèi)存進(jìn)行，則稱之為內(nèi)查找；反之，若查找過程中需要訪問外存，則稱之為外查找。3、平均査找長(zhǎng)度ASL查找運(yùn)算的主要操作是關(guān)鍵字的比較，所以通常把查找過程中對(duì)關(guān)鍵字需要執(zhí)行的平均比較次數(shù)(也稱為平均查找長(zhǎng)度)作為衡量一個(gè)查找算法效率優(yōu)劣的標(biāo)準(zhǔn)。平均查找長(zhǎng)度ASL(AverageSearchLength)定義為：2=1其中：n是結(jié)點(diǎn)的個(gè)數(shù)；Pi是查找第i個(gè)結(jié)點(diǎn)的概率。若不特別聲明，認(rèn)為每個(gè)結(jié)點(diǎn)的查找概率相等，即Pl=P2?..=Pn=1/nCj是找到第i個(gè)結(jié)點(diǎn)所需進(jìn)行的比較次數(shù)。注意：為了簡(jiǎn)單起見，假定表中關(guān)鍵字的類型為整數(shù)：typedefintKeyType；//KeyType應(yīng)由用戶定義順序查找(SequentialSearch)在表的組織方式中，線性表是最簡(jiǎn)單的一種。順序查找是一種最簡(jiǎn)單的查找方法。1、順序査找的基本思想基本思想是：從表的一端開始，順序掃描線性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵宇和給定值K相比較。若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字與K相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于K的結(jié)點(diǎn)，則查找失敗。2、 順序査找的存儲(chǔ)結(jié)構(gòu)要求順序查找方法既適用于線性表的順序存儲(chǔ)結(jié)構(gòu)，也適用于線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（使用單鏈表作存儲(chǔ)結(jié)構(gòu)時(shí)，掃描必須從第一個(gè)結(jié)點(diǎn)開始）。3、 基于順序結(jié)構(gòu)的順序查找算法（1）類型說明typedefstruct{KeyTypekey；InfoTypeotherinfo；〃此類型依賴于應(yīng)用}NodeType；typedefNodeTypeSeqList[n+1]；〃0號(hào)單元用作哨兵（2）具體算法intSeqSearch（SeqlistR，KeyTypeK）{//在順序表R[1..n]中順序查找關(guān)鍵字為K的結(jié)點(diǎn)，〃成功時(shí)返回找到的結(jié)點(diǎn)位置，失敗時(shí)返回0inti；R[O].key=K;〃設(shè)置哨兵for(i=n;R[i].key!=K;i--);//從表后往前找returni;〃若i為0,表示查找失敗，否則R[i]是要找的結(jié)點(diǎn)}//SeqSearch注意：監(jiān)視哨設(shè)在高端的順序查找【參見練習(xí)】(3)算法分析算法中監(jiān)視哨R[0]的作用為了在for循環(huán)中省去判定防止下標(biāo)越界的條件i>1，從而節(jié)省比較的時(shí)間。成功時(shí)的順序査找的平均查找長(zhǎng)度：期鼻=Zp心=+ =切+〔丹-1妙2+…+2巧-1+血2=12=1在等概率情況下，p=1/n(1<i<n)，故成功的平均查找長(zhǎng)度為(n+...+2+1)/n=(n+1)/2即查找成功時(shí)的平均比較次數(shù)約為表長(zhǎng)的一半。若K值不在表中，則須進(jìn)行n+1次比較之后才能確定查找失敗。表中各結(jié)點(diǎn)的查找概率并不相等的ASL順序查找演示過程【動(dòng)畫演示【例】在由全校學(xué)生的病歷檔案組成的線性表中，體弱多病同學(xué)的病歷的查找概率必然高于健康同學(xué)的病歷，由于上式的ASLsq在pn>pn-1>_>p2>p1時(shí)達(dá)到最小值。若事先知道表中各結(jié)點(diǎn)的查找概率不相等和它們的分布情況，則應(yīng)將表中結(jié)點(diǎn)按查找概率由小到大地存放，以便提高順序查找的效率。為了提高查找效率，對(duì)算法SeqSearch做如下修改：每當(dāng)查找成功，就將找到的結(jié)點(diǎn)和其后繼（若存在）結(jié)點(diǎn)交換。這樣，使得查找概率大的結(jié)點(diǎn)在查找過程中不斷往后移，便于在以后的查找中減少比較次數(shù)。順序査找的優(yōu)點(diǎn)算法簡(jiǎn)單，且對(duì)表的結(jié)構(gòu)無任何要求，無論是用向量還是用鏈表來存放結(jié)點(diǎn)，也無論結(jié)點(diǎn)之間是否按關(guān)鍵字有序，它都同樣適用。順序査找的缺點(diǎn)查找效率低，因此，當(dāng)n較大時(shí)不宜采用順序查找。二分查找1、 二分查找但inarySearch）二分查找又稱折半查找，它是一種效率較高的查找方法。二分查找要求：線性表是有序表，即表中結(jié)點(diǎn)按關(guān)鍵字有序，并且要用向量作為表的存儲(chǔ)結(jié)構(gòu)。不妨設(shè)有序表是遞增有序的。2、 二分查找的基本思想二分查找的基本思想是：（設(shè)R[low..high]是當(dāng)前的查找區(qū)間）(1)首先確定該區(qū)間的中點(diǎn)位置：tnid=|_(low+high)/2)(2)然后將待查的K值與R[mid].key比較：若相等，則查找成功并返回此位置，否則須確定新的查找區(qū)間，繼續(xù)二分查找，具體方法如下：①若R[mid].key>K，則由表的有序性可知R[mid..n].keys均大于K,因此若表中存在關(guān)鍵字等于K的結(jié)點(diǎn)，則該結(jié)點(diǎn)必定是在位置mid左邊的子表R[1..mid-1]中，故新的查找區(qū)間是左子表R[1..mid-1]。②類似地，若R[mid].key<K，則要查找的K必在mid的右子表R[mid+1..n]中，即新的查找區(qū)間是右子表R[mid+1..n]。下一次查找是針對(duì)新的查找區(qū)間進(jìn)行的。因此，從初始的查找區(qū)間R[1..n]開始，每經(jīng)過一次與當(dāng)前查找區(qū)間的中點(diǎn)位置上的結(jié)點(diǎn)關(guān)鍵字的比較，就可確定查找是否成功，不成功則當(dāng)前的查找區(qū)間就縮小一半。這一過程重復(fù)直至找到關(guān)鍵字為K的結(jié)點(diǎn)，或者直至當(dāng)前的查找區(qū)間為空(即查找失敗)時(shí)為止。3、二分査找算法intBinSearch(SeqListR，KeyTypeK){//在有序表R[1..n沖進(jìn)行二分查找，成功時(shí)返回結(jié)點(diǎn)的位置，失敗時(shí)返回零intlow=1，high=n，mid；〃置當(dāng)前查找區(qū)間上、下界的初值while(lowv=high){//當(dāng)前查找區(qū)間R[low..high]非空mid=(low+high)/2；if(R[mid].key==K)returnmid；〃查找成功返回if(R[mid].kdy>K)high=mid-1;〃繼續(xù)在R[low..mid-1]中查找elseIow=mid+1;〃繼續(xù)在R[mid+1..high]中查找}return0;〃當(dāng)low>high時(shí)表示查找區(qū)間為空，查找失敗}//BinSeareh二分查找算法亦很容易給出其遞歸程序【參見練習(xí)】4、二分査找算法的執(zhí)行過程設(shè)算法的輸入實(shí)例中有序的關(guān)鍵字序列為(05,13,19,21,37,56,64,75,80,88,92)要查找的關(guān)鍵字K分別是21和85。具體查找過程【參見動(dòng)畫演示5、二分查找判定樹二分查找過程可用二叉樹來描述：把當(dāng)前查找區(qū)間的中間位置上的結(jié)點(diǎn)作為根，左子表和右子表中的結(jié)點(diǎn)分別作為根的左子樹和右子樹。由此得到的二叉樹，稱為描述二分查找的判定樹(DecisionTree)或比較樹(ComparisonTree)。注意：判定樹的形態(tài)只與表結(jié)點(diǎn)個(gè)數(shù)n相關(guān)，而與輸入實(shí)例中R[1..n].keys的取值無關(guān)?！纠烤哂?1個(gè)結(jié)點(diǎn)的有序表可用下圖所示的判定樹來表示。（1）二分查找判定樹的組成圓結(jié)點(diǎn)即樹中的內(nèi)部結(jié)點(diǎn)。樹中圓結(jié)點(diǎn)內(nèi)的數(shù)字表示該結(jié)點(diǎn)在有序表中的位置。外部結(jié)點(diǎn)：圓結(jié)點(diǎn)中的所有空指針均用一個(gè)虛擬的方形結(jié)點(diǎn)來取代，即外部結(jié)點(diǎn)。樹中某結(jié)點(diǎn)i與其左（右）孩子連接的左（右）分支上的標(biāo)記"<"、"（"、">"、"）"表示：當(dāng)待查關(guān)鍵字KvR[i].key（K>R[i].key）時(shí)，應(yīng)走左（右）分支到達(dá)i的左（右）孩子，將該孩子的關(guān)鍵字進(jìn)一步和K比較。若相等，則查找過程結(jié)束返回，否則繼續(xù)將K與樹中更下一層的結(jié)點(diǎn)比較。（2）二分查找判定樹的查找二分查找就是將給定值K與二分查找判定樹的根結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較。若相等，成功。否則若小于根結(jié)點(diǎn)的關(guān)鍵字，到左子樹中查找。若大于根結(jié)點(diǎn)的關(guān)鍵字，則到右子樹中查找?！纠繉?duì)于有11個(gè)結(jié)點(diǎn)的表，若查找的結(jié)點(diǎn)是表中第6個(gè)結(jié)點(diǎn)，則只需進(jìn)行一次比較；若查找的結(jié)點(diǎn)是表中第3或第9個(gè)結(jié)點(diǎn)，則需進(jìn)行二次比較；找第1,4,7,10個(gè)結(jié)點(diǎn)需要比較三次；找到第2,5,8,11個(gè)結(jié)點(diǎn)需要比較四次。由此可見，成功的二分查找過程恰好是走了一條從判定樹的根到被查結(jié)點(diǎn)的路徑，經(jīng)歷比較的關(guān)鍵字次數(shù)恰為該結(jié)點(diǎn)在樹中的層數(shù)。若查找失敗，則其比較過程是經(jīng)歷了一條從判定樹根到某個(gè)外部結(jié)點(diǎn)的路徑，所需的關(guān)鍵字比較次數(shù)是該路徑上內(nèi)部結(jié)點(diǎn)的總數(shù)。【例】待查表的關(guān)鍵字序列為：(05,13,19,21,37,56,64,75,80,88,92)，若要查找K=85的記錄，所經(jīng)過的內(nèi)部結(jié)點(diǎn)為6、9、10，最后到達(dá)方形結(jié)點(diǎn)"9-10"，其比較次數(shù)為3。實(shí)際上方形結(jié)點(diǎn)中"i-i+1"的含意為被查找值K是介于R[i].key和R[i+1].key之間的，即R[i].keyvKvR[i+1].key。(3)二分查找的平均查找長(zhǎng)度設(shè)內(nèi)部結(jié)點(diǎn)的總數(shù)為n=2h-1，則判定樹是深度為h=lg(n+1)的滿二叉樹(深度h不計(jì)外部結(jié)點(diǎn))。樹中第k層上的結(jié)點(diǎn)個(gè)數(shù)為2k-i，查找它們所需的比較次數(shù)是k。因此在等概率假設(shè)下，二分查找成功時(shí)的平均查找長(zhǎng)度為：ASLbn=lg(n+1)-1二分查找在查找失敗時(shí)所需比較的關(guān)鍵字個(gè)數(shù)不超過判定樹的深度在最壞情況下查找成功的比較次數(shù)也不超過判定樹的深度。即為：卩靜+1)1二分查找的最壞性能和平均性能相當(dāng)接近。6、二分査找的優(yōu)點(diǎn)和缺點(diǎn)雖然二分查找的效率高，但是要將表按關(guān)鍵字排序。而排序本身是一種很費(fèi)時(shí)的運(yùn)算。既使采用高效率的排序方法也要花費(fèi)0(nign)的時(shí)間。二分查找只適用順序存儲(chǔ)結(jié)構(gòu)。為保持表的有序性，在順序結(jié)構(gòu)里插入和刪除都必須移動(dòng)大量的結(jié)點(diǎn)。因此，二分查找特別適用于那種一經(jīng)建立就很少改動(dòng)、而又經(jīng)常需要查找的線性表。對(duì)那些查找少而又經(jīng)常需要改動(dòng)的線性表，可采用鏈表作存儲(chǔ)結(jié)構(gòu)，進(jìn)行順序查找。鏈表上無法實(shí)現(xiàn)二分查找。分塊查找分塊查找(BlockingSearch)又稱索引順序查找。它是一種性能介于順序查找和二分查找之間的查找方法。1、二分查找表存儲(chǔ)結(jié)構(gòu)二分查找表由"分塊有序"的線性表和索引表組成。(1)"分塊有序"的線性表s=「n/b]表R[1..n]均分為b塊，前b-1塊中結(jié)點(diǎn)個(gè)數(shù)為 ，第b塊的結(jié)點(diǎn)數(shù)小于等于s;每一塊中的關(guān)鍵字不一定有序，但前一塊中的最大關(guān)鍵字必須小于后一塊中的最小關(guān)鍵字，即表是"分塊有序"的。(2)索引表抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成一個(gè)索引表ID[l..b]，即：ID[i](1<i<b)中存放第i塊的最大關(guān)鍵字及該塊在表R中的起始位置。由于表R是分塊有序的，所以索引表是一個(gè)遞增有序表?！纠肯聢D就是滿足上述要求的存儲(chǔ)結(jié)構(gòu)，其中R只有18個(gè)結(jié)點(diǎn)，被分成3塊，每塊中有6個(gè)結(jié)點(diǎn)，第—塊中最大關(guān)鍵字22小于第二塊中最小關(guān)鍵字24，第二塊中最大關(guān)鍵字48小于第三塊中最小關(guān)鍵字49。2、分塊查找的基本思想分塊查找的基本思想是：(1)首先查找索引表索引表是有序表，可采用二分查找或順序查找，以確定待查的結(jié)點(diǎn)在哪一塊。(2)然后在已確定的塊中進(jìn)行順序查找由于塊內(nèi)無序，只能用順序查找。3、分塊査找示例【例】對(duì)于上例的存儲(chǔ)結(jié)構(gòu)：(1)查找關(guān)鍵字等于給定值K=24的結(jié)點(diǎn)因?yàn)樗饕硇?，不妨用順序查找方法查找索引表。即首先將K依次和索引表中各關(guān)鍵字比較，直到找到第1個(gè)關(guān)鍵宇大小等于K的結(jié)點(diǎn)，由于Kv48，所以關(guān)鍵字為24的結(jié)點(diǎn)若存在的話，則必定在第二塊中；然后，由ID[2].addr找到第二塊的起始地址7，從該地址開始在R[7..12]中進(jìn)行順序查找，直到R[11].key=K為止。(2)查找關(guān)鍵字等于給定值K=30的結(jié)點(diǎn)先確定第二塊，然后在該塊中查找。因該塊中查找不成功，故說明表中不存在關(guān)鍵字為30的結(jié)點(diǎn)。具體過程【參見動(dòng)畫演示4、算法分析(1)平均查找長(zhǎng)度ASL分塊查找是兩次查找過程。整個(gè)查找過程的平均查找長(zhǎng)度是兩次查找的平均查找長(zhǎng)度之和。以二分查找來確定塊，分塊查找成功時(shí)的平均查找長(zhǎng)度ASLb|k=ASLbn+ASLsq=lg(b+1)-1+(s+1)公lg(n/s+1)+s/2以順序查找確定塊，分塊查找成功時(shí)的平均查找長(zhǎng)度ASL'blk=(b+1)/2+(s+1)/2=(S2+2s+n)/(2s)注意：當(dāng)s=^時(shí)ASL'b|k取極小值臨+1，即當(dāng)采用順序查找確定塊時(shí)，應(yīng)將各塊中的結(jié)點(diǎn)數(shù)選定為石?！纠咳舯碇杏?0000個(gè)結(jié)點(diǎn)，則應(yīng)把它分成100個(gè)塊，每塊中含100個(gè)結(jié)點(diǎn)。用順序查