搜索
1安庆师范学院教案（课时计划）课程名称：数据结构授课班级：授课地点：主讲教师：程玉胜2015----2016学年第2学期2目录01、数据结构的概念及相关术语02、抽象数据类型的表示与实现、算法和算法分析03、线性表的类型定义、线性表的顺序表示和实现04、线性表的链式表示和实现（线性链表）05、循环链表、双向链表、一元多项式的表示及相加06、栈、栈应用举例（数制转换、括号匹配、行编辑）07、迷宫求解、表达式求值、栈与递归的实现08、队列09、机动10、习题课11、串类型的定义、串的表示和实现12、串的模式匹配算法、串操作应用举例13、数组的定义、顺序表示和实现、矩阵的压缩存储14、稀疏矩阵的存储结构、广义表15、树的定义和基本术语、二叉树的定义16、二叉树的性质、二叉树的存储结构17、遍历二叉树和线索二叉树18、树和森林19、赫夫曼树及其应用20、习题课21、图的定义和术语、图的存储结构22、十字链表、邻接多重表、图的遍历23、图的连通性问题24、有向无环图及其应用25、最短路径26、静态查找表27、二叉排序树和平衡二叉树28、B-树和B+树29、哈希表30、排序概述、插入排序31、快速排序、选择排序32、归并排序、基数排序33、外部排序、各种排序方法的比较34、文件3编号1周次1日期9.3课时安排2课题数据结构的概念及相关术语教材的重点、难点分析重点：(1)数据结构的逻辑结构(2)数据结构的存储结构(3)抽象数据类型的概念教学目标掌握数据、数据元素、数据对象的概念熟练掌握数据结构的概念及其逻辑结构和物理结构的分类掌握抽象数据类型的定义方法教学方法和教学手段讲授法多媒体教学过程教学内容安排与板书设计：第一章绪论1．1什么是数据结构非数值计算问题举例《数据结构》产生的背景《数据结构》在计算机科学中的地位和作用4教学过程1．2基本概念和术语数据数据元素数据对象数据结构数据结构的形式定义Data-Structure=(D,S)数据的逻辑结构及分类：集合、线性、树形、图形结构数据的物理结构：顺序存储结构与链式存储结构数据类型抽象数据类型抽象数据类型的形式定义ADT=(D,S,P)抽象数据类型定义举例—Triplet师生双边活动：提问：什么是数据类型？举例：演示实验：教具准备：课后作业1.2,1.19教学后记教材：[1]严蔚敏吴伟民编著：数据结构（C语言版），清华大学出版社，1997年参考书目：[1]WirthN：Algorithms+DataStructures=Programs，Prentice-HallInc.，1976[2][美]S巴斯：计算机算法：设计和分析引论，复旦大学出版社，19855编号2周次1日期9.6课时安排2课题抽象数据类型的表示与实现、算法和算法分析教材的重点、难点分析重点：(1)算法复杂度的分析方法难点：(1)算法复杂度的分析方法教学目标(1)理解数据抽象的意义(2)熟悉类C语言(3)掌握抽象数据类型的表示和实现方法(4)掌握算法描述和算法分析的方法教学方法和教学手段教学过程教学内容安与排板书设计：1．3抽象数据类型的表示和实现数据抽象的意义类C语言抽象数据类型的表示和实现举例6教学过程1．4算法和算法分析算法算法的定义算法的特性：有穷性、确定性、可行性、输入、输出算法设计的要求正确性、可读性、健壮性、效率与低存储量需求算法效率的度量时间度量的方法分析时间复杂度T(n)=O(f(n))时间复杂度的计算算法的存储空间需求S(n)=O(f(n))师生双边活动：提问：举例：演示实验：教具准备：课后作业1.4,1.20教学后记7编号3周次2日期9.10课时安排2课题线性表的类型定义、线性表的顺序表示和实现教材的重点、难点分析重点：(1)顺序表的基本运算(2)顺序表上实现的各种算法的时间性能分析教学目标(1)理解线性表的逻辑结构特征(2)熟练掌握顺序表的描述方法、特点及有关概念(3)熟练掌握顺序表的基本运算教学方法和教学手段教学过程教学内容安排与板书设计：第二章线性表线性结构的特点2．1线性表的类型定义线性表的定义及其表示线性表的类型定义线性表操作举例：用线性表表示集合、线性表的合并8教学过程2．2线性表的顺序表示和实现线索性表的顺序表示线性表的顺序存储结构的定义及其特征顺序表的基本运算顺序表的初始化顺序表的插入操作顺序表的删除操作顺序表的合并顺序表基本操作的时间复杂度计算师生双边活动：提问：举例：演示实验：教具准备：课后作业2.12教学后记9编号4周次2日期9.13课时安排2课题线性表的链式表示和实现（线性链表）教材的重点、难点分析重点：(1)链表的基本运算(2)链表上实现的各种算法的时间性能分析教学目标(1)熟练掌握链表的描述方法、特点及有关概念(2)掌握链表的基本运算(3)掌握静态链表的构造方法教学方法和教学手段教学过程教学内容安排与板书设计：2．3线性表的链式表示和实现2．3．1线性链表单链表的定义单链表的存储结构特征单链表的基本操作：插入10教学过程删除有序链表的合并静态链表静态链表的定义静态链表的操作举例师生双边活动：提问：malloc()free()举例：演示实验：教具准备：课后作业2.17,2.25教学后记11编号5周次3日期9.17课时安排2课题循环链表、双向链表、一元多项式的表示及相加教材的重点、难点分析难点：(1)循环链表教学目标(1)掌握循环链表的特点(2)掌握双向链表的特点(3)从时空角度综合比较顺序表和链表的不同特点及使用场合(4)能应用线性表解决一些实际问题教学方法和教学手段教学过程教学内容安排与板书设计：2．3．2循环链表循环链表的定义循环链表的操作12教学过程2．3．3双向链表双向链表的定义双向链表的操作特点线性链表的类型定义2．4一元多项式的表示及相加一元多项式的表示一元多项式的相加一元多项式的类型定义多项式的相加算法师生双边活动：提问：举例：演示实验：教具准备：课后作业2.32教学后记13编号6周次3日期9.20课时安排2课题栈、栈应用举例（数制转换、括号匹配、行编辑）教材的重点、难点分析重点：(1)栈在两种存储结构上实现的基本运算。难点：栈满栈空的条件及它们的描述教学目标(1)掌握栈这种数据结构的特点(2)熟悉栈与线性表的关系(3)重点掌握顺序栈和链式栈的五种基本运算(4)掌握栈的应用方法教学方法和教学手段教学过程教学内容安排与板书设计：第三章栈与队列3．1栈3．1．1抽象数据类型栈的定义栈及其与线性表的关系栈的类型定义14教学过程3．1．2栈的表示和实现顺序栈的定义链栈的定义3．2栈的应用举例3．2．1数制转换3．2．2括号匹配的检验3．2．3行编辑程序师生双边活动：提问：举例：演示实验：教具准备：课后作业3.15教学后记15编号7周次4日期9.24课时安排2课题迷宫求解、表达式求值、栈与递归的实现教材的重点、难点分析教学目标(1)能应用栈解决一些实际问题(2)了解递归算法执行过程中栈的变化过程教学方法和教学手段教学过程教学内容安排与板书设计：3．2．4迷宫求解3．2．5表达式求值3．3栈与递归的实现16教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业3.19,3.25教学后记17编号8周次4日期9.27课时安排2课题队列教材的重点、难点分析重点：(1)队列在两种存储结构上实现的基本运算。难点：(1)循环队列（注意队满队空的条件及它们的描述）教学目标(1)掌握队列这种数据结构的特点(2)熟悉队列与线性表的关系(3)掌握循环队列和链式队列的五种基本运算(4)能应用队列解决一些实际问题教学方法和教学手段教学过程教学内容安排与板书设计：3．4队列3．4．1抽象数据类型队列的定义队列的定义(FIFO)队列的类型定义18教学过程3．4．2链队列—队列的链式表示和实现单链队列的定义单链队列的操作3．4．3循环队列—队列的顺序表示和实现队列的顺序存储结构循环队列的基本操作师生双边活动：提问：举例：演示实验：教具准备：课后作业3.29教学后记19编号9周次5日期10.1课时安排2课题机动教材的重点、难点分析教学目标教学方法和教学手段教学过程教学内容安排与板书设计：20教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记21编号10周次5日期10.4课时安排2课题习题课教材的重点、难点分析教学目标教学方法和教学手段讲授法教学过程教学内容安排与板书设计：22教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记23编号11周次6日期10.8课时安排2课题串类型的定义、串的表示和实现教材的重点、难点分析重点：(1)串的基本运算难点：(1)串的动态存储结构教学目标(1)熟悉串的有关概念，串与线性表的关系(2)掌握串的静态存储结构与动态存储结构和它们的优缺点(3)熟练掌握串的基本运算教学方法和教学手段教学过程教学内容安排与板书设计：第四章串4．1串类型的定义串的概念串类型的定义24教学过程4．2串的表示和实现4．2．1定长顺序存储表示串的定长顺序存储表示串联接求子串4．2．2堆分配存储表示串的堆分配存储表示堆的基本操作4．2．3串的块链存储表示师生双边活动：提问：举例：演示实验：教具准备：课后作业4.17,4.22/4.24教学后记25编号12周次6日期10.11课时安排2课题串的模式匹配算法、串操作应用举例教材的重点、难点分析教学目标(1)理解串的模式匹配算法(2)了解串的应用教学方法和教学手段教学过程教学内容安排与板书设计：4．3串的模式匹配算法4．3．1求子串位置的定位函数4．3．2模式匹配的一种改进算法KMP算法26教学过程4．4串操作应用举例4．4．1文本编辑师生双边活动：提问：举例：演示实验：教具准备：课后作业4.8教学后记27编号13周次7日期10.15课时安排2课题数组的定义、顺序表示和实现、矩阵的压缩存储教材的重点、难点分析重点：(1)多维数组的存储方式(2)矩阵的压缩存储方式难点：(1)稀疏矩阵的压缩存储表示下实现的算法教学目标(1)熟悉数组的按行（列）优先顺序的存储结构中的地址计算方法(2)熟悉特殊矩阵在压缩存储时的下标变换(3)理解稀疏矩阵的三元组和十字链表两种压缩存储表示教学方法和教学手段教学过程教学内容安排与板书设计：第五章数组和广义表5．1数组的定义数组的类型定义二维数组28教学过程5．2数组的顺序表示和实现二维数组的存储方式数组的顺序存储表示和实现5．3矩阵的压缩存储5．3．1特殊矩阵对称矩阵对角矩阵5．3．2稀疏矩阵稀疏矩阵的类型定义1、三元组顺序表师生双边活动：提问：举例：演示实验：教具准备：课后作业5.21教学后记29编号14周次7日期10.18课时安排2课题稀疏矩阵的存储结构、广义表的定义和存储结构教材的重点、难点分析重点：(1)广义表的定义及其运算教学目标(1)掌握稀疏矩阵的存储结构(2)熟悉广义表的有关概念和运算(3)掌握广义表的两种存储结构教学方法和教学手段教学过程教学内容安排与板书设计：2、行逻辑链接的顺序表3、十字链表5．4广义表的定义30教学过程广义表的类型定义广义表举例广义表的特点5．5广义表的存储结构讨论：M元多项式的表示广义表的递归算法师生双边活动：提问：举例：演示实验：教具准备：课后作业5.26,5.12教学后记31编号15周次8日期10.22课时安排2课题树的定义和基本术语、二叉树的定义教材的重点、难点分析重点：(1)树的基本术语(2)二叉树的定义教学目标(1)掌握树的定义和有关术语(2)熟悉二叉树的递归定义，有关术语及基本概念教学方法和教学手段教学过程教学内容安排与板书设计：第六章树和二叉树6．1树的定义和基本术语树的类型定义基本术语32教学过程6．2二叉树6．2．1二叉树的定义二叉树的类型定义二叉树的基本形态师生双边活动：提问：举例：演示实验：教具准备：课后作业6.2教学后记33编号16周次8日期10.25课时安排2课题二叉树的性质和和存储结构教材的重点、难点分析重点：(1)二叉树的存储结构难点：(1)二叉树的性质教学目标(1)熟练掌握二叉树的性质及证明方法(2)熟练掌握二叉树