数据结构（Java语言版）（第2版）（微课版） 教案9-2：动态表查找

授课题目第9章查找-动态查找授课时间授课学时22学时授课地点授课形式理论教学目标知识目标能力目标素质目标学情分析基础：学生已经具备了一定的数学和计算机基础，但可能缺乏对数据结构的深入理解和应用能力。在进行查找单元的教学前，需要评估学生对线性表、数组、树等基本概念的掌握情况；发展进阶：查找单元的教学内容通常包括二叉排序树，平衡二叉树等。教师需要根据学生的学情来安排教学内容的深度和广度；学习障碍：二叉排序树，平衡二叉树是学生学习中的难点，需要教师在教学过程中给予更多的指导和练习。教学内容教学重点解决方法采用任务驱动法和案例教学法相结合的策略，通过设置实际问题和任务，引导学生运用所学知识解决问题，培养学生的逻辑思维和解决问题的能力。教学难点解决方法二叉排序树，平衡二叉树是学生学习中的难点，需要教师在教学过程中给予更多的指导和练习。教学策略循序渐进：内容设计从简单到复杂，先讲解基础概念，再逐步深入复杂的树结构和查找算法。这样可以帮助学生建立稳固的知识体系，避免因跳跃式教学而导致的理解困难。动手实践：通过手动构建树结构、模拟查找过程、编写和分析代码等实践活动，帮助学生将理论知识应用于实际，提升动手能力和编程技能。直观展示：利用动画、图示、PPT等直观工具，帮助学生理解抽象概念和复杂算法的动态过程，增强学生的直观感受和理解深度。对比分析：通过对不同数据结构（如BST、AVL树）的比较，帮助学生理解各自的特点、优势和适用场景，培养分析和选择能力。互动讨论：通过教师提问、学生讨论、小组合作等方式，增强课堂互动，激发学生的思维，鼓励他们提出问题和发表见解，从而深化对知识的理解。案例教学：结合实际应用场景和案例分析，使学生理解这些查找算法在现实中的应用，增强学习的实用性和趣味性。学习方法理解基础概念：在学习每一种查找树时，首先要掌握其基本概念和性质，为进一步理解查找算法打好基础。动手操作与练习：通过手动绘制树结构、模拟查找过程、编写代码等实际操作，巩固对理论知识的理解，提升解决问题的能力。多看、多想、多问：通过观看动画演示、思考教师提出的问题、主动提出自己的疑问，积极参与课堂互动，加深对复杂算法的理解。比较与反思：在学习不同查找树时，注意对比它们的异同，反思其应用场景和效果，这有助于在实际编程中选择合适的算法。复习与总结：课后及时复习所学内容，整理笔记，梳理每种查找树的特点和查找过程，形成系统的知识结构。教学资源

教学过程教学环节及时间教学内容教师活动学生活动设计意图课前预习（网络调研）：线性查找是如何工作的？在最坏的情况下，线性查找的时间复杂度是多少？线性查找适用于哪些类型的数据结构？；1.发布并布置学习任务；2.推送相关学习资源；3.开启课前答疑讨论活动。1.接受并查看课前学习任务；2.完成网络调研及学习任务；3.完成课前讨论；通过网络调研，了解数据结果在软件设计中的应用，加深对数据结构的认识。课中环节一导言（5分钟）问题：1、有哪些基本的查找算法？它们各自适用于什么样的数据集？1.对学生进行提问，了解学生对查找内容的了解和认识程度；2.教师点评学生回答效果，并进行强调和总结；1.结合自己课前预习，回答教师问题；2.根据教师总结，进行学习记录和反思；通过对相关知识的介绍，引出数据结构相关知识和内容；加深对数据结构的理解。课中环节二目标（5分钟）1.本讲内容的目标：能够理解查找的基本概念，能够理解折半查找，能够理解分块查找，能够理解哈希查找；2.本讲内容的重点、难点内容；3.本将内容的学习方法；1.展示本次课程的学习目标、重点和难点内容；2.介绍和强调本次课程的学习方法；1.熟悉本次课程需要巩固的知识、提高的技能、提升的认识；2.理解学习本次课程的目的和意义以及方法途径；通过生活中的实际例子引入查找的概念，使学生感受到数据结构中的查找问题与实际生活的联系，从而提高学习兴趣。课中环节三介绍性讲解（70分钟）知识点1：二叉排序树（BST）（30分钟）核心知识点：算法实现、时间复杂度、空间复杂度素质点：通过此部分知识培养学生逻辑思维能力；概念讲解：介绍二叉排序树的定义和性质，说明树中每个节点的左子树和右子树分别是小于或大于该节点值的元素集合。查找过程演示：通过PPT或手绘树形结构图，演示在BST中查找特定值的过程。代码讲解：展示BST查找的伪代码，解释每一步的逻辑，强调递归思想。参与讨论：学生思考并讨论BST的性质，如左小右大、无重复节点等。手动模拟：学生根据教师提供的数列手动构建BST，并模拟查找过程。代码实现：学生在教师指导下编写或理解BST的查找算法代码，运行测试并验证结果。通过树形结构的直观展示帮助学生理解BST的基本概念和查找过程。通过手动操作和代码实现，强化学生对BST递归思想的理解和应用。知识点2：平衡二叉树（AVL树）（40分钟）核心知识点：算法实现、时间复杂度、空间复杂度素质点：培养学生理解其分治思想；引入平衡概念：解释平衡二叉树的定义及其重要性，指出BST在极端情况下可能退化为链表。旋转操作讲解：通过动画演示AVL树的左旋、右旋、左-右旋、右-左旋操作，帮助学生理解平衡调整的过程。查找过程讲解：演示在AVL树中查找节点的过程，并展示其伪代码。动手练习：学生尝试通过手动调整平衡因子、旋转操作，理解AVL树的自平衡特性。代码实现：学生尝试编写AVL树的查找代码，并验证其性能与BST的对比。通过旋转操作的动态演示，帮助学生直观理解AVL树的平衡调整。通过代码实践，让学生体验AVL树在查找效率上的改进及其实现复杂度。课中环节五总结（10分钟）1.总结：（1）理解和掌握三种查找相关概念；（2）掌握算法的描述方法和规则（3）学会对算法进行分析和评价，并能根据实际需求进行算法设计；1.结合授课内容对本讲主要知识进行总结；2.引导学生应用算法评价方法设计算法和程序；3.布置课后学习任务；根据本讲总结查找不足，并通过答疑、作业等巩固知识；通过总结查找的相关知识，并能巩固学习；课后1.总结反思2.完成拓展知识的学