《数据结构》教案

1、安庆师范学院教案（课时计划）课程名称：数据结构 授课班级： 授课地点： 主讲教师：程玉胜20152016 学年第 2学期7201 、数据结构的概念及相关术语02、抽象数据类型的表示与实现、算法和算法分析03、线性表的类型定义、线性表的顺序表示和实现04、线性表的链式表示和实现（线性链表）05、循环链表、双向链表、一元多项式的表示及相加06、栈、栈应用举例（数制转换、括号匹配、行编辑）07、迷宫求解、表达式求值、栈与递归的实现08、队列09、机动10、习题课11 、串类型的定义、串的表示和实现12、串的模式匹配算法、串操作应用举例13、数组的定义、顺序表示和实现、矩阵的压缩存储14、稀疏矩阵的存

2、储结构、广义表15、树的定义和基本术语、二叉树的定义16、二叉树的性质、二叉树的存储结构17、遍历二叉树和线索二叉树18、树和森林19、赫夫曼树及其应用20、习题课21 、图的定义和术语、图的存储结构22、十字链表、邻接多重表、图的遍历23、图的连通性问题24、有向无环图及其应用25、最短路径26、静态查找表27、二叉排序树和平衡二叉树28、 B-树和B+树29、哈希表30、排序概述、插入排序31 、快速排序、选择排序32、归并排序、基数排序33、外部排序、各种排序方法的比较34、文件编号1周次1日期9.3课时安排2课题数据结构的概念及相关术语教材 的重 点、 难点 分析重点：(1)数据结构的

3、逻辑结构(2)数据结构的存储结构(3)抽象数据类型的概念教 学 目 标掌握数据、数据元素、数据对象的概念熟练掌握数据结构的概念及其逻辑结构和物理结构的分类掌握抽象数据类型的定义方法教学方法和 教学 手段讲授法多媒体教 学 过 程教学内容安排与板书设计：第一章绪论1 1 什么是数据结构非数值计算问题举例数据结构产生的背景数据结构在计算机科学中的地位和作用1 2 基本概念和术语数据数据元素数据对象数据结构教数据结构的形式定义Data-Structure = (D, S)数据的逻辑结构及分类：集合、线性、树形、图形结构学数据的物理结构：顺序存储结构与链式存储结构数据类型过抽象数据类型抽象数据类型的形

4、式定义ADT =(D, S, P)程抽象数据类型定义举例Triplet师生双边活动：提问：什么是数据类型？举例：演示实验：教具准备：课后1.2,1.19作业教材：1 严蔚敏吴伟民编著：数据结构(C 语言版)，清华大学出版社，1997 年教学 后记参考书目：1Wirth N ： Algorithms+Data Structures=Programs ， Prentice-Hall Inc.， 19762 美 S 巴斯：计算机算法：设计和分析引论，复旦大学出版社，1985编号2周次1日期9.6课时安排2课题抽象数据类型的表示与实现、算法和算法分析教材 的重 点、 难点 分析重点：(1)算法复杂度的

