数据结构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 四教学后记教 案（理论课） 第 32 次课 2 学时章 节第九章 排序9.1 排序的基本概念9.2 插入排序9.3 交换排序讲授主要内 容排序的基本概念；插入排序；交换排序重 点难 点重点：1排序的基本概念2插入排序3交换排序难点：1插入排序2交换排序要求掌握知识点和分析方法l 理解排序的基本概念：排序、稳定性、内排序与外排序、就地排序l 熟练掌握直接插入排序l 熟练掌握二分插入排序l 理解希尔排序 l 熟练掌握冒泡排序、快排教学设计1. 给出排序的相关基本概念：排序、稳定性、内排序与外排序、就地排序。2. 利用算法动态演示，讲解直接插入排序，给出算法及其性能分析3. 利用算法动态演示，讲解二分插入排序，给出算法并分析算法的优缺点及特性4. 利用算法动态演示，讲解希尔排序，给出算法及其性能分析5. 利用算法动态演示，讲解冒泡排序，给出算法及其性能分析。要求学生分析标志位的使用，仿写从后往前的冒泡算法6. 利用算法动态演示，讲解快速排序，给出算法及其性能分析。作业布置习题9教学后记教 案（理论课） 第 33 次课 2 学时章 节第九章 排序9.4 选择排序9.5 归并排序9.6 基数排序9.7 各种排序方法的比较和选择讲授主要内 容选择排序；归并排序；基数排序；各种排序方法的比较和选择重 点难 点重点：1选择排序2归并排序3基数排序4各种排序方法的比较和选择难点：1选择排序2归并排序3基数排序4各种排序方法的比较和选择要求掌握知识点和分析方法l 熟练掌握直接选择排序l 掌握堆排序l 理解归并排序l 理解基数排序l 掌握各种排序方法的比较和选择教学设计1. 利用算法动态演示，讲解直接选择排序，给出算法及其性能分析2. 利用算法动态演示，讲解堆排序，给出算法及其性能分析。重点分析堆排序的步骤3. 利用算法动态演示，讲解归并排序，给出算法及其性能分析4. 利用算法动态演示，讲解基数排序，给出算法及其性能分析5. 分析各种排序方法的比较和选择，并通过课堂练习加以深刻理解作业布置习题9教学后记教 案（实验课） 第 34次课 2 学时章 节第九章 排序重 点难 点重点：各种排序算法的基本思想难点：各种排序算法的基本思想要求掌握知识点和分析方法l 掌握各种排序的基本原理l 掌握本章要求的排序算法教学内容上机完成案例。要求：完成本章排序综合案例。作业布置完成本次课程实验报告教学后记教 案（理论课） 第 27 次课 2 学时章 节第八章 查找8.1 查找的基本概念8.2 线性表的查找讲授主要内 容查找的基本概念；顺序查找；二分查找；分块查找重 点难 点重点：1查找的基本概念2顺序查找3二分查找4. 分块查找难点：1顺序查找2二分查找要求掌握知识点和分析方法l 理解查找的基本概念：查找、关键字、ASL等l 熟练掌握顺序查找l 熟练掌握二分查找l 掌握折半查找判定树 l 理解分块查找教学设计7. 结合实例分析查找的操作，给出查找的相关基本概念：查找、关键字、静态查找、动态查找、ASL。8. 利用算法动态演示，讲解顺序查找：分析“监视哨”的设置及作用；给出算法；分析算法的优缺点及特性9. 从“顺序查找”引入“二分查找”。利用算法动态演示，讲解二分查找：分析二分查找的基本思想，举例分析查找成功和查找不成功的案例；给出算法；分析算法的优缺点及特性；强调二分查找的前提（有序的顺序表）10. 给出折半查找判定树的定义及构造方法，分析查找成功和查找不成功时的查找性能11. 分析分块查找。强调“块间有序，块内无序”，分析两步的查找性能12. 比较三种线性表的查找性能作业布置习题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 了解二叉排序树的删除教学设计6. 通过二叉树的中序遍历引出二叉排序树7. 讲解二叉排序树的定义及查找方法，举例分析并给出算法8. 利用算法动画演示，说明二叉排序树的插入和生成方法，给出算法9. 利用算法动画演示，说明二叉排序树的删除方法，给出算法10. 分析、演示：二叉排序树的综合应用案例11. 当堂练习作业布置习题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 理解哈希表的查找及其性能分析教学设计1. 举例讲解哈希表的定义及其主要思想2. 提出哈希表需要解决的主要问题，结合实例讲解常用的几种散列函数3. 利用算法动画演示线性探测和拉链法的基本思想，讲授哈希表处理冲突的几种方法：开发定址法、拉链法和建立公共溢出区。对开放定址法又细分成线性探测等几种方法，并以例题做详细分析4. 分析哈希表的查找，提出装填因子的概念。并与线性表查找、树表查找做比较。5. 课堂练习，加深理解作业布置习题8一1621 二.1,8,11 三. (教师指定) 四.(教师指定)教学后记教 案（实验课） 第 31次课 2 学时章 节第八章 查找重 点难 点重点：1. 线性表的查找。2. 树表的查找3. 哈希查找难点：1. 线性表的查找。2. 树表的查找3. 哈希查找要求掌握知识点和分析方法l 掌握各种查找的基本原理l 掌握本章要求的查找算法教学内容上机完成案例。要求：完成本章查找综合案例。作业布置完成本次课程实验报告教学后记教 案（理论课） 第 21 次课 2 学时章 节第七章 图7.1 图的逻辑结构7.2 图的存储结构讲授主要内 容图的定义和基本术语；图的抽象数据类型定义；图的存储结构：邻接矩阵重 点难 点重点：1图的定义和基本术语2邻接矩阵3邻接表难点：1图的定义和基本术语2邻接矩阵要求掌握知识点和分析方法l 熟练掌握图的定义和基本术语l 理解图的抽象数据类型l 掌握图的邻接矩阵 教学设计13. 由案例引入图的教学。14. 给出图的定义，结合实例分析讲授图的基本术语15. 给出图的抽象数据类型16. 由存储图要解决的关键问题引出图的各种存储结构17. 给出图的邻接矩阵存储结构，分析有向图、无向图、有向网、无向网的邻接矩阵表示方法。分析图的邻接矩阵存储结构的特点，采用算法动态演示，以有向图为例给出邻接矩阵建立算法作业布置习题7一1,2,3,4,7 二1,2,3,5,6,7,9,10 三. 2,4教学后记教 案（理论课） 第 22 次课 2 学时章 节第七章 图7.2 图的存储结构讲授主要内 容图的存储结构：邻接表、十字链表、邻接多重表、边集数组重 点难 点重点：1邻接表2边集数组难点：1邻接表要求掌握知识点和分析方法l 掌握图的邻接表l 理解图的十字链表、邻接多重表、边集数组教学设计12. 给出图的邻接表存储结构，分析有向图、无向图、有向网、无向网的邻接矩阵表示方法。分析图的邻接表存储结构的特点，采用算法动态演示，以有向图为例给出邻接表建立算法13. 介绍图的十字链表、邻接多重表、边集数组14. 讲授图的各种存储结构的比较15. 当堂练习作业布置习题7二10,11 四.1教学后记教 案（理论课） 第 23 次课 2 学时章 节第七章 图7.3 图的遍历7.4 图的连通性讲授主要内 容图的深度优先搜索；图的广度优先搜索；图的连通性：无向图、有向图；重 点难 点重点：5. 图的深度优先搜索6. 图的广度优先搜索7. 图的连通性：无向图、有向图8. 生成树和最小生成树：生成树的概念；普里姆（Prim）算法；克鲁斯卡尔（Kruskal）算法难点：1图的深度优先搜索2图的广度优先搜索3普里姆（Prim）算法4克鲁斯卡尔（Kruskal）算法要求掌握知识点和分析方法l 掌握图的深度优先搜索、广度优先搜索l 理解图的连通性l 理解生成树、最小生成树的概念l 掌握普里姆（Prim）算法l 掌握克鲁斯卡尔（Kruskal）算法教学设计7. 利用算法动态演示，讲解图的深度优先搜索，并分析算法8. 利用算法动态演示，讲解图的广度优先搜索，并分析算法9. 讲授图的连通性，通过举例的方式，分别分析无向图和有向图10. 分析生成树和最小生成树的概念11. 利用算法动态演示，讲解普里姆（Prim）算法12. 利用算法动态演示，讲解克鲁斯卡尔（Kruskal）算法作业布置习题7一9,10,11 二 4,8,12 三3 四.2,3教学后记教 案（理论课） 第 24 次课 2 学时章 节第七章 图 7.5 图的应用讲授主要内 容拓扑排序；关键路径重 点难 点重点：1拓扑排序2关键路径难点：1拓扑排序2关键路径要求掌握知识点和分析方法l 理解AOV网的含义及特点l 掌握拓扑排序的方法l 掌握关键路径的求解思想教学设计6. 给出AOV网的定义，通过实例说明AOV网的建模意义，分析其性质7. 给出拓扑序列定义和拓扑排序的方法8. 利用算法动态演示，分析拓扑排序的方法9. 课堂练习：给出一个AOV网，由学生完成拓扑排序10. 给出AOE网的定义，通过实例说明AOE网的性质11. 结合实例分析关键路径和关键活动的概念12. 利用算法动态演示，给出求解关键路径的方法和步骤。注意分析多条关键路径同时存在时的情况。13. 课堂练习：给出一个AOE网，由学生完成关键路径的求解和关键活动分析作业布置习题7一8,9 三3,4,9,10 四.4教学后记教 案（理论课） 第 25 次课 2 学时章 节第七章 图 7.5 图的应用 7.6 案例实现讲授主要内 容最短路径；图的综合操作重 点难 点重点：1 最短路径的思想2 迪杰斯特拉(Dijkstra)算法难点：迪杰斯特拉(Dijkstra)算法要求掌握知识点和分析方法l 理解最短路径的思想l 掌握迪杰斯特拉(Dijkstra)算法求解思想及过程教学设计1. 举例说明在网中最短路径的含义2. 利用算法动态演示，分析、展示迪杰斯特拉(Dijkstra)算法求解思想及过程3. 根据教学情况，选讲弗洛伊德（Floyd）算法4. 课堂练习：给出一网图，分析从某点出发的最短路径。5. 结合整章的教学内容，整理、分析图的综合案例作业布置习题7 四.11,12教学后记教 案（实验课） 第 26 次课 2 学时章 节第七章 图重 点难 点重点：1 图的存储结构：邻接矩阵、邻接表的实现2 图的遍历算法 难点：1. 图的存储结构：邻接矩阵、邻接表的实现2. 图的遍历算法 要求掌握知识点和分析方法l 熟练掌握图的存储结构的实现l 熟练掌握图的遍历算法教学内容上机完成案例。要求：完成本章案例。有能力的同学可以在此基础上完成拓扑排序。作业布置完成本次课程实验报告教学后记教 案（理论课） 第 15 次课 2 学时章 节第六章 树6.1 树6.2 二叉树讲授主要内 容树的定义和基本术语；树的抽象数据类型定义；树的存储结构；二叉树的定义；二叉树的基本性质；二叉树的抽象数据类型定义重 点难 点重点：1树的定义和基本术语2树的存储结构3二叉树的定义4二叉树的性质难点：1 二叉树的定义2 二叉树的性质要求掌握知识点和分析方法l 掌握树的定义和基本术语l 理解树的抽象数据类型l 掌握树的四种存储结构l 掌握二叉树的定义和基本性质l 理解二叉树的抽象数据类型教学设计6. 分析“团委的人事管理系统”组织图，给出树的定义，深刻理解树的逻辑结构。7. 结合实例分析讲授树的基本术语8. 给出树的抽象数据类型9. 提出问题：如何实现树的存储，引出树的各种存储结构。分别从双亲、孩子多个角度引出解决方案，并分析各种存储结构的优缺点10. 给出二叉树的定义，分析根据二叉树的定义得出的二叉树的基本形态11. 给出两种特殊形态的二叉树满二叉树和完全二叉树的定义，说明其特点12. 推导、证明二叉树的基本性质13. 介绍二叉树的抽象数据类型作业布置习题6一1,2,710 二2,4,5,6 三1,2,3,4 四 五. 14教学后记教 案（理论课） 第 16 次课 2 学时章 节第六章 树6.2 二叉树讲授主要内 容二叉树的存储结构；二叉树的遍历；二叉树遍历的应用重 点难 点重点：二叉树的遍历难点：二叉树的遍历；二叉树遍历的应用要求掌握知识点和分析方法l 熟练掌握二叉树的遍历操作l 掌握二叉树遍历的应用教学设计13. 分析二叉树的三种存储结构：顺序存储、二叉链表、三叉链表14. 由二叉树的组成得到三种遍历次序：前序遍历、中序遍历、后序遍历 通过算法演示分析各种遍历的过程，给出递归算法及其分析15. 由树的层次特征得到层次遍历16. 给出二叉树的建立算法17. 以案例形式给出二叉树遍历的应用实例（教材内容可选讲）作业布置习题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 理解线索二叉树的定义教学设计14. 从应用的角度分析树、森林和二叉树转换的意义15. 分析树、森林和二叉树转换中的几个特点：树的孩子兄弟表示法与二叉树的二叉链表表示法的相似之处，引入转换方法。利用算法动态演示，形象展示转换方法。16. 从树的组成得到树的遍历方法：前序和后序，层次遍历17. 分析森林与树的关系，得到森林的遍历方法18. 由“保存二叉树的遍历序列的方法”，分析二叉链表的构造，引入线索链表19. 给出线索链表的存储思想，说明结点结构，根据实例画出一棵二叉树的线索链表20. 根据教学情况，选讲线索链表的操作作业布置习题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 了解哈夫曼编码和译码算法教学设计14. 以几棵不同的二叉树为例，讲授哈夫曼树的定义及基本概念，重点分析其权值、WPL15. 利用算法动态演示，分析、展示哈夫曼树的构造方法16. 给出哈夫曼树的构造算法17. 介绍等长和不等长编码，引出前缀编码18. 利用哈夫曼树构造不等长编码的方法，通过案例讲解编码、译码的过程19. 根据教学情况，选讲编码和译码算法作业布置习题6一10,11,12 二14 三8 四11,12教学后记教 案（实验课） 第 20 次课 2 学时章 节第六章 树6.5 哈夫曼树及其应重 点难 点重点：1哈夫曼树的基本概念2哈夫曼树的构造方法3哈夫曼编码难点：1哈夫曼树的构造方法2哈夫曼编码要求掌握知识点和分析方法l 理解哈夫曼树的定义及基本概念l 熟练掌握哈夫曼树的构造方法l 理解哈夫曼树的构造算法l 理解哈夫曼编码l 了解哈夫曼编码和译码算法教学内容一、分析本章案例，由学生课后完成 二、上机完成案例。要求：利用所学的哈夫曼树知识，构建一棵哈夫曼树，并实现编码功能。作业布置完成本次课程实验报告教学后记教 案（理论课） 第 13 次课 2 学时章 节第五章 数组和广义表5.1 多维数组5.2 矩阵的压缩存储讲授主要内 容数组的定义；数组的存储结构与寻址；特殊矩阵的压缩存储；稀疏矩阵的压缩存储重 点难 点重点：掌握二维数组的存储方式和矩阵的压缩方式难点：特殊矩阵的压缩存储；稀疏矩阵的压缩存储要求掌握知识点和分析方法l 掌握数组的定义l 熟练掌握二维数组的存储方法及寻址l 掌握矩阵压缩存储的思想l 掌握特殊矩阵的压缩存储方法及寻址l 掌握稀疏矩阵的压缩存储方法及寻址：三元组表教学设计21. 给出数组的定义22. 提出问题：多维数组如何存储在内存中呢？引入二维数组的存储方法：行优先和列优先存储方法23. 给出练习，加强学生对二维数组存储方法及寻址方式的理解24. 给出一个对称矩阵的例子，分析一下采用普通存储方式的缺陷，提出矩阵压缩存储。25. 介绍对称矩阵、三角矩阵、对角矩阵的存储方式26. 给出一个稀疏矩阵的例子，引出稀疏矩阵的压缩存储。27. 介绍三元组表示法，并以三元组为存储结构分析稀疏矩阵转置算法。作业布置习题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教学后记教 案（理论课） 第 12 次课 2 学时章 节第四章 串讲授主要内 容串的定义及基本操作；串的存储结构；串的模式匹配算法。重 点难 点重点：1、“串”类型定义中各基本操作。2、 串的模式匹配算法：BF算法。难点： 串的模式匹配算法。要求掌握知识点和分析方法l 掌握串的定义及其基本概念l 理解串的抽象数据类型l 掌握串的基本操作l 理解串的存储结构l 掌握BF算法l 了解KMP算法教学设计20. 由案例给出串的定义，总结串的特性。注意区分空串与空白串的不同。21. 介绍串的抽象数据类型22. 举例分析串的基本操作23. 分析串与普通线性表的不同，引出串的三种存储结构24. 利用算法动画演示，分析模式匹配的基本过程，给出相应算法并分析25. 分析BF算法，找出其效率低下的原因，引出KMP算法。对KMP算法的基本思想做简单介绍，具体分析及算法实现可以根据情况由学生课后完成。作业布置习题4教学后记教 案（理论课） 第 8 次课 2 学时章 节第三章 栈和队列3.1 栈讲授主要内 容分析栈的逻辑结构，讲述顺序栈与链栈的存储特点及分别在顺序栈和链栈上实现的运算。介绍“顺序栈和链栈的比较”，以所学的知识实现“栈的应用”。重 点难 点重点：28. 栈的类型定义。29. 栈的顺序存储和链接存储的表示。30. 在栈的顺序存储和链接存储上进行各种栈操作的算法。难点：1. 栈的顺序存储和链接存储的表示。2. 在栈的顺序存储和链接存储上进行各种栈操作的算法。要求掌握知识点和分析方法l 掌握栈的定义及其逻辑结构l 理解栈的抽象数据类型l 掌握顺序栈和链栈的实现方法l 了解双栈共享空间教学设计26. 以汉诺塔游戏引入栈，分析其逻辑结构及其“后进先出”的特性27. 给出栈的抽象数据类型28. 分析顺序栈的工作原理，介绍“上溢”和“下溢”29. 利用算法动画演示，分析顺序栈的进栈、出栈过程，给出相应算法并分析30. 利用例题，分析链栈的进栈、出栈过程，给出相应算法并分析31. 介绍顺序栈和链栈的比较：从时间性能和空间性能两个角度32. 简单介绍双栈的原理33. 介绍栈的应用：递归作业布置习题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 了解双端队列教学设计31. 给出队列的存储结构示意图，强调存储要点，总结存储特点32. 利用算法动画演示，分析顺序队列的入队、出队过程 33. 由例题引出顺序队列的“假溢出”现象34. 分析“假溢出”的解决方案，引入循环队列的教学。35. 讲授循环队列的基本操作，注意分析队空和队满的判定条件36. 讲授链队列的基本操作37. 介绍双端队列38. 分析循环队列与链队列的对比作业布置习题3一3,1116 二1,3,7 三58 五.5,6,7教学后记教 案（实验课） 第 11 次课 2 学时章 节第三章 栈和队列3.3队列重 点难 点重点：1、队列的类型定义。2、队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。难点：1、队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。要求掌握知识点和分析方法l 掌握链表的存储结构及特点l 熟练掌握链表的基本运算：插入、删除及查找运算及其性能分析l 掌握单循环链表、双链表的基本操作教学内容一、 讲授：1. 介绍队列的应用：舞伴问题2. 利用算法动画演示，杨辉三角问题 二、上机完成案例。要求：1. 实现本章案例：键盘缓冲区2. 实现本章案例：杨辉三角问题作业布置完成本次课程实验报告教学后记教 案（理论课） 第 3 次课 2 学时章 节第二章 线性表2.1 线性表的逻辑结构2.2 线性表的顺序存储结构讲授主要内 容举例讲解线性表，分析其逻辑结构。介绍线性表的抽