T12-基于線性表的查找算法

基于線性表的查找算法第六章

主講：周翔回顧請(qǐng)思考如何用鄰接表來存儲(chǔ)圖。請(qǐng)簡述圖的廣度優(yōu)先遍歷和深度優(yōu)先遍歷。預(yù)習(xí)檢查請(qǐng)描述一下折半查找的算法思想。請(qǐng)回答構(gòu)造哈希函數(shù)有哪幾種方法。本章目標(biāo)3樹表的查找重點(diǎn)了解掌握2哈希表的查找線性表的查找1查找的基本概念查找的定義是在一些（有序的/無序的）數(shù)據(jù)元素中，通過一定的方法找出與給定關(guān)鍵字相同的數(shù)據(jù)元素。查找的基本概念列表：由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合，可利用任意數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。關(guān)鍵字：數(shù)據(jù)元素的某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)列表中的一個(gè)或一組數(shù)據(jù)元素。主關(guān)鍵字：惟一標(biāo)識(shí)列表中的一個(gè)數(shù)據(jù)元素次關(guān)鍵字：不是主關(guān)鍵字，就為次關(guān)鍵字當(dāng)數(shù)據(jù)元素僅有一個(gè)數(shù)據(jù)項(xiàng)時(shí)，數(shù)據(jù)元素的值就是關(guān)鍵字查找的基本概念查找：根據(jù)給定的關(guān)鍵字值，在特定的列表中確定一個(gè)其關(guān)鍵字與給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在列表中的位置。靜態(tài)查找：在查找過程中只是對(duì)數(shù)據(jù)元素進(jìn)行查找動(dòng)態(tài)查找：在實(shí)際查找的同時(shí)，插入找不到的元素，或從查找表中刪除已查到的某個(gè)元素查找的基本概念查找的基本方法：比較式查找法計(jì)算式查找法－HASH（哈希）查找法基于線性表的查找法基于樹的查找法查找的基本概念在查找算法中要用到三類參量：①查找對(duì)象K（找什么）②查找范圍L（在哪找）③查找的結(jié)果（K在L中的位置）①、②為輸入?yún)⒘?，在函?shù)中不可缺少③為輸出參量，可用函數(shù)返回值表示查找的基本概念平均查找長度（ASL）：為確定數(shù)據(jù)元素在列表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值，稱為查找算法在查找成功時(shí)的平均查找長度。平均查找長度（ASL）的計(jì)算方式對(duì)于長度為n的列表，查找成功時(shí)的平均查找長度為：Pi為查找列表中第i個(gè)數(shù)據(jù)元素的概率Ci為找到列表中第i個(gè)數(shù)據(jù)元素時(shí)，已經(jīng)進(jìn)行過的關(guān)鍵字比較次數(shù)。ASL=P1C1+P2C2+…+PnCn=

i=1nPiCi基于線性表的查找法順序表的查找法有序表的查找法索引順序查找法順序表的查找法基本思想：從表的一端開始，順序掃描線性表，依次將掃描到的元素的關(guān)鍵字與給定的關(guān)鍵字k相比較。若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字與k相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字與k相等的元素，則查找失敗。dagw…kqo順序表的查找法平均查找長度（ASL）的計(jì)算方式假設(shè)列表長度為n，查找從最后一個(gè)元素開始找起：查找第1個(gè)元素，需進(jìn)行n次比較；查找第2個(gè)元素，需進(jìn)行n-1次比較；…………查找第n個(gè)元素，需進(jìn)行1次比較又假設(shè)查找每個(gè)數(shù)據(jù)元素的概率相等，即Pi=1/n則順序查找算法的平均查找長度為： ASL=1*1/n+2*1/n+…+n*1/n =(1+2+…+n)*1/n=(n+1)/2順序表的查找法假設(shè)列表長度為n，從最后一個(gè)元素開始找起：查找第i個(gè)元素，需進(jìn)行()次比較?

若順序查找法從第一個(gè)元素開始找起，則平均查找長度為(

)？

n-i+1(n+1)/2，一樣!順序表的查找法順序表的查找算法的特點(diǎn)算法簡單，對(duì)表結(jié)構(gòu)無任何要求（順序和鏈?zhǔn)剑﹏很大時(shí)查找效率較低改進(jìn)措施：非等概率查找時(shí)，可按照查找概率進(jìn)行排序。有序表的查找法有序表是元素有序排列的查找表，它也是順序表中的一種，但相比于無序表來說，有序表中的元素都是有序排列的，因此查找時(shí)會(huì)有一些效率更高的方法。常用的有序查找算法：折半查找插值查找斐波那契查找有序表的查找法——折半查找法(二分查找法)前提條件：必須采用順序存儲(chǔ)結(jié)構(gòu)必須按關(guān)鍵字大小有序排列！?。』舅枷耄簩⒈碇虚g位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。有序表的查找法——折半查找法(二分查找法)假設(shè)要查找元素：e=42

121728313336384259middleleft=1right=9middle=512345678967比較次數(shù)：1比較次數(shù)：288比較次數(shù)：3middle

leftright

