《数据结构》1-9章教案整本书电子讲义教案.doc

教 案（理论课） 第 1 次课 2 学时章 节第一章 绪论1.1 数据结构的发展1.2 数据结构的意义1.3 数据结构的基本概念和术语讲授主要内 容介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语。重 点难 点重点： 数据结构及相关概念； 数据的逻辑结构、存储结构及运算之间的关系；难点： 数据元素；逻辑关系；抽象数据类型要求掌握知识点和分析方法l 了解数据结构的发展l 理解数据结构中的基本概念l 理解抽象数据类型的概念、记法和用法教学设计1. 从数据在计算机中的处理过程入手，介绍课程2. 介绍数据结构课程的意义及其在教学计划中的核心地位3. 介绍教材整体结构4. 提出学习方法及要求：强调课后练习及实验的重要性，介绍配套网络教学平台5. 讲授数据结构的基本概念6. 通过实例辅助分析数据结构的三个方面：逻辑结构、存储结构及运算，重点结束逻辑关系，强调存储结构如何表示逻辑关系。注意引申三者之间的关系7. 在理解数据类型和抽象的基础上，给出抽象数据类型的定义。分析：为什么对数据结构仅定义基本操作作业布置习题1一13 二16 三1,2教学后记教 案（理论课） 第 2 次课 2 学时章 节第一章 绪论1.4 算法及其分析讲授主要内 容介绍算法的定义，算法的基本特性，算法的描述方法，讲授算法复杂度的分析方法。重 点难 点重点：算法的定义及基本特性；算法复杂度的分析方法。难点： 算法复杂度的分析方法。要求掌握知识点和分析方法l 理解算法的定义及基本特性l 理解算法的描述方法l 理解算法与程序的关系l 掌握算法复杂度的分析方法教学设计1. 以实例引入算法定义2. 从使用的角度分析算法的特性3. 介绍算法的描述方法：自然语言、流程图、程序设计语言等4. 分析算法与程序的关系，指出：程序设计的核心是算法设计5. 给出算法分析的意义，介绍事前分析法和事后统计法6. 给出问题规模、语句频度、大O记号的概念7. 结合例题，讲授常用的几种时间复杂度作业布置习题1一4 二79 三3 四教学后记教 案（理论课） 第 3 次课 2 学时章 节第二章 线性表2.1 线性表的逻辑结构2.2 线性表的顺序存储结构讲授主要内 容举例讲解线性表，分析其逻辑结构。介绍线性表的抽象数据类型。讲授顺序表的存储结构及特点，分析讲授顺序表的各种基本运算。重 点难 点重点： 线性表的定义及其逻辑结构顺序表的存储结构及特点顺序表的基本运算及其性能分析难点：顺序表的基本运算及其性能分析要求掌握知识点和分析方法l 掌握线性表的定义及其逻辑结构l 理解线性表的抽象数据类型l 掌握顺序表的存储结构及特点l 掌握顺序表的基本运算：插入、删除及查找运算及其性能分析教学设计8. 给出线性表的定义，注意强调要点，分析其逻辑结构9. 给出线性表的抽象数据类型10. 给出顺序表的存储结构示意图，强调存储要点，总结存储特点11. 给出顺序表的建表算法12. 利用算法动画演示，分析顺序表的插入运算执行过程，写出插入算法并分析13. 利用算法动画演示，分析顺序表的删除运算执行过程，写出删除算法并分析14. 利用算法动画演示，分析顺序表的查找运算执行过程，写出查找算法及分析作业布置习题2一16 二1,2,4,5,6 三1,2教学后记教 案（实验课） 第 4 次课 2 学时章 节第二章 线性表线性表的顺序存储结构重 点难 点重点：顺序表的基本运算及其性能分析难点：顺序表的基本运算及其性能分析要求掌握知识点和分析方法l 掌握顺序表的存储结构及特点l 掌握顺序表的基本运算：插入、删除及查找运算及其性能分析教学内容实现在顺序表上的基本运算。要求：1. 实现顺序表的建立，采用给定的数组做输入和从键盘输入两种方式实现2. 实现顺序表的插入3. 实现顺序表的删除4. 实现顺序表的查找：按值查找和按位置查找5. 实现顺序表的逆置作业布置完成本次课程实验报告教学后记教 案（理论课） 第 5 次课 2 学时章 节第二章 线性表2.3 线性表的链式存储结构 讲授主要内 容举例讲解链表，分析其逻辑结构。讲授单链表上实现的基本运算。重 点难 点重点：链表的结构。单链表上实现的基本运算：头插法难点：单链表上实现的基本运算要求掌握知识点和分析方法l 理解链表的含义及其逻辑结构l 掌握单链表的基本运算及其性能分析教学设计1. 给出单链表的存储结构示意图，强调存储要点，总结存储特点2. 利用算法动画演示，分析单链表的头插法、尾插法建表运算执行过程，写出算法并分析3. 利用算法动画演示，分析单链表的插入运算执行过程，写出插入算法并分析4. 利用算法动画演示，分析单链表的删除运算执行过程，写出删除算法并分析5. 利用算法动画演示，分析单链表的查找运算执行过程，写出查找算法及分析作业布置习题2一710 二3,7 三3,4,5教学后记教 案（理论课） 第 6 次课 2 学时章 节第二章 线性表2.4 顺序表与链表的比较2.5 案例实现讲授主要内 容讲授单循环链表、双链表。分析顺序表与链表的差异。分析本章案例。重 点难 点重点：单循环链表与双链表的逻辑结构与基本操作。顺序表与链表的比较难点：单循环链表的基本操作双链表的基本操作要求掌握知识点和分析方法l 掌握循环链表、双链表的存储结构l 熟练掌握循环链表的基本操作l 掌握双链表的基本操作l 掌握顺序表与链表的比较教学设计1. 通过在单链表中查找前驱结点的问题，引入单循环链表。分析单循环链表的逻辑结构及其与单链表的区别。解决“求循环链表中任意一个结点的前驱结点”的问题2. 分析双链表的逻辑结构及其特点，通过图示讲解在双链表上实现的基本查找3. 分析解析顺序表与链表在时间、空间、程序设计语言三方面的区别与联系。4. 通过顺序表、链表两种方式实现本章案例：通讯录管理系统。作业布置习题2一1114 二8,9,10 三6,7教学后记教 案（实验课） 第 7 次课 2 学时章 节第二章 线性表线性表的链式存储结构重 点难 点重点：链表的基本运算及其性能分析难点：链表的基本运算及其性能分析要求掌握知识点和分析方法l 掌握链表的存储结构及特点l 熟练掌握链表的基本运算：插入、删除及查找运算及其性能分析l 掌握单循环链表、双链表的基本操作教学内容实现在顺序表上的基本运算。要求：1. 实现链表的建立，选用头插法或尾插法实现2. 实现链表的插入3. 实现链表的删除4. 实现链表的查找：按值查找和按位置查找5. 实现单链表中查找任意顶点前驱的操作6. 实现双链表中的插入运算：在值为x的结点前插入值为2x的结点7. 实现单链表的逆置作业布置完成本次课程实验报告教学后记教 案（理论课） 第 8 次课 2 学时章 节第三章 栈和队列3.1 栈讲授主要内 容分析栈的逻辑结构，讲述顺序栈与链栈的存储特点及分别在顺序栈和链栈上实现的运算。介绍“顺序栈和链栈的比较”，以所学的知识实现“栈的应用”。重 点难 点重点：6. 栈的类型定义。7. 栈的顺序存储和链接存储的表示。8. 在栈的顺序存储和链接存储上进行各种栈操作的算法。难点：1. 栈的顺序存储和链接存储的表示。2. 在栈的顺序存储和链接存储上进行各种栈操作的算法。要求掌握知识点和分析方法l 掌握栈的定义及其逻辑结构l 理解栈的抽象数据类型l 掌握顺序栈和链栈的实现方法l 了解双栈共享空间教学设计1. 以汉诺塔游戏引入栈，分析其逻辑结构及其“后进先出”的特性2. 给出栈的抽象数据类型3. 分析顺序栈的工作原理，介绍“上溢”和“下溢”4. 利用算法动画演示，分析顺序栈的进栈、出栈过程，给出相应算法并分析5. 利用例题，分析链栈的进栈、出栈过程，给出相应算法并分析6. 介绍顺序栈和链栈的比较：从时间性能和空间性能两个角度7. 简单介绍双栈的原理8. 介绍栈的应用：递归作业布置习题3一1,2,710 二2,4,5,6 三1,2,3,4 四 五. 14教学后记教 案（实验课） 第 9 次课 2 学时章 节第三章 栈和队列 3.1 栈重 点难 点重点：1. 栈的类型定义。2. 栈的顺序存储和链接存储的表示。3. 在栈的顺序存储和链接存储上进行各种栈操作的算法。难点：1. 栈的顺序存储和链接存储的表示。2. 在栈的顺序存储和链接存储上进行各种栈操作的算法。要求掌握知识点和分析方法l 掌握栈的定义及其逻辑结构l 理解栈的抽象数据类型l 掌握顺序栈和链栈的实现方法l 了解双栈共享空间教学内容一、 讲授：1. 介绍栈的应用：表达式求值2. 利用算法动画演示，分析括号匹配算法 二、上机完成案例。要求：1. 实现算数表达式的求值2. 实现判定表达式是否为“回文”3. 实现本章案例：汉诺塔作业布置完成本次课程实验报告教学后记教 案（理论课） 第 10 次课 2 学时章 节第三章 栈和队列3.2 队列 讲授主要内 容讲解队列并分析其逻辑结构。讲授队列上实现的基本运算。重 点难 点重点：1、队列的类型定义。2、队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。难点：1、队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。要求掌握知识点和分析方法l 理解顺序队列、循环队列、链队列的类型定义及其逻辑结构l 掌握顺序队列、循环队列、链队列的基本运算及其性能分析l 了解双端队列教学设计9. 给出队列的存储结构示意图，强调存储要点，总结存储特点10. 利用算法动画演示，分析顺序队列的入队、出队过程 11. 由例题引出顺序队列的“假溢出”现象12. 分析“假溢出”的解决方案，引入循环队列的教学。13. 讲授循环队列的基本操作，注意分析队空和队满的判定条件14. 讲授链队列的基本操作15. 介绍双端队列16. 分析循环队列与链队列的对比作业布置习题3一3,1116 二1,3,7 三58 五.5,6,7教学后记教 案（实验课） 第 11 次课 2 学时章 节第三章 栈和队列3.3队列重 点难 点重点：1、队列的类型定义。2、队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。难点：1、队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。要求掌握知识点和分析方法l 掌握链表的存储结构及特点l 熟练掌握链表的基本运算：插入、删除及查找运算及其性能分析l 掌握单循环链表、双链表的基本操作教学内容一、 讲授：1. 介绍队列的应用：舞伴问题2. 利用算法动画演示，杨辉三角问题 二、上机完成案例。要求：1. 实现本章案例：键盘缓冲区2. 实现本章案例：杨辉三角问题作业布置完成本次课程实验报告教学后记教 案（理论课） 第 12 次课 2 学时章 节第四章 串讲授主要内 容串的定义及基本操作；串的存储结构；串的模式匹配算法。重 点难 点重点：1、“串”类型定义中各基本操作。2、 串的模式匹配算法：BF算法。难点： 串的模式匹配算法。要求掌握知识点和分析方法l 掌握串的定义及其基本概念l 理解串的抽象数据类型l 掌握串的基本操作l 理解串的存储结构l 掌握BF算法l 了解KMP算法教学设计9. 由案例给出串的定义，总结串的特性。注意区分空串与空白串的不同。10. 介绍串的抽象数据类型11. 举例分析串的基本操作12. 分析串与普通线性表的不同，引出串的三种存储结构13. 利用算法动画演示，分析模式匹配的基本过程，给出相应算法并分析14. 分析BF算法，找出其效率低下的原因，引出KMP算法。对KMP算法的基本思想做简单介绍，具体分析及算法实现可以根据情况由学生课后完成。作业布置习题4教学后记教 案（理论课） 第 13 次课 2 学时章 节第五章 数组和广义表5.1 多维数组5.2 矩阵的压缩存储讲授主要内 容数组的定义；数组的存储结构与寻址；特殊矩阵的压缩存储；稀疏矩阵的压缩存储重 点难 点重点：掌握二维数组的存储方式和矩阵的压缩方式难点：特殊矩阵的压缩存储；稀疏矩阵的压缩存储要求掌握知识点和分析方法l 掌握数组的定义l 熟练掌握二维数组的存储方法及寻址l 掌握矩阵压缩存储的思想l 掌握特殊矩阵的压缩存储方法及寻址l 掌握稀疏矩阵的压缩存储方法及寻址：三元组表教学设计17. 给出数组的定义18. 提出问题：多维数组如何存储在内存中呢？引入二维数组的存储方法：行优先和列优先存储方法19. 给出练习，加强学生对二维数组存储方法及寻址方式的理解20. 给出一个对称矩阵的例子，分析一下采用普通存储方式的缺陷，提出矩阵压缩存储。21. 介绍对称矩阵、三角矩阵、对角矩阵的存储方式22. 给出一个稀疏矩阵的例子，引出稀疏矩阵的压缩存储。23. 介绍三元组表示法，并以三元组为存储结构分析稀疏矩阵转置算法。作业布置习题5一13 二15 三1,2,3 四.1,2 五.1教学后记教 案（理论课） 第 14 次课 2 学时章 节第五章 数组和广义表5.2 矩阵的压缩存储5.3 广义表5.4案例实现讲授主要内 容稀疏矩阵的十字链表表示法；广义表重 点难 点重点：掌握广义表的基本概念。难点：十字链表、广义表的存储结构和操作。要求掌握知识点和分析方法l 掌握稀疏矩阵的压缩存储方法及寻址：十字链表l 掌握广义表的定义及基本性质和基本运算l 理解广义表的存储结构教学设计8. 由三元组顺序表的缺点引出十字链表，画出存储示意图9. 分析十字链表的建立算法10. 给出广义表的定义，分析广义表的性质，指出与线性表、数组的区别联系11. 讲授广义表的基本运算，通过课堂练习加深学生的理解12. 介绍广义表的存储结构13. 根据本章的理论知识，引导学生学习本章的案例实现作业布置习题5一46 二6 三4,5 四3,4 五.2,3教学后记教 案（理论课） 第 27 次课 2 学时章 节第八章 查找8.1 查找的基本概念8.2 线性表的查找讲授主要内 容查找的基本概念；顺序查找；二分查找；分块查找重 点难 点重点：1查找的基本概念2顺序查找3二分查找4. 分块查找难点：1顺序查找2二分查找要求掌握知识点和分析方法l 理解查找的基本概念：查找、关键字、ASL等l 熟练掌握顺序查找l 熟练掌握二分查找l 掌握折半查找判定树 l 理解分块查找教学设计15. 结合实例分析查找的操作，给出查找的相关基本概念：查找、关键字、静态查找、动态查找、ASL。16. 利用算法动态演示，讲解顺序查找：分析“监视哨”的设置及作用；给出算法；分析算法的优缺点及特性17. 从“顺序查找”引入“二分查找”。利用算法动态演示，讲解二分查找：分析二分查找的基本思想，举例分析查找成功和查找不成功的案例；给出算法；分析算法的优缺点及特性；强调二分查找的前提（有序的顺序表）18. 给出折半查找判定树的定义及构造方法，分析查找成功和查找不成功时的查找性能19. 分析分块查找。强调“块间有序，块内无序”，分析两步的查找性能20. 比较三种线性表的查找性能作业布置习题8一19,11,12 二2,3,5,6,7,9,10 三. (教师指定) 四.(教师指定)教学后记教 案（理论课） 第 28 次课 2 学时章 节第八章 查找8.3.1二叉排序树讲授主要内 容二叉排序树的定义；二叉排序树的查找； 二叉排序树的插入和生成；二叉排序树的删除重 点难 点重点：1二叉排序树的定义2二叉排序树的查找3二叉排序树的插入和生成4二叉排序树的删除难点：1二叉排序树的定义2二叉排序树的查找3二叉排序树的插入和生成4二叉排序树的删除要求掌握知识点和分析方法l 掌握二叉排序树的定义、查找l 理解二叉排序树的插入和生成l 了解二叉排序树的删除教学设计1. 通过二叉树的中序遍历引出二叉排序树2. 讲解二叉排序树的定义及查找方法，举例分析并给出算法3. 利用算法动画演示，说明二叉排序树的插入和生成方法，给出算法4. 利用算法动画演示，说明二叉排序树的删除方法，给出算法5. 分析、演示：二叉排序树的综合应用案例6. 当堂练习作业布置习题8一10,13,14,15 二2 三. (教师指定) 四.(教师指定)教学后记教 案（理论课） 第 29 次课 2 学时章 节第八章 查找8.3.2平衡二叉树8.3.3 B-树讲授主要内 容平衡二叉树；B-树及其查找；B-树查找分析；B-树的插入和删除重 点难 点重点：1. 平衡二叉树2. B-树及其查找3. B-树查找分析4. B-树的插入难点：1. 平衡二叉树2. B-树及其查找3. B-树查找分析4. B-树的插入要求掌握知识点和分析方法l 理解平衡二叉树的定义和平衡因子BFl 了解平衡二叉树的调整思想及方法l 理解B-树的插入操作l 了解B-树的删除操作教学设计1. 由二叉排序树的查找性能引出平衡二叉树2. 给出平衡二叉树和平衡因子的概念，理解平衡的含义3. 给出构造平衡二叉树的基本思想，介绍平衡调整的四种情况4. 介绍B-树的定义，以4阶B-树为例分析其查找过程5. 简单介绍B-树的插入、删除情况6. 对树表的查找做综合练习作业布置习题8三. (教师指定) 四.(教师指定)教学后记教 案（理论课） 第 30 次课 2 学时章 节第八章 查找8.4 哈希表讲授主要内 容哈希表的定义；哈希函数的构造方法；处理冲突的方法；哈希表的查找及分析重 点难 点重点：1哈希表的定义2哈希函数的构造方法3处理冲突的方法4. 哈希表的查找及分析难点：1哈希函数的构造方法2处理冲突的方法3. 哈希表的查找及分析要求掌握知识点和分析方法l 熟练掌握哈希表的定义l 掌握常用哈希函数的构造方法l 掌握处理冲突的方法l 理解哈希表的查找及其性能分析教学设计24. 举例讲解哈希表的定义及其主要思想25. 提出哈希表需要解决的主要问题，结合实例讲解常用的几种散列函数26. 利用算法动画演示线性探测和拉链法的基本思想，讲授哈希表处理冲突的几种方法：开发定址法、拉链法和建立公共溢出区。对开放定址法又细分成线性探测等几种方法，并以例题做详细分析27. 分析哈希表的查找，提出装填因子的概念。并与线性表查找、树表查找做比较。28. 课堂练习，加深理解作业布置习题8一1621 二.1,8,11 三. (教师指定) 四.(教师指定)教学后记教 案（实验课） 第 31次课 2 学时章 节第八章 查找重 点难 点重点：1. 线性表的查找。2. 树表的查找3. 哈希查找难点：1. 线性表的查找。2. 树表的查找3. 哈希查找要求掌握知识点和分析方法l 掌握各种查找的基本原理l 掌握本章要求的查找算法教学内容上机完成案例。要求：完成本章查找综合案例。作业布置完成本次课程实验报告教学后记教 案（理论课） 第 32 次课 2 学时章 节第九章 排序9.1 排序的基本概念9.2 插入排序9.3 交换排序讲授主要内 容排序的基本概念；插入排序；交换排序重 点难 点重点：1排序的基本概念2插入排序3交换排序难点：1插入排序2交换排序要求掌握知识点和分析方法l 理解排序的基本概念：排序、稳定性、内排序与外排序、就地排序l 熟练掌握直接插入排序l 熟练掌握二分插入排序l 理解希尔排序 l 熟练掌握冒泡排序、快排教学设计21. 给出排序的相关基本概念：排序、稳定性、内排序与外排序、就地排序。22. 利用算法动态演示，讲解直接插入排序，给出算法及其性能分析23. 利用算法动态演示，讲解二分插入排序，给出算法并分析算法的优缺点及特性24. 利用算法动态演示，讲解希尔排序，给出算法及其性能分析25. 利用算法动态演示，讲解冒泡排序，给出算法及其性能分析。要求学生分析标志位的使用，仿写从后往前的冒泡算法26. 利用算法动态演示，讲解快速排序，给出算法及其性能分析。作业布置习题9教学后记教 案（理论课） 第 33 次课 2 学时章 节第九章 排序9.4 选择排序9.5 归并排序9.6 基数排序9.7 各种排序方法的比较和选择讲授主要内 容选择排序；归并排序；基数排序；各种排序方法的比较和选择重 点难 点重点：1选择排序2归并排序3基数排序4各种排序方法的比较和选择难点：1选择排序2归并排序3基数排序4各种排序方法的比较和选择要求掌握知识点和分析方法l 熟练掌握直接选择排序l 掌握堆排序l 理解归并排序l 理解基数排序l 掌握各种排序方法的比较和选择教学设计7. 利用算法动态演示，讲解直接选择排序，给出算法及其性能分析8. 利用算法动态演示，讲解堆排序，给出算法及其性能分析。重点分析堆排序的步骤9. 利用算法动态演示，讲解归并排序，给出算法及其性能分析10. 利用算法动态演示，讲解基数排序，给出算法及其性能分析11. 分析各种排序方法的比较和选择，并通过课堂练习加以深刻理解作业布置习题9教学后记教 案（实验课） 第 34次课 2 学时章 节第九章 排序重 点难 点重点：各种排序算法的基本思想难点：各种排序算法的基本思想要求掌握知识点和分析方法l 掌握各种排序的基本原理l 掌握本章要求的排序算法教学内容上机完成案例。要求：完成本章排序综合案例。作业布置完成本次课程实验报告教学后记教 案（理论课） 第 15 次课 2 学时章 节第六章 树6.1 树6.2 二叉树讲授主要内 容树的定义和基本术语；树的抽象数据类型定义；树的存储结构；二叉树的定义；二叉树的基本性质；二叉树的抽象数据类型定义重 点难 点重点：1树的定义和基本术语2树的存储结构3二叉树的定义4二叉树的性质难点：1 二叉树的定义2 二叉树的性质要求掌握知识点和分析方法l 掌握树的定义和基本术语l 理解树的抽象数据类型l 掌握树的四种存储结构l 掌握二叉树的定义和基本性质l 理解二叉树的抽象数据类型教学设计27. 分析“团委的人事管理系统”组织图，给出树的定义，深刻理解树的逻辑结构。28. 结合实例分析讲授树的基本术语29. 给出树的抽象数据类型30. 提出问题：如何实现树的存储，引出树的各种存储结构。分别从双亲、孩子多个角度引出解决方案，并分析各种存储结构的优缺点31. 给出二叉树的定义，分析根据二叉树的定义得出的二叉树的基本形态32. 给出两种特殊形态的二叉树满二叉树和完全二叉树的定义，说明其特点33. 推导、证明二叉树的基本性质34. 介绍二叉树的抽象数据类型作业布置习题6一1,2,710 二2,4,5,6 三1,2,3,4 四 五. 14教学后记教 案（理论课） 第 16 次课 2 学时章 节第六章 树6.2 二叉树讲授主要内 容二叉树的存储结构；二叉树的遍历；二叉树遍历的应用重 点难 点重点：二叉树的遍历难点：二叉树的遍历；二叉树遍历的应用要求掌握知识点和分析方法l 熟练掌握二叉树的遍历操作l 掌握二叉树遍历的应用教学设计7. 分析二叉树的三种存储结构：顺序存储、二叉链表、三叉链表8. 由二叉树的组成得到三种遍历次序：前序遍历、中序遍历、后序遍历 通过算法演示分析各种遍历的过程，给出递归算法及其分析9. 由树的层次特征得到层次遍历10. 给出二叉树的建立算法11. 以案例形式给出二叉树遍历的应用实例（教材内容可选讲）作业布置习题6一1,2,710 二2,4,5,6 三1,2,3,4 四 五.教学后记教 案（实验课） 第 17 次课 2 学时章 节第六章 树 6.2 二叉树重 点难 点重点：二叉树的遍历难点：二叉树的遍历；二叉树遍历的应用要求掌握知识点和分析方法l 熟练掌握二叉树的遍历操作l 掌握二叉树遍历的应用教学内容上机完成案例。要求：1. 设计一个程序，利用递归算法完成二叉树的建立、前序遍历、中序遍历、后序遍历和层次遍历2. 仿照案例6-3,6-4,6-5，编写程序实现习题6 五大题中的3个小题作业布置完成本次课程实验报告教学后记教 案（理论课） 第 18 次课 2 学时章 节第六章 树 6.3 树、森林与二叉树6.4 线索二叉树 6.6 案例实现团委人事管理系统讲授主要内 容树与二叉树的转换；森林与二叉树的转换；树与森林的遍历线索二叉树的定义重 点难 点重点：1树、森林与二叉树之间的转换2树与森林的遍历3. 线索二叉树的定义难点：1 树、森林与二叉树之间的转换2 线索二叉树的定义要求掌握知识点和分析方法l 掌握树、森林与二叉树之间的转换l 熟练掌握树与森林的遍历l 理解线索二叉树的定义教学设计29. 从应用的角度分析树、森林和二叉树转换的意义30. 分析树、森林和二叉树转换中的几个特点：树的孩子兄弟表示法与二叉树的二叉链表表示法的相似之处，引入转换方法。利用算法动态演示，形象展示转换方法。31. 从树的组成得到树的遍历方法：前序和后序，层次遍历32. 分析森林与树的关系，得到森林的遍历方法33. 由“保存二叉树的遍历序列的方法”，分析二叉链表的构造，引入线索链表34. 给出线索链表的存储思想，说明结点结构，根据实例画出一棵二叉树的线索链表35. 根据教学情况，选讲线索链表的操作作业布置习题6一8,9 三3,4,9,10 四.5,6,7,8教学后记教 案（理论课） 第 19 次课 2 学时章 节第六章 树6.5 哈夫曼树及其应用讲授主要内 容哈夫曼树的基本概念；哈夫曼树的构造方法；哈夫曼编码重 点难 点重点：1哈夫曼树的基本概念2哈夫曼树的构造方法3哈夫曼编码难点：1哈夫曼树的构造方法2哈夫曼编码要求掌握知识点和分析方法l 理解哈夫曼树的定义及基本概念l 熟练掌握哈夫曼树的构造方法l 理解哈夫曼树的构造算法l 理解哈夫曼编码l 了解哈夫曼编码和译码算法教学设计1. 以几棵不同的二叉树为例，讲授哈夫曼树的定义及基本概念，重点分析其权值、WPL2. 利用算法动态演示，分析、展示哈夫曼树的构造方法3. 给出哈夫曼树的构造算法4. 介绍等长和不等长编码，引出前缀编码5. 利用哈夫曼树构造不等长编码的方法，通过案例讲解编码、译码的过程6. 根据教学情况，选讲编码和译码算法作业布置习题6一10,11,12 二14 三8 四11,12教学后记教 案（实验课） 第 20 次课 2 学时章 节第六章 树6.5 哈夫曼树及其应重 点难 点重点：1哈夫曼树的基本概念2哈夫曼树的构造方法3哈夫曼编码难点：1哈夫曼树的构造方法2哈夫曼编码要求掌握知识点和分析方法l 理解哈夫曼树的定义及基本概念l 熟练掌握哈夫曼树的构造方法l 理解哈夫曼树的构造算法l 理解哈夫曼编码l 了解哈夫曼编码和译码算法教学内容一、分析本章案例，由学生课后完成 二、上机完成案例。要求：利用所学的哈夫曼树知识，构建一棵哈夫曼树，并实现编码功能。作业布置完成本次课程实验报告教学后记教 案（理论课） 第 21 次课 2 学时章 节第七章 图7.1 图的逻辑结构7.2 图的存储结构讲授主要内 容图的定义和基本术语；图的抽象数据类型定义；图的存储结构：邻接矩阵重 点难 点重点：1图的定义和基本术语2邻接矩阵3邻接表难点：1图的定义和基本术语2邻接矩阵要求掌握知识点和分析方法l 熟练掌握图的定义和基本术语l 理解图的抽象数据类型l 掌握图的邻接矩阵 教学设计7. 由案例引入图的教学。8. 给出图的定义，结合实例分析讲授图的基本术语9. 给出图的抽象数据类型10. 由存储图要解决的关键问题引出图的各种存储结构11. 给出图的邻接矩阵存储结构，分析有向图、无向图、有向网、无向网的邻接矩阵表示方法。分析图的邻接矩阵存储结构的特点，采用算法动态演示，以有向图为例给出邻接矩阵建立算法作业布置习题7一1,2,3,4,7 二1,2,3,5,6,7,9,10 三. 2,4教学后记教 案（理论课）