搜寻资料结构.ppt

《搜寻资料结构.ppt》由会员分享，可在线阅读，更多相关《搜寻资料结构.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、搜尋資料結構Search Structures學習目標在學習本章之後，讀者們要能夠瞭解：搜尋的定義。搜尋的種類及不同搜尋的資料結構及演算法。電腦程式如何處理資料的搜尋。搜尋主要目的是從一組資料中尋找符合某種條件的資料，若是以資料的值來搜尋，可以把這個值當作搜尋鍵(Search key)，根據搜尋鍵找到的是所有和搜尋鍵等值的資料。電腦搜尋資料的優點是快速當資料量很龐大時，如何快速搜尋到資料是本章所要探討的一般電腦檔案是記錄的集合，每一筆記錄包含許多欄位，其中必須至少有一個欄位可當作關鍵值（key），從資料檔案中找出滿足某些關鍵值的記錄之動作稱之為搜尋（search）搜尋的分類搜尋的分類 在最短時

2、間內有效的找到所需資料，是一個相當重要的課題 影響插搜尋時間長短的主要因素包括有演算法、資料儲存的方式及結構 內部搜尋與外部搜尋內部搜尋與外部搜尋 內部搜尋：欲找尋的資料或檔案較小，可以直接全部載入欲找尋的資料或檔案較小，可以直接全部載入記憶體中來進行搜尋的動作。記憶體中來進行搜尋的動作。外部搜尋：若要找尋的資料數目很大，無法一次將全部內若要找尋的資料數目很大，無法一次將全部內容置於主記憶體內，而需使用到外部的輔助記容置於主記憶體內，而需使用到外部的輔助記憶體來分次處理。憶體來分次處理。靜態搜尋及動態搜尋靜態搜尋及動態搜尋靜態搜尋(Static Search)：在搜尋過程中，資料不會有增加、刪

3、除或更新在搜尋過程中，資料不會有增加、刪除或更新等行為。例如符號表的搜尋。等行為。例如符號表的搜尋。動態搜尋(Dynamic Search)：在搜尋過程中，資料會經常有增加、刪除或更在搜尋過程中，資料會經常有增加、刪除或更新等行為。新等行為。循序搜尋法Sequential search定義循序搜尋(Sequential search)，又稱為線性搜尋(Linear Searching)，是最單純亦是最基本的搜尋方式不需事先將被搜尋的檔案記錄按其鍵值排序，只需依照資料儲存的順序，逐一比較資料值是否與指定的值相等，若找到則傳回陣列的索引值，否則傳回0。演算法虛擬碼/n指a 中的元素個數，key為欲

4、比對的資料/procedure seqsch(int a,int n,int key)index i;for(a 的第一個元素至最後一個元素)if(key=a i)顯示找到的訊息並跳出迴圈;if(到最後的元素仍找不到)顯示找不到的訊息;C語言程式碼int seqsch(int a,int n,int key)int i=0;an=key;while(ai!=key)i+;if(i n)printf(“%d 在陣列中的第%d 筆.n”,key,i+1);return(i);elseprintf(“找不到資料!n”);return(-1);時間複雜度分析最差狀況指的是必須搜尋整個陣列，即資料並未出

5、現在陣列中，在此情況下演算法必須做n次比較。在平均狀況下，假設資料出現在陣列中的機率都相等的話，那也要做(n+1)/2次。【分析】當資料量n很大時，就不適合用循序搜尋法，但可估計每一筆資料所要搜尋的機率，將機率高的放在檔案的前端，以減少搜尋的時間。程式實作#include void main()int data 10=75,33,98,44,56,24,65,48,83,12int i,input;printf(“nn”);printf(“nData:“);for(i=0;i 10;i+)printf(“%d“,data i);puts(“);printf(“nPlease enter a n

6、umber from data:“);scanf(“%d”,&input);printf(“nSearch.n”);for(i=0;i 10;i+)for(i=0;i 10;i+)printfprintf(“(“nDatanData when searching%2d when searching%2d time(stime(s)is%d!”,)is%d!”,i+1,i+1,dataidatai););if(input=data i)break;if(input=data i)break;if(i=10)if(i=10)printfprintf(“(“nnSorrynnSorry,%d not

7、 found!“,input);,%d not found!“,input);elseelseprintfprintf(“(“nnSorrynnSorry,%d is the%,%d is the%dthdth record in data!“,record in data!“,input,i+1);input,i+1);二分搜尋法Binary Search定義假如資料本身是經過排序的，在搜尋時可以利用二分的方法，每次都把陣列分成兩半，然後從其中的一半繼續搜尋，這種方法叫做二分搜尋(Binary search)二分搜尋的演算法 演算法則檔案中的資料須按鍵值排序，並找出檔案中間檔案中的資料須按鍵

8、值排序，並找出檔案中間檔案中的資料須按鍵值排序，並找出檔案中間檔案中的資料須按鍵值排序，並找出檔案中間位罝的鍵值位罝的鍵值位罝的鍵值位罝的鍵值KmKm用來作比較，其中用來作比較，其中用來作比較，其中用來作比較，其中m=(1+u)/2m=(1+u)/2，1 1及及及及u u表示資料的開始及結束位址。表示資料的開始及結束位址。表示資料的開始及結束位址。表示資料的開始及結束位址。搜尋方式分下面三種情形進行：搜尋方式分下面三種情形進行：搜尋方式分下面三種情形進行：搜尋方式分下面三種情形進行：1.1.Key KmKey KmKey Km：則表示欲尋找的資料在檔案的後半部。：則表示欲尋找的資料在檔案的後半

