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

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

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

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

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

)？

n-i+1(n+1)/2，一樣!順序表的查找法順序表的查找算法的特點算法簡單，對表結構無任何要求（順序和鏈式）n很大時查找效率較低改進措施：非等概率查找時，可按照查找概率進行排序。有序表的查找法有序表是元素有序排列的查找表，它也是順序表中的一種，但相比于無序表來說，有序表中的元素都是有序排列的，因此查找時會有一些效率更高的方法。常用的有序查找算法：折半查找插值查找斐波那契查找有序表的查找法——折半查找法(二分查找法)前提條件：必須采用順序存儲結構必須按關鍵字大小有序排列！??！基本思想：將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。有序表的查找法——折半查找法(二分查找法)假設要查找元素：e=42

121728313336384259middleleft=1right=9middle=512345678967比較次數：1比較次數：288比較次數：3middle

leftright

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

ASLbs＝

i=1nPiCi＝n1

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