搜寻资料结构

《搜寻资料结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、稱為線性搜尋(LinearSearching)，是最單純亦是最基本的搜尋方式不需事先將被搜尋的檔案記錄按其鍵值排序，只需依照資料儲存的順序，逐一比較資料值是否與指定的值相等，若找到則傳回陣列的索引值，否則傳回0。演算法＝＞虛擬碼//n指a[]中的元素個數，key為欲比對的資料//procedureseqsch(inta[],intn,intkey){indexi;for(a[]的第一個元素至最後一個元素){if(key==a[i]){顯示找到的訊息並跳出迴圈;}}if(到最後的元素仍找不到)顯示找不到的訊息;}＝＞C語言程式碼intseqsch(inta[],intn,intkey){int

4、i=0;a[n]=key;while(a[i]!=key)i++;if(ivoid

5、main(){intdata[10]={75,33,98,44,56,24,65,48,83,12}inti,input;printf(“<>”);printf(“Data:“);for(i=0;i<10;i++){printf(“%d“,data[i]);puts(““);printf(“Pleaseenteranumberfromdata:“);scanf(“%d”,&input);printf(“Search…..”);for(i=0;i<10;i++){printf(“nDatawhensearching%2dtime(s)i

6、s%d!”,i+1,data[i]);if(input==data[i])break;}if(i==10)printf(“Sorry,%dnotfound!“,input);elseprintf(“Sorry,%disthe%dthrecordindata!“,input,i+1);}二分搜尋法BinarySearch定義假如資料本身是經過排序的，在搜尋時可以利用二分的方法，每次都把陣列分成兩半，然後從其中的一半繼續搜尋，這種方法叫做「二分搜尋」(Binarysearch)二分搜尋的演算法演算法則檔案中的資料須按鍵值排序，並找出檔案中間位罝的鍵值Km用來作比較，其中m=(1+

7、u)/2，1及u表示資料的開始及結束位址。搜尋方式分下面三種情形進行：KeyKm：則表示欲尋找的資料在檔案的後半部。重新調整1及u，並重複上述步驟，直到搜尋成功或資料已全部搜尋完畢為止。演算法＝＞虛擬程式碼intbinsch(inta[],intlow,inthigh,intkey){intmid;if(low<