资源简介

中小学教育资源及组卷应用平台
项目九 实现查找指定商品
——查找算法的应用及数据结构的选择
第一课时 采用顺序查找法查找商品
教材分析
本节的主要内容是采用顺序查找法查找商品。在学习中，学生将尝试使用顺序查找法查找对应价格的商品数据。本项目的学习强调引导学生对实际问题从数据量大小、运行时间、存储空间和算法实现难易度等方面进行综合考虑，选择恰当的查找算法，使用合适的存储结构,通过编程实现问题的解决。在体验使用二分查找法查找商品的过程中，分别采用迭代法和递归法来完成算法设计，进一步提升计算思维。索引查找法虽然有一定难度，但是有助于学生进一步认识算法与数据结构的关系，从而进一步提升计算思维。
教学目标
1.掌握常用的数据查找方法——顺序查找法；
2.理解迭代概念。
3.理解递归概念。
4.进一步理解算法与数据结构的关系。
5.培养学生的信息意识和计算思维能力。
教学重点
1.掌握常用的数据查找方法、理解迭代和递归概念；
2.进一步理解算法与数据结构的关系。
教学难点
1.进一步理解算法与数据结构的关系；
2.培养学生的信息意识和计算思维能力。
教学方法
体验法、讲授法、讨论法、示例法
教学准备
　　计算机教室、多媒体设备、多媒体广播软件、Python编程环境、待查找的商品价格数据、教学课件等。
教学过程
一、新课导入
通常网络购物平台中出售的商品非常多，要在众多商品信息中查找某一商品，若依次翻页比对，可能要花相当长的时间。因此，平台一般都会提供查找功能，如图 5-6 所示。程序员在编程实现查找功能时，要依靠好的算法和合适的数据结构以提高查找效率。
二、查找
查找是根据给定的某个值，在查找表中找到一个其关键字等于给定值(也称待查关键字)的数据元素。
查找表是由同一类型的数据元素(或记录)构成的集合，是由所要查找的元素区间构成的表。查找表可以是线性表，也可以是树表(二叉查找树)，如商品信息表就是一种线性的查找表。
常用的查找方法有顺序查找法、二分查找法、索引查找法等。
三、顺序查找算法
1.核心概念
查找算法是程序中经常用到的算法。假定要从n个元素中查找 x 的值是否存在，最原始的方法是从头到尾挨个查找，这种查找的方法叫顺序查找方法。
2.顺序查找基本思路
在一组数据中，从第一个数据开始，按照这组数据的排列顺序将每个数据逐个与给定的值进行比较。若某个数据与给定值相等，则查找成功，找到所查数据的位置;反之查找不成功。
假定有n个记录存放在数组r[1]，r[2]，…，r[n]中，其中第i个记录的关键字值为r[i].key。待查关键字为k，将k依次与r[n].key，r[n-1].key，...，r[1].key 进行比较，一旦某个r[i]. key等于k，查找成功，返回下标i，若所有的数据元素都与k值不相等，则给出查找失败(i=0)的信息。
3.顺序查找示例
输入查找的元素值，key=32
例如：Dim d(1 To 4) As Integer ‘定义一个数组d
定义一个变量i，让i由1变化到4，判断d(i)是否等于key。
顺序查找法的特点是算法比较简单，但查找一个数据元素的比较次数多，算法效率较低，一以数据量n很大，查找时间就相对较长。
顺序查找有三种情形可能发生：最好的情况，第一项就是要查找的数据对象，只有一次比较，最差的情况，需要 n 次比较，全部比较完之后找不到数据。平均情况下，比较次数为 n/2 次。算法的时间复杂度是 O(n) 。
例 ： 在列表中查找 x 是否存在
def sequest(alist, item):
pos=0 #初始查找位置
found=False #未找到数据对象
while posif alist[pos] == item: # 找到匹配对象，返回TRUE
found=True
else: #否则查找位置 + 1
pos = pos+1
return found
def main():
testlist=[1,3,5,6,7,8,9,11,23,44]
print(sequest(testlist,11))
if __name__=='__main__':
main()
例 ： 在列表顺序中 查找最大值和最小值
def Max(alist):
pos = 0 #初始位置
imax=alist[0] #假设第一个元素是最大值
while pos < len(alist): #在列表中循环
if alist[pos] > imax: #当前列表的值大于最大值 ，则为最大值
imax=alist[pos]
pos = pos+1 #查找位置 +1
return imax
def Min(alist):
pos = 0 # 初始位置
imin = alist[0] #假设第一个元素是最小值
for item in alist: #对于列表中的每一个值
if item < imin: #当前的值小于最小的值 则为最小值
imin = item
return imin
def main():
testlist=[2,3,4,5,6,8,34,23,55,234]
print('最大值是：',Max(testlist))
print('最小值是：',Min(testlist))
if __name__=='__main__':
main()
4.流程图
5.Python顺序算法实现:
def sequaential_search(lis, key):
length = len(lis)
for i in range(length):
if lis[i] == key:
return i
else:
return False
if __name__ == '__main__':
LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
result = sequential_search(LIST, 123)
print(result)
四、采用顺序查找法查找商品
假设某店铺出售的某品种商品有11种不同的价格15.83.19.88.37.96.64.5.80,18,92,要在其中查找价格为64的商品，最简单、最基本的方法是将商品价格序列存放在数组中，将待查元素64依次与数组中的每个元素一一比较，这种方法称为顺序查找法，如图5-7所示。
5-7顺序查找过程示意
图中所示的是从数组最后往前依次比较，当i为7时查找成功，此时共比较了5次。为编程方便，将待查元素64放在数组的0号空间，若序列中没有64,那i会移到0,查找失败。把0号空间称为监视哨，即i不可能越过0为负数。
思考与讨论？
顺序查找法的特点是什么？
顺序查找法的特点是算法比较简单，但查找一个数据元素的比较次数多，算法效率较低，一旦数据量很大查找时间就相对较长。
五、课堂活动
在右部的流程框图(局部)中，完成顺序查找算法(假设n个数据在数组r中，待查关键字k)；编程实现，并运行测试。
参考答案：
程序：
r=[64,15,83,19,88,37,96,64,5,80,18,92]
i=11
while i>=0 and r[i]! =r[0]:
i=i+1
print(i) #输出为待查找数据在列表中的下标
21世纪教育网 www.21cnjy.com 精品试卷·第 2 页 （共 2 页）
HYPERLINK "http://21世纪教育网(www.21cnjy.com)
" 21世纪教育网(www.21cnjy.com)(共31张PPT)
第一课时 采用顺序查找法查找商品
信息技术沪教版 选择性必修1
第五单元 排序与查找
项目九 实现查找指定商品
——查找算法的应用及数据结构的选择
一、新课导入
二、查找
三、顺序查找算法
四、采用顺序查找法查找商品
五、课堂活动
一、新课导入
通常网络购物平台中出售的商品非常多，要在众多商品信息中查找某一商品，若依次翻页比对，可能要花相当长的时间。因此，平台一般都会提供查找功能，如图 5-6 所示。程序员在编程实现查找功能时，要依靠好的算法和合适的数据结构以提高查找效率。
二、查找
查找是根据给定的某个值，在查找表中找到一个其关键字等于给定值(也称待查关键字)的数据元素。
查找表是由同一类型的数据元素(或记录)构成的集合，是由所要查找的元素区间构成的表。查找表可以是线性表，也可以是树表(二叉查找树)，如商品信息表就是一种线性的查找表。
01
02
03
索引查找法
二分查找法
顺序查找法
三、顺序查找算法
1.核心概念
查找算法是程序中经常用到的算法。假定要从n个元素中查找 x 的值是否存在，最原始的方法是从头到尾挨个查找，这种查找的方法叫顺序查找方法。
2.顺序查找基本思路
在一组数据中，从第一个数据开始，按照这组数据的排列顺序将每个数据逐个与给定的值进行比较。若某个数据与给定值相等，则查找成功，找到所查数据的位置;反之查找不成功。
假定有n个记录存放在数组r[1]，r[2]，…，r[n]中，其中第i个记录的关键字值为r[i].key。待查关键字为k，将k依次与r[n].key，r[n-1].key，...，r[1].key 进行比较，一旦某个r[i]. key等于k，查找成功，返回下标i，若所有的数据元素都与k值不相等，则给出查找失败(i=0)的信息。
3.顺序查找示例
输入查找的元素值，key=32
例如：Dim d(1 To 4) As Integer ，定义一个数组d，定义一个变量i，让i由1变化到4，判断d(i)是否等于key。
3.顺序查找示例
顺序查找法的特点是算法比较简单，但查找一个数据元素的比较次数多，算法效率较低，一以数据量n很大，查找时间就相对较长。
顺序查找有三种情形可能发生：最好的情况，第一项就是要查找的数据对象，只有一次比较，最差的情况，需要 n 次比较，全部比较完之后找不到数据。平均情况下，比较次数为 n/2 次。算法的时间复杂度是 O(n) 。
3.顺序查找示例
例1： 在列表中查找 x 是否存在
def sequest(alist, item):
pos=0 #初始查找位置
found=False #未找到数据对象
while posif alist[pos] == item: # 找到匹配对象，返回TRUE
found=True
else: #否则查找位置 + 1
pos = pos+1
return found
3.顺序查找示例
例1： 在列表中查找 x 是否存在
def main():
testlist=[1,3,5,6,7,8,9,11,23,44]
print(sequest(testlist,11))
if __name__=='__main__':
main()
3.顺序查找示例
例2： 在列表顺序中 查找最大值和最小值
def Max(alist):
pos = 0 #初始位置
imax=alist[0] #假设第一个元素是最大值
while pos < len(alist): #在列表中循环
if alist[pos] > imax: #当前列表的值大于最大值 ，则为最大值
imax=alist[pos]
pos = pos+1 #查找位置 +1
return imax
3.顺序查找示例
例2： 在列表顺序中 查找最大值和最小值
def Min(alist):
pos = 0 # 初始位置
imin = alist[0] #假设第一个元素是最小值
for item in alist: #对于列表中的每一个值
if item < imin: #当前的值小于最小的值 则为最小值
imin = item
return imin
3.顺序查找示例
例2： 在列表顺序中 查找最大值和最小值
def main():
testlist=[2,3,4,5,6,8,34,23,55,234]
print('最大值是：',Max(testlist))
print('最小值是：',Min(testlist))
if __name__=='__main__':
main()
4.流程图
5.Python顺序算法实现:
def sequaential_search(lis, key):
length = len(lis)
for i in range(length):
if lis[i] == key:
return i
else:
return False
if __name__ == '__main__':
LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
result = sequential_search(LIST, 123)
print(result)
四、采用顺序查找法查找商品
假设某店铺出售的某品种商品有11种不同的价格15、83、19、88、37、96、64、5、80、18、92,要在其中查找价格为64的商品，最简单、最基本的方法是将商品价格序列存放在数组中，将待查元素64依次与数组中的每个元素一一比较，这种方法称为顺序查找法，如图所示。
图中所示的是从数组最后往前依次比较，当i为7时查找成功，此时共比较了5次。为编程方便，将待查元素64放在数组的0号空间，若序列中没有64,那i会移到0,查找失败。把0号空间称为监视哨，即i不可能越过0为负数。
思考与讨论
顺序查找法的特点是什么？
思考与讨论
顺序查找法的特点是什么？
顺序查找法的特点是算法比较简单，但查找一个数据元素的比较次数多，算法效率较低，一旦数据量很大查找时间就相对较长。
五、课堂活动
在右部的流程框图(局部)中，完成顺序查找算法(假设n个数据在数组r中，待查关键字k)；编程实现，并运行测试。
参考答案：
参考答案：
r=[64,15,83,19,88,37,96,64,5,80,18,92]
i=11
while i>=0 and r[i]! =r[0]:
i=i+1
print(i) #输出为待查找数据在列表中的下标
谢谢
21世纪教育网（www.21cnjy.com) 中小学教育资源网站
有大把高质量资料？一线教师？一线教研员？
欢迎加入21世纪教育网教师合作团队！！月薪过万不是梦！！
详情请看：
https://www.21cnjy.com/help/help_extract.php

展开更多......

收起↑