资源简介

(共22张PPT)
5.4 数 据 查 找
——查找算法的应用
册 别：选择性必修1
学 科：高中信息技术（浙教版）
学习目标：
能对给定的文件中的数据进行抽象并建立模型。
能合理选用数据结构，设计查找算法。
能用Python语言编写具体的查找程序。
能自觉对学习生活具体问题抽象建模、设计算法并编写程序及调试程序。
阅读教材P141-144，可根据个性学习暂停或加速播放课程。
查找应用：
想一想：
航空公司VIP会员积分查询部分数据（Excel数据）
VIP号 姓名 飞行里程（KM） 积分
600214 韩江辉 16801 519
601278 蒋志来 5321 78
600815 李亚东 28745 436
607854 王庆生 1861 39
605719 李燕 7493 138
603532 王晓燕 6875 102
600101 郑煜明 14253 236
600087 蔡佳宁 112703 958
（一）抽象与建模
问题：从表中的数据可以看出，每个会员的信息是一条记录，包括VIP号、姓名、飞行里程、积分等数据项。
实践体验：Excel表格中，对记录快速查询会员积分，查找应当如何进行？
VIP号 姓名 飞行里程（KM） 积分
600214 韩江辉 16801 519
601278 蒋志来 5321 78
600815 李亚东 28745 436
607854 王庆生 1861 39
605719 李燕 7493 138
603532 王晓燕 6875 102
600101 郑煜明 14253 236
600087 蔡佳宁 112703 958
（二）设计算法与数据结构
：
请思考：
数据组织形式有两种，哪种更适合？
数据查找算法有两种，哪种更方便？
（二）设计算法与数据结构
数据组织形式有两种，哪种更方便？
方法一是采用4个一维数组按列存储，即每个数组分别存储每个用户的VIP号、姓名、飞行里程（KM） 、积分等，如定义a数组存储表中每个用户的VIP号，其对应的值为[“600214”,” 601278 ” ,” 600815 ” ,” 607854” , ” 605719” ……];
定义b数组存储表中姓名；
定义c数组存储表中飞行里程（KM）；
定义d数组存储表中积分信息。
a b c d
VIP号 姓名 飞行里程（KM） 积分
600214 韩江辉 16801 519
601278 蒋志来 5321 78
600815 李亚东 28745 436
607854 王庆生 1861 39
605719 李燕 7493 138
603532 王晓燕 6875 102
600101 郑煜明 14253 236
600087 蔡佳宁 112703 958
b[0]
b[1]
b[2]
b[3]
b[4]
b[5]
b[6]
b[7]
c[0]
c[1]
c[2]
c[3]
c[4]
c[5]
c[6]
c[7]
d[0]
d[1]
d[2]
d[3]
d[4]
d[5]
d[6]
d[7]
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
（二）设计算法与数据结构
数据组织形式有两种，哪种更方便？
方法二是采用1个一维数组按行存储，每个数组元素对应某个国家的一条记录信息，如a[1]为[600214，韩江辉，16801 ，519]对应第一条记录的相关信息。
VIP号为索引值[0]的元素
积分为索引值[3]的元素
VIP号 姓名 飞行里程（KM） 积分
600214 韩江辉 16801 519
601278 蒋志来 5321 78
600815 李亚东 28745 436
607854 王庆生 1861 39
605719 李燕 7493 138
603532 王晓燕 6875 102
600101 郑煜明 14253 236
600087 蔡佳宁 112703 958
a[i][0] a[i][1] a[i][2] a[i][3]
a[1][0] a[1][1] a[1][2] a[1][3]
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
（二）设计算法与数据结构
：
请思考：数据查找算法有两种，哪种更方便？
查找可采用顺序查找算法或二分查找算法，
对数据进行一次查找，采用顺序查找算法。
对数据重复查找，二分查找算法的效率高于顺序查找算法，
但二分查找提前：被查找的数据序列必须是有序，即在查找VIP号前要按VIP号为关键字进行排序。
(三）编写程序并调试
#数据读入
import csv #导入csv模块
csvFile = open("vip.csv", "r") #打开vip.csv数据文件
reader = csv.reader(csvFile) )#建立一个读入数据的对象reader
a = [] #定义空列表a
for item in reader: #每一行为a列表一个元素
a.append(item) #csv通过这种样式读入的数据为字符串
csvFile.close() #关闭vip.csv数据文件
for i in range(len(a)): #输出VIP表信息
print(a[i])
key=input('请输入要查询的VIP号：') #输入要查询的VIP号：key为字符串
#顺序查找
f=False #设置没查找标记
for i in range(1,len(a)): #查询范围不包含第一行数据
if a[i][0]==key: #逐一比较
m=i #记录找到了的位置
f=True #标记查找成功
break #结束查找
if f==True: #标记查找成功，输出信息
print(a[m][1],"先生/女士，',您的积分为：",a[m][3])
else: #查找不成功，输出信息
print('找不到VIP号对应的用户信息！')
（算法一:顺序查找）
待查询文件在vip.csv中
VIP号 姓名 飞行里程（KM） 积分
600214 韩江辉 16801 519
601278 蒋志来 5321 78
600815 李亚东 28745 436
607854 王庆生 1861 39
VIP号 姓名 飞行里程（KM） 积分
(三）编写程序并调试
#数据读入
import csv #导入csv模块
csvFile = open("vip.csv", "r") #打开vip.csv数据文件
reader = csv.reader(csvFile) )#建立一个读入数据的对象reader
a = [] #定义空列表a
for item in reader: #每一行为a列表一个元素,此元素为字符串
a.append(item) #csv通过这种样式读入的数据为字符串
csvFile.close() #关闭vip.csv数据文件
for i in range(len(a)): #输出VIP表信息
print(a[i])
key=input('请输入要查询的VIP号：') #输入要查询的VIP号：key为字符串
#顺序查找
f=False #设置没查找标记
for i in range(1,len(a)): #查询范围不包含第1行数据
if a[i][0]==key: #逐一比较
m=i #记录找到了的位置
f=True #标记查找成功
break #结束查找
if f==True: #标记查找成功，输出信息
print(a[m][1],"先生/女士，',您的积分为：",a[m][3])
else: #查找不成功，输出信息
print('找不到VIP号对应的用户信息！')
（算法一:顺序查找）
#数据读入
import csv #导入csv模块
csvFile = open("vip.csv", "r") #打开vip.csv数据文件
reader = csv.reader(csvFile) #建立一个读入数据的对象reader
a = [] #定义空列表a
for item in reader: #每一行为a列表一个元素,此元素为字符串
a.append(item) #csv通过这种样式读入的数据为字符串
csvFile.close() #关闭vip.csv数据文件
for i in range(len(a)): #输出VIP表信息
print(a[i])
key=input('请输入要查询的VIP号：') #输入要查询的VIP号：key为字符
#顺序查找
def seq_search(a,key):
global m #定义全局变量m
f=False #设置没查找标记
for i in range(1,len(a)): #查询范围不包含第一行数据
if a[i][0] ==key: #逐一比较
f=True #标记查找成功
m=i #记录找到了的位置
break #结束查找
return f #返回f
f=seq_search(a,key)
if f==True: #标记查找成功，输出信息
print(a[m][1],"先生/女士，',您的积分为：",a[m][3])
else: #查找不成功，输出信息
print('找不到VIP号对应的用户信息！')
(三）编写程序并调试
（算法一:顺序查找）
#数据读入
import csv #导入csv模块
csvFile = open("vip.csv", "r") #打开vip.csv数据文件
reader = csv.reader(csvFile) #建立一个读入数据的对象reader
a = [] #定义空列表a
for item in reader: #每一行为a列表一个元素,此元素为字符串
a.append(item) #csv通过这种样式读入的数据为字符串
csvFile.close() #关闭vip.csv数据文件
for i in range(len(a)): #输出VIP表信息
print(a[i])
key=input('请输入要查询的VIP号：') #输入要查询的VIP号：key为字符
#顺序查找
def seq_search(a,key):
global m #定义全局变量m
f=False #设置没查找标记
for i in range(1,len(a)): #查询范围不包含第一行数据
if a[i][0] ==key: #逐一比较
f=True #标记查找成功
m=i #记录找到了的位置
break #结束查找
return f #返回f
f=seq_search(a,key)
if f==True: #标记查找成功，输出信息
print(a[m][1],"先生/女士，',您的积分为：",a[m][3])
else: #查找不成功，输出信息
print('找不到VIP号对应的用户信息！')
(三）编写程序并调试（算法二:二分查找）
import csv #导入csv模块
#数据读入
csvFile = open("vip.csv", "r") #打开vip.csv数据文件
reader = csv.reader(csvFile)#建立一个读入数据的对象reader
a = [] #定义空列表a
for item in reader:#每一行为a列表一个元素,此元素为字符串
a.append(item) #csv通过这种样式读入的数据为字符串
csvFile.close() #关闭vip.csv数据文件
#冒泡排序
for i in range(1,len(a)):
for j in range(1,len(a)-i):
if int(a[j][0])>int(a[j+1][0]): #升序排序
a[j],a[j+1]=a[j+1],a[j]
print('排序后:')
for i in range(len(a)):#输出排序后的VIP表信息
print(a[i])
key=int(input('请输入要查询的VIP号：'))
#二分查找
i = 1 #查找范围不包含第一行数据，左端点初值1
j = len(a)-1 #右端点初值为最后一个元素索引值
f=False #设置查找标记
while i <= j:
m = (i+j) //2 #确定中点
if int(a[m][0]) ==key:#key与中点VIP号相等
f=True #标记查找成功
break #结束查找
if key < int(a[m][0]): #key<中点VIP号
j = m-1 #到左半区间找
else: #key>中点VIP号
i = m+1 #到右边区间找
if f==True: #标记查找成功，输出信息
print(a[m][1],"先生/女士,您的积分为：",a[m][3])
else:
print('找不到VIP号对应的用户信息！')
(三）编写程序并调试（算法二:二分查找）
import csv #导入csv模块
#数据读入
csvFile = open("vip.csv", "r") #打开vip.csv数据文件
reader = csv.reader(csvFile)#建立一个读入数据的对象reader
a = [] #定义空列表a
for item in reader:#每一行为a列表一个元素,此元素为字符串
a.append(item) #csv通过这种样式读入的数据为字符串
csvFile.close() #关闭vip.csv数据文件
#冒泡排序
for i in range(1,len(a)):
for j in range(1,len(a)-i):
if int(a[j][0])>int(a[j+1][0]): #升序排序
a[j],a[j+1]=a[j+1],a[j]
print('排序后:')
for i in range(len(a)):#输出排序后的VIP表信息
print(a[i])
key=int(input('请输入要查询的VIP号：'))
#二分查找
i = 1 #查找范围不包含第一行数据，左端点初值1
j = len(a)-1 #右端点初值为最后一个元素索引值
f=False #设置查找标记
while i <= j:
m = (i+j) //2 #确定中点
if int(a[m][0]) ==key:#key与中点VIP号相等
f=True #标记查找成功
break #结束查找
if key < int(a[m][0]): #key<中点VIP号
j = m-1 #到左半区间找
else: #key>中点VIP号
i = m+1 #到右边区间找
if f==True: #标记查找成功，输出信息
print(a[m][1],"先生/女士,您的积分为：",a[m][3])
else:
print('找不到VIP号对应的用户信息！')
(三）编写程序并调试（算法二:二分查找）
import csv #导入csv模块
#数据读入
csvFile = open("vip.csv", "r") #打开vip.csv数据文件
reader = csv.reader(csvFile)#建立一个读入数据的对象reader
a = [] #定义空列表a
for item in reader:#每一行为a列表一个元素,此元素为字符串
a.append(item) #csv通过这种样式读入的数据为字符串
csvFile.close() #关闭vip.csv数据文件
#冒泡排序函数
def bubble_sort(d):
for i in range(1,len(d)):
for j in range(1,len(d)-i):
if int(d[j][0])>int(d[j+1][0]):#升序排序
d[j],d[j+1]=d[j+1],d[j]
#二分查找函数
def bsearch(s,array):
i = 1 #查找范围不包含第一行数据，左端点初值1
j = len(array)-1#右端点初值为最后一个元素索引值
f=False #设置查找标记
while i <= j:
m = (i+j) //2 #确定中点
if int(array[m][0]) ==s:#s与中点VIP号相等
return m #找到就结束查找，返回中点m
if s < int(array[m][0]):#s<中点VIP号
j = m-1 #到左边区间找
else: #s>中点VIP号
i = m + 1 #到右边区间找
return -1 #未找到返回-1
#主程序
bubble_sort(a) #调用冒泡排序
print('排序后:')
for i in range(len(a)):#输出排序后的VIP表信息
print(a[i])
key=int(input('请输入要查询的VIP号：'))
m=bsearch(key,a) #调用二分查找函数
if m !=-1: #标记查找成功，输出信息
print(a[m][1],"先生/女士，',您的积分为：",a[m][3])
else: #未找到
print('找不到VIP号对应的用户信息！')
(三）编写程序并调试（算法二:二分查找）
import csv #导入csv模块
#数据读入
csvFile = open("vip.csv", "r") #打开vip.csv数据文件
reader = csv.reader(csvFile)#建立一个读入数据的对象reader
a = [] #定义空列表a
for item in reader:#每一行为a列表一个元素,此元素为字符串
a.append(item) #csv通过这种样式读入的数据为字符串
csvFile.close() #关闭vip.csv数据文件
#冒泡排序函数
def bsort(d):
for i in range(1,len(d)):
for j in range(1,len(d)-i):
if int(d[j][0])>int(d[j+1][0]):#升序排序
d[j],d[j+1]=d[j+1],d[j]
#二分查找函数
def bsearch(s,array):
i = 1 #查找范围不包含第一行数据，左端点初值1
j = len(array)-1#右端点初值为最后一个元素索引值
f=False #设置查找标记
while i <= j:
m = (i+j) //2 #确定中点
if int(array[m][0]) ==s:#s与中点VIP号相等
return m #找到就结束查找，返回中点m
if s < int(array[m][0]):#s<中点VIP号
j = m-1 #到左边区间找
else: #s>中点VIP号
i = m + 1 #到右边区间找
return -1 #未找到返回-1
#主程序
bsort(a) #调用冒泡排序
print('排序后:')
for i in range(len(a)):#输出排序后的VIP表信息
print(a[i])
key=int(input('请输入要查询的VIP号：'))
m=bsearch(key,a) #调用二分查找函数
if m !=-1: #标记查找成功，输出信息
print(a[m][1],"先生/女士，',您的积分为：",a[m][3])
else: #未找到
print('找不到VIP号对应的用户信息！')
学习生活中的应用实践：
校园一卡通号码查询。某校共n名学生，严老师编写了一个校园一卡通号码查询程序，输入号码就能查询该号码所属的班级和学生姓名。如右图所示所有学生数据存储在“校园一卡通.csv”表格中，该表格分别保存了本校所有学生的号码、所在班级和姓名的信息，号码的编码规则为入学年份+班级加身份证号后三位。第i个学生的号码保存在第1列中，对应的班级和姓名保存在第2列和第3列中。输入号码，电脑开始查找该号码的信息，如果找到对应的信息，就显示所属班级和姓名，如果没有找到，则显示“没有查询到该号码信息!”。
学习生活中的应用实践：
相应程序如下，请在程序划线①②③处填入相应的代码，把程序补充完整。
import csv
flie1=open('校园一卡通.csv','r')
reader=csv.reader(flie1)
st=[]
for it in reader:
①
flie1.close()
# 冒泡排序
for i in range(1,len(st)-1):
for j in range(len(st)-1,i,-1):
if ② :
st[j],st[j-1]=st[j-1],st[j]
for i in range(len(st)):
print(st[i])
# 二分查找
key=input(‘请输入需要查找的卡号：')
i=1;j=len(st)-1
while i<=j:
m=(i+j)//2
if ③ :
i=m+1
else:
j=m-1
if st[i][0]==key:
print(st[0])
print(st[i])
else:
print("没有该号码信息！")
st.append(it)
st[j][0]st[m][0]读取csv文件数据
st[m][0]>=key
课堂小结
抽象与建模
编写程序并调试
查找算法的应用
设计算法与数据结构
学习评价
对自己的表现进行客观的评价，并思考后续完善的方向。（3=优秀，2=一般，1=仍需加油）
评分项 自我评价
能对vip.csv文件中的数据进行抽象并建立模型 3 2 1
能对vip.csv数据选用合适的数据结构，设计查找算法 3 2 1
能用Python语言编写具体的查找程序。 3 2 1
能自觉对学习生活具体问题抽象建模、设计算法并编写程序及调试程序，如：查找姓名、查找校园卡号等实际应用。 3 2 1
课后作业：
2.用二分查找实现开平方根函数squareroot(x,p)。x是被开方的数，假定输入的数都为非负数整数，p是误差上限，输出一个浮点数结果。程序代码如下，请在划线处填入合适的代码。
def ① :
if x<0:
return -1
a=0
b=x
while a<=b:
②
if abs(m**2-x)return m
elif m**2>x:
③
else:
a=m
print(square(2,0.01))
print(square(1,0.01))
print(square(9,0.01))
print(square(100,0.01))
1.D
2.①square(x,p) ②m=(a+b)/2
③b=m
1.已知输入a[0]至a[7]的值依次为“88,79,62,55,46,31,20,1”,查找某key值的程序段如下：
i=0;j=7;n=0
key=int(input())
while i<=j:
m=(i+j)//2
if key==a[m]:
break
elif key>a[m]:
j=m-1;n-=1
else:
i=m+1;n+=1
print(n)
当输入不同的key值，运行该程序后，输出的不同结果共有：
A.5种 B.6种
C.7种 D.8种
课后作业：
3.某超市商品销售表结构如下图所示，为了模拟超市销售系统的部分功能，某程序具有功能如下：
1)程序运行后自动从shangpin.xlsx表中读取商品信息，
2)并按照“商品编号”从小到大的顺序将所有商品信息排序。
3)用户输入一个商品编号 ，程序自动查找是否存在该商品，若找到该商品，将该商品的销量加1，并返回“操作已成功”的提示信息，若找不到该商品，则提示“不存在该商品”的提示信息。
程序代码如下，请在划线处填入合适的代码。
import pandas as pd
def check(x,y):
i=x
j=y
flag=False
while ① :
m=(i+j)//2
if int(a[m][0])==key:
flag=True
elif int(a[m][0])>key:
j=m-1
else:
②
if flag:
a[m][3]=int(a[m][3])+1
return flag
if __name__=='__main__':
df=pd.read_excel('shangpin.xlsx') #读取文件
a=df.values.tolist() #将Excel表中的数据转换成列表
#排序
n=len(a)
for i in range(1,n):
for j in range(n-i):
if int(a[j][0])>int(a[j+1][0]):
a[j],a[j+1]= a[j+1],a[j]
key=int(input("请输入商品编号："))
if ③ :
df=pd.DataFrame(a,columns=['商品编号','商品名称','单价','销售量'])
④ #存入shangpin2.xlsx文件中
print("恭喜，操作已完成！")
else:
print("对不起，不存在该商品，请重新输入！")
①i<=j and not flag
②i=m+1
③check(0,n-1)
④df.to_excel("shangpin2.xlsx",index=False)

展开更多......

收起↑