温州大学课程教案

• 学院：计算机科学与学院
• 课程名称：["数据结构"]
• 学时：54
• 教材：[:数据结构教材:数据结构——C语言描述]
• 授课教师：[:czk:陈忠克]
• 授课对象：计算机本科

第一课

1. 授课时间：

2课时

2. 授课类型：

理论课

3. 授课题目：

[:数据结构概述:数据结构中的基本概念和术语]

4. 本授课单元教学目标：

熟悉数据结构中各名词、术语的含义，掌握其基本概念；理解数据类型和抽象数据类型的含义；理解算法五个要素的确切含义，注意算法与程序的区别；掌握计算语句频度和估算算法时间复杂度的方法。

5. 本授课单元教学重点和难点：

• 重点：数据结构中的基本概念、算法复杂度
• 难点：算法复杂度分析

6. 本授课单元教学过程设计：

1. （5分钟）介绍计算机处理信息的类型
2. （15分钟）实例分析数据结构可以解决的问题（电话号码查询问题、田径赛的时间安排问题）
3. （10分钟）介绍数据结构的课程安排
4. （20分钟）介绍数据、数据元素、逻辑结构、存储结构、运算、数据结构等概念
5. （5分钟）介绍抽象数据类型的概念
6. （5分钟）介绍算法的概念以及算法的基本要求
7. （20分钟）介绍算法时间复杂度和空间复杂度的表示方式和分析的方法
8. （10分钟）实例分析算法的时间复杂度

第二课

1. 授课时间：

8课时

2. 授课类型：

理论课

3. 授课题目：

线性表

4. 本授课单元教学目标：

了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构；熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现；能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合；掌握用线性表来表示一元多项式的方法及相应操作的实现。

5. 本授课单元教学重点和难点：

• 重点：顺序表和链表的实现
• 难点：链表的实现

6. 本授课单元教学过程设计：

1. （20分钟）介绍线性表的概念、特点和操作
2. （20分钟）线性表的顺序存储的原理
3. （20分钟）线性表的顺序存储结构的定义
4. （30分钟）线性表的顺序存储简单操作的实现
5. （20分钟）练习：顺序表的翻转和合并等操作
6. （20分钟）线性表的链式存储的原理
7. （20分钟）线性表的链式存储结构
8. （30分钟）线性表的链式存储简单操作的实现
9. （30分钟）练习：链表的合并和翻转等操作
10. （30分钟）循环链表的概念、特点和实现
11. （30分钟）双向链表的概念、特点和实现
12. （40分钟）线性表的具体应用：一元多项式的表示和操作
13. （20分钟）顺序表与链表的比较
14. （30分钟）综合练习（约瑟夫环等问题）

第三课

1. 授课时间：

6课时

2. 授课类型：

理论课

3. 授课题目：

栈和队列

4. 本授课单元教学目标：

掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们；熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法；熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法；理解递归算法执行过程中栈的状态变化过程。

5. 本授课单元教学重点和难点：

• 重点：栈和队列的概念、实现，栈的应用
• 难点：循环队列的实现

6. 本授课单元教学过程设计：

1. （20分钟）栈的定义、特点和基本操作
2. （15分钟）顺序栈的表示和原理
3. （30分钟）顺序栈的定义和实现
4. （15分钟）链栈的表示和原理
5. （20分钟）链栈的定义和实现
6. （30分钟）栈的应用：括号匹配
7. （20分钟）队列的定义、特点和基本操作
8. （40分钟）循环队列的表示和基本操作
9. （30分钟）链式队列的表示和基本操作
10. （20分钟）队列的应用：输入缓冲
11. （30分钟）综合练习：医院模拟

第四课

1. 授课时间：

2课时

2. 授课类型：

理论课

3. 授课题目：

串

4. 本授课单元教学目标：

熟悉串的定义及串的基本操作；熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法；了解串的堆存储结构及块链存储结构；掌握串的模式匹配算法的基本算法，了解其改进算法。

5. 本授课单元教学重点和难点：

• 重点：
• 难点：KMP算法

6. 本授课单元教学过程设计：

• 函数的声明与定义
• 由带参数宏引出内联函数
• 由很多参数的函数引出代缺省参数的函数
• 重载函数

第五课

1. 授课时间：

4课时

2. 授课类型：

理论课

3. 授课题目：

数组

4. 本授课单元教学目标：

