《数据结构[Python语言描述]》教案第15课查找（8.1-8.2）.docx

课题第15课查找(8.1-8.2)课时2课时(90min)教学目标知识目标：(1)熟悉查找的基本术语(2)掌握顺序杳找、折半杳找和分块杳找的基本算法和杳找性能技能目标：能灵活运用静态查找算法解决实际应用中的杳找问题素质目标：自觉培养发散思维，积极开拓思路，寻求问题的多种解决方法教学重难点教学重点：顺序查找、折半查堤口分块查找的基本算法和查找性能教学难点：顺序直找、折半直找和分块杳找的基本算法教学方法问答法、讨论法、讲授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假人员及原因问题导入【教师】提出以下问题：计算机中杳找操作有哪些？【学生】思考、举手回答传授新知【教师】通过学生的回答引入要讲的知识，介绍直找概述、静态查找算法8.1 查找概述查找是计算机在进行数据处理时经常使用的一种运算。例如，对于一个表结构，经常进行的操作如下。(1)在表中插入一个数据元素。(2)查找表中已经存在的数据元素。(3)删除表中已经存在的数据元素。以上操作都需要使用查找运算。由此可见，当数据量较大时，杳找操作便会成为数据处理过程中较为耗时的一部分。因此，一个高效的查找算法是提高程序运行速度的关键。1 .查找表查找表是按某种数据形式(可以是前面章节中的任何一种数据结构，如线性表、二叉树或图等)存储的同一类型数据元素的集合，每个数据元素通常由若干数据项组成。查找表可分为静态杳找表和动态查找表。如果在进行杳找操作时，不能改变杳找表中的原始数据，则相应的查找表称为静态查找表；如果在进行查找操作时，还可以对查找表进行修改操作(如向查找表中插入新的数据元素或从查找表中删除已有的数据元素)，则相应的查找表称为动态查找表。2 .关键字关键字是数据元素中某个数据项的值，用它可以标识一个数据元素。其中，能唯一标识一个数据元素的关键字称为主关键字，也就是说，对于不同的数据元素，其主关键字各不相同。反之，不能唯一标识一个数据元素的关键字称为次关键字.数据元素类型定义如下.classRNode:def_init_(self,key,data):self.key=key#关键字self.data=data#其他数据项【提示】当数据元素只有一个数据项时，其数据元素的值就是关键字。3 .查找直找是指根据给定的值，在杳找表中找出关键字与给定值相等的雌元素。若找到相应的数据元素，则有找成功，查找结果可以是数据元素的信息，也可以是数据元素在查找表中的位置；否则有找失败，查找结果为Nonee÷【教师】随机邀请学生回答以下问题以关键字或次关键字进行杳找时，直找结果有区别吗？÷【学生】聆听、思考、回答当关键字是主关键字且杳找成功时，查找结果是唯一的；当关键字是次关键字时，需要查找整个查找表，直找成功后返回所有直找结果。4 .平均查找长度(ASL)平均直找长度是指为确定某一数据元素在查找表中的位置，需与给定值进行比较的关键字个数的期望值。对于含有n个数据元素的直找表，直找成功时的平均直找长度ASL为-1ASL=ZPGi=0其中，月是查找第7个数据元素的概率；C是找到第/个雌元素所需的关键字比较次数。5 .2静态查找算法基于静态杳找表的查找又称静态查找。8.2.1顺序直找顺序直找是最简单、最常用的直找算法，其基本思想是从J顺序表的一端开始，将数据元素的关键字逐个与给定值进行比较。若某个数据元素的关键字与给定值相等，则查找成功，返回该数据元素在直找表中的位置；否则，杳找失败，返回-1.【算法描述】defSeqSearch(self,key):n=self.Ien#查找表的长度i=0whilei<nandself.listi.key!=key:#从表头开始向后顺序查找i+=1ifi>=n:#查找失败return-1else:#查找成功returni此外，还可以设置一个“哨兵"，即将顺序表的IiStml的关键字设置为key.这样，i从0开始依次比较，当满足hsti=key时，若i=n,说明查找失败，返回T；否则，查找成功，返回数据元素在查找表中的位置。【算法描述】详见教材【高手点拨】在第一种算法SeqSearCh()中，查找时需要反复判断是否已经杳找完厕事表中的所有数据元素。而在第二种算法SeqSearchIMP()中查找时从顺序表的第一个数据元素开始自前向后依次进行关键字的比较。【教师】讲解实例8-1(详见教材)【教师】随机邀请学生回答以下问题顺序直找有哪些优缺点？*【学生】聆听、思考、回答顺序查找的优点是算法简单且对查找表本身没有任何要求。无论数据元素是否按关键字有序排列或以何种存储结构存储，都可以采用顺序查找。顺序杳找的缺点是平均直找长度较大，尤其是当数据量较大时，直找效率相对较低。8.2.2折半查找折半查找又称二分查找，它是一种效率较高的直找算法。采用折半查找的查找表必须是按数据元素的关键字有序排列的顺序表.为实现折半查找，可以设置3个变量，分别是low.high和mid。其中,而，用来记录当前查找范围的起始位置；high用来记录当前查找范围的终止位置；mid用来记录当前查找范围内中间数据元素的位置。折半杳找的基本步骤如下.(1)初始状态时,令Iow=O,high=len-l.,low+highmid=-(2)确定当前直找范围内中间数据元素的位置，即L2Je(3)将位于mid处数据元素的关键字与给定值key进行如下上匕较。 若listmid.key=key,则查找成功。 若lisimid.key>key,则high=mid-l 若listmid.key<key,则IoW=mid+1.(4)重复步骤(2)和步骤(3),直到查找成功或low>high(即杳找范围为空，直找失败).【算法描述】详见教材÷【教师】讲解实例8-2(详见教材)由于折半直找是以查找表的中间数据元素为比较对象,每经过一次腕，就将相应的杳找范围缩小了一半，因此，折半查找的过程可以用二叉树来描述。二叉树中的一个结点表示查找表中的一个数据元素，结点中的值为数据元素在查找表中的位置。其中，根结点对应当前查找范围的中间数据元素，左子树对应当前查找范围的前半部分，右子树对应当前查找范围的后半部分，这种描述查找过程的二叉树称为判定树。折半杳找在直找成功时关键字的比较次数最多不超过树的深度，而判定树的形态只与查找表中数据元素的个数有关，而与关键字的值无关。由于具有«个结点的判定树的深度为log?+1,所以，对于长度为的查找表，折半查找在查找成功时关键字的比较次数至多为口。&11J+lo同理，折半查找在查找失败时关键字的比较次数也至多为Liog2+1。假设查找表的长度为=2-1,则判定树是深度为7=k)g2m+i)的满二叉树。该满二叉树中层次为1的结点个数为I,比较次数为1；层次为2的结点个数为2,比较次数为2；以此类推,层次为J(1jh)的结点个数为比较次数为八假设查找表中每个叫元素的查找概率相等，即Pi=-,则杳找成功n时折半查找的平均查找长度为H-I1n.1ASL=VPiCi=Vy×2y,=Iog1(w+1)-1logw+l)-1?H因此，折半查找的时间复杂度为O(Iog2)。÷【教师】随机邀请学生回答以下问题折半直找有哪些优缺点？÷【学生】聆听、思考、回答折半查找的优点是关键字的比较次数少,杳找速度快,平均性能好;缺点是要求查找表为有序表，且插入、删除操作困难。因此，折半杳找算法适用于数据元素变动较少但杳找频繁的有序表。8.2.3分块查找分块直找是一种性能介于顺序直找和折半杳找之间的查找算法。分块是分块查找的基础，是指将查找表划分为若干等长的块，其中最后一块可以不满。划分时要保证孀元素的关键字在块与块之间是有序的，即第二块中所有数据元素的关键字均大于第一块中数据元素的最大关键字，第三块中所有数据元素的关键字均大于第二块中数据元素的最大关键字，；而块内数据元素可以任意排列。划分完成后，为每个块建立一个索引项，其中包含关键字项和指针项两部分，分别用于记录每块中的最大关键字和每块在查找表中的起始地址。将所有块的索引项按关键字有序排列，即可构成索引表。【教师】讲解实例8-3(详见教材)分块直找又称索引顺序直找，其基本步骤如下。(1)将给定值与索引表中的关键字进行比较，以确定给定值所在的块。(2)在相应的块中进行查找。【高手点拨】由于索引表是按关键字有序排列的顺序表，故可以采用顺序杳找或折半查找来确定给定值所在的块。而块内数据元素不要求按关键字有序排列，故进行块内杳找时一般采用顺序直找。【算法描述】详见教材【教师】讲解实例8-4(详见教材)【学生】聆听、思考、理解、记录任务实施任务一利用折半宜找算法宜找学生成绩【教师】描述问题，分析问题，安排学生扫描微课二维码观看视频“利用折半查找算法查找学生成绩“(详见教材)，要求学生完成任务【问即描述】现有数据结构课程的成绩表，表中记录了参加该课程考试的所有学生的学号、姓名和分数，且表中记录按学生学号递增有序，请利用折半查找算法查找指定学生的成绩信息。【问题分析】创建一个顺序表来存储学生的成绩信息，其中每个学生的成绩信息包括学号、姓名和分数。然后输入学生人数，并依次录入每个学生的成绩信息。最后使用折半查找算法直找指定学生的成绩信息，若找到，输出学生的成绩信息；否则输出"未找到该学生的成绩信息！"。【学生】自行扫码观看配套微课，按照要求完成任务，如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问题课堂小结【教师】简要总结本节课的要点查找概述：查找表、关键字、杳找、平均查找长度（ASL）静态查找算法：顺序直找、折半查找、分块直找【学生】总结回顾知识点作业布置【教师】布置课后作业完成课后习题中的相关练习。【学生】完成课后任务教学反思