资源简介

(共25张PPT)
查找算法的应用
生活实例引入
学生选课信息表中查找某同学的选课情况
航空公司VIP会员积分查询
不少航空公司都会提供优惠的会员服务，当某会员飞行里程累计达到一定数量后，可以使用里程积分兑换奖励机票或奖励升舱等服务。
现给定某航空公司部分VIP会员的飞行里程、积分等信息
航空公司VIP会员积分查询
不少航空公司都会提供优惠的会员服务，当某会员飞行里程累计达到一定数量后，可以使用里程积分兑换奖励机票或奖励升舱等服务。
现给定某航空公司部分VIP会员的飞行里程、积分等信息，如右图所示，要求实现根据VIP号码快速查询会员积分的功能。
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号码快速查询会员积分呢？
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
第一步：抽象与建模
“600101”
第一步：抽象与建模
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号查找到该
会员的记录
第二步：设计算法与数据结构
思考：
如何用Python实现根据VIP号码找到该会员的记录呢？
1. 存储所有会员记录
2. 实现查找功能
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
第二步：设计算法与数据结构
列
点击此处添加正文，请言简意赅的阐述观点。
存储所有会员记录
点击此处添加正文，请言简意赅的阐述观点。
数组
点击此处添加正文，请言简意赅的阐述观点。
行
点击此处添加正文，请言简意赅的阐述观点。
第二步：设计算法与数据结构
存储所有会员记录
1.采用4个一维数组按列存储
a数组：存储VIP号码
b数组：存储姓名
c数组：存储飞行里程(km)
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
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
存储所有会员记录
1.采用4个一维数组按列存储
2.采用1个一维数组按行存储
a数组：
每个元素对应每位会员的记录信息
a[i]存储第i条记录
a[i][3]存储记录的第3个数据项，积分
第二步：设计算法与数据结构
实现查找功能
顺序查找 二分查找
查找对象 无要求 有序
最少查找次数 1 1
最多查找次数 n int()+1
平均查找次数 (n+1)/2 +1)-1
查找可采用顺序查找算法或二分查找算法：
请同学们根据表格思考：
要实现快速查询，哪一种查找算法的效率更高？
查找前要根据VIP号码为关键字进行排序
第二步：设计算法与数据结构
1.采用4个一维数组按列存储
2.采用1个一维数组按行存储
选用哪种数据结构存储更方便呢？
二分查找算法
1.查找前排序过程中需要实现记录的两两交换
第三步：编写程序
会员的记录信息存储在“vip.csv”文件中
开始
读取”vip.csv”文件中数据保存到数组a中
按照vip号码对数组a中元素进行冒泡排序
打印排序后的vip记录信息
输入查询的vip号码
二分查找
输出查找结果
结束
第三步：编写程序
会员的记录信息存储在“vip.csv”文件中
开始
读取”vip.csv”文件中数据保存到数组a中
按照vip号码对数组a中元素进行冒泡排序
打印排序后的vip记录信息
输入查询的vip号码
二分查找
输出查找结果
结束
import csv
csvFile=open("vip.csv","r") #打开文件
reader=csv.reader(csvFile)
a=[]
for item in reader: #将每行数据（列表）依次追加到列表a中
a.append(item)
csvFile.close() #关闭文件
for i in range(1,len(a)):
for j in range(1,len(a)-i): #从第1条记录开始比较
if int(a[j][0])>int(a[j+1][0]): #按照第0个数据项vip号排列
temp=a[j]
a[j]=a[j+1]
a[j+1]=temp
第三步：编写程序
会员的记录信息存储在“vip.csv”文件中
开始
读取”vip.csv”文件中数据保存到数组a中
按照vip号码对数组a中元素进行冒泡排序
打印排序后的vip记录信息
输入查询的vip号码
二分查找
输出查找结果
结束
print('排序后的会员信息：')
for i in range(len(a)):
print(a[i])
key=int(input("请输入要查找的VIP号："))
i=1;j=len(a)-1
flag=False #设置查找标记
while i<=j:
m=(i+j)//2 #取中间索引
if int(a[m][0])==key:
flag=True;break #查找成功，结束查找
if keyj=m-1
else: #查询右区间
i=m+1
第三步：编写程序
会员的记录信息存储在“vip.csv”文件中
开始
读取”vip.csv”文件中数据保存到数组a中
按照vip号码对数组a中元素进行冒泡排序
打印排序后的vip记录信息
输入查询的vip号码
二分查找
输出查找结果
结束
if flag==True: #查找成功
print(a[m][1],"先生/女士，您的积分为：",a[m][3])
else:
print("找不到VIP号对应的用户信息！")
第三步：编写程序
会员的记录信息存储在“vip.csv”文件中
开始
读取”vip.csv”文件中数据保存到数组a中
按照vip号码对数组a中元素进行冒泡排序
打印排序后的vip记录信息
输入查询的vip号码
二分查找
输出查找结果
结束
封装成函数
第三步：编写程序
import csv
#数据读入
csvFile=open("vip.csv","r")
reader=csv.reader(csvFile)
a=[]
for item in reader:
a.append(item)
csvFile.close()
#排序
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]):
temp=d[j]
d[j]=d[j+1]
d[j+1]=temp
#二分查找
def bsearch(s,array):
i=1;j=len(array)-1 #查找范围不包含第一行数据
while i<=j:
m=(i+j)//2
if int(array[m][0])==s:
return m
if sj=m-1
else:
i=m+1
return -1 #未找到返回-1
bubble_sort(a)
key=int(input("请输入要查找的VIP号："))
m=bsearch(key,a)
if m!=-1:
print(a[m][1],"先生/女士，您的积分为：",a[m][3])
else:
print("找不到VIP号对应的用户信息！")
读入数据
冒泡排序
二分查找
输出结果
调用冒泡排序函数
调用二分查找函数
应用实践：学生“七选三”选课查询
某校高一学期结束，学生进行了“七选三”预选课，选课信息存储在“course.csv”中，如右图所示，前3列分别存储学生的学号、姓名、班号，第4列到第10列分别表示物理、化学、生物、政治、历史、地理和技术的选课情况，其中“1”表示选择，“0”表示未选择。
应用实践：学生“七选三”选课查询
李老师编写了一个查询程序，此程序有以下功能：程序运行后自动从“course.csv”中读取学生信息，按照学号从小到大的顺序将所有学生信息排序，并打印输出。输入一个学生的学号，程序自动查找是否存在该学生，若找到，输出该生的“七选三”科目，如果没有找到，则显示“没有查询到该学号信息!”。查询结果如右图所示。
应用实践：学生“七选三”选课查询
程序如下，请同学们根据注释，
将横线处缺失的代码补充完整。
import csv
csvFile=open("course.csv","r") #打开文件
reader=csv.reader(csvFile)
a=[]
for item in reader:
a.append(item)
csvFile.close()
for i in range(1,len(a)):
for j in range(1,len(a)-i): #从第1条记录开始比较
#按照每条记录的第0个元素学号进行升序排列
if ________①_______:
temp=a[j]
a[j]=a[j+1]
a[j+1]=temp
print('排序后：’)
for i in range(len(a)):
print(a[i])
key=int(input("请输入要查找的学号："))
i=1; j=len(a)-1 #查找范围不包含第一行数据
flag=False #设置查找标记
while i<=j:
m=(i+j)//2 #取中间索引
if int(a[m][0])==key:
________②_________ #查找成功，结束查找
break
if ________③________: #查找学号<当前学号
j=m-1 #查询左区间
else:
i=m+1
#根据查找结果输出学生的选考科目
应用实践：学生“七选三”选课查询
#根据查找结果输出学生的选考科目
b=['物理','化学','生物','政治','历史','地理','技术']
if flag==True: #查找成功
print(a[m][1],"同学，您的7选3科目为：")
for j in range(3,10):
if a[m][j]=='1':
print(b[j-3],end=" ")
else:
print("找不到此学号对应的同学信息！")
应用实践：学生“七选三”选课查询
程序如下，请同学们根据注释，
将横线处缺失的代码补充完整。
import csv
csvFile=open("course.csv","r") #打开文件
reader=csv.reader(csvFile)
a=[]
for item in reader:
a.append(item)
csvFile.close()
for i in range(1,len(a)):
for j in range(1,len(a)-i): #从第1条记录开始比较
#按照每条记录的第0个元素学号进行升序排列
if ________①_______:
temp=a[j]
a[j]=a[j+1]
a[j+1]=temp
print('排序后：’)
for i in range(len(a)):
print(a[i])
key=int(input("请输入要查找的学号："))
i=1; j=len(a)-1 #查找范围不包含第一行数据
flag=False #设置查找标记
while i<=j:
m=(i+j)//2 #取中间索引
if int(a[m][0])==key:
________②_________ #查找成功，结束查找
break
if ________③________: #查找学号<当前学号
j=m-1 #查询左区间
else:
i=m+1
#根据查找结果输出学生的选考科目
应用实践：学生“七选三”选课查询
程序如下，请同学们根据注释，
将横线处缺失的代码补充完整。
import csv
csvFile=open("course.csv","r") #打开文件
reader=csv.reader(csvFile)
a=[]
for item in reader:
a.append(item)
csvFile.close()
for i in range(1,len(a)):
for j in range(1,len(a)-i): #从第1条记录开始比较
#按照每条记录的第0个元素学号进行升序排列
if ________①_______:
temp=a[j]
a[j]=a[j+1]
a[j+1]=temp
print('排序后：’)
for i in range(len(a)):
print(a[i])
key=int(input("请输入要查找的学号："))
i=1; j=len(a)-1 #查找范围不包含第一行数据
flag=False #设置查找标记
while i<=j:
m=(i+j)//2 #取中间索引
if int(a[m][0])==key:
________②_________ #查找成功，结束查找
break
if ________③________: #查找学号<当前学号
j=m-1 #查询左区间
else:
i=m+1
#根据查找结果输出学生的选考科目
读入数据
冒泡排序
二分查找
int(a[j][0])>int(a[j+1][0])
flag=True
key小结与练习
查找算法的应用
实际问题
航空公司VIP会员
积分查询
抽象与建模
编写程序
上机调试
设计算法与数据结构
哪种数据结构存储更方便
哪种算法
效率更高

展开更多......

收起↑