数据结构1-9章教案电子教案讲义.doc

教 案（理论课）
第 1 次课 2 学时
章 节
第一章 绪论
1.1 数据结构的发展
1.2 数据结构的意义
1.3 数据结构的基本概念和术语
讲授主要内 容
介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语。
重 点
难 点
重点：
数据结构及相关概念；
数据的逻辑结构、存储结构及运算之间的关系；
难点：
数据元素；逻辑关系；抽象数据类型
要求掌握知识点和分析方法
l 了解数据结构的发展
l 理解数据结构中的基本概念
l 理解抽象数据类型的概念、记法和用法
教学设计
1. 从数据在计算机中的处理过程入手，介绍课程
2. 介绍数据结构课程的意义及其在教学计划中的核心地位
3. 介绍教材整体结构
4. 提出学习方法及要求：强调课后练习及实验的重要性，介绍配套网络教学平台
5. 讲授数据结构的基本概念
6. 通过实例辅助分析数据结构的三个方面：逻辑结构、存储结构及运算，重点结束逻辑关系，强调存储结构如何表示逻辑关系。注意引申三者之间的关系
7. 在理解数据类型和抽象的基础上，给出抽象数据类型的定义。分析：为什么对数据结构仅定义基本操作
作业布置
习题1
一．1~3 二．1~6 三．1,2
教学后记

教 案（理论课）
第 2 次课 2 学时
章 节
第一章 绪论
1.4 算法及其分析

讲授主要内 容
介绍算法的定义，算法的基本特性，算法的描述方法，讲授算法复杂度的分析方法。
重 点
难 点
重点：
算法的定义及基本特性；
算法复杂度的分析方法。
难点：
算法复杂度的分析方法。
要求掌握知识点和分析方法
l 理解算法的定义及基本特性
l 理解算法的描述方法
l 理解算法与程序的关系
l 掌握算法复杂度的分析方法
教学设计
1. 以实例引入算法定义
2. 从使用的角度分析算法的特性
3. 介绍算法的描述方法：自然语言、流程图、程序设计语言等
4. 分析算法与程序的关系，指出：程序设计的核心是算法设计
5. 给出算法分析的意义，介绍事前分析法和事后统计法
6. 给出问题规模、语句频度、大O记号的概念
7. 结合例题，讲授常用的几种时间复杂度
作业布置
习题1
一．4 二．7~9 三．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
一．1~9,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 理解平衡二叉树的定义和平衡因子BF
l 了解平衡二叉树的调整思想及方法
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
一．16~21 二.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,7~10 二．2,4,5,6 三．1,2,3,4 四 五. 1~4
教学后记

教 案（理论课）
第 16 次课 2 学时
章 节
第六章 树
6.2 二叉树
讲授主要内 容
二叉树的存储结构；二叉树的遍历；二叉树遍历的应用
重 点
难 点
重点：
二叉树的遍历
难点：
二叉树的遍历；二叉树遍历的应用
要求掌握知识点和分析方法
l 熟练掌握二叉树的遍历操作
l 掌握二叉树遍历的应用

教学设计
13. 分析二叉树的三种存储结构：顺序存储、二叉链表、三叉链表
14. 由二叉树的组成得到三种遍历次序：前序遍历、中序遍历、后序遍历
通过算法演示分析各种遍历的过程，给出递归算法及其分析
15. 由树的层次特征得到层次遍历
16. 给出二叉树的建立算法
17. 以案例形式给出二叉树遍历的应用实例（教材内容可选讲）
作业布置
习题6
一．1,2,7~10 二．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. 以几棵不同的二叉树为例，讲授哈夫曼树的定义及基本概念，重点分析其权值、WPL
15. 利用算法动态演示，分析、展示哈夫曼树的构造方法
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
一．1~3 二．1~5 三．1,2,3 四.1,2 五.1
教学后记

教 案（理论课）
第 14 次课 2 学时
章 节
第五章 数组和广义表
5.2 矩阵的压缩存储
5.3 广义表
5.4案例实现
讲授主要内 容
稀疏矩阵的十字链表表示法；广义表
重 点
难 点
重点：
掌握广义表的基本概念。
难点：
十字链表、广义表的存储结构和操作。

要求掌握知识点和分析方法
l 掌握稀疏矩阵的压缩存储方法及寻址：十字链表
l 掌握广义表的定义及基本性质和基本运算
l 理解广义表的存储结构
教学设计
8. 由三元组顺序表的缺点引出十字链表，画出存储示意图
9. 分析十字链表的建立算法
10. 给出广义表的定义，分析广义表的性质，指出与线性表、数组的区别联系
11. 讲授广义表的基本运算，通过课堂练习加深学生的理解
12. 介绍广义表的存储结构
13. 根据本章的理论知识，引导学生学习本章的案例实现
作业布置
习题5
一．4~6 二．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,7~10 二．2,4,5,6 三．1,2,3,4 四 五. 1~4
教学后记

教 案（实验课）
第 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,11~16 二．1,3,7 三．5~8 五.5,6,7
教学后记

教 案（实验课）
第 11 次课 2 学时
章 节
第三章 栈和队列
3.3队列
重 点
难 点
重点：
1、队列的类型定义。
2、队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。
难点：
1、队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。

要求掌握知识点和分析方法
l 掌握链表的存储结构及特点
l 熟练掌握链表的基本运算：插入、删除及查找运算及其性能分析
l 掌握单循环链表、双链表的基本操作
教学内容
一、 讲授：
1. 介绍队列的应用：舞伴问题
2. 利用算法动画演示，杨辉三角问题
二、上机完成案例。
要求：
1. 实现本章案例：键盘缓冲区
2. 实现本章案例：杨辉三角问题
作业布置
完成本次课程实验报告
教学后记

教 案（理论课）
第 3 次课 2 学时
章 节
第二章 线性表
2.1 线性表的逻辑结构
2.2 线性表的顺序存储结构

讲授主要内 容
举例讲解线性表，分析其逻辑结构。介绍线性表的抽