教学要点

2020-03-03 11:57:51 来源：范文大全收藏下载本文

教学要点

第一章绪论

对本章的教学要抓住两条主线，一条主线是数据结构，包括数据结构的研究对象及相关概念；另一条主线是算法，包括算法的相关概念、描述方法以及时间复杂度的分析方法。

数据结构部分，从问题的求解过程入手，理解“数据结构+算法=程序”；注意强调数据结构和程序设计之间的关系。数据结构部分的核心概念是数据元素，注意通过具体实例引申数据元素之间的关系；数据结构部分的重要概念是数据结构，要抓住两个方面：逻辑结构和存储结构，并注意把握二者之间的关系。

算法部分，要以算法的概念和特性为基本点，并在以后的教学中注意应用算法的特性，不要孤立地讲授概念，注意概念的引申和应用；对于算法时间性能的分析，要将注意力集中在增长率上，即基本语句执行次数的数量级，强调三个要点：基本语句、执行次数、数量级，算法时间性能分析的结果是用大O记号表示的数量级。

最后强调数据结构和算法分析都是针对大数据量，即大数据量的组织、大数据量的处理效率。随着计算机运算速度的增长，对于能够处理大量数据的快速程序的需求也变得日益强烈。

教学重点：数据结构的基本概念；数据的逻辑结构、存储结构以及二者之间的关系；算法及特性；大O记号的表示。

教学难点：抽象数据类型的定义和使用；算法的时间复杂度分析。

第二章线性表

本章的教学要抓住一条明线：线性表的逻辑结构→线性表的存储结构。对于线性表的逻辑结构，要从线性表的定义出发，抓住要点深刻理解概念，引申出线性表的特性及逻辑特征，最后给出线性表抽象数据类型定义。对于线性表的存储结构，要把握两条支线：顺序存储结构和链接存储结构，对每种存储结构，从存储思想出发，根据存储示意图理解存储要点，基于存储结构设计线性表抽象数据类型。对于本章的教学主要抓住五条暗线：

1) 顺序表和单链表的比较：从存储思想、存储特点、算法实现等方面进行比较，从而深刻理解并掌握两种基本的存储结构，在实际应用中能为线性表选择或设计合适的存储结构。

2) 顺序表和静态链表的比较：从存储思想、存储特点、算法实现等方面进行比较，从而灵活运用内存中一段连续的存储空间。

3) 单链表、循环链表和双链表的比较：从存储思想、存储特点、算法实现等方面进行比较，从而理解时空权衡的观点，灵活运用链接存储结构。

4) 单链表算法的设计模式：在讲完单链表的查找算法后，总结单链表算法的设计模式，并在单链表的插入、删除等算法中应用该模式。

5) 整体讲授思路上，按照线性表抽象数据类型的定义→设计存储结构→线性表抽象数据类型的设计展开对线性表的讨论。

教学重点：顺序存储结构和链接存储结构的基本思想；基于顺序表和单链表基本操作的实现；基于顺序表和单链表基本操作的时间性能分析；顺序表和单链表之间的比较。

教学难点：线性表的抽象数据类型定义；基于单链表的算法设计，尤其是要求算法满足一定的时间性能和空间性能；双链表操作的实现。

第三章栈和队列

对于栈要抓住一条明线：栈的逻辑结构→栈的存储结构。对于栈的逻辑结构，要从栈的定义入手，在与线性表的定义和操作比较的基础上，得出栈的操作特性，最后给出栈的抽象数据类型说明。对于栈的存储结构要把握两条支线：顺序栈和链栈，栈的存储结构及实现都与线性表类似，本质上是线性表的简化。

对于栈的教学主要抓住四条暗线：

1) 顺序栈和顺序表的比较：将顺序栈与顺序表的存储方法进行比较，将顺序栈的算法实现与顺序表的算法实现进行比较。

2) 链栈和单链表的比较：将链栈和单链表的存储方法进行比较，将链栈的算法实现与单链表的算法实现进行比较。

3) 顺序栈和链栈的比较：将顺序栈与链栈的存储方法进行比较，将顺序栈和链栈的算法实现进行比较。

4) 整体讲授思路上，按照栈的抽象数据类型的定义→设计存储结构→栈的抽象数据类型的设计展开对栈的讨论。

对于队列的教学要抓住一条明线：队列的逻辑结构→队列的存储结构。对于队列的逻辑结构，要从队列的定义出发，在与线性表的定义和操作比较的基础上，得出队列的操作特性，最后给出队列的抽象数据类型说明。对于队列的存储结构要把握两条支线：循环队列和链队列，队列的存储结构以及实现都与线性表类似，本质上是线性表的简化。

