资源简介

(共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.拓展题：在链表中顺序查找的程序实现。

展开更多......

收起↑