9、部。：則表示欲尋找的資料在檔案的後半部。：則表示欲尋找的資料在檔案的後半部。重新調整重新調整重新調整重新調整1 1及及及及u u，並重複上述步驟，直到搜尋成，並重複上述步驟，直到搜尋成，並重複上述步驟，直到搜尋成，並重複上述步驟，直到搜尋成功或資料已全部搜尋完畢為止。功或資料已全部搜尋完畢為止。功或資料已全部搜尋完畢為止。功或資料已全部搜尋完畢為止。演算法虛擬程式碼int binsch(int a,int low,int high,int key)int mid;if(low key)return(binsch(a,low,mid 1,key);else returnreturn(binsch

10、(a,low,mid+1,key);elsereturn(-1);C語言程式碼int binsch(int a,int low,int high,int key)int mid;if(low key)return(binsch(a,low,mid 1,key);else returnreturn(binsch(a,low,mid+1,key);elsereturn(-1);時間複雜度分析【分析】由於二分搜尋每一次搜尋都要比上一次少一半的範圍，所以要找出資料的位置，最多只需要比較log2n+1或log2(n)次。程式實作#include void main()int data 10=12,24,

11、29,38,44,57,64,75,82,98int i,l=1,u=10,m,cnt=0,input,ok=0;printf(“nn”);printf(“nSorted Data:“);for(i=0;i 10;i+)printf(“%d“,data i);puts(“);printf(“nPlease enter a number from data:“);scanf(“%d”,&input);printf(“nSearch.n”);m=(1+u)/2while(l input)u=m 1print(“-Choice number is smaller than%d,datam);else

12、if(data m Choice number is bigger than%d”,data m);elseprintf(“nnfound,%d is the%dth record in data!“,input,m);ok=1;m=(1+u)/2if(ok=0)printf(“nnSorry,%d not found!“,input);內插式搜尋法定義內插式搜尋法是二分搜尋法的改良，它能內插式搜尋法是二分搜尋法的改良，它能更準確地預測資料位置所在，若假設所有更準確地預測資料位置所在，若假設所有資料是平均分佈在整個陣列之中，也就是資料是平均分佈在整個陣列之中，也就是每一筆資料值的差距是很接近的

13、。每一筆資料值的差距是很接近的。資料資料key位置的合理假設為：位置的合理假設為：Middle=Min+(target-Middle=Min+(target-List(MinList(Min)*(Max-Min)/()*(Max-Min)/(List(MaxList(Max)-)-List(MinList(Min)或或或或Middle=low+(key a low)*(high-low)/(Middle=low+(key a low)*(high-low)/(ahighahigh alowalow)其中其中其中其中keykey是要尋找之鍵值是要尋找之鍵值是要尋找之鍵值是要尋找之鍵值Max(hi

14、ghMax(high)和和和和Min(lowMin(low)分別是剩餘待尋找之記錄中值最分別是剩餘待尋找之記錄中值最分別是剩餘待尋找之記錄中值最分別是剩餘待尋找之記錄中值最小和最大者。小和最大者。小和最大者。小和最大者。1.1.先將記錄按鍵值不遞減之順序加以排序並編號，編號為先將記錄按鍵值不遞減之順序加以排序並編號，編號為先將記錄按鍵值不遞減之順序加以排序並編號，編號為先將記錄按鍵值不遞減之順序加以排序並編號，編號為1,2,3,N1,2,3,N。2.2.令令令令a=1a=1，b=Nb=N。3.3.當當當當a ba b時重覆步驟時重覆步驟時重覆步驟時重覆步驟4 4、5 5。4.4.令令令令m=M

15、in+m=Min+。5.5.若若若若key key key keykeymm，且，且，且，且List(MinList(Min)m+1)m+1，則令，則令，則令，則令List(MinList(Min)=m+1)=m+1。插補搜尋之步驟演算法虛擬程式碼intint intpsch(intintpsch(int a,a,intint n,n,intint key)key)intint mid,high,low;mid,high,low;high=n 1;high=n 1;low=0;low=0;while(low=high)while(low key)high=mid 1;else low=mid+

16、1;return(-1);C語言程式碼intint intpsch(intintpsch(int a,a,intint n,n,intint key)key)intint mid,high,low;mid,high,low;high=n 1;high=n 1;low=0;low=0;while(low=high)while(low key)else if(a mid key)high=mid 1;high=mid 1;else else low=mid+1;low=mid+1;return(-1);return(-1);時間複雜度分析【分析】一般而言，內插式搜尋法優於循序法，但與其他方法的優劣

17、勝負則完全決定於鍵值分佈平均與否，通常N 500且鍵值分佈均勻時會優於二元搜尋法。程式實作#include void main()int data 10=12,24,29,38,44,57,64,75,82,98int i,l=1,n=10,m,cnt=0,input,ok=0;printf(“nn”);printf(“nSorted Data:“);for(i=0;i 1&ok=0)m=l+(input data l*(n l-1)/(data n data l+1;if(m n|m input)n=m;printf(“-Choice number is smaller than%d,datam);elseif(data m Choice number is bigger than%d”,data m);elseprintf(“nnfound,%d is the%dth record in data!“,input,m);ok=1;if(ok=0)printf(“nnSorry,%d not found!“,input);