队列部分的暗线与栈的暗线类似，此外，还要把握下面两条暗线： 1) 栈和队列的比较：将二者的操作特性进行比较，将二者的存储结构进行比较，将二者的基本操作及其实现进行比较，在不断比较的过程中加深对栈和队列的理解。

2) 循环队列的引入过程：不要直接引入循环队列存储方法，而要贯彻分析问题、提出问题、解决问题的方法逐渐引入循环队列，一方面训练了学生的逻辑思维能力，另一方面也体现了存储结构的灵活性。

栈和队列有较多经典应用，如汉诺塔问题、迷宫问题、八皇后问题，等等。提示学生有意识的接触这些经典问题，深刻理解站核对列在程序设计中的重要作用，在实践中培养数据结构应用和算法设计的意识和能力。

教学重点：栈和队列的操作特性；栈和队列基本操作的实现。

教学难点：两栈共享空间的实现；循环队列的组织及队空和队满的判定条件。

第四章串

对于串要抓住一条明线：串的逻辑结构→串的存储结构→串的模式匹配。对于串的逻辑结构，要从串的定义入手，得出串在逻辑结构上的特性，从逻辑上掌握串的基本操作，最后给出串的抽象数据类型定义。对于串在逻辑结构上的特性，从顺序存储和链接存储两种基本的存储机构出发，体会串的存储特点。对于串的模式匹配，根据学生的具体情况定位教学目标，注意关键部分要采用图示方式并从不同角度反复讲解。KMP算法的技巧性很强，学生如果能真正学懂这个算法，将会极大地增强学习兴趣，同时对教师的思维表达也是个挑战。

教学重点：串的模式匹配算法。

教学难点：改进的模式匹配KMP算法。

第五章数组和广义表

对于多维数组的教学要抓住一条明线：数组的逻辑结构→数组的存储结构→矩阵的压缩存储。对于数组的逻辑结构，要从数组的定义出发，把握数组的广义线性特征和基本操作的特点，再给出数组的抽象数据类型定义。对于数组的存储结构，要基于数组的逻辑结构和操作特点，得出数组的顺序存储方法。对于矩阵的压缩存储，首先明确矩阵的存储表现形式是二维数组，根据矩阵的具体特点设计压缩存储方案。

对于多维数组的教学要把握三条暗线：

1) 在设计数组的存储结构时，要回顾顺序表和单链表存储表示的优越点，基于数组的逻辑结构和操作特点，得出数组的顺序存储方法。

2) 特殊矩阵的压缩存储原则上仍然采用行优先的映射方式，注意二维数组的一般存储、对称矩阵的压缩存储、三角矩阵的压缩存储以及对角矩阵的压缩存储之间的关系。

3) 对于数组以及特殊矩阵的寻址，首先要回顾内存的绝对地址和相对地址的有关概念，再给出寻址方式。

对于广义表打得教学要抓住一条明线：广义表的逻辑结构→广义表的存储结构。对于广义表的逻辑结构，要从广义表的定义出发，理解广义表中的数据元素的推广特性，把握广义表的广义线性特征和求表头和表尾操作，再给出抽象数据类型定义。对于广义表的存储结构，从广义表中数据元素的推广特性出发，理解为什么通常用链接存储结构而且链表中具有不同的结点结构。

教学重点：数组的寻址方式；特殊矩阵、稀疏矩阵的压缩存储方法；广义表中求表头和表尾的方法。

教学难点：稀疏矩阵压缩存储的转置算法；广义表的存储结构。

第六章树和二叉树

本章的内容由树和二叉树两部分组成，并且以二叉链表存储结构为媒介，实现了树和二叉树之间的转换。

对于树的教学要抓住一条明线：树的逻辑结构→树的存储结构，一个重点：树的遍历操作。对于树的逻辑结构，要从树的定义出发，在与线性表定义比较的基础上，把握要点理解树的定义及其逻辑特征，通过具体实例理解树的基本术语，从逻辑上理解树的遍历操作，最后给出树的抽象数据类型定义。对于树的存储结构，要以如何表示树中结点之间的逻辑关系为出发点，掌握树的不同存储方法以及它们之间的关系。

