资源简介

(共39张PPT)
3.3数据的查找
高中信息技术/教科版/选择性必修1
目录
1.创设情境，
导入新课
2.体验探究，初始查找
3.讨论探究，实现查找
4.自主探究，二分查找
5.递归实现二分查找
6.课堂小结
1.创设情境，导入新课
在网上商城众多的商品数据中，如何快速地查找到所需商品的相关信息呢
本节围绕“网上商城查找商品”项目展开学习，通过项目活动体验计算机查找数据的过程，理解算法与数据结构的关系。本节主要包含“根据品牌查找商品”和“根据价格查找商品”两个任务。
2.体验探究，初始查找
任务一 根据品牌查找商品 活动1体验顺序查找过程
表3.3.1所示是某网上商城的签字笔销售数据，如何在表中查询到品牌为“得利”的签字笔销售数据呢
品牌 销量/盒 价格/元 评论数/条
博士 80 66 108
英雄 188 78 86
永辉 236 58 186
晨辉 200 46 190
得利 56 68 50
梅花 185 26 92
凌梅 68 32 65
巧虎 221 72 198
表3.3.1签字笔销售数据
从表格的第1行数据开始，先比较第1行数据中的品牌与“得利”是否相等，如果相等则说明查找成功;如果不相等则继续与下一个数据进行比较，直到所有数据都比较完毕。
任务一 根据品牌查找商品 活动1体验顺序查找过程
第 1次比较:“博士”与“得利”不相等,继续与下一个数据比较第 2次比较:“英雄”与“得利”不相等,继续与下一个数据比较。请根据这个思路，继续完成后面几个数据的比对过程。
第3次比较: 。
第4次比较: 。
第5次比较: 。
从第1个数据开始，按顺序逐一进行比较，经过5次比较，找到品牌为“得利”的签字笔销售数据。
填一填
“永辉”与“得利”不相等,继续与下一个数据比较
“晨辉”与“得利”不相等,继续与下一个数据比较
“得利”与“得利”相等,结束比较
通过刚才的查找体验，你能分别给查找和顺序查找下个定义吗？
查找(searching)就是在数据表中确定一个与给定值相等的数据若存在这样的数据则表示查找成功，否则表示查找不成功。
顺序查找(sequential search )是一种从头开始逐个数据进行比较的查找方法。
从数据表中第1个数据开始，逐个与要查找的数据进行比较，如果与要查找的数据相等，则查找成功;
如果直至最后个数据，与要查找的数据都不相等，则查找不成功。
顺序查找的过程
3.讨论探究，实现查找
任务一 根据品牌查找商品 活动2建立数据结构
创建一个线性表对象alist，存放表3.3.1所示的签字笔销售数据对象。请补全下面的代码。
填一填
01. from linearList import LinearList #导人线性表
02.alist= #创建线性表对象
03.alist.appendItem(pen("博士",80,66,108))#添加签字笔数据元素
04.alist.appendItem(pen("英雄",188,78,86))#添加签字笔数据元素
05.alist.appendItem(pen("永辉",236,58,186))#添加签字笔数据元素
LinearList ( )
任务一 任务一 根据品牌查找商品 活动2建立数据结构
06. alist.appendItem(pen( ))#添加签字笔数据元素
07. alist.appendItem(pen( ))#添加签字笔数据元素
08. alist.appendItem(pen( ))#添加签字笔数据元素
09. alist.appendItem(pen( ))#添加签字笔数据元素
10. alist.appendItem(pen( ))#添加签字笔数据元素
"晨辉",200,46,190
"得利",56,68,50
"梅花",185,26,92
"凌美",68,32,65
"巧虎",221,72,198
任务一 根据品牌查找商品 活动3顺序查找算法的设计与实现
假设有n个签字笔销售数据，实现顺序查找的算法描述如下。
(1) 从线性表中的第1个数据开始，依次进行操作 (2)
(2)将当前数据与要查找数据进行比较，如果相等，则查找成功，返回数据在表中的位置，查找结束。如果不相等，则继续查找。
(3) 查找失败。
请将上述顺序查找的算法过程转化为流程图。
任务一 根据品牌查找商品 活动3顺序查找算法的设计与实现
根据上述算法，定义sequentialSearch(alist,key,item)函数，参数alist表示存储数据的线性表，key表示查找的关键词，参数item表示要查找的数据。请补全下面的代码。
11.#顺序查找算法
12. def sequentialSearch(alist， key， item):
13.i=0 #初始化循环变量
14.while i15.#判断第i个位置上的数据与查找的数据是否相等
16.if getattr( ,key)==item:
17.return #返回查找到的数据在表中的位置
18.else:
19.i=i+l #进行下一个数据比较
19.return -1 #返回查找失败
alist.getItem(i)
i
任务一 根据品牌查找商品 活动3顺序查找算法的设计与实现
以表3.3.1中的数据为例，利用顺序查找法查找品牌为“得利”的签字笔，并显示查找到的签字笔销售数据。请补全下面的代码。
21. result=sequentialSearch(alist， ， ) #调用顺序查找函数
22.print(“顺序查找的结果是:“)
23. if result==-1:
24.print("查找失败")
25.else:
print(getattr(alist.getItem(result),'brand'), ,
, )#显示查找结果
‘brand’
‘凌美’
alist.getItem(result),'sales'
alist.getItem(result),'price'
alist.getItem(result),'comments'
假设有n个数据，利用顺序查找法，整个查找过程需要进行k(1kn)次数据比较，可以利用循环语句实现。
4.自主探究，二分查找
任务二 根据价格查找商品 活动1体验二分查找过程
在表3.3.1中如何快速查找到价格是68的签字笔销售数据呢
品牌 销量/盒 价格/元 评论数/条
博士 80 66 108
英雄 188 78 86
永辉 236 58 186
晨辉 200 46 190
得利 56 68 50
梅花 185 26 92
凌梅 68 32 65
巧虎 221 72 198
表3.3.1 按价格升序排列后的签字笔销售数据
把签字笔销售数据表按照价格进行升序排列，找到中间项 (位于表中间位置 ) 数据，如果查找项与中间项相等，则查找结束。如果查找项比中间项大，可以把数据表中较小的那部分 (包括中间项) 排除了，因为如果查找项在中，那它一定在较大的那一半中。接下来，可以在较大的一半中重这个过程。如果查找项比中间项小，可以把数据表中较大的那部分包括中间项) 排除了，因为如果查找项在表中，那它一定在较小的那一半中。接下来，在较小的一半中重复这个过程即可。
任务二 根据价格查找商品 活动1体验二分查找过程
品牌 销量/盒 价格/元 评论数/条
梅花 185 26 92
凌梅 68 32 65
晨辉 200 46 190
永辉 236 58 186
博士 80 66 108
得利 56 68 50
巧虎 221 72 198
英雄 188 78 86
表3.3.2 按价格升序排列后的签字笔销售数据
任务二 根据价格查找商品 活动1体验二分查找过程
第1次查找:确定数据表的中间项是价格为58的签字笔，如图所示。将查找项与中间项进行比较，68>58，排除较小的那部分和中间项。
梅花26
凌梅32
晨辉46
永辉58
博士66
得利68
巧虎72
英雄78
中间项
第1次查找
任务二 根据价格查找商品 活动1体验二分查找过程
第2次查找:在数据表较大的部分中继续查找，确定数据表较大部分的中间项是68，如图所示。将查找项与中间项进行比较，68=68，查找成功。
博士66
得利68
巧虎72
英雄78
中间项
第2次查找
请根据这个思路，写出查找价格是46的签字笔销售数据的过程。
任务二 根据价格查找商品 活动1体验二分查找过程
第1次查找:确定数据表的中间项是价格为 58 的签字笔，将查找项与中间项进行比较，46<58，排除较大的那部分和中间项。
梅花26
凌梅32
晨辉46
永辉58
博士66
得利68
巧虎72
英雄78
中间项
第 2次查找:确定数据表的中间项是价格为 32 的签字笔，将查找项与中间项进行比较，46>32，排除较小的那部分和中间项。
梅花26
凌梅32
晨辉46
中间项
第
1
次查找
第
2
次查找
第 3次查找:确定数据表的中间项是价格为46 的签字笔，46=46，查找成功。
对于有序表的查找，从表的中间项开始比对，如果表的中间项匹配查找项，则查找结束。如果不匹配，就有两种情况: 表的中间项比查找项大，那么查找项只可能出现在前半部分;表的中间项比查找项小，那么查找项只可能出现在后半部分。重复上述查找过程，每次都会将比对范围缩小一半，直到查找结束。这种查找的方法，称为二分查找。
二分查找概念
任务二 根据价格查找商品 活动2二分查找算法的设计与实现
假设有n种商品，实现二分查找的算法描述如下：
(1)确定查找范围，每次查找如步骤 (2)和(3)，如果没有完成则继续操作。第1次查找的范围是n个数据。
(2) 取得查找范围的中间位置，将查找数据与中间位置的数据进行比对，如果二者相等则查找成功，返回数据在表中的位置。
(3) 如果查找数据小于中间位置的数据则缩小查找范围至前半部分，如果大于中间位置的数据则缩小查找范围至后半部分。
二分查找的算法步骤
任务二 根据价格查找商品 活动2二分查找算法的设计与实现
根据上述算法，定义binarySearch(alist,key,item)函数，参数alist表示按关键字key排序后的线性表，参数key表示查找的关键字，参数item表示要查找的数据。请补全下面的代码。
填一填
11.#二分找算法
12. def binarySearch(alist， key， item)：
13.first=0 #标记查找范围起始位置
14.last=alist.size()-1 #标记查找范围终点位置
15.while first<=last:
16.mid=( )//2 #取得查找范围的中间位置
first+last
任务二 根据价格查找商品 活动2二分查找算法的设计与实现
填一填
17.#判断中间项是否等于查找项
18. if getattr(alist.getItem(mid),key)==item:
19.#返回查找到的商品在线性表中的位置
20. return mid
21. else:
22.#判断查找项是否小于中间项
23.if item24.last=mid-1 #缩小查找范围至前半部分
25.else:
26.first= .
27.return -1 #返回查找失败
alist.getItem(mid),key
mid+1
任务二 根据价格查找商品 活动2二分查找算法的设计与实现
以表3.3.1中的数据为例，利用二分查找法查找价格为68的签字笔销售数据，并显示查找到的签字笔销售数据。请补全下面的代码。
28.bubbleSort(alist，'price') #调用冒泡排序函数
29.result=binarySearch(alist， ， #调用二分查找函数
30.print("二分查找法查找的结果是:“)
31.if result==-1:
32. print("查找失败")
33.else:
34. print(getattr(alist.getItem(result),'brand'), ，
35. ， )
‘price’
68
getattr(alist.getItem(result),'price')
getattr(alist.getItem(result),'sales')
getattr(alist.getItem(result),'comments')
5.递归实现二分查找
任务二 根据价格查找商品 活动3利用递归法实现二分查找
利用递归法实现二分查找，定义recursionSearch(alist,key,item,first,last)函数，参数alist表示按关键字key排序后的线性表对象，参数key表示查找的关键字，参数item表示要查找的数据，参数first表示查找范围的起始位置，参数last表示查找范围的结束位置。利用Pvthon编写的代码如下，请补全下面的代码。
01.#利用递归方法实现二分查找算法
02. def recursionSearch(alist,key,item,first,last):
03.if first<=last:
04.mid=(first+last)//2 #取得中间项位置
05.else:
06.return -1 #返回查找失败
任务二 根据价格查找商品 活动3利用递归法实现二分查找
以表3.3.1中的数据为例，利用递归二分查找法查找商品价格为32的商品，并显示该商品的相关信息。请补全下面的代码。
18.bubbleSort(alist，'price') #调用冒泡排序函数
19.#调用递归二分查找函数
20.result=recursionSearch(alist， , , , )
21.print(“递归二分查找法查找的结果是:“)
22.if result==-1:
23.print("查找失败")
24.else:
25.#显示查找结果
26.print(getattr( ,‘brand')， ,
‘price’
32
alist.size( )
0
alist.getItem(result)
getattr(alist.getItem(result),‘sales'
任务二 根据价格查找商品 活动3利用递归法实现二分查找
07.#中间项与查找项比较
08.if getattr(alist.getItem(mid), key)==item:
09.return mid #返回查找到的商品在线性表中的位置
10.else:
11.#判断查找项是否小于中间项
12.if item13.#递归调用
14.return recursionSearch(alist,key,item,first, )
15.else:
16.#递归调用
17.return recursionSearch(alist,key,item, ,last)
alist.getItem(mid)
mid-1
填一填
mid+1
当对一个有序表执行二分查找时，首先确定中间项。如果查找项比中间项小，可以在原来表的前半部分执行二分查找;如果查找项比中间项大，可以在后半部分执行二分查找。分析二分查找算法的过程可以发现它是把一个问题分解成更小规模的问题，先用一些方法解决这些更小规模的问题，然后重组整个问题来得到结果。
6.课堂小结
本节我们学习了查找的基本概念、顺序查找算法的基本思想和实现方法、二分查找算法的基本思想和实现方法、递归方法实现二分查找算法的基本思路。
请同学们认真完成教材中的拓展练习哦！
下节课见！

展开更多......

收起↑