5、分析方法难点：(1)算法复杂度的分析方法教 学 目 标(1)理解数据抽象的意义(2)熟悉类C 语言(3)掌握抽象数据类型的表示和实现方法(4)掌握算法描述和算法分析的方法教学方法和 教学 手段教 学 过 程教学内容安与排板书设计：1 3 抽象数据类型的表示和实现数据抽象的意义类 C 语言抽象数据类型的表示和实现举例1 4 算法和算法分析算法算法的定义算法的特性：有穷性、确定性、可行性、输入、输出算法设计的要求教正确性、可读性、健壮性、效率与低存储量需求算法效率的度量学时间度量的方法分析时间复杂度过T(n) = O(f(n)时间复杂度的计算程算法的存储空间需求S(n) = O(f(n)师生双边活

6、动：提问：举例：演示实验：教具准备：课后1.4,1.20作业教学后记编号3周次2日期9.10课时安排2课题线性表的类型定义、线性表的顺序表示和实现教材 的重 点、 难点 分析重点：(1)顺序表的基本运算(2)顺序表上实现的各种算法的时间性能分析教 学 目 标(1)理解线性表的逻辑结构特征(2)熟练掌握顺序表的描述方法、特点及有关概念(3)熟练掌握顺序表的基本运算教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：第二章线性表线性结构的特点21 线性表的类型定义线性表的定义及其表示线性表的类型定义线性表操作举例：用线性表表示集合、线性表的合并教学过程2 2 线性表的顺序表示和实现线索性表

7、的顺序表示线性表的顺序存储结构的定义及其特征顺序表的基本运算顺序表的初始化顺序表的插入操作顺序表的删除操作顺序表的合并顺序表基本操作的时间复杂度计算师生双边活动：提问：举例：演示实验：教具准备：课后 作业2.12教学 后记编号4周次2日期9.13课时安排2课题线性表的链式表示和实现(线性链表)教材 的重 点、 难点 分析重点：(1)链表的基本运算(2)链表上实现的各种算法的时间性能分析教 学 目 标(1)熟练掌握链表的描述方法、特点及有关概念(2)掌握链表的基本运算(3)掌握静态链表的构造方法教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：2 3 线性表的链式表示和实现2 3 1

8、线性链表单链表的定义单链表的存储结构特征单链表的基本操作：插入删除有序链表的合并静态链表静态链表的定义静态链表的操作举例教学过程师生双边活动：提问：malloc() free()举例：演示实验：教具准备：课后2.17,2.25作业教学后记编号5周次3日期9.17课时安排2课题循环链表、双向链表、一元多项式的表示及相加教材 的重 点、 难点 分析难点：(1)循环链表教 学 目 标(1)掌握循环链表的特点(2)掌握双向链表的特点(3)从时空角度综合比较顺序表和链表的不同特点及使用场合(4)能应用线性表解决一些实际问题教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：2 3 2 循环链表循

9、环链表的定义循环链表的操作2 3 3 双向链表双向链表的定义双向链表的操作特点线性链表的类型定义2 4 一元多项式的表示及相加教一元多项式的表示一元多项式的相加学一元多项式的类型定义多项式的相加算法过程师生双边活动：提问：举例：演示实验：教具准备：课后2.32作业教学后记编号6周次3日期9.20课时安排2课题栈、栈应用举例(数制转换、括号匹配、行编辑)教材重点：(1)栈在两种存储结构上实现的基本运算。的重难点分析难点：栈满栈空的条件及它们的描述(1)掌握栈这种数据结构的特点教 学(2)熟悉栈与线性表的关系(3)重点掌握顺序栈和链式栈的五种基本运算目 标(4)掌握栈的应用方法教学方法和 教学手段

10、教学内容安排与板书设计：第三章栈与队列教3 1 栈学 过 程3 1 1抽象数据类型栈的定义栈及其与线性表的关系栈的类型定义3 1 2 栈的表示和实现顺序栈的定义链栈的定义3 2 栈的应用举例教3 2 1 数制转换3 2 2 括号匹配的检验学3 2 3 行编辑程序过程师生双边活动：提问：举例：演示实验：教具准备：课后3.15作业教学后记编号7周次4日期9.24课时安排2课题迷宫求解、表达式求值、栈与递归的实现教材 的重 点、 难点 分析教 学 目 标(1)能应用栈解决一些实际问题(2)了解递归算法执行过程中栈的变化过程教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：3 2 4 迷宫求

11、解3 2 5 表达式求值3 3 栈与递归的实现程课后师生双边活动：提问：举例：演示实验：教具准备：3.19,3.25作业教学 后记编号8周次4日期9.27课时安排2课题队列教材重点：(1)队列在两种存储结构上实现的基本运算。的重难点分析难点：(1)循环队列(注意队满队空的条件及它们的描述)(1) 掌握队列这种数据结构的特点教 学(2)熟悉队列与线性表的关系(3)掌握循环队列和链式队列的五种基本运算目 标(4)能应用队列解决一些实际问题教学方法和 教学手段教学内容安排与板书设计：3 4 队列教3 4 1抽象数据类型队列的定义学 过 程队列的定义(FIFO)队列的类型定义3 4 2 链队列队列的链

12、式表示和实现单链队列的定义单链队列的操作3 4 3 循环队列队列的顺序表示和实现队列的顺序存储结构教循环队列的基本操作学过程师生双边活动：提问：举例：演示实验：教具准备：课后3.29作业教学后记编号9周次5日期10.1课时安排2课题机动教材 的重 点、 难点 分析教 学 目 标教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：程师生双边活动： 提问： 举例： 演示实验： 教具准备：课后 作业教学 后记编号10周次5日期10.4课时安排2课题习题课教材 的重 点、 难点 分析教 学 目 标教学方法和 教学 手段讲授法教 学 过 程教学内容安排与板书设计：程师生双边活动： 提问： 举例：

13、 演示实验： 教具准备：课后 作业教学 后记编号11周次6日期10.8课时安排2课题串类型的定义、串的表示和实现教材 的重 点、 难点 分析重点：(1)串的基本运算难点：(1)串的动态存储结构教 学 目 标(1)熟悉串的有关概念，串与线性表的关系(2)掌握串的静态存储结构与动态存储结构和它们的优缺点(3)熟练掌握串的基本运算教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：第四章串41 串类型的定义串的概念串类型的定义4 2 串的表示和实现4 2 1 定长顺序存储表示串的定长顺序存储表示串联接求子串教4 2 2 堆分配存储表示串的堆分配存储表示学堆的基本操作4 2 3 串的块链存储表

14、示过程师生双边活动：提问：举例：演示实验：教具准备：课后4.17,4.22/4.24作业教学后记编号12周次6日期10.11课时安排2课题串的模式匹配算法、串操作应用举例教材 的重 点、 难点 分析教 学 目 标(1)理解串的模式匹配算法(2)了解串的应用教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：4 3 串的模式匹配算法4 3 1 求子串位置的定位函数4 3 2 模式匹配的一种改进算法KMP 算法4 4 串操作应用举例4 4 1 文本编辑教学过程师生双边活动：提问：举例：演示实验：教具准备：课后4.8作业教学后记编号13周次7日期10.15课时安排2课题数组的定义、顺序表示和

15、实现、矩阵的压缩存储教材 的重 点、 难点 分析重点：(1)多维数组的存储方式(2)矩阵的压缩存储方式难点：(1)稀疏矩阵的压缩存储表示下实现的算法教 学 目 标(1)熟悉数组的按行(列)优先顺序的存储结构中的地址计算方法(2)熟悉特殊矩阵在压缩存储时的下标变换(3)理解稀疏矩阵的三元组和十字链表两种压缩存储表示教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：第五章数组和广义表5 1 数组的定义数组的类型定义二维数组5 2 数组的顺序表示和实现二维数组的存储方式数组的顺序存储表示和实现5 3 矩阵的压缩存储教5 3 1 特殊矩阵对称矩阵学对角矩阵5 3 2 稀疏矩阵过稀疏矩阵的类型

16、定义1、三元组顺序表程师生双边活动：提问：举例：演示实验：教具准备：课后5.21作业教学后记编号14周次7日期10.18课时安排2课题稀疏矩阵的存储结构、广义表的定义和存储结构教材 的重 点、 难点 分析重点：(1)广义表的定义及其运算教 学 目 标(1)掌握稀疏矩阵的存储结构(2)熟悉广义表的有关概念和运算(3)掌握广义表的两种存储结构教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：2、行逻辑链接的顺序表3、十字链表5 4 广义表的定义广义表的类型定义广义表举例广义表的特点5 5 广义表的存储结构教学讨论：M 元多项式的表示过广义表的递归算法程师生双边活动：提问：举例：演示实验：

17、教具准备：课后5.26,5.12作业教学后记编号15周次8日期10.22课时安排2课题树的定义和基本术语、二叉树的定义教材 的重 点、 难点 分析重点：(1)树的基本术语(2)二叉树的定义教 学 目 标(1)掌握树的定义和有关术语(2)熟悉二叉树的递归定义，有关术语及基本概念教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：第六章树和二叉树61 树的定义和基本术语树的类型定义基本术语6 2 二叉树6 2 1 二叉树的定义二叉树的类型定义二叉树的基本形态教学过程师生双边活动：提问：举例：演示实验：教具准备：课后6.2作业教学后记编号16周次8日期10.25课时安排2课题二叉树的性质和和

18、存储结构教材 的重 点、 难点 分析重点：(1)二叉树的存储结构难点：(1)二叉树的性质教 学 目 标(1)熟练掌握二叉树的性质及证明方法(2)熟练掌握二叉树的顺序和链式存储结构及特点教学方法和 教学 手段讲授法教 学 过 程教学内容安排与板书设计：6 2 2 二叉树的性质性质1性质2性质3性质4性质56 2 3 二叉树的存储结构顺序存储结构链式存储结构教学过程师生双边活动：提问：举例：演示实验：教具准备：课后6.6,6.11作业教学后记编号17周次9日期10.29课时安排2课题遍历二叉树和线索二叉树教材 的重 点、 难点 分析重点：(1)二叉树的遍历算法及其相关应用难点：(1)二叉树的非递归

19、遍历算法教 学 目 标(1)熟练掌握二叉树的各种遍历(2)能灵活运用遍历算法实现二叉树的基本运算(3)掌握二叉树的线索化及相应算法教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：6 3 遍历二叉树和线索二叉树6 3 1 遍历二叉树遍历二叉树的递归算法先序遍历中序遍历后序遍历遍历二叉树的非递归算法遍历二叉树的其他算法二叉树的其他操作6 3 2 线索二叉树线索二叉树及其存储结构教二叉树的线索化学过程师生双边活动：提问：举例：演示实验：教具准备：课后6.43,6.47,6.56作业教学后记编号18周次9日期11.1课时安排2课题树和森林教材 的重 点、 难点 分析重点：(1)树的存储结构

20、难点：(1) 森林、树与二叉树之间的转换教 学 目 标(1)掌握树的存储结构及其特点(2)熟练掌握森林、树与二叉树之间的转换方法(3)掌握森林和树的遍历教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：6 4 树和森林6 4 1 树的存储结构双亲表示法孩子表示法孩子兄弟表示法6 4 2 森林与二叉树的转换森林与二叉树的对应关系二叉树与森林的对应关系6 4 3 树和森林的遍历先序遍历森林教中序遍历森林学过程师生双边活动：提问：举例：演示实验：教具准备：课后6.60,6.66作业教学后记编号19周次10日期11.5课时安排2课题赫夫曼树及其应用教材 的重 点、 难点 分析重点：(1)赫夫

21、曼编码难点：(1)赫夫曼编码教 学 目 标(1)掌握最优化二叉树的特性、熟练掌握建立最优二叉树的方法(2)熟练掌握哈夫曼编码的方法教学方法和 教学 手段讲授法教 学 过 程教学内容安排与板书设计：6 6 赫夫曼树6 6 1 最优二叉树最优二叉树的概念构造赫夫曼树最优判定算法6 6 2 赫夫曼编码求赫夫曼编码程课后师生双边活动：提问：举例：演示实验：教具准备：6.26作业教学 后记编号20周次10日期11.8课时安排2课题习题课教材 的重 点、 难点 分析教 学 目 标教学方法和 教学 手段讲授法教 学 过 程教学内容安排与板书设计：程师生双边活动： 提问： 举例： 演示实验： 教具准备：课后

22、作业教学 后记编号21周次11日期11.12课时安排2课题图的定义和术语、图的存储结构教材 的重 点、 难点 分析重点：(1)图的存储教 学 目 标(1)熟悉图的有关术语和概念(2)熟练掌握图的四种存储结构和建立算法教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：第七章图7 1 图的定义和术语图的类型定义图的分类连通图、连通分量、生成树7 2 图的存储结构7 2 1 数组表示法图的邻接矩阵网及其邻接矩阵7 2 2 邻接表教图的邻接表存储表示邻接表和逆邻接表学过程师生双边活动：提问：举例：演示实验：教具准备：课后7.14,7.15作业教学后记编号22周次11日期11.15课时安排2课

23、题十字链表、邻接多重表、图的遍历教材 的重 点、 难点 分析重点：(1)图的遍历难点：(1)图的遍历非递归算法教 学 目 标(1)熟练掌握图的四种存储结构和建立算法(2)熟练掌握图的深度优先遍历和广度优先遍历教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：7 2 3 十字链表有向图的十字链表存储表示构造有向图7 2 4 邻接多重表无向图的邻接多重表7 3 图的遍历7 3 1 深度优先搜索7 3 2 广度优先搜索教学学过程师生双边活动：提问：举例：演示实验：教具准备：课后7.22,7.28作业教学 后记编号23周次12日期11.19课时安排2课题图的连通性问题教材 的重 点、 难点

24、分析重点：(1)最小生成树的构造教 学 目 标掌握最小生成树的两种构造方法教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：7 4 图的连通性问题7 4 1 无向图的连通分量和生成树7 4 2 有向图的强连通分量7 4 3 最小生成树Prim 算法Kruskal 算法7 4 3 关节点和重连通分量教学过程师生双边活动：提问：举例：演示实验：教具准备：课后7.32作业教学后记编号24周次12日期11.22课时安排2课题有向无环图及其应用教材 的重 点、 难点 分析重点：(1)拓扑排序(2)求关键路径难点：(1)求关键路径教 学 目 标(1)掌握拓扑排序的方法(2)掌握关键路径的求法教学

25、方法和 教学 手段教 学 过 程教学内容安排与板书设计：7 5 有向无环图及其应用DAG7 5 1 拓扑排序7 5 2 关键路径AOE 网关键路径过程师生双边活动： 提问： 举例： 演示实验： 教具准备：课后7.36作业教学 后记编号25周次13日期11.26课时安排2课题最短路径教材 的重 点、 难点 分析重点：(1)求最短路径难点：(1)求每一对顶点之间的最短路径教 学 目 标熟练掌握从某个源点到其余各顶点的最短路径的求法掌握求每一对顶点之间的最短路径的求法教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：7 6 最短路径7 6 1 从某个源点到其余各顶点的最短路径Dijkstr

26、a 算法7 6 2 每一对顶点之间的最短路径教学学过程师生双边活动：提问：举例：演示实验：教具准备：课后7.42作业教学后记编号26周次13日期11.29课时安排2课题静态查找表教材 的重 点、 难点 分析重点：(1)顺序查找(2)折半查找教 学 目 标(1)熟练掌握静态查找的各种方法教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：第八章查找查找表与静态查找表和动态查找表关键字与主关键字和次关键字查找与成功和不成功8 1 静态查找表静态查找表的类型定义8 1 1 顺序表的查找顺序查找平均查找长度教8 1 2 有序表的查找折半查找学折半查找的性能分析8 1 3 静态树表的查找过8 1

27、 4 索引顺序表的查找表其索引表程分块查找师生双边活动：提问：举例：演示实验：教具准备：课后9.29作业教学后记编号27周次14日期12.3课时安排2课题二叉排序树和平衡二叉树教材重点：(1)动态查找表及查找算法的重(2)二叉排序树难点分析难点：(1)二叉排序树(1)熟练掌握二叉排序树的构造方法及查找过程教 学(2)掌握AVL 树的构造目 标教学方法和 教学手段教学内容安排与板书设计：8 2 动态查找表教动态查找表的类型定义学 过 程8 2 1二叉排序树和平衡二叉树1、二叉排序树及其查找过程二叉排序树2、二叉排序树的插入和删除二叉排序树的构造二叉排序树的删除3、二叉排序树的查找分析教4、平衡二

28、叉树平衡二叉树与不平衡的二叉树学平衡树的生成过程二叉排序树的平衡旋转过二叉排序树的类型定义5、平衡树查找的分析程师生双边活动：提问：举例：演示实验：教具准备：课后9.33作业教学后记编号28周次14日期12.6课时安排2课题B-树和B+树教材 的重 点、 难点 分析教 学 目 标(1)掌握B-树和B+树的构造和查找(2)了解键树的构造方法教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：8 2 2 B-树和B+树1、 B-树及其查找2、B-树查找分析3、B-树的插入和删除4、 B+树8 2 3 键树教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号29周次15

29、日期12.10课时安排2课题哈希表教材 的重 点、 难点 分析难点：(1)哈希表及查找算法教 学 目 标(1)熟练掌握哈希表的建表方法、冲突的处理及查找过程(2)理解哈希表与其它存储结构的表的本质区别(3)熟练掌握哈希表的平均查找长度的计算(等概率)教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：8 3 哈希表8 3 1 什么是哈希表哈希函数冲突散列教学过程8 3 2 哈希函数的构造方法1、直接定址法2、数字分析法3、平方取中法4、折叠法5、除留余数法6、随机数法8 3 3 处理冲突的方法1、开放定址法2、再哈希法3、链地址法4、建立一个公共溢出区8 3 4 哈希表的查找及其分析师

30、生双边活动：提问：举例：演示实验：教具准备：课后 作业9.46教学 后记编号30周次15日期12.13课时安排2课题排序概述、插入排序教材 的重 点、 难点 分析重点：(1)希尔排序教 学 目 标(1)深刻理解插入排序的基本思想及其特点(2)熟练掌握插入排序方法的排序过程(3)掌握插入排序算法时间复杂度的分析方法并熟记其分析结论教学方法和 教学 手段教 学 过 程教学内容安排与板书设计：第九章排序9 1 排序概述排序排序方法的稳定性内部排序与外部排序9 2 插入排序9 2 1 直接插入排序9 2 2 其他插入排序1、折半插入排序教2、2-路插入排序3、表插入排序学9 2 3 希尔排序过程师生双边活动：提问：举例：演示实验：教具准备：课后10.25作业教学后记编号31周次16日期12.17课时安排2课题快速排序、选择排序教材 的重 点、 难点 分析重点：(1)快速排序(2)堆排序难点：(1)快速排序(2)堆排序教 学 目 标(1)深刻理解快速排序的基本思想及其特点(2)熟练掌握快速排序方法的排序过程(3)掌握快速排序算法时间复杂度的分析方法并熟记其分析结论(4)深刻理解选择排序的基本思想及其特