《《查找》ppt課件高中信息技術.ppt》由會員分享，可在線閱讀，更多相關《《查找》ppt課件高中信息技術.ppt（17頁珍藏版）》請在裝配圖網上搜索。
1、查找(search)是一種查詢數據或信息的技術，其目標是能以比較少的步驟或較短的時間找到所需的對象。查詢的方法很多，對不同的數據結構有不同的查找方法。例如，對以排序好的固定規(guī)模的數據序列進行查找時，其方法有對分查找等；對某些復雜的結構的查找，可用樹型查找方法等等。查字典、查資料是我們經常進行的查找工作，在這里，是以在程序的某個數組變量中存儲的一批數據內，尋找出特定的一個數據，或者確定在該數組內無這樣的數據，作為查找的目的。通常，程序將按照查找的結果(找到或未找到)來決定執(zhí)行后面的哪個計算步驟。,1、觀察順序查找的處理過程,假定被查找的數據（如8個）存儲在有8個元素的數組變量 d 中，要尋找的數
2、據（這個數據稱為查找鍵）已經存儲在變量 key 中。,順序查找算法的輸入輸出說明,輸入：查找鍵（設在變量 key 中）。,被查找的數據（設在數組變量 d 中）。,輸出：若找到，結果是，值為 key 的數據所在的數組元素的下標。,未找到，結果是，0。,2、順序查找算法流程圖,m = 0 key = Int(InputBox(請輸入要查找的數據，即查找鍵key值：, 對數組d進行順序查找, 0)) i = 1 Do While i <= 8 If d(i) = key Then MsgBox 找到，數組下標值是： & i, 0, 順序查找 m = 1 Exit Do End If i = i +
3、1 Loop If m = 0 Then MsgBox 未找到，結果是： & m, 0, 順序查找 End If,3、順序查找算法的VB編程代碼(以規(guī)模為8的數組d舉例),,建立循環(huán)結構,從第一個元素開始遍歷，逐個檢驗是否與查找鍵相等。,1、觀察對分查找的處理過程,假定被查找的數據（如16個）存儲在有16個元素的數組變量 d 中，并且，數組 d 是有序的（已經按非遞減次序排列）。要尋找的數據（這個數據稱為查找鍵）已經存儲在變量 key 中。（參考P38圖2.22）,對分查找算法的輸入輸出說明,輸入：查找鍵（設在變量 key 中）。,被查找的數據（設在有序數組變量 d 中）。,輸出：若找到，結果
4、是，值為 key 的數據所在的數組元素的下標。,未找到，結果是，0。,對分查找的基本方法是：在查找范圍（i，j）內，可以利用數據的有序性，而不必逐個數據地進行查找，進行簡單地計算后，可得到查找范圍的中點位置，并使用變量如m，記錄這個中點位置。,把查找范圍（i，j）的中點位置上的數據 dm 與查找鍵 key 進行比較，結果必然是如下三種情況之一：,（1） key< dm 查找鍵小于中點處的數據 dm 。由數組d 中數據的遞增性，可以確定：在（m，j）內不可能存在值為key 的數據，必須在新的范圍（i，m-1）中繼續(xù)查找。,（2） key = dm 查找鍵等于中點處的數據 dm 。找到了需要的數據
5、。,（3） key dm 查找鍵大于中點處的數據 dm 。根據與（1）類似的理由，必須在新的范圍（m+1，j）中繼續(xù)查找。,因此，除了出現情況（2），在通過一次比較后，新的查找范圍大約是原查找范圍的一半。,舉例觀察圖2.22對分查找過程中查找范圍的變化。,d,i,m,j,第1次：初值 i1，j16，m8，key22,因 key
6、r,d,i,m,j,第2次：i1，j7，m4，key22,j=m-1=8-1=7,int((i+j)/2)=int((1+7)/2)=4,因 keydm，故（i，m）范圍不存在值為key的數據。,因key=22，dm=8,對分查找過程中查找范圍的變化,d,i,m,j,第3次：i5，j7，m6，key22,i=m+1=4+1=5,int((i+j)/2)=int((5+7)/2)=6,因 keydm，故（i，m）范圍不存在值為key的數據。,對分查找過程中查找范圍的變化,因key=22，dm=17,d,i，j，m,第4次：i7，j7，m7，key22,i=m+1=6+1=7,int((i+j)/
7、2)=int((7+7)/2)=7,因 dm=key 故輸出： “找到，數組下標值是：” & m,對分查找過程中查找范圍的變化,因key=22，dm=22,對分查找過程中查找范圍的變化,d,i,m,j,d,i,m,j,d,i,m,j,d,i，j，m,P38圖2.22對分查找過程中查找范圍的變化,2、對分查找算法的流程圖,使用對分查找算法在具有n個數據的數組變量d中查找key時，因事先并不能確定比較的次數，但可以通過條件來控制重復是否繼續(xù)進行。每進行一次比較后，當情況（1）(key dm )出現（即尚未找到key）時，應把原查找范圍的一半作為新的查找范圍，在這個新的范圍內繼續(xù)查找key。但這是需
8、要前提的，即新的查找范圍內必須至少有一個數據。由此得到的繼續(xù)進行重復的條件是：,查找范圍（i，j）中的數據個數,j-i+10,即,i<=j,i = 1: j = n: b = 0 Do While i <= j m = Int((i + j) / 2) If d(m) = key Then b = 1 Text2.Text = 找到，數組下標值是： & m Exit Do ElseIf d(m) < key Then i = m + 1 Else j = m - 1 End If Loop If b = 0 Then Text2.Text = 未找到，結果是： & b End I
9、f,3、對分查找算法的VB編程代碼(以規(guī)模為n的數組d舉例),對分查找是先取中間元素和查找鍵比較，若不相等則縮小近一半的查找范圍，在剩下的元素中繼續(xù)查找。,,循環(huán)初始值,實踐體驗,現代化學的元素周期律是1869年俄國科學家門得列夫(Dmitri Mendeleev)首創(chuàng)的，他將當時已知的63種元素依原子量大小并以表的形式排列，把有相似化學性質的元素放在同一行，就是元素周期表的雛形。利用周期表，門得列夫成功的預測當時尚未發(fā)現的元素的特性(鎵、鈧、鍺)。1913年英國科學家莫色勒利用陰極射線撞擊金屬產生X射線，發(fā)現原子序越大，X射線的頻率就越高，因此他認為核的正電荷決定了元素的化學性質，并把元素依
10、照核內正電荷(即質子數或原子序)排列，經過多年修訂后才成為當代的周期表。 在周期表中，元素是以元素的原子序排列，最小的排行最先。表中一橫行稱為一個周期，一列稱為一個族。,1、主題（參考教材P39）,查找原子序數。,2、要求,元素周期表是化學學習中經常要使用的，通過查閱元素周期表，我們可以知道元素名稱、元素符號、原子序數及原子量等信息?，F在要求構建一個數組，按原子序數存放對應元素的元素符號。試設計一個算法，使得輸入元素符號后，就能快速查找到對應的原子序數。,小結,1、掌握查找的概念；,2、順序查找是按照數組元素的先后次序，從第一個元素開始進行遍歷，逐個檢驗是否和查找鍵相等。,3、對分查找的前提是待查找的數據是有序的。對分查找是先取中間的元素和查找鍵比較，若不相等則縮小近一半的查找范圍，在剩下的元素中繼續(xù)查找。,4、對分查找的效率遠高于順序查找。,5、在數組中的查找結果，若找到，輸出結果是，值為 key 的數據所在的數組元素的下標；若未找到，輸出結果是，0。,
《查找》ppt課件高中信息技術.ppt
