《查找》ppt課件高中信息技術(shù).ppt

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