left42>3342>3842==42有序表的查找法——折半查找法(二分查找法)用折半查找法查找12的過程：有序表的查找法——折半查找法(二分查找法)有序表的查找法——折半查找法(二分查找法)用折半查找法查找50的過程：有序表的查找法——折半查找法(二分查找法)當(dāng)high<low時(shí)，表示不存在這樣的子表空間，查找失敗!!!!有序表的查找法——折半查找法(二分查找法)折半查找法的平均查找長度（ASL）假設(shè)列表長度為n：查找第1個(gè)元素，需進(jìn)行？次比較；查找第2個(gè)元素，需進(jìn)行？次比較；…………查找位于中間位置的元素，需進(jìn)行？次比較；…………查找第n個(gè)元素，需進(jìn)行？次比較又假設(shè)查找每個(gè)數(shù)據(jù)元素的概率相等，即Pi=1/n有序表的查找法——折半查找法(二分查找法)折半查找過程可用一判定樹描述判定樹：樹中每一結(jié)點(diǎn)表示表中一記錄，結(jié)點(diǎn)值記錄在表中的位置。從根到被查結(jié)點(diǎn)路徑關(guān)鍵字比較次數(shù)為被查結(jié)點(diǎn)層數(shù)成功進(jìn)行最多比較次數(shù)不超過樹的深度有序表的查找法——折半查找法(二分查找法)用折半查找法查找12的過程：251546182858122235660比較1次，1個(gè)比較2次，2個(gè)比較3次，4個(gè)比較4次，4個(gè)有序表的查找法——折半查找法(二分查找法)n個(gè)結(jié)點(diǎn)的判定樹的深度與n個(gè)結(jié)點(diǎn)的完全二叉樹的深度相等，均為假定表的長度n=2h-1，則相應(yīng)判定樹必為深度是h的滿二叉樹h=log2(n+1)折半查找法的平均查找長度為：

ASLbs＝

i=1nPiCi＝n1

j=1nj×2j-1＝nn+1log2(n+1)-1有序表的查找法——折半查找法(二分查找法)優(yōu)點(diǎn)：比較次數(shù)少，查找速度快，平均性能好缺點(diǎn)：要求待查表為有序表，且插入刪除困難。有序表的查找法——插值查找法插值查找是對(duì)折半查找的一種優(yōu)化，但是它的適用場景也比折半查找更狹窄，要求查找表不僅是已經(jīng)排好序的，而且呈均勻分布。在折半查找中，mid=(begin+last)/2，而在插值查找中，如果要查找的關(guān)鍵字為key，則mid=begin+(key-arr[begin])*(last-begin)/(arr[last]-arr[begin])。有序表的查找法——斐波那契查找在C語言中我們學(xué)習(xí)過斐波那契數(shù)列，在斐波那契數(shù)列中，有一個(gè)特性，對(duì)于任一角標(biāo)k(k>=2)，F(xiàn)[k]=F[k-1]+F[k-2]，即后邊每一個(gè)數(shù)都是前兩個(gè)數(shù)的和。而且隨著數(shù)列的遞增，前后兩個(gè)數(shù)的比值會(huì)越來越接近黃金分割數(shù)—0.618，利用這個(gè)特性，就可以將黃金比例運(yùn)用到查找技術(shù)中。但要注意：如果一個(gè)有序表的元素個(gè)數(shù)為n，并且n正好是某個(gè)斐波那契數(shù)減1，即滿足n=F[k]-1時(shí)，才能使用斐波那契查找。如果元素個(gè)數(shù)n不滿足這個(gè)關(guān)系，那么需要將查找表擴(kuò)展，直到n滿足這個(gè)關(guān)系。索引順序查找索引順序查找又叫分塊查找，它是介于順序查找和折半查找之間的一種查找方法。在此查找方法中，除查找表外還需要為查找表建立一個(gè)“索引表”，索引表是分段有序的。將查找表分為若干個(gè)子表，為每一個(gè)子表建立一個(gè)索引項(xiàng)存儲(chǔ)在索引表中，索引項(xiàng)包括兩項(xiàng)內(nèi)容：關(guān)鍵字項(xiàng)和指針項(xiàng)。索引順序查找前提條件：要求將列表組織成以下索引順序結(jié)構(gòu)首先將列表分成若干個(gè)塊（子表）。一般情況下，塊的長度均勻，最后一塊可以不滿。每塊中元素任意排列，即塊內(nèi)無序，但塊與塊之間有序。構(gòu)造一個(gè)索引表。其中每個(gè)索引項(xiàng)對(duì)應(yīng)一個(gè)塊并記錄每塊的起始位置，和每塊中的最大關(guān)鍵字（或最小關(guān)鍵字）。索引表按關(guān)鍵字有序排列索引順序查找此表包括三個(gè)塊：第一個(gè)塊的起始地址為0，塊內(nèi)最大關(guān)鍵字為25；第二個(gè)塊的起始地址為5，塊內(nèi)最大關(guān)鍵字為58；第三個(gè)塊的起始地址為10，塊內(nèi)最大關(guān)鍵字為88。索引順序查找基本思想：（1）首先根據(jù)給定的關(guān)鍵字key，在索引表中查找以確定key所在的子表；（2）然后再在子表中查找關(guān)鍵字為key的元素，如果找到，則查找成功；否則查找失敗。索引表是有序表，則既可進(jìn)行順序查找也可進(jìn)行折半查找，以確定待查元素所在子表；而子表可能是無序的，因此只能用順序查找。索引順序查找查找36：將36與索引表中的關(guān)鍵字比較，因?yàn)?5<36≤58，所以36在第二塊中；在第二塊中順序查找，最后在8單元中找到36。索引順序查找分塊查找法的平均查找長度包括兩個(gè)部分：查找索引表時(shí)的平均查找長度為LB，在相應(yīng)塊內(nèi)進(jìn)行順序查找的平均查找長度LW。ASLbs=LB+LW索引順序查找假定將長度為n的