高中信息技术沪教版（2019）选修1 数据与数据结构1.采用顺序查找法查找商品优秀课件ppt

项目九 实现查找指定商品

——查找算法的应用及数据结构的选择

第一课时 采用顺序查找法查找商品

❑教材分析

本节的主要内容是采用顺序查找法查找商品。在学习中，学生将尝试使用顺序查找法查找对应价格的商品数据。本项目的学习强调引导学生对实际问题从数据量大小、运行时间、存储空间和算法实现难易度等方面进行综合考虑，选择恰当的查找算法，使用合适的存储结构,通过编程实现问题的解决。在体验使用二分查找法查找商品的过程中，分别采用迭代法和递归法来完成算法设计，进一步提升计算思维。索引查找法虽然有一定难度，但是有助于学生进一步认识算法与数据结构的关系，从而进一步提升计算思维。

❑教学目标

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<len(alist) and not found:  # 列表未结束并且还未找到则一直循环

        if 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) #输出为待查找数据在列表中的下标