了解数组的存储结构，并掌握数组在以行为主的存储结构中的地址计算方法；掌握对特殊矩阵进行压缩存储时的下标变换公式；了解稀疏矩阵的三类压缩存储方法的特点和适用范围，掌握以三元组顺序表表示稀疏矩阵时进行矩阵运算采用的处理方法；了解广义表的结构特点及其存储表示方法。

5. 本授课单元教学重点和难点：

• 重点：稀疏矩阵
• 难点：

6. 本授课单元教学过程设计：

• 介绍const常量定义
• 介绍bool类型
• 介绍四种强制类型转换
• 介绍C++变量可以在多种地方定义
• 对比C语言和C++语言的内存分配
• 对比C语言的字符串和C++的string类

第六课

1. 授课时间：

10课时

2. 授课类型：

理论课

3. 授课题目：

树和二叉树

4. 本授课单元教学目标：

熟练掌握二叉树的结构特性(五个性质)，了解相应的证明方法；熟悉二叉树的各种存储结构的特点及适用范围；遍历二叉树是二叉树各种操作的基础，熟练掌握各种遍历策略的递归算法，了解其非递归算法；熟悉树的各种存储结构及其特点，掌握树和森林与二叉树之间的相互转换方法；了解Huffman树的特性，掌握建立Huffman树和Huffman编码的算法。

5. 本授课单元教学重点和难点：

重点：树与二叉树的概念，二叉树的性质，二叉树的存储表示和实现，二叉树的遍历算法 难点：Huffman算法和Huffman编码

6. 本授课单元教学过程设计：

1. 用例子说明C语言中定义自定义类型的方法：用C语言结构体定义自定义类型，用函数实现操作结构体的方法
2. 将C语言的结构体和操作结构体的函数结合在一起，引出C++类的概念
3. 举例说明C++类的语法
4. 举例说明对象的定义方法
5. 练习类和对象的使用
6. 举例说明类成员的访问权限控制

第七课

1. 授课时间：

8课时

2. 授课类型：

理论课

3. 授课题目：

图

4. 本授课单元教学目标：

熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系；熟练掌握图的两种搜索路径（深度优先和广度优先）的遍历算法，注意图的遍历算法与树的遍历算法之间的类似和差异；熟练掌握求最小生成树的Prim算法。

5. 本授课单元教学重点和难点：

• 重点：图的基本概念、图的存储结构、图的遍历算法、拓扑排序算法、最小生成树算法、最短路径算法
• 难点：最短路径算法

6. 本授课单元教学过程设计：

1. 举例说明构造函数的作用
2. 介绍构造函数的定义语法
3. 举例说明构造函数可以重载
4. 举例说明调用构造函数定义对象的方法
5. 组合对象的构造
6. 举例说明对象的析构函数的作用
7. 举例说明拷贝构造函数的作用
8. 练习构造函数、拷贝构造函数、析构函数的使用

第八课

1. 授课时间：

8课时

2. 授课类型：

理论课

3. 授课题目：

查找

4. 本授课单元教学目标：

熟练掌握顺序表和有序表的查找方法及其平均查找长度的计算方法；熟练掌握二叉排序树的构造和查找方法，掌握在二叉排序树上插入结点和删除结点的算法；熟练掌握平衡二叉树(AVL树)的定义及平衡旋转技术，了解其相应的算法；熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。

5. 本授课单元教学重点和难点：

• 重点：折半查找算法、二叉排序树的概念及有关算法、平衡二叉排序树的概念、哈希表的概念和算法
• 难点：平衡二叉树有关算法

6. 本授课单元教学过程设计：

1. 举例说明静态数据成员的用途
2. 举例说明静态成员函数的用途
3. 练习使用静态成员
4. 举例说明友员函数的作用
5. 举例说明友员类的作用
6. 举例说明常成员函数的用法
7. 举例说明常对象的用法

第九课

1. 授课时间：

6课时

2. 授课类型：

理论课

3. 授课题目：

内部排序

4. 本授课单元教学目标：

了解排序的定义和各种排序方法的特点，熟悉各种方法的排序过程及其依据的原则；熟练掌握直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序和归并排序的实现算法；掌握各种排序方法的时间复杂度的分析方法，能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能；了解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。

5. 本授课单元教学重点和难点：

• 重点：直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序，各种排序方法的比较
• 难点：堆排序

6. 本授课单元教学过程设计：

1. 举实例说明继承的概念
2. 派生类的定义方法
3. 举例说明派生类的初始化方法，构造函数的定义
4. 举例说明派生类的析构函数
5. 举例说明派生类的权限控制