資源簡介

(共22張PPT)
5.4 數 據 查 找 （一）
——順 序 查 找
冊 別：選擇性必修1
學 科：高中信息技術（浙教版）
學習目標：
能理解順序查找的思想。
能合理選用數據結構，理解順序查找的范圍與條件。
能用自然語言、流程圖、Python語言描述順序查找算法。
能分析順序查找最壞、最好情況、平均比較次數。
能熟練應用各種順序查找程序，完成生活、學習中的問題。
引入：選一選
下列5個圖標找出哪一個是微信圖標：
查找概念：
查找（Search）又稱檢索，計算機根據所給條件查找出滿足條件的對象，即在存儲的一批數據內尋找出一個特定的數據，或者確定在該批數據內是否存在這樣的數據。
若沒有找到滿足條件的對象，則返回特定值，表明查找失敗；若查找到滿足條件的對象，則表明查找成功，一般要求返回該對象的存儲位置或對象值本身。
順序（線性）查找算法思想
②輸入查找關鍵值key；
③從數組中的第一個元素開始與關鍵值key進行比較，若相等d[i]==key ，則輸出相應信息；否則，繼續比較下一個元素。
①定義待查找數據所儲存的數組；
④直到找完數組的最后一個元素仍沒有，輸出查找失敗。
66
96
33
58
d[0]
d[1]
d[2]
d[3]
d[4]
輸入查找的元素值key=33
i=0
i=1
i=2
此時d[i]=key,數組中的第3個位置
如果輸入查找的元素值key=22
i=0
i=1
i=2
i=3
d[0]
d[1]
d[2]
d[3]
d[4]
66
96
33
58
33
58
77
77
此時i等于4,還是沒有找到
自然語言描述順序查找過程
i=4
開始
i=0
i<=n-1
Y
d[i]==key
N
i=i+1
未找到，輸出結果
找到，輸出結果
結束
Y
N
順序查找的流程圖描述：
轉化成程序：
開始
i=0
i<=n-1
Y
d[i]==key
N
i=i+1
未找到，輸出結果
找到，輸出結果
結束
Y
N
#參考浙江版作業本P71－圖5－6
a=[86,63,35,88,99,78,51,10,8]
n=len(a)
key=int(input(“輸入查找數據："))
flag=False
for i in range(n):
if a[i]==key:
flag=True
break
if flag==True:
print("查找成功！")
else:
print("未找到！")
流程圖：
a=[86,63,35,88,99,78,51,10,8]
n=len(a)
key=int(input(“輸入查找數據："))
flag=False
for i in range(n):
if a[i]==key:
flag=True
break
if flag==True:
print("查找成功！")
else:
print("未找到！")
12345
678
9
1011
12
for i in range(0，n，1):
上機調試程序：
a=[86,63,35,88,99,78,51,10,8]
n=len(a)
key=int(input(“輸入查找數據："))
flag=False
for i in range(n):
if a[i]==key:
flag=True
break
if flag==True:
print("查找成功！")
else:
print("未找到！")
#定義查找的數組
#n為數組元素個數
#輸入待查找數據
#設置查找到的標記flag
#設置查找范圍從索引0至n-1，步長1
#逐個進行判斷
#相同設置標記flag為True
#退出for循環
#如果標記flag為True
#否則標記flag為False
順序查找次數分析
若一個數組有n個元素
找到第1個元素,查找1次
找到第2個元素,查找2次
……
找到第n個元素，查找n次
平均查找次數（1+2+……+n）/n
（n+1）/2
實例：查找水果問題
A數組中存放了一些水果名稱“apple”、“orange”、 “pineapple”、“banana”、“watermelon”、“peach”、“pear”，現在想查找水果“watermelon”是否在其中，如找到輸出“查找成功！是第幾個水果”，否則輸出“查找失敗”，無論查找成功與否都輸出比較的次數。
上機編寫并調試程序。
#例1查找動物
a=["apple","orange","pineapple","banana","watermelon","peach","pear"]
n=len(a);c=0
key=input("請輸入待查找水果：")
flag=False
for i in range(n):
c+=1
if a[i]==key:
flag=True
break
if flag==True:
print("查找成功！在第"+str(i+1)+"個,比較次數："+str(c))
else:
print("未找到！",key,"比較次數：",c)
查找水果問題程序實現（一）：從前往后找
#定義查找的數組
#n為數組元素個數
#輸入待查找水果，調試時直接用
key="watermelon"
#設置查找到的標記flag
#設置查找范圍從索引0至n-1，步長1
#逐個進行判斷
#相同設置標記flag為True
#退出for循環
#如果標記flag為True
#否則標記flag為False
#查找次數增加1
#例1查找動物
a=["apple","orange","pineapple","banana","watermelon","peach","pear"]
n=len(a)
key=input("請輸入待查找水果：")
flag=False
for i in range(n-1,-1,-1):
c+=1
if a[i]==key:
flag=True
break
if flag==True:
print("查找成功！在第"+str(i+1)+"個,比較次數："+str(c))
else:
print("未找到！",key)
查找水果問題程序實現（二）：從后往前找
#定義查找的數組
#n為數組元素個數
#輸入待查找水果，調試時直接用
key="watermelon"
#設置查找到的標記flag
#設置查找范圍從索引n-1至0，步長－1
#逐個進行判斷
#相同設置標記flag為True
#退出for循環
#如果標記flag為True
#否則標記flag為False
#查找次數增加1
#例1查找動物
a=["apple","orange","pineapple","banana","watermelon","peach","pear"]
n=len(a)
key="watermelon" #key=input("請輸入待查找水果：")
flag=False
for i in range((n+1)//2):
c+=1
if a[i]==key: x=i+1;flag=True;break
if a[n-1-i]==key:x=n-i;flag=True; break
if flag==True:
print("查找成功！在第"+str(x)+"個,比較次數："+str(c))
else:
print("未找到！",key)
查找水果問題程序實現（三）：前后一起找
#設置查找范圍從索引0至n的一半，步長為1
#逐個進行第i和
第n-1-i個判斷
#找到標記flag為True
#退出for循環
#查找次數增加1
拓展提升
某個班級的部分學生信息技術成績如下表所示，要求實現根據考號查詢該生的信息技術成績，如查詢不到則顯示“該班無此學生”。
思考：
用哪一種數據結構對表格數據進行存儲？
對哪個字段進行順序查找？
實例應用：查找學生
import csv
csvFile = open("cj.csv", "r")
reader = csv.reader(csvFile)
a = []
for item in reader:
print(item)
a.append(item)
csvFile.close()
key=input('請輸入要查詢的考號：')
flag=False #flag做標記（預設沒找到）
length = len(a)
for i in range(length):#一個一個的舉例
if a[i][1] == key:#一個一個的判斷
flag=True
break
if flag==True:
print("該生IT是"+ str(a[i][5])+"分")
else:
print("該班無此學生")
實例應用：查找學生
#數據讀入
#順序查找
行索引
0
1
2
列索引
0 1 2 3 4 5 6
#練習：順序查找信息最高分和信息最低分：
print("順序查找信息最高分和信息最低分：")
max1=a[1][5];min1=a[1][5]#假設第一個是最大值也是最小值
for i in range(2,length): #此后一個一個的舉例
if a[i][5]>max1: #一個一個的判斷，比最大值大嗎？
max1=a[i][2]
elif a[i][5]min1=a[i][5]
print("最高分:",max1,"最低分：",min1)
實例應用：查找最大、最小值
max1=a[1][5];min1=a[1][5]
for i in range(2,length):
if a[i][5]>max1:
max1=a[i][2]
elif a[i][5]min1=a[i][5]
我們班一共有40個同學，查找成功最好情況是比較幾次？最差呢？若查找不成功，需要比較幾次？
那么若有n個數據，那順序查找的平均比較次數為幾次？并求出時間復雜度。時間復雜度為
課堂小結
若一個數據序列有n個數，查找不成功的比較次數為n，查找成功：最好的情況為1次，最差的情況為n次，所以查找成功時的平均比較次數為(n+1)/2，且順序查找的時間復雜度為O(n)
思考：
1
1
40
40
生活實戰應用：雙向有序查找
某校運動會投鉛球項目分兩小組，每組評委已經將每組的前8名從高到低排好序。取本項目的前m名頒獎，其中小李同學收集的2組選手的名次及其成績如表所示，請在劃線處填上合適語句。
n=len(a);c=[0]*8;i=0;j=8；k=0
for k in range(m):
if j>n or :
c[k]=a[i];i=i+1
else :
c[k]=a[j];j=j+1
print(c[k])
a[j]<=a[i] and i<=7
i
↓
j
↓
c[k]鉛球項目前m名 c[0] c[1] c[2] …… c[m-1]
a[8]
↑
k
課堂小結
順序（線性）查找
算法思想 算法描述
從前往后找
多向一起找
程序實現
從后往前找
從后往前找
學習評價
對自己的表現進行客觀的評價，并思考后續完善的方向。（3=優秀，2=一般，1=仍需加油）
評分項 自我評價
查找微信圖標的問題總結出順序查找方法 3 2 1
能理解查找的概念并舉例生活中的實際例子 3 2 1
能自主學習教材并用自然語言、流程圖描述順序查找算法 3 2 1
能夠用Python語言描述順序查找算法 3 2 1
能獨立完成水果查找的程序實現 3 2 1
能總結出順序查找最壞、最好情況的比較次數，并得出平均比較次數 3 2 1
能夠從前往后、從后往前、雙向順序查找應用 3 2 1
課后作業
1.一般情況是，當需要查找的數據規模為n時，順序查找最少查找1次，最多查找　　　次。其平均查找次數是　　 　　。
2.順序查找最大的優點是查找的數據可以亂序，但是其缺點是查找效率太低。順序查找將待查找的數值與序列中的數逐個進行比較，直到找出與給定數值相同的數為止，其時間復雜度為　　　。
3.在程序劃線處填空題：找數字
n
(1 ＋ n)/2
O(n)
a=[1，9，8，19，28，13，99]
n=len(a)；flag=False
key=int（input("請輸入待查找數字：")
for i in range(n):
if a[i]==key:
flag=True
break
if :
print("查找成功！在第"+str(i)+"個")
else:
print("未找到！",key)
Flag==True
4.拓展題：在鏈表中順序查找的程序實現。

展開更多......

收起↑