选修1 数据与数据结构第五章 数据结构与算法5.4 数据查找一等奖ppt课件

这是一份选修1 数据与数据结构第五章 数据结构与算法5.4 数据查找一等奖ppt课件，共22页。PPT课件主要包含了学习目标，引入选一选，查找概念，in-1，dikey，ii+1，未找到输出结果，找到输出结果，转化成程序，流程图等内容，欢迎下载使用。

能理解顺序查找的思想。
能合理选用数据结构，理解顺序查找的范围与条件。
能用自然语言、流程图、Pythn语言描述顺序查找算法。
能分析顺序查找最坏、最好情况、平均比较次数。
能熟练应用各种顺序查找程序，完成生活、学习中的问题。
下列5个图标找出哪一个是微信图标：
查找（Search）又称检索，计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。 若没有找到满足条件的对象，则返回特定值，表明查找失败；若查找到满足条件的对象，则表明查找成功，一般要求返回该对象的存储位置或对象值本身。
顺序（线性）查找算法思想
②输入查找关键值key；
③从数组中的第一个元素开始与关键值key进行比较，若相等d[i]==key ，则输出相应信息；否则，继续比较下一个元素。
①定义待查找数据所储存的数组；
④直到找完数组的最后一个元素仍没有，输出查找失败。
输入查找的元素值key=33
此时d[i]=key,数组中的第3个位置
如果输入查找的元素值key=22
此时i等于4,还是没有找到
自然语言描述顺序查找过程
顺序查找的流程图描述：
#参考浙江版作业本P71－图5－6a=[86,63,35,88,99,78,51,10,8]n=len(a)key=int(input(“输入查找数据："))flag=Falsefr i in range(n): if a[i]==key: flag=True breakif flag==True: print("查找成功！")else: print("未找到！")
a=[86,63,35,88,99,78,51,10,8]
key=int(input(“输入查找数据："))
fr i in range(n):
if a[i]==key:
if flag==True:
print("查找成功！")
print("未找到！")
a=[86,63,35,88,99,78,51,10,8]n=len(a)key=int(input(“输入查找数据："))flag=Falsefr i in range(n): if a[i]==key: flag=True breakif flag==True: print("查找成功！")else: print("未找到！")
#设置查找到的标记flag
#设置查找范围从索引0至n-1，步长1
#相同设置标记flag为True
#如果标记flag为True
#否则标记flag为False
找到第1个元素,查找1次找到第2个元素,查找2次……找到第n个元素，查找n次
平均查找次数（1+2+……+n）/n
A数组中存放了一些水果名称“apple”、“range”、 “pineapple”、“banana”、“watermeln”、“peach”、“pear”，现在想查找水果“watermeln”是否在其中，如找到输出“查找成功！是第几个水果”，否则输出“查找失败”，无论查找成功与否都输出比较的次数。
a=["apple","range","pineapple","banana","watermeln","peach","pear"]n=len(a);c=0key=input("请输入待查找水果：")flag=Falsefr i in range(n): c+=1 if a[i]==key: flag=True breakif flag==True: print("查找成功！在第"+str(i+1)+"个,比较次数："+str(c))else: print("未找到！",key,"比较次数：",c)
查找水果问题程序实现（一）：从前往后找
#输入待查找水果，调试时直接用key="watermeln"
a=["apple","range","pineapple","banana","watermeln","peach","pear"]n=len(a)key=input("请输入待查找水果：")flag=Falsefr i in range(n-1,-1,-1): c+=1 if a[i]==key: flag=True breakif flag==True: print("查找成功！在第"+str(i+1)+"个,比较次数："+str(c))else: print("未找到！",key)
查找水果问题程序实现（二）：从后往前找
#设置查找范围从索引n-1至0，步长－1
a=["apple","range","pineapple","banana","watermeln","peach","pear"]n=len(a)key="watermeln" #key=input("请输入待查找水果：")flag=Falsefr i in range((n+1)//2): c+=1 if a[i]==key: x=i+1;flag=True;break if a[n-1-i]==key:x=n-i;flag=True; breakif flag==True: print("查找成功！在第"+str(x)+"个,比较次数："+str(c))else: print("未找到！",key)
查找水果问题程序实现（三）：前后一起找
#设置查找范围从索引0至n的一半，步长为1
#逐个进行第i和第n-1-i个判断
#找到标记flag为True
某个班级的部分学生信息技术成绩如下表所示，要求实现根据考号查询该生的信息技术成绩，如查询不到则显示“该班无此学生”。
思考：用哪一种数据结构对表格数据进行存储？对哪个字段进行顺序查找？
imprt csvcsvFile = pen("cj.csv", "r")reader = csv.reader(csvFile) a = [] fr item in reader: print(item) a.append(item)csvFile.clse()
key=input('请输入要查询的考号：')flag=False #flag做标记（预设没找到）length = len(a)fr i in range(length):#一个一个的举例 if a[i][1] == key:#一个一个的判断 flag=True breakif flag==True: print("该生IT是"+ str(a[i][5])+"分")else: print("该班无此学生")
列索引0 1 2 3 4 5 6
#练习：顺序查找信息最高分和信息最低分：print("顺序查找信息最高分和信息最低分：")max1=a[1][5];min1=a[1][5]#假设第一个是最大值也是最小值fr i in range(2,length): #此后一个一个的举例 if a[i][5]>max1: #一个一个的判断，比最大值大吗？ max1=a[i][2] elif a[i][5]实例应用：查找最大、最小值
max1=a[1][5];min1=a[1][5]
fr i in range(2,length):
if a[i][5]>max1:
max1=a[i][2]
elif a[i][5]min1=a[i][5]
我们班一共有40个同学，查找成功最好情况是比较几次？最差呢？若查找不成功，需要比较几次？ 那么若有n个数据，那顺序查找的平均比较次数为几次？并求出时间复杂度。时间复杂度为
若一个数据序列有n个数，查找不成功的比较次数为n，查找成功：最好的情况为1次，最差的情况为n次，所以查找成功时的平均比较次数为(n+1)/2，且顺序查找的时间复杂度为O(n)
生活实战应用：双向有序查找
某校运动会投铅球项目分两小组，每组评委已经将每组的前8名从高到低排好序。取本项目的前m名颁奖，其中小李同学收集的2组选手的名次及其成绩如表所示，请在划线处填上合适语句。n=len(a);c=[0]*8;i=0;j=8；k=0fr k in range(m): if j>n r : c[k]=a[i];i=i+1 else : c[k]=a[j];j=j+1 print(c[k])
a[j]<=a[i] and i<=7
对自己的表现进行客观的评价，并思考后续完善的方向。（3=优秀，2=一般，1=仍需加油）