數(shù)據(jù)結(jié)構(gòu)第九章查找知識(shí)點(diǎn)總結(jié)

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