《大数据结构》教案设计

1、录word 录师学院教案（课时计划）课程名称：数据结构授课班级：授课地点：主讲教师：程玉胜2015-2016 学年第 2 学期目1 / 70 1 word 1 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、文件编号2 / 70 1数据结构的概念及相关术语重点： (1)数据结构的逻辑结构(2)

3、数据结构的存储结构(3)抽象数据类型的概念掌握抽象数据类型的定义方法讲授法多媒体绪论11 什么是数据结构非数值计算问题举例数据结构产生的背景11数据结构的概念及相关术语重点： (1)数据结构的逻辑结构(2)数据结构的存储结构(3)抽象数据类型的概念掌握抽象数据类型的定义方法讲授法多媒体绪论11 什么是数据结构非数值计算问题举例数据结构产生的背景12 基本概念和术语日期9.3课时安排2周次课题教材的重点、难点分析掌握数据、数据元素、数据对象的概念熟练掌握数据结构的概念及其逻辑结构和物理结构的分类教学目标教学方法和教学手段教学容安排与板书设计：第一章教学过程数据结构在计算机科学中的地位和作用教3

4、/ 70 数据元素数据结构Data-Structure = 数据的逻辑结构及分类：集合、线性、树形、图形结构ADT = Triplet 1.2,1.19 C语言版），清华大学， 1997 年数据元素数据结构Data-Structure = 数据的逻辑结构及分类：集合、线性、树形、图形结构ADT = Triplet 1.2,1.19 C语言版），清华大学， 1997 年参考书目：1985(D, S) (D, S, P) 数据学数据对象过数据结构的形式定义程数据的物理结构：顺序存储结构与链式存储结构数据类型抽象数据类型抽象数据类型的形式定义抽象数据类型定义举例师生双边活动：提问： 什么是数据类型？

5、举例：演示实验：教具准备：课后作业教材：1严蔚敏 吴伟民编著：数据结构（教学后记1Wirth N ：Algorithms+Data Structures=Programs，Prentice-Hall Inc.，1976 2美S 巴斯：计算机算法：设计和分析引论，复旦大学，4 / 70 2 1抽象数据类型的表示与实现、算法和算法分析重点： (1)算法复杂度的分析方法难点： (1)算法复杂度的分析方法(3)掌握抽象数据类型的表示和实现方法(4)掌握算法描述和算法分析的方法数据抽象的意义类 C2 1抽象数据类型的表示与实现、算法和算法分析重点： (1)算法复杂度的分析方法难点： (1)算法复杂度的分

6、析方法(3)掌握抽象数据类型的表示和实现方法(4)掌握算法描述和算法分析的方法数据抽象的意义类 C 语言抽象数据类型的表示和实现举例日期9.6课时安排2编号周次课题教材的重点、难点分析(1)理解数据抽象的意义(2)熟悉类 C 语言教学目标教学方法和教学手段教学容安与排板书设计：13 抽象数据类型的表示和实现教学过程5 / 70 正确性、可读性、健壮性、效率与低存储量需求时间度量的方法分析1.4,1.20 word 正确性、可读性、健壮性、效率与低存储量需求时间度量的方法分析1.4,1.20 14 算法和算法分析算法算法的定义算法的特性：有穷性、确定性、可行性、输入、输出算法设计的要求教算法效率