对于二叉树的教学要抓住一条明线：二叉树的逻辑结构→二叉树的存储结构，一个重点：二叉树的遍历操作及其实现。对于二叉树的逻辑结构，要从二叉树的定义出发，在与树的定义比较的基础上，理解树和二叉树是两种树结构，通过二叉树的性质加深对二叉树逻辑结构的理解，从逻辑上掌握二叉树的遍历方法，最后给出二叉树的抽象数据类型定义。对于二叉树的存储结构，要从二叉树的逻辑特征和基本擦欧洲哦出发，掌握二叉树的不同存储方法以及它们之间的关系，基于二叉链表存储结构讨论二叉树遍历操作的实现。

教学重点：二叉树的性质；二叉树和树的存储表示；二叉树的遍历以及算法实现；树与二叉树的转换关系；哈夫曼树及应用。

教学难点：二叉树遍历算法的非递归实现；基于二叉树的遍历实现二叉树的其他操作；线索二叉树；树的基本操作的实现。

第七章图

对于本章的教学要抓住一条明线：图的逻辑结构→图的存储将诶够→图的应用举例。对于图的逻辑结构，要从图的定义出发，抓住要点，在与线性表的定义和树的定义比较的基础上，深刻理解图结构的逻辑特征，通过具体实例理解图的基本术语，在与树的遍历进行比较的基础上，从逻辑上掌握图的遍历操作，最后给出图的抽象数据类型定义。对于图的存储结构，以如何表示途中顶点之间的逻辑关系为出发点，掌握图的不同存储结构以及它们之间的关系，并学会在实际问题中修改存储结构。在理解图的存储结构和遍历操作的基础上，基于邻接矩阵和邻接表存储结构实现图的遍历操作。图有很多重要应用，例如最小生成树、最短路径、拓扑排序、关键路径等，这些重要应用构成了本章的难点，对这些应用的学习，首先要把握其基本思想，其次，掌握算法的执行过程和顶层伪代码描述，再次，分析算法采用的存储结构和引入的辅助数据结构，最后才能掌握具体的算法。

教学重点：图的基本术语；图的各种存储表示；图的两种遍历的思想及算法；图的各种应用。

教学难点：运用图的遍历算法解决图的其他相关问题；最小生成树算法；最短路径算法；拓扑排序算法；关键路径算法。

第九章查找

对于本章的教学要以静态查找和动态查找为主线，注意各种查找技术适用的条件以及查找性能的比较。对于静态查找，适用的查找技术是顺序查找和折半查找，这部分讲授的思路是：说明基本思想→运行实例，根据图示理解查找过程→描述算法→查找性能分析→适用情况。对于动态查找，适用的查找技术主要是二叉排序树，这部分的讲授思路是：首先复习二叉树的相关知识，分别讨论二叉排序树的插入、删除和查找操作，体会为什么二叉排序树能使插入、删除和查找操作同时获得较好的时间性能。在对二叉排序树查找性能分析的基础上，引入平衡二叉树，通过具体实例讲解平衡旋转。哈希表既适用于静态查找也适用于动态查找，哈希表是围绕两个问题展开讨论的，一个是哈希函数，另一个是处理冲突的方法。对于哈希函数要明确哈希函数的设计具有很大的灵活性，要学会根据查找集合以及记录的特点设计合适的哈希函数。对于处理冲突的方法要明确实质上是两种基本存储方法——顺序存储和链接存储的应用。最后说明在选择合适的装填因子后，哈希查找的时间性能是常数O(1)。

教学重点：折半查找的过程及性能分析；二叉排序树的构造及查找方法；平衡二叉树的调整方法；哈希表的构造和查找方法；各种查找技术的时间性能及对比。

教学难点：二叉排序树的删除操作；平衡二叉树的调整方法。

第十章内部排序

本章通过分析简单排序方法（直接擦何如排序、起泡排序、简单选择排序等）的缺点以及产生缺点的原因，引入改进的排序方法（希尔排序、快速排序、堆排序等）。

排序算法体现了较高超的算法设计技术和算法分析技术，从技能应用的角度，本章要求：深刻理解各种排序算法的设计思想，并能应用排序算法的设计思想解决和排序相关的问题，从而提高解决问题能力；对改进的算法，分析其改进的着眼点是什么，自己能否从某一个方面改进一个排序算法，从而提高算法设计能力；学习完各种排序算法后，对它们进行综合对比，从而得出自己的看法，在实际中可以根据实际情况选取合适的排序方法。

教学重点：各种排序算法的基本思想、执行过程、设计方法、算法时间复杂度的分析，以及各种排序算法之间的比较。

教学难点：快速排序、堆排序、归并排序等算法的设计；快速排序算法的时间复杂度的分析。