数据结构（Python Java）（微课版） 教案 -单元8查找

教案课程名称数据结构与算法设计课程代码总学时64课程负责人任课教师

单元教案授课日期年月日—月日授课地点授课班级班级人数教学单元单元8查找教学时数8教学目标AOB1:掌握计算机程序设计中的线性表、栈、队列、树和图的逻辑结构与存储结构。了解递归的数据逻辑组织结构；AOB2:掌握计算机程序设计中的线性表、栈、队列、树、图的数据增、删、改、查操作运算。了解递归的处理算法。掌握选择与排序处理算法；AOB3:掌握对算法的科学分析方法。BOB1:能根据实际问题中的数据特性选择适当的数据结构；BOB2:设计出适当的算法和程序。EOB1:掌握使用搜索引擎、论坛、帮助文档、课外书籍等方法解决学习中出现的问题；EOB2:能主动阅读书后拓展知识并进行实验验证；EOB3:能独立分析解决问题，能把自己的想法用代码实现。教学方式混合式教学评价方式课堂考勤（20%），课堂活动参与程度（20%）线上单元测试（40%）线下课堂教学参与程度（20%）教学资源1.算法与数据结构（Java语言描述），陈媛，清华大学大学出版社2.电脑50台（含eclips）;3.网络学习资源：/forums/ST_Arithmetic：课程平台网址：/teacher/mainCourse/courseHome.html?courseOpenId=u3bwaoaqhzdgvlcf34d8ea单元教学设计第一次课（2学时）教学内容1查找的概念关键字：数据元素中的一个数据项，可以标识数据元素，主关键字，次关键字查找表：具有同一属性的数据元素的集合，分为静态查找表和动态查找表两类查找：给定关键字值K，在表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置。否则查找失败，返回相关的指示信息查找方法的评价查找效率：占用存储空间多少，算法本身复杂程度平均查找长度ASL：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值静态查找静态查找问题：查找过程中数据不变静态查找表结构：顺序表，线性链表静态查找分类：顺序查找、折半查找、分块查找等2顺序查找查找过程:从表的一端开始逐个进行记录的关键字和给定值的比较顺序查找的评价：查找成功时，平均查找长度约为元素个数的一半顺序查找的优点：算法简单，顺序表或用链表均适用，结点是否按关键字有序，都同样适用顺序查找的缺点：查找效率低提高顺序查找的效率：合理安排节点位置，使访问越频繁的数据，比较的次数越少3.折半查找二分查找条件：顺序表，表中数据元素按关键字有序基本思想：每次将待查记录所在区间缩小一半举例实现过程的基本思想：确定查找区间的中点mid，将待查的K值与seqlist[mid].key比较，若相等，查找成功并返回此位置；若不相等，确定新的查找区间,返回1，重新开始二分法查找，当上下界相等时,结束查找过程。二分查找过程二叉树实现已知表中有n个结点，以当前查找区间的中点为作为根，左半区和右半区中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为二分查找的判定树(DecisionTree)或比较树(ComparisonTree)折半查找的特点虽然二分查找的效率高，但是要将表按关键字排序。只适用于顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。适用于表结点比较稳定的，很少做插入或删除操作的顺序表。不适用于链表。教学重点顺序查找，折半查找教学难点折半查找的实现教学流程教学环节教师活动学生活动讲评和考勤（5分钟）1平台发布任务2考勤1考勤讲授（80分钟）1.查找的概念（15分钟）2.顺序查找（25分钟）3.折半查找（40分钟）1.积极回答教师提问2.认真思考、记录关键内容3.积极参与课堂的讨论和互动总结与发布课后任务（5分钟）1.总结课堂内容以及在练习过程中出现的，问题。2.布置课后任务1.思考教师总结2.记录课后任务第二次课（2学时）教学内容技能训练：折半查找训练目标：掌握利用二分查找判定树实现折半查找的方法训练步骤：1根据数组元素的个数创建完全二叉树2数组中的元素是有序的，对建立好的二叉树进行中序遍历，同时按顺序放入数据。完成二分查找判定树的创建3创建查询元素的方法4主函数测试方法教学重点二分查找判定树的创建，查询元素的方法教学难点二分查找判定树的创建教学流程教学环节教师活动学生活动考勤（5分钟）1.考勤1.考勤技能训练（80分钟）1.布置技能训练任务（5分钟）2.在技能训练过程中巡视并启发学生解决遇到的问题。1.独立完成老师下发的课堂练习2.在遇到问题时与同学讨论。总结与发布课后任务（5分钟）1.总结本次课程内容；2.布置课后任务1.思考教师总结，2.记录教师的任务要求并在课后完成。第三次课（2学时）教学内容分块查找分块查找表由“分块有序”的线性表和索引表组成。块间有序，块内无序。索引表有序，又称“索引顺序查找”。查找过程：将表分成几块，块内无序，块间有序。先确定待查记录所在块，再在块内查找。适用条件：后一个子表中,所有记录的关键字均大于前一个子表中的最大关键字。算法实现：顺序存储待查记录,每个数据元素包含关键字域。建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针。分块查找算法分析假设：表中有10000个结点顺序查找：平均比较5000次二分查找：平均比较14次分块查找：将其分成100个数据块，每块含100个数据元素。顺序查找确定块，块内顺序查找，平均比较100次分块查找的效率于顺序和二分查找之间动态查找静态查找过程中仅仅是执行“查找”的操作动态查找在查找过程中会对表进行构建、扩充、修改、删除的操作动态查找：二叉排序树、平衡二叉树、B-/B+树、红黑树等二叉排序树查找二叉排序树定义：二叉排序树或者是一棵空树；或者满足如下性质:若左子树不空，则左子树上所有结点的值均小于根结点的值。若右子树不空，则右子树上所有结点的值均大于根结点的值。左右子树本身也都是二叉排序树。按中序遍历该树得到的序列是递增有序的二叉排序树生成：从空树出发，经过一系列的插入操作之后，可生成一棵二叉排序树。插入原则：若二叉排序树为空，则插入结点应为新的根结点；否则，在其左、右子树上查找，直至某个结点的左子树或右子树为空为止，则插入结点应为该结点的左孩子或右孩子二叉排序树的生成举例：二叉排序树查找算法分析平均查找长度和二叉树的形态有关二叉排序树是把表的n个结点依次插入生成的最坏情况，二叉排序树是深度为n的单支树，其平均查找长度和顺序查找相同，是(n+1)/2最好情况，生成的二叉排序树，其形态比较匀称，得到与二分查找的判定树形态相似的二叉排序树，此时平均查找长度大约是log2n。插入、删除和查找算法的时间复杂度均为O(log2n)。教学重点分块查找，二叉排序树查找教学难点二叉排序树查找教学流程教学环节教师活动学生活动讲评和考勤（5分钟）1平台发布任务2考勤1考勤讲授（70分钟）1.分块查找（25分钟）2.静态查找算法比较（10分钟）3动态查找（5分钟）4.二叉排序树查找（30分钟）1.积极回答教师提问2.认真思考、记录关键内容3.积极参与课堂的讨论和互动课堂练习（10分钟）1.二叉排序树的构造（10分钟）认真思考，独立完成练习总结与发布课后任务（5分钟）1.总结课堂内容以及在练习过程中出现的，问题。2.布置课后任务1.思考教师总结2.记录课后任务第五次课（2学时）教学内容散列表查找概念的引入：二分法,顺序查找，二叉排序树都以关键字的比较作为查找的基础。如果建立关键字与存储地址的映射关系，则已知关键字时，可以直接定位到相应的存储位置上，从而达到查找的目的理想情况下，无须任何比较就可以找到待查关键字，查找的期望时间为O(1)以结点的关键字K为自变量，通过一个确定的函数关系h，计算出函数值h(K)这个值可理解为结点的存储地址，将结点存入h(K)所指的存储位置上查找时，根据关键字，用函数h(K)计算出地址，再到相应的单元里去取出结点。函数h称为散列函数，h(K)称为散列地址，散列方法存储的线性表称为散列表(HashTable)，哈希表举例：常用哈希函数-平方取中法求关键字的平方值,扩大相近数的差别然后根据表长度取中间的几位数作为散列函数值如{0100,0010,1010,1001,0111}，散列表长度为1000平方后得到：{0010000,0012100,1020100,1002001,0012321}根据表长度,可取中间三位数作为散列地址：{100，121，201，020，123}常用哈希函数-除留余数法h(key)=key％p例：{159，259，359，459，559}取p=100,得到地址:{59,59,59,59,59}取p=1000,得到地址:{159,259,359,459,559}选取的p值应使得散列函数值尽可能与关键字的各位相关，p最好为素数，通常p的取值为表的长度m常用的哈希函数-数字分析法例：有80个记录，关键字为8位十进制数，哈希地址为2位十进制数常用的哈希函数-折叠例：关键字为：0442205864，哈希地址位数为4将关键字分割成若干部分，然后取它们的叠加和为哈希地址，此法适合于关键字的数字位数特别多的情形散列表冲突散列表的冲突现象：两个不同的关键字，可能得到相同的散列函数值，从而被映射到表的同一位置上称为冲突或碰撞。发生冲突的若干个关键字称为该散列函数的同义词避免冲突：选择合适的散列函数，关键字的个数小于或等于散列表的长度冲突不可能完全避免：若关键字的个数大于散列表的长度,则无论怎样设计h，也不可能完全避免冲突。设计散列函数时尽可能使冲突最少。要确定解决冲突的方法，使发生冲突的同义词能够存储到散列表中。处理冲突的方法-线性探测法堆积现象：散列地址不同的关键字，争夺同一个后继位置。使得非同义词也加入了探测序列，增加了探查的长度，即增加了查找时间。若散列函数不好或装填因子过大，会使堆积加剧。装填因子α=填入表中的元素个数/哈希表的长度处理冲突的方法-拉链法分配指针数组，建立m个空链表，由哈希函数对关键字转换后，映射到同一哈希地址的同义词均加入到相应指向的链表中拉链法优点：处理冲突简单，无堆积现象，非同义词绝不会发生冲突，因此平均查找长度较短；链表上的结点空间是动态申请的，更适合于造表前无法确定表长的情况；开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。拉链法缺点：指针需要额外的空间。当结点规模较小时，效率低于线性探测法。若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，减少了开放定址法中的冲突，从而提高平均查找速度处理冲突的方法-建立公共溢出区建立公共溢出区存储所有哈希冲突的数据。为哈希地址集分配两个表：一个基本表，每个单元只能存放一个元素，一个溢出表，放“溢出”的元素散列表的查找分析散列表的查找过程基本上和造表过程相同。一些关键字可通过哈希函数转换的地址直接找到，另一些关键字在哈希函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键字进行比较的过程。哈希表查找效率的量度，用平均查找长度来衡量。查找过程中，关键字的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。影响产生冲突多少的因素，也就是影响查找效率的因素，有以下三个方面，哈希函数是否均匀，处理冲突的方法，哈希表的装填因子教学重点常用哈希函数，处理冲突的方法教学难点常用哈希函数，处理冲突的方法教学流程教学环节教师活动学生活动讲评和考勤（5分钟）1.平台发布任务2.考勤1.考勤讲授（80分钟）1.散列的引入（10分钟）2.常用哈希函数（30分钟）3.散列表冲突概念（10分钟）4.处理冲突的方法（20分钟）5.散列表的查找分析（10分钟）1.积极回答教师提问2.认真思考、记录关键内容3.积极参与课堂的讨论和互动总结与发布课后任务（5分钟）1.总结课堂内容以及在练习过程中出现的，问题。2.布置课后任务1.思考教师总结2.记录课后任务教学效果与