教科版高二选择性必修1信息技术第3单元第3课《数据的查找》课件

3.3数据的查找高中信息技术/教科版/选择性必修1目录1.创设情境，导入新课2.体验探究，初始查找3.讨论探究，实现查找4.自主探究，二分查找5.递归实现二分查找6.课堂小结1.创设情境，导入新课在网上商城众多的商品数据中，如何快速地查找到所需商品的相关信息呢?本节围绕“网上商城查找商品”项目展开学习，通过项目活动体验计算机查找数据的过程，理解算法与数据结构的关系。本节主要包含“根据品牌查找商品”和“根据价格查找商品”两个任务。2.体验探究，初始查找

任务一根据品牌查找商品

活动1体验顺序查找过程表3.3.1所示是某网上商城的签字笔销售数据，如何在表中查询到品牌为“得利”的签字笔销售数据呢?品牌销量/盒价格/元评论数/条博士8066108英雄1887886永辉23658186晨辉20046190得利566850梅花1852692凌梅683265巧虎22172198表签字笔销售数据从表格的第1行数据开始，先比较第1行数据中的品牌与“得利”是否相等，如果相等则说明查找成功;如果不相等则继续与下一个数据进行比较，直到所有数据都比较完毕。

任务一根据品牌查找商品

活动1体验顺序查找过程第1次比较:“博士”与“得利”不相等,继续与下一个数据比较第2次比较:“英雄”与“得利”不相等,继续与下一个数据比较。请根据这个思路，继续完成后面几个数据的比对过程。第3次比较:

。第4次比较:

。第5次比较:

。从第1个数据开始，按顺序逐一进行比较，经过5次比较，找到品牌为“得利”的签字笔销售数据。填一填“永辉”与“得利”不相等,继续与下一个数据比较“晨辉”与“得利”不相等,继续与下一个数据比较“得利”与“得利”相等,结束比较通过刚才的查找体验，你能分别给查找和顺序查找下个定义吗？查找(searching)就是在数据表中确定一个与给定值相等的数据若存在这样的数据则表示查找成功，否则表示查找不成功。顺序查找(sequentialsearch)是一种从头开始逐个数据进行比较的查找方法。从数据表中第1个数据开始，逐个与要查找的数据进行比较，如果与要查找的数据相等，则查找成功;如果直至最后个数据，与要查找的数据都不相等，则查找不成功。顺序查找的过程3.讨论探究，实现查找

任务一根据品牌查找商品

活动2建立数据结构创建一个线性表对象alist，存放表3.3.1所示的签字笔销售数据对象。请补全下面的代码。填一填01.fromlinearListimportLinearList

#导人线性表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.defsequentialSearch(alist，key，item):13.i=0

#初始化循环变量14.whilei<alist.size():15.#判断第i个位置上的数据与查找的数据是否相等16.ifgetattr(

,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.ifresult==-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的签字笔销售数据呢?品牌销量/盒价格/元评论数/条博士8066108英雄1887886永辉23658186晨辉20046190得利566850梅花1852692凌梅683265巧虎22172198表3.3.1按价格升序排列后的签字笔销售数据把签字笔销售数据表按照价格进行升序排列，找到中间项(位于表中间位置)数据，如果查找项与中间项相等，则查找结束。如果查找项比中间项大，可以把数据表中较小的那部分(包括中间项)排除了，因为如果查找项在中，那它一定在较大的那一半中。接下来，可以在较大的一半中重这个过程。如果查找项比中间项小，可以把数据表中较大的那部分包括中间项)排除了，因为如果查找项在表中，那它一定在较小的那一半中。接下来，在较小的一半中重复这个过程即可。

任务二根据价格查找商品

活动1体验二分查找过程品牌销量/盒价格/元评论数/条梅花1852692凌梅683265晨辉20046190永辉23658186博士8066108得利566850巧虎22172198英雄1887886表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.defbinarySearch(alist，key，item)：13.first=0

#标记查找范围起始位置14.last=alist.size()-1

#标记查找范围终点位置15.whilefirst<=last:16.mid=(

)//2

#取得查找范围的中间位置first+last

任务二根据价格查找商品

活动2二分查找算法的设计与实现填一填17.#判断中间项是否等于查找项18.ifgetattr(alist.getItem(mid),key)==item:19.#返回查找到的商品在线性表中的位置20.returnmid21.else:22.#判断查找项是否小于中间项23.ifitem<getattr(

）：24.last=mid-1

#缩小查找范围至前半部分25.else:26.first=

.27.return-1

#返回查找失败alist.getItem(mid),keymid+1

任务二根据价格查找商品

活动2二分查找算法的设计与实现以表3.3.1中的数据为例，利用二分查找法查找价格为68的签字笔销售数据，并显示查找到的签字笔销售数据。请补全下面的代码。28.bubbleSort(alist，'price')

#调用冒泡排序函数29.result=binarySearch(alist，

，

#调用二分查找函数30.print("二分查找法查找的结果是:“)31.ifresult==-1:32.print("查找失败")33.else:34.print(getattr(alist.getItem(result),'brand'),

，

35.

，

)‘price’68getattr(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.defrecursionSearch(alist,key,item,first,last):03.iffirst<=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.ifresult==-1:23.print("查找失败")24.else:25.#显示查找结果26.print(getattr(

,‘brand')，