數據結構第九章查找知識點總結188第7章查找本書在第2章至第6章中已經介紹了線性表、樹和圖等數據結構在這一章將討論另一種在數據應用中大量使用的數據結構——查找表。和查找表相關的查找操作是數據結構及算法中一種常見操作在計算機中有著廣泛的應用。利用計算機進行查找首先需要把原始數據按照一定的邏輯結構整理起來并按照一定的存儲結構存入到計算機中變為計算機可處理的數據結構如順序表、鏈表等然后再通過查找算法在這個查找表上查找出必需的信息。數據的存儲結構除了已經討論過的順序存儲結構和鏈式存儲結構外還有索引存儲結構和散列存儲結構。下面將就這些存儲結構討論各種查找算法以及分析多種算法的性能。7.1查找的基本概念查找表table是由同一類型的數據元素或記錄構成的集合。對查找表經常進行的操作有1查詢某個“特定的”數據元素是否在查找表中2檢索某個“特定的”數據元素的各種屬性3在查找表中插入一個數據元素4從查找表中刪去某個數據元素。在日常生活中人們每天都要進行“查找工作”。例如在電話號碼簿中查閱“某單位”或“某人”的電話號碼從字典中查閱“某個詞”的讀音和含義等等。其中“電話號碼簿”和“字典”均可視作是一張查找表。由此可見所謂“查找”就是在一個含有眾多的數據運算或記錄的查找表中找出某個“特定的”數據元素或記錄。為了便于討論這里給出“特定的”詞的確切含義。首先需引入一個“關鍵字”的概念。關鍵字key是數據元素或記錄中某個數據項的值用以標識識別一個數據元素或記錄。若此關鍵字可以唯一的識別一個記錄則稱之謂“主關鍵字”PrimaryKey反之若此關鍵字能識別若干記錄則稱之謂“次關鍵字”。查找Search也稱檢索即根據給定的某個值在查找表中確定一個其關鍵字等于給定值的第一條記錄元素或全部記錄。若表中存在這樣的記錄則查找成功通常要求返回該記錄存儲位置若不存在這樣的記錄表明查找失敗返回特定值。例如當用計算機進行學籍管理時學生的基本情況可以用表7-1所示的表結構存儲在計算機中表中每一行為一個記錄學生的學號為記錄的關鍵字。若在此表中查找學號為“98182”的學生信息將給定值“98182”依次和學號列中的各個值進行比較最后可得到該學生的姓名為“袁秋慧”、“女”、來自于“廣州”、1980年10月出生此時查找是成功的。若在此表中查找學號為“98200”的學生信息則由于表中沒有關鍵字為“98200”189的記錄則查找不成功。表7-1學生基本信息表學號姓名性別籍貫出生年月198131劉激揚男北京1979.12298164衣春生男青島1979.07398165盧聲凱男天津1981.02498182袁秋慧女廣州1980.10598203林德康男上海1980.05用于在表上查找記錄的條件情況比較復雜它由具體應用而定但其中最具代表性的條件是上述例子中的條件即在關鍵字段項上查找關鍵字等于給定值Key所在的記錄。由于表中每個記錄的關鍵字都不同在某些特殊應用中也可能出現相同的關鍵字所以這種條件只可能查找到惟一的一條記錄。在本章的討論中我們將以這種條件為依據給出各種查找的算法。作為查找對象的表的結構不同其查找方法一般也不同。但無論哪一種方法其查找過程都是用給定值K同關鍵項上的關鍵字按照一定的次序進行比較的過程比較次數的多少就是相應算法的時間復雜度這是衡量查找算法優劣的重要指標。對于一個查找算法的時間復雜度既可以用數量級的形式表示也可以采用平均查找長度ASL——AverageSearchLength即用在查找成功情況下的平均比較次數來表示。平均查找長度的計算公式為niiiCPASL1其中:n為表長Pi為查找表中第i個記錄的概率且11niiPCi為找到該記錄時曾和給定值比較過的關鍵字的個數若查找每個元素的概率相同則平均查找長度的計算公式可簡化為ASL1/nniiiCPASL1Ci例如在具有n個元素的線性表上順序查找關鍵字等于K的元素時Cii所以平均查找長度為niiiCPASL11/nniiiCPASL1in1/2對應算法的時間復雜度為On。1907.2順序表查找7.2.1順序查找1順序查找思路順序表SequentialList指線性表的順序存儲結構。本章討論中設順序表采用一維數組A表示其元素類型為ElemType它含有關鍵字域key和其它一些數據域并設定A的大小為整型常量MaxSize數組的元素個數為nn應小于等于MaxSize。typedefstructKeyTypekey…ElemType順序查找SequentialSearch又稱線性查找它是一種最簡單最基本查找方法。查找思路從順序表的一端開始依次將每個元素關鍵字同給定值K進行比較若某個元素關鍵字等于K則查找成功返回該元素所在下標若直到所有元素都比較完畢仍找不到關鍵字為K的元素則查找失敗返回特定值常用-1表示。2“順序查找”算法順序查找的算法描述如下IntSeqschElemTypeAintnKeyTypeK//從順序表A的n個元素中順序查找關鍵字為K的元素//若成功返回其下標否則返回-1forinti0iltniifAi.keyKbreak//查找成功返回下標否則返回-1ifiltnreturnielsereturn-1例如利用上述算法在下述順序表中查找56要比較3次。0123452345643278在順序表中查找56比較3次1913“順序查找”改進算法對順序表而言平均查找長度的計算公式中的Ci可由下述公式得到Cin-i1所以ASLnP1n-1P2…2Pn-1Pn在等概率查找的情況下nPi1順序表查找的平均查找長度為21111ninnASLniss在不等概率查找的情況下ASLss在PnPn-1P2P1時取極小值若查找概率無法事先測定則查找過程采取的改進辦法是在表的尾端An設一崗哨在查找前先將K賦給An這樣每循環一次不需比較下標是否越界當比較到第n位置時由于An.keyK成立必退出循環。intSeqschElemTypeAintnKeyTypeK//從順序表A的n個元素中順序查找關鍵字為K的元素//若成功返回其下標否則返回-1An.keyk//設置崗哨forinti0iifAi.keyKbreakifiltnreturnielsereturn-10123456234564327856在順序表中查找56設A656為崗哨4“順序查找”算法性能描述順序查找的缺點是速度較慢查找成功最多需比較n次平均查找長度約為表長一半。查找失敗也需比較n1次所以順序查找的時間復雜度為On。192順序查找的優點是既適用于順序表也適用于單鏈表同時對表中元素的排列次序無要求這將給插入元素帶來方便因為不需要為新元素尋找插入位置和移動原有元素只要把它加入到表尾對于順序表或表頭單鏈表即可。7.2.2二分查找上述順序查找表的查找算法簡單但平均查找長度較大特別不適用于表長較大的查找表。1二分查找思路二分查找BinarySearch又稱折半查找。作為二分查找對象的表必須是順序存儲的有序表。通常假定有序表是按關鍵字從小到大排序。查找的過程是首先取整個有序表A0An-1的中點元素Amidmid?n-1/2?的關鍵字與K比較其具體描述為2二分查找過程圖示查找23查找96193查找583二分查找的遞歸算法intBinschElemTypeAintlowinthighKeyTypeK//在AlowAhigh內查找Klow初值為0high初值n-1iflowlthighintmidlowhigh/2//求中間點下標ifKAmid.keyreturnmid//查找成功返回elseifKltAmid.keyreturnBinschAlowmid-1K//左子表上查找else194returnBinschAmid1hignK//右子表上查找elsereturn-1//查找失敗返回-14二分查找的非遞歸算法二分查找的遞歸算法也屬于末尾遞歸的調用很容易把它改成非遞歸算法其算法描述為intBinschElemTypeAintnKeyTypeK//在A0An-1區間內查找關鍵字為K的元素intlow0highn-1//給表示待查區間上界和下界的變量賦初值whilelowlthighintmidlowhigh/2//求出待查區間中間點元素的下標ifKAmid.keyreturnmid//查找成功返回elseifKltAmid.keyhighmid-1//修改區間上界使下一次循環在左子表上查找elselowmid-1//修改區間上界使下一次循環在右子表上查找elsereturn-1//查找失敗返回-1例如在有序表A中有10個元素即n10的關鍵字序列為12232637546068758296當給定值K分別為2396和58時進行二分查找的過程如前2二分查找過程圖示所示。5二分查找判定樹二分查找判定樹將二分查找過程用一棵二叉樹來描述樹中每個根結點對應當前查找區間的中點元素Amid該樹是一棵二叉排序樹。例假定有序表A中10個元素關鍵字序列為12232637546068758296123456789其判定樹如圖7-1所示判定樹高h與結點數n的關系h?log2n?1195圖7-1二分查找判定樹二分查找的平均查找長度為1/nniiiCPASL1Ci其中niiiCPASL1Ci為查找所有元素所需的比較次數之和。二分查找的平均查找長度為ASL1/nniiiCPASL1Ci1/nin112i-1ihn1-2h-1二分查找時間復雜度為Olog2n二分查找的優點是比較次數少查找速度快但在查找之前要為建立有序表付出代價同時對有序表的插入和刪除都需要平均比較和移動表中的一半元素是很浪費時間的操作所以二分查找適用于數據相對穩定的情況。另外二分查找只適應于順序存儲的有序表不適應于鏈式存儲的有序表。7.3索引查找7.3.1索引的概念和索引表的類型定義索引查找IndexSearch又稱分級查找。它在日常生活中有廣泛的應用。例如要在《數據結構》一書中查找“二叉樹”的內容則先在目錄中查找到對應章節的頁碼然后再到該頁碼的正文中去查找相應內容在這里整本書就是索引查找的對象章節的正文是教材的主要內容被稱之為主表目錄是為了便于查找主表而建立的索引被稱之為索引表。索引表可以有多級。在計算機中為索引查找而建立的主表和各級索引表其主表只有一個索引表的級數和數量不受限制可根據具體需要確定。在計算機中索引查找是在集合或線性表的索引存儲結構的基礎上進行的。索引存儲的基本思想是首先把一個線性表對應為主表按照一定的函數關系或條件劃分成若干個邏輯上的子表為每個子表分別建立一個索引項由所有這些索引項構成主表的一個索引196表然后可采用順序或鏈接方式存儲索引表和子表。索引表中每個索引項通常包含三個域一是索引值域index用來存儲標識對應子表的索引值它相當于記錄的關鍵字在索引表中由此索引值來惟一標識一個索引項亦即惟一標識一個子表二是子表開始位置域start用來存儲對應子表的第一個元素的存儲位置三是子表長度域length用來存儲對應子表的元素個數。索引項的類型和順序存儲的索引表的類型可分別定義為structInbdexItemIndexKeyindex//IndexKeyType為事先定義的索引值類型Intstart//子表中第一個元素所在的下標位置Intlength//子表的長度域typedefIndexItemindexlistILMSize//ILMSize為事先定義的整型常量它要大于等于索引項數m若所有子表合稱為主表被順序存儲或靜態鏈接存儲在同一個數組中則該數組的類型定義為typedefElemTypemainlistMaxSize//MaxSize為事先定義的整型常量它要大于等于主表中元素的個數n例如一個學校的教師登記表如表7-2所示此表可看作為按記錄前后位置順序排列的線性表若以每個記錄的“職工號”作為關鍵字則線性表假定用LA表示可簡記為LAJS001JS002JS003S004DZ001DZ002DZ003JJ001JJ002HG001HG002HG003若按照“單位”數據項的值或關鍵字中的前兩位字符對線性表LA進行劃分使得具有相同值的元素在同一個子表中則得到的四個子表分別為JSJS001JS002JS003JS004DZDZ001DZ002DZ003JJJJ001JJ002HGHG001HG002HG003可得索引表b1如表7-3所示表7-2教師登記表職工號姓名單位職稱工資JS001王大明計算機教授680JS002吳進計算機講師440JS003邢懷學計算機講師460DZ001趙利電子助教380DZ002劉平電子講師480DZ003張衛電子副教授600197JJ001安曉軍機械講師450JJ002趙京華機械講師440HG001孫亮化工教授720HG002陸新化工副教授580HG003王方化工助教400表7-3索引表b1indexstartlength0JS031DZ332JJ623HG83若使用具有mainlist類型的一維數組a來順序存儲這四個子表即整個主表在每個子表的后面可以預留一些空閑位置待插入新元素之用假定在質量不預留空閑位置同時使用具有indexlist類型的一維數組b1來順序存儲這種劃分所得到的索引表則b1中的內容如表7-3所示。對于上面的線性表LA若按照職稱數據項的值進行劃分使得具有相同職稱的記錄在同一個子表中則得到的四個子表分別為JHSJS001HG001KJSJS004DZ003HG002JIAJS002JS003DZ002JJ001JJ002ZHUDZ001HG003若在上一次劃分使用的主表a的基礎上來鏈接存儲這一次劃分所得到的子表則首先需要在主表a的元素類型ElebType中增加一個整數類型的指針域next然后利用這個指針域把這一次每個子表中的元素分別鏈接起來鏈接后得到的每個鏈接子表如圖7-2所示其中每個指針上的數值為該指針的具體值即所指向節點元素的下標位置。JS001HG001-1JS004DZ003HG002-1JS002JS003DZ002JJ001JJ002-1DZ001HG003-1圖7-2鏈接子表設用具有indexlist類型的一維數組b2來順序存儲這次劃分所得到的索引表每個子表已在主表a中鏈接存儲則b2中的內容如表7-4所示。JIAJSHFJSZHU198表7-4索引表b2indexstartlength0教授021副教授332講師153助教427.3.2索引查找算法索引查找算法思路索引查找是在索引表和主表上進行的查找其過程是首先根據給定的索引值K1在索引表上查找出索引值等于K1的索引項以確定對應子表在主表中開始位置和長度然后再根據給定關鍵字K2在對應子表中查找出關鍵字等于K2的元素結點。設數組A是具有mainlist類型的一個主表數組B是具有indexlist類型的在主表A上建立的一個索引表m為索引表B的實際長度即所含的索引項的個數K1和K2分別為給定待查找的索引值和關鍵字當然他們的類型應分別為索引表中索引值域的類型和主表中關鍵字域的類型并假定每個子表采用順序存儲則索引查找算法的描述為intIndschmainlistAindexlistBintmIndexKeyTypeK1KeyTypeK2//利用主表A和大小為m的索引表B索引查找索引值為K1關鍵字為K2的記錄//返回該記錄在主表中的下標位置若查找失敗返回-1intij//在索引表中順序查找索引值為K1的索引項fori0iltmiifK1Bi.indexbreakifimreturn-1//在已查找到的第i個子表中順序查找關鍵字為K2的記錄jBi.startwhilejltBi.startBi.lengthifK2Aj.keybreakelsejifjltBi.startBi.lengthreturnjelsereturn-1若每個子表在主表A中采用的是鏈接存儲只要把上述算法中的while循環和其后的if語句進行修改即可請讀者自己完成。設索引表長度為m相應子表長度為s索引查找的平均查找長度為ASLm1/2s1/21997.3.3分塊查找分塊查找BlockingSearch屬于索引查找它要求主表中每個子表之間遞增或遞減有序即前塊中的最大關鍵字必須小于后塊中的最小關鍵字或者說后塊中的最小關鍵字必須大于前塊中的最大關鍵字但每塊中元素的排列次序可以是任意的它還要求索引表中每個索引項的索引值域用來存儲對應塊中的最大關鍵字。由分塊查找對主表和索引表的要求可知1索引表是按索引值遞增或遞減有序的即索引表是一個有序表2主表中的關鍵字域和索引表中的索引值域具有相同的類型即為關鍵字所屬的類型。圖7-3所示就是一個分塊查找的示例主表被劃分為三塊每塊占有5個記錄位置第一塊中含有4個紀錄第二塊中含有5個記錄第三塊中含有3個記錄。第一塊中的最大關鍵字為34它小于第二塊中的最小關鍵字36第二塊中的最大關鍵字為72它小于第三塊中的最小關鍵字86所以主表中塊與塊之間是遞增有序的。從圖中的索引表可以看出每個索引項中的索引值域保持著對應塊中的最大關鍵字索引表是按照索引值遞增有序的。圖7-3分塊查找示例分塊查找的思路進行分塊查找時應根據所給的關鍵字首先查找索引表從中查找出給定值K剛好小于等于索引值的那個索引項從而找到待查塊然后再查找這個塊從中找到待查的記錄若存在的話。由于索引表是有序的所以在順序表上即可以采用順序查找也可以采用二分查找而每個塊中的記錄排列是任意的所以在塊內只能采用順序查找。如根據圖8-3查找關鍵字為40的記錄時。假定采用順序的方法查找索引表首先用40和第一項索引值34進行比較因40gt34則接著和第二項索引值72進行比較因40lt72所以查找結束轉而順序查找主表中從下標5開始的塊因關鍵字為40的記錄位于該塊的第三個位置所以經過三次比較后查找成功。分塊查找的算法同上面已經給出的索引查找算法類似其算法描述為intBlockschmainlistAindexlistBintmKeyTypeK//利用主表A和大小為m的索引表B分塊查找關鍵字為K的記錄intij//在索引表中順序查找關鍵字為K所對應的索引項fori0iltmi200ifKltBi.indexbreakifimreturn-1//在已經查找到的第i個子表中順序查找關鍵字KjBi.startwhilejltBi.startBi.lengthifKAj.keybreakelsej//若查