温州大学课程教案
- 学院：计算机科学与学院
课程名称：数据结构
- 学时：54
教材：数据结构——C语言描述
授课教师：陈忠克
- 授课对象：计算机本科
第一课
1. 授课时间：
2课时
2. 授课类型：
理论课
3. 授课题目：
4. 本授课单元教学目标：
熟悉数据结构中各名词、术语的含义，掌握其基本概念；理解数据类型和抽象数据类型的含义；理解算法五个要素的确切含义，注意算法与程序的区别；掌握计算语句频度和估算算法时间复杂度的方法。
5. 本授课单元教学重点和难点：
- 重点：数据结构中的基本概念、算法复杂度
- 难点：算法复杂度分析
6. 本授课单元教学过程设计：
- （5分钟）介绍计算机处理信息的类型
- （15分钟）实例分析数据结构可以解决的问题（电话号码查询问题、田径赛的时间安排问题）
- （10分钟）介绍数据结构的课程安排
- （20分钟）介绍数据、数据元素、逻辑结构、存储结构、运算、数据结构等概念
- （5分钟）介绍抽象数据类型的概念
- （5分钟）介绍算法的概念以及算法的基本要求
- （20分钟）介绍算法时间复杂度和空间复杂度的表示方式和分析的方法
- （10分钟）实例分析算法的时间复杂度
第二课
1. 授课时间：
8课时
2. 授课类型：
理论课
3. 授课题目：
4. 本授课单元教学目标：
了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构；熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现；能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合；掌握用线性表来表示一元多项式的方法及相应操作的实现。
5. 本授课单元教学重点和难点：
- 重点：顺序表和链表的实现
- 难点：链表的实现
6. 本授课单元教学过程设计：
- （20分钟）介绍线性表的概念、特点和操作
- （20分钟）线性表的顺序存储的原理
- （20分钟）线性表的顺序存储结构的定义
- （30分钟）线性表的顺序存储简单操作的实现
- （20分钟）练习：顺序表的翻转和合并等操作
- （20分钟）线性表的链式存储的原理
- （20分钟）线性表的链式存储结构
- （30分钟）线性表的链式存储简单操作的实现
- （30分钟）练习：链表的合并和翻转等操作
- （30分钟）循环链表的概念、特点和实现
- （30分钟）双向链表的概念、特点和实现
- （40分钟）线性表的具体应用：一元多项式的表示和操作
- （20分钟）顺序表与链表的比较
- （30分钟）综合练习（约瑟夫环等问题）
第三课
1. 授课时间：
6课时
2. 授课类型：
理论课
3. 授课题目：
4. 本授课单元教学目标：
掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们；熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法；熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法；理解递归算法执行过程中栈的状态变化过程。
5. 本授课单元教学重点和难点：
- 重点：栈和队列的概念、实现，栈的应用
- 难点：循环队列的实现
6. 本授课单元教学过程设计：
- （20分钟）栈的定义、特点和基本操作
- （15分钟）顺序栈的表示和原理
- （30分钟）顺序栈的定义和实现
- （15分钟）链栈的表示和原理
- （20分钟）链栈的定义和实现
- （30分钟）栈的应用：括号匹配
- （20分钟）队列的定义、特点和基本操作
- （40分钟）循环队列的表示和基本操作
- （30分钟）链式队列的表示和基本操作
- （20分钟）队列的应用：输入缓冲
- （30分钟）综合练习：医院模拟
第四课
1. 授课时间：
2课时
2. 授课类型：
理论课
3. 授课题目：
4. 本授课单元教学目标：
熟悉串的定义及串的基本操作；熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法；了解串的堆存储结构及块链存储结构；掌握串的模式匹配算法的基本算法，了解其改进算法。
5. 本授课单元教学重点和难点：
- 重点：
- 难点：KMP算法
6. 本授课单元教学过程设计：
- （20分钟）串的定义
- （20分钟）串的表示和实现
- （15分钟）串的简单模式匹配算法
- （35分钟）KMP算法
第五课
1. 授课时间：
4课时
2. 授课类型：
理论课
3. 授课题目：
4. 本授课单元教学目标：
了解数组的存储结构，并掌握数组在以行为主的存储结构中的地址计算方法；掌握对特殊矩阵进行压缩存储时的下标变换公式；了解稀疏矩阵的三类压缩存储方法的特点和适用范围，掌握以三元组顺序表表示稀疏矩阵时进行矩阵运算采用的处理方法；了解广义表的结构特点及其存储表示方法。
5. 本授课单元教学重点和难点：
- 重点：稀疏矩阵
- 难点：
6. 本授课单元教学过程设计：
- （15分钟）数组的定义
- （20分钟）数组的顺序存储表示和实现
- （20分钟）稀疏矩阵的概念
- （35分钟）稀疏矩阵的三元组表示
- （45分钟）稀疏矩阵的三元组表示的操作实现
- （45分钟）广义表的基本概念
第六课
1. 授课时间：
10课时
2. 授课类型：
理论课
3. 授课题目：
4. 本授课单元教学目标：
熟练掌握二叉树的结构特性(五个性质)，了解相应的证明方法；熟悉二叉树的各种存储结构的特点及适用范围；遍历二叉树是二叉树各种操作的基础，熟练掌握各种遍历策略的递归算法，了解其非递归算法；熟悉树的各种存储结构及其特点，掌握树和森林与二叉树之间的相互转换方法；了解Huffman树的特性，掌握建立Huffman树和Huffman编码的算法。
5. 本授课单元教学重点和难点：
重点：树与二叉树的概念，二叉树的性质，二叉树的存储表示和实现，二叉树的遍历算法 难点：Huffman算法和Huffman编码
6. 本授课单元教学过程设计：
- （30分钟）树的基本概念
- （20分钟）二叉树的概念
- （40分钟）二叉树的性质
- （30分钟）二叉树的存储表示
- （30分钟）二叉树的递归创建算法
- （30分钟）二叉树的前序、中序、后序遍历原理
- （30分钟）二叉树的遍历算法的递归实现
- （30分钟）二叉树的遍历算法的非递归实现
- （30分钟）线索二叉树的作用和原理
- （30分钟）练习：二叉树简单算法的实现（统计叶子个数、计算结点的总和等）
- （30分钟）树和森林的存储表示和实现
- （30分钟）树和森林与二叉树之间的相互转换
- （30分钟）Huffman算法的原理和用途
- （30分钟）Huffman算法的实现
- （30分钟）Huffman编码的原理和实现
第七课
1. 授课时间：
8课时
2. 授课类型：
理论课
3. 授课题目：
4. 本授课单元教学目标：
熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系；熟练掌握图的两种搜索路径（深度优先和广度优先）的遍历算法，注意图的遍历算法与树的遍历算法之间的类似和差异；熟练掌握求最小生成树的Prim算法。
5. 本授课单元教学重点和难点：
- 重点：图的基本概念、图的存储结构、图的遍历算法、拓扑排序算法、最小生成树算法、最短路径算法
- 难点：最短路径算法
6. 本授课单元教学过程设计：
- （30分钟）图的定义和基本概念
- （20分钟）图的邻接矩阵存储结构
- （30分钟）图的邻接表和逆邻接表存储结构
- （30分钟）图的创建算法
- （20分钟）图的深度优先遍历算法的原理
- （20分钟）图的深度优先遍历算法的实现
- （20分钟）图的广度优先遍历算法的原理
- （20分钟）图的广度优先遍历算法的实现
- （15分钟）图的最小生成树的概念
- （20分钟）最小生成树的Prim算法的原理
- （20分钟）最小生成树的Kruskal算法的原理
- （30分钟）最短路径djikstra算法的原理
- （25分钟）最短路径djikstra算法的实现
- （30分钟）拓扑排序算法的原理
- （30分钟）练习：图的简单算法实现（存储结构的转换）
第八课
1. 授课时间：
8课时
2. 授课类型：
理论课
3. 授课题目：
4. 本授课单元教学目标：
熟练掌握顺序表和有序表的查找方法及其平均查找长度的计算方法；熟练掌握二叉排序树的构造和查找方法，掌握在二叉排序树上插入结点和删除结点的算法；熟练掌握平衡二叉树(AVL树)的定义及平衡旋转技术，了解其相应的算法；熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。
5. 本授课单元教学重点和难点：
- 重点：折半查找算法、二叉排序树的概念及有关算法、平衡二叉排序树的概念、哈希表的概念和算法
- 难点：平衡二叉树有关算法
6. 本授课单元教学过程设计：
- （20分钟）查找表的基本概念
- （15分钟）顺序查找算法的原理和实现
- （20分钟）折半查找算法的原理和实现
- （25分钟）平均查找长度的概念和分析
- （20分钟）二叉排序树的定义
- （20分钟）二叉树的创建方法和实现
- （20分钟）二叉树的查找算法和实现
- （20分钟）平衡二叉树的定义，AVL树的定义
- （45分钟）AVL平衡算法的原理
- （30分钟）练习：AVL树的创建
- （15分钟）哈希表的概念
- （30分钟）哈希函数的实现
- （30分钟）哈希表处理冲突的方法
- （20分钟）哈希表的查找过程和性能分析
- （30分钟）练习：哈希表创建和查找
第九课
1. 授课时间：
6课时
2. 授课类型：
理论课
3. 授课题目：
内部排序
4. 本授课单元教学目标：
了解排序的定义和各种排序方法的特点，熟悉各种方法的排序过程及其依据的原则；熟练掌握直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序和归并排序的实现算法；掌握各种排序方法的时间复杂度的分析方法，能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能；了解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。
5. 本授课单元教学重点和难点：
- 重点：直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序，各种排序方法的比较
- 难点：堆排序
6. 本授课单元教学过程设计：
- （20分钟）排序的概念和特性
- （20分钟）直接插入排序的原理和实现
- （25分钟）冒泡排序的原理和实现
- （25分钟）简单选择排序的原理和实现
- （45分钟）快速排序的原理和实现
- （45分钟）堆排序的原理和实现
- （40分钟）归并排序的原理和实现
- （30分钟）各种排序方法的比较
- （20分钟）综合练习：各种排序方法的选择