中小学教育资源及组卷应用平台 项目九 实现查找指定商品 ———查找算法的应用及数据结构的选择 第一课时 采用顺序查找法查找商品 教材分析 本节的主要内容是采用顺序查找法查找商品。在学习中，学生将尝试使用顺序查找法查找对应价格的商品数据。本项目的学习强调引导学生对实际问题从数据量大小、运行时间、存储空间和算法实现难易度等方面进行综合考虑，选择恰当的查找算法，使用合适的存储结构,通过编程实现问题的解决。在体验使用二分查找法查找商品的过程中，分别采用迭代法和递归法来完成算法设计，进一步提升计算思维。索引查找法虽然有一定难度，但是有助于学生进一步认识算法与数据结构的关系，从而进一步提升计算思维。 教学目标 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 pos
~~ 您好，已阅读到文档的结尾了 ~~