7、的度量学时间复杂度T(n) = O(f(n)过时间复杂度的计算算法的存储空间需求程S(n) = O(f(n) 师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记6 / 70 3 2线性表的类型定义、线性表的顺序表示和实现重点： (1)顺序表的基本运算(2)顺序表上实现的各种算法的时间性能分析(3)熟练掌握顺序表的基本运算线性表线性结构的特点21 线性表的类型定义线性表的定义及其表示3 2线性表的类型定义、线性表的顺序表示和实现重点： (1)顺序表的基本运算(2)顺序表上实现的各种算法的时间性能分析(3)熟练掌握顺序表的基本运算线性表线性结构的特点21 线性表的类型定义线性表的定义及

8、其表示日期9.10课时安排2编号周次课题教材的重点、难点分析(1)理解线性表的逻辑结构特征(2)熟练掌握顺序表的描述方法、特点及有关概念教学目标教学方法和教学手段教学容安排与板书设计：第二章教学过程线性表的类型定义线性表操作举例：用线性表表示集合、线性表的合并7 / 70 顺序表的插入操作顺序表的合并2.12 word 顺序表的插入操作顺序表的合并2.12 22 线性表的顺序表示和实现线索性表的顺序表示线性表的顺序存储结构的定义及其特征顺序表的基本运算顺序表的初始化教顺序表的删除操作学顺序表基本操作的时间复杂度计算过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记8 / 70

9、4 2线性表的链式表示和实现（线性链表）重点： (1)链表的基本运算(2)链表上实现的各种算法的时间性能分析(3)掌握静态链表的构造方法231 线性链表单链表的定义单链表的存储结构特征4 2线性表的链式表示和实现（线性链表）重点： (1)链表的基本运算(2)链表上实现的各种算法的时间性能分析(3)掌握静态链表的构造方法231 线性链表单链表的定义单链表的存储结构特征日期9.13课时安排2编号周次课题教材的重点、难点分析(1)熟练掌握链表的描述方法、特点及有关概念(2)掌握链表的基本运算教学目标教学方法和教学手段教学容安排与板书设计：23 线性表的链式表示和实现教学过程单链表的基本操作：插入9

10、/ 70 free() 2.17,2.25 word free() 2.17,2.25 删除有序链表的合并静态链表静态链表的定义静态链表的操作举例教学过程师生双边活动：提问： malloc() 举例：演示实验：教具准备：课后作业教学后记10 / 70 5 3循环链表、双向链表、一元多项式的表示及相加难点： (1)循环链表(3)从时空角度综合比较顺序表和链表的不同特点及使用场合(4)能应用线性表解决一些实际问题循环链表的定义循环链表的操作日期9.17课时安排25 3循环链表、双向链表、一元多项式的表示及相加难点： (1)循环链表(3)从时空角度综合比较顺序表和链表的不同特点及使用场合(4)能应用

11、线性表解决一些实际问题循环链表的定义循环链表的操作日期9.17课时安排2编号周次课题教材的重点、难点分析(1)掌握循环链表的特点(2)掌握双向链表的特点教学目标教学方法和教学手段教学容安排与板书设计：232 循环链表教学过程11 / 70 2.32 word 2.32 233 双向链表双向链表的定义双向链表的操作特点线性链表的类型定义24 一元多项式的表示及相加一元多项式的表示教一元多项式的相加一元多项式的类型定义学多项式的相加算法过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记12 / 70 6 3栈、栈应用举例（数制转换、括号匹配、行编辑）重点： (1)栈在两种存储结构上

12、实现的基本运算。难点：栈满栈空的条件及它们的描述(3)重点掌握顺序栈和链式栈的五种基本运算(4)掌握栈的应用方法栈与队列31 栈36 3栈、栈应用举例（数制转换、括号匹配、行编辑）重点： (1)栈在两种存储结构上实现的基本运算。难点：栈满栈空的条件及它们的描述(3)重点掌握顺序栈和链式栈的五种基本运算(4)掌握栈的应用方法栈与队列31 栈311 抽象数据类型栈的定义栈及其与线性表的关系日期9.20课时安排2编号周次课题教材的重点、难点分析(1)掌握栈这种数据结构的特点(2)熟悉栈与线性表的关系教学目标教学方法和教学手段教学容安排与板书设计：第三章教学过程栈的类型定义13 / 70 321 数制

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

14、 3.19,3.25 word 3.19,3.25 教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记16 / 70 8 4队列重点： (1)队列在两种存储结构上实现的基本运算。难点： (1)循环队列（注意队满队空的条件及它们的描述）(3)掌握循环队列和链式队列的五种基本运算(4)能应用队列解决一些实际问题341 8 4队列重点： (1)队列在两种存储结构上实现的基本运算。难点： (1)循环队列（注意队满队空的条件及它们的描述）(3)掌握循环队列和链式队列的五种基本运算(4)能应用队列解决一些实际问题341 抽象数据类型队列的定义队列的定义 (FIFO) 队列的类型定义日期

15、9.27课时安排2编号周次课题教材的重点、难点分析(1) 掌握队列这种数据结构的特点(2)熟悉队列与线性表的关系教学目标教学方法和教学手段教学容安排与板书设计：34 队列教学过程17 / 70 3.29 word 3.29 342 链队列队列的链式表示和实现单链队列的定义单链队列的操作343 循环队列队列的顺序表示和实现队列的顺序存储结构循环队列的基本操作教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记18 / 70 9 5 机动日期10.1 课时安排2 word 9 5 机动日期10.1 课时安排2 编号周次课题教材的重点、难点分析教学目标教学方法和教学手段教学容安排与

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

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

18、：教具准备：课后作业教学后记24 / 70 12 6 串的模式匹配算法、串操作应用举例431 求子串位置的定位函数432 模式匹配的一种改进算法12 6 串的模式匹配算法、串操作应用举例431 求子串位置的定位函数432 模式匹配的一种改进算法KMP 算法日期10.11 课时安排2 编号周次课题教材的重点、难点分析(1)理解串的模式匹配算法(2)了解串的应用教学目标教学方法和教学手段教学容安排与板书设计：43 串的模式匹配算法教学过程25 / 70 4.8 word 4.8 44 串操作应用举例441 文本编辑教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记26 / 70

19、 13 7 数组的定义、顺序表示和实现、矩阵的压缩存储重点： (1)多维数组的存储方式(2)矩阵的压缩存储方式难点： (1)稀疏矩阵的压缩存储表示下实现的算法(3)理解稀疏矩阵的三元组和十字链表两种压缩存储表示数组和广义表51 13 7 数组的定义、顺序表示和实现、矩阵的压缩存储重点： (1)多维数组的存储方式(2)矩阵的压缩存储方式难点： (1)稀疏矩阵的压缩存储表示下实现的算法(3)理解稀疏矩阵的三元组和十字链表两种压缩存储表示数组和广义表51 数组的定义数组的类型定义二维数组日期10.15 课时安排2 编号周次课题教材的重点、难点分析(1)熟悉数组的按行（列）优先顺序的存储结构中的地址计

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

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

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

23、学后记32 / 70 16 8 二叉树的性质和和存储结构重点： (1)二叉树的存储结构难点： (1)二叉树的性质讲授法性质 1 16 8 二叉树的性质和和存储结构重点： (1)二叉树的存储结构难点： (1)二叉树的性质讲授法性质 1 性质 2 性质 3 日期10.25 课时安排2 编号周次课题教材的重点、难点分析(1)熟练掌握二叉树的性质及证明方法(2)熟练掌握二叉树的顺序和链式存储结构及特点教学目标教学方法和教学手段教学容安排与板书设计：622 二叉树的性质教学过程性质 4 性质 533 / 70 6.6,6.11 word 6.6,6.11 623 二叉树的存储结构顺序存储结构链式存储结构

24、教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记34 / 70 17 9 遍历二叉树和线索二叉树重点： (1)二叉树的遍历算法及其相关应用难点： (1)二叉树的非递归遍历算法(3)掌握二叉树的线索化及相应算法631 17 9 遍历二叉树和线索二叉树重点： (1)二叉树的遍历算法及其相关应用难点： (1)二叉树的非递归遍历算法(3)掌握二叉树的线索化及相应算法631 遍历二叉树遍历二叉树的递归算法先序遍历日期10.29 课时安排2 编号周次课题教材的重点、难点分析(1)熟练掌握二叉树的各种遍历(2)能灵活运用遍历算法实现二叉树的基本运算教学目标教学方法和教学手段教学容安排与

25、板书设计：63 遍历二叉树和线索二叉树教学过程中序遍历后序遍历35 / 70 6.43,6.47,6.56 word 6.43,6.47,6.56 遍历二叉树的非递归算法遍历二叉树的其他算法二叉树的其他操作632 线索二叉树线索二叉树及其存储结构二叉树的线索化教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记36 / 70 18 9 树和森林重点： (1)树的存储结构难点： (1) 森林、树与二叉树之间的转换(3)掌握森林和树的遍历618 9 树和森林重点： (1)树的存储结构难点： (1) 森林、树与二叉树之间的转换(3)掌握森林和树的遍历641 树的存储结构双亲表示法孩

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

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

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