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

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