《数据结构》教案教学提纲.docx

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

2、存储14、稀疏矩阵的存储结构、广义表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)抽象数据类型的概念教学目标掌握数据、数据元素、数据对象的概念熟练掌握数据结构的概念及其逻辑结构和物理结构的分类掌握抽象数据类型的定义方法教学方法和 教学手段讲授法多媒体教学过程教学内容安排与板书设计：第一章 绪论11 什么是数据结构非数值计算问题举例数据结构产生的背景数据结构在计算机科学中的地位和作用教学过程12 基本概念和术语数据数据元素数据对象数据结构数据结构的形式定义 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)算法复杂度的分析方法难点：(1

5、)算法复杂度的分析方法教学目标(1)理解数据抽象的意义(2)熟悉类C语言(3)掌握抽象数据类型的表示和实现方法(4)掌握算法描述和算法分析的方法教学方法和 教学手段教学过程教学内容安与排板书设计：13 抽象数据类型的表示和实现数据抽象的意义类C语言抽象数据类型的表示和实现举例教学过程14 算法和算法分析算法 算法的定义算法的特性：有穷性、确定性、可行性、输入、输出算法设计的要求 正确性、可读性、健壮性、效率与低存储量需求算法效率的度量 时间度量的方法分析 时间复杂度 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 线性表的类型定义线性表的定义及其表示线性表的类型定义线性表操作举例：用线性表表示集合、线性表的合并教学过程22 线性表的顺序表示和实现线索性表的顺序表示线性表的顺序存储结构的定义及其特征顺序

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

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

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

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

11、4日期9.27课时安排2课题队列教材的重点 、难点分析重点：(1)队列在两种存储结构上实现的基本运算。难点：(1)循环队列（注意队满队空的条件及它们的描述）教学目标(1) 掌握队列这种数据结构的特点(2)熟悉队列与线性表的关系(3)掌握循环队列和链式队列的五种基本运算(4)能应用队列解决一些实际问题教学方法和 教学手段教学过程教学内容安排与板书设计：34 队列341 抽象数据类型队列的定义队列的定义(FIFO)队列的类型定义教学过程342 链队列队列的链式表示和实现单链队列的定义单链队列的操作343 循环队列队列的顺序表示和实现队列的顺序存储结构循环队列的基本操作师生双边活动：提问：举例：演示

12、实验：教具准备：课后作业3.29教学后记编号9周次5日期10.1课时安排2课题机动教材的重点 、难点分析教学目标教学方法和 教学手段教学过程教学内容安排与板书设计：教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号10周次5日期10.4课时安排2课题习题课教材的重点 、难点分析教学目标教学方法和 教学手段讲授法教学过程教学内容安排与板书设计：教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号11周次6日期10.8课时安排2课题串类型的定义、串的表示和实现教材的重点 、难点分析重点：(1)串的基本运算难点：(1)串的动态存储结构教学目标(1)熟悉串

13、的有关概念，串与线性表的关系(2)掌握串的静态存储结构与动态存储结构和它们的优缺点(3)熟练掌握串的基本运算教学方法和 教学手段教学过程教学内容安排与板书设计：第四章 串41 串类型的定义串的概念串类型的定义教学过程42 串的表示和实现421 定长顺序存储表示串的定长顺序存储表示串联接求子串422 堆分配存储表示串的堆分配存储表示堆的基本操作423 串的块链存储表示师生双边活动：提问：举例：演示实验：教具准备：课后作业4.17,4.22/4.24教学后记编号12周次6日期10.11课时安排2课题串的模式匹配算法、串操作应用举例教材的重点 、难点分析教学目标(1)理解串的模式匹配算法(2)了解串

14、的应用教学方法和 教学手段教学过程教学内容安排与板书设计：43 串的模式匹配算法431 求子串位置的定位函数432 模式匹配的一种改进算法KMP算法教学过程44 串操作应用举例441 文本编辑师生双边活动：提问：举例：演示实验：教具准备：课后作业4.8教学后记编号13周次7日期10.15课时安排2课题数组的定义、顺序表示和实现、矩阵的压缩存储教材的重点 、难点分析重点：(1)多维数组的存储方式(2)矩阵的压缩存储方式难点：(1)稀疏矩阵的压缩存储表示下实现的算法教学目标(1)熟悉数组的按行（列）优先顺序的存储结构中的地址计算方法(2)熟悉特殊矩阵在压缩存储时的下标变换(3)理解稀疏矩阵的三元组

15、和十字链表两种压缩存储表示教学方法和 教学手段教学过程教学内容安排与板书设计：第五章 数组和广义表51 数组的定义数组的类型定义二维数组教学过程52 数组的顺序表示和实现二维数组的存储方式数组的顺序存储表示和实现53 矩阵的压缩存储531 特殊矩阵对称矩阵对角矩阵532 稀疏矩阵稀疏矩阵的类型定义1、三元组顺序表师生双边活动：提问：举例：演示实验：教具准备：课后作业5.21教学后记编号14周次7日期10.18课时安排2课题稀疏矩阵的存储结构、广义表的定义和存储结构教材的重点 、难点分析重点：(1)广义表的定义及其运算教学目标(1)掌握稀疏矩阵的存储结构(2)熟悉广义表的有关概念和运算(3)掌握

16、广义表的两种存储结构教学方法和 教学手段教学过程教学内容安排与板书设计：2、行逻辑链接的顺序表3、十字链表54 广义表的定义教学过程广义表的类型定义广义表举例广义表的特点55 广义表的存储结构讨论：M元多项式的表示广义表的递归算法师生双边活动：提问：举例：演示实验：教具准备：课后作业5.26,5.12教学后记编号15周次8日期10.22课时安排2课题树的定义和基本术语、二叉树的定义教材的重点 、难点分析重点：(1)树的基本术语 (2)二叉树的定义教学目标(1)掌握树的定义和有关术语 (2)熟悉二叉树的递归定义，有关术语及基本概念教学方法和 教学手段教学过程教学内容安排与板书设计：第六章 树和二

17、叉树61 树的定义和基本术语树的类型定义基本术语教学过程62 二叉树621 二叉树的定义二叉树的类型定义二叉树的基本形态师生双边活动：提问：举例：演示实验：教具准备：课后作业6.2教学后记编号16周次8日期10.25课时安排2课题二叉树的性质和和存储结构教材的重点 、难点分析重点：(1)二叉树的存储结构难点：(1)二叉树的性质教学目标(1)熟练掌握二叉树的性质及证明方法(2)熟练掌握二叉树的顺序和链式存储结构及特点教学方法和 教学手段讲授法教学过程教学内容安排与板书设计：622 二叉树的性质性质1性质2性质3性质4性质5教学过程623 二叉树的存储结构顺序存储结构链式存储结构师生双边活动：提问

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

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

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