《数据结构》教案

PAGE安庆师范学院教案（课时计划）课程名称：数据结构授课班级：授课地点：主讲教师：程玉胜20152016学年第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、文件编号1周次1日期课时安排2课题数据结构的概念及相关术语教材的重点、难点分析重点：(1)数据结构的逻辑结构(2)数据结构的存储结构(3)抽象数据类型的概念教学目标掌握数据、数据元素、数据对象的概念熟练掌握数据结构的概念及其逻辑结构和物理结构的分类掌握抽象数据类型的定义方法教学方法和教学手段讲授法多媒体教学过程教学内容安排与板书设计：第一章 绪论1．1什么是数据结构非数值计算问题举例《数据结构》产生的背景《数据结构》在计算机科学中的地位和作用教学过程1．2基本概念和术语数据数据元素数据对象数据结构数据结构的形式定义Data-Structure=(D,S)数据的逻辑结构及分类：集合、线性、树形、图形结构数据的物理结构：顺序存储结构与链式存储结构数据类型抽象数据类型抽象数据类型的形式定义ADT=(D,S,P)抽象数据类型定义举例—Triplet师生双边活动：提问：什么是数据类型举例：演示实验：教具准备：课后作业,教学后记教材：[1]严蔚敏吴伟民编著：数据结构（C语言版），清华大学出版社，1997年参考书目：[1]WirthN：Algorithms+DataStructures=Programs，Prentice-HallInc.，1976[2][美]S巴斯：计算机算法：设计和分析引论，复旦大学出版社，1985编号2周次1日期课时安排2课题抽象数据类型的表示与实现、算法和算法分析教材的重点、难点分析重点：(1)算法复杂度的分析方法难点：(1)算法复杂度的分析方法教学目标(1)理解数据抽象的意义(2)熟悉类C语言(3)掌握抽象数据类型的表示和实现方法(4)掌握算法描述和算法分析的方法教学方法和教学手段教学过程教学内容安与排板书设计：1．3抽象数据类型的表示和实现数据抽象的意义类C语言抽象数据类型的表示和实现举例教学过程1．4算法和算法分析算法算法的定义算法的特性：有穷性、确定性、可行性、输入、输出算法设计的要求正确性、可读性、健壮性、效率与低存储量需求算法效率的度量时间度量的方法分析时间复杂度T(n)=O(f(n))时间复杂度的计算算法的存储空间需求S(n)=O(f(n))师生双边活动：提问：举例：演示实验：教具准备：课后作业,教学后记编号3周次2日期课时安排2课题线性表的类型定义、线性表的顺序表示和实现教材的重点、难点分析重点：(1)顺序表的基本运算(2)顺序表上实现的各种算法的时间性能分析教学目标(1)理解线性表的逻辑结构特征(2)熟练掌握顺序表的描述方法、特点及有关概念(3)熟练掌握顺序表的基本运算教学方法和教学手段教学过程教学内容安排与板书设计：第二章 线性表线性结构的特点2．1线性表的类型定义线性表的定义及其表示线性表的类型定义线性表操作举例：用线性表表示集合、线性表的合并教学过程2．2线性表的顺序表示和实现线索性表的顺序表示线性表的顺序存储结构的定义及其特征顺序表的基本运算顺序表的初始化顺序表的插入操作顺序表的删除操作顺序表的合并顺序表基本操作的时间复杂度计算师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号4周次2日期课时安排2课题线性表的链式表示和实现（线性链表）教材的重点、难点分析重点：(1)链表的基本运算(2)链表上实现的各种算法的时间性能分析教学目标(1)熟练掌握链表的描述方法、特点及有关概念(2)掌握链表的基本运算(3)掌握静态链表的构造方法教学方法和教学手段教学过程教学内容安排与板书设计：2．3线性表的链式表示和实现2．3．1线性链表单链表的定义单链表的存储结构特征单链表的基本操作：插入教学过程删除有序链表的合并静态链表静态链表的定义静态链表的操作举例师生双边活动：提问：malloc()free()举例：演示实验：教具准备：课后作业,教学后记编号5周次3日期课时安排2课题循环链表、双向链表、一元多项式的表示及相加教材的重点、难点分析难点：(1)循环链表教学目标(1)掌握循环链表的特点(2)掌握双向链表的特点(3)从时空角度综合比较顺序表和链表的不同特点及使用场合(4)能应用线性表解决一些实际问题教学方法和教学手段教学过程教学内容安排与板书设计：2．3．2循环链表循环链表的定义循环链表的操作教学过程2．3．3双向链表双向链表的定义双向链表的操作特点线性链表的类型定义2．4一元多项式的表示及相加一元多项式的表示一元多项式的相加一元多项式的类型定义多项式的相加算法师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号6周次3日期课时安排2课题栈、栈应用举例（数制转换、括号匹配、行编辑）教材的重点、难点分析重点：(1)栈在两种存储结构上实现的基本运算。难点：栈满栈空的条件及它们的描述教学目标(1)掌握栈这种数据结构的特点(2)熟悉栈与线性表的关系(3)重点掌握顺序栈和链式栈的五种基本运算(4)掌握栈的应用方法教学方法和教学手段教学过程教学内容安排与板书设计：第三章 栈与队列3．1栈3．1．1抽象数据类型栈的定义栈及其与线性表的关系栈的类型定义教学过程3．1．2栈的表示和实现顺序栈的定义链栈的定义3．2栈的应用举例3．2．1数制转换3．2．2括号匹配的检验3．2．3行编辑程序师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号7周次4日期课时安排2课题迷宫求解、表达式求值、栈与递归的实现教材的重点、难点分析教学目标(1)能应用栈解决一些实际问题(2)了解递归算法执行过程中栈的变化过程教学方法和教学手段教学过程教学内容安排与板书设计：3．2．4迷宫求解3．2．5表达式求值3．3栈与递归的实现教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业,教学后记编号8周次4日期课时安排2课题队列教材的重点、难点分析重点：(1)队列在两种存储结构上实现的基本运算。难点：(1)循环队列（注意队满队空的条件及它们的描述）教学目标(1)掌握队列这种数据结构的特点(2)熟悉队列与线性表的关系(3)掌握循环队列和链式队列的五种基本运算(4)能应用队列解决一些实际问题教学方法和教学手段教学过程教学内容安排与板书设计：3．4队列3．4．1抽象数据类型队列的定义队列的定义(FIFO)队列的类型定义教学过程3．4．2链队列—队列的链式表示和实现单链队列的定义单链队列的操作3．4．3循环队列—队列的顺序表示和实现队列的顺序存储结构循环队列的基本操作师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号9周次5日期课时安排2课题机动教材的重点、难点分析教学目标教学方法和教学手段教学过程教学内容安排与板书设计：教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号10周次5日期课时安排2课题习题课教材的重点、难点分析教学目标教学方法和教学手段讲授法教学过程教学内容安排与板书设计：教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号11周次6日期课时安排2课题串类型的定义、串的表示和实现教材的重点、难点分析重点：(1)串的基本运算难点：(1)串的动态存储结构教学目标(1)熟悉串的有关概念，串与线性表的关系(2)掌握串的静态存储结构与动态存储结构和它们的优缺点(3)熟练掌握串的基本运算教学方法和教学手段教学过程教学内容安排与板书设计：第四章 串4．1串类型的定义串的概念串类型的定义教学过程4．2串的表示和实现4．2．1定长顺序存储表示串的定长顺序存储表示串联接求子串4．2．2堆分配存储表示串的堆分配存储表示堆的基本操作4．2．3串的块链存储表示师生双边活动：提问：举例：演示实验：教具准备：课后作业,教学后记编号12周次6日期课时安排2课题串的模式匹配算法、串操作应用举例教材的重点、难点分析教学目标(1)理解串的模式匹配算法(2)了解串的应用教学方法和教学手段教学过程教学内容安排与板书设计：4．3串的模式匹配算法4．3．1求子串位置的定位函数4．3．2模式匹配的一种改进算法KMP算法教学过程4．4串操作应用举例4．4．1文本编辑师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号13周次7日期课时安排2课题数组的定义、顺序表示和实现、矩阵的压缩存储教材的重点、难点分析重点：(1)多维数组的存储方式(2)矩阵的压缩存储方式难点：(1)稀疏矩阵的压缩存储表示下实现的算法教学目标(1)熟悉数组的按行（列）优先顺序的存储结构中的地址计算方法(2)熟悉特殊矩阵在压缩存储时的下标变换(3)理解稀疏矩阵的三元组和十字链表两种压缩存储表示教学方法和教学手段教学过程教学内容安排与板书设计：第五章 数组和广义表5．1数组的定义数组的类型定义二维数组教学过程5．2数组的顺序表示和实现二维数组的存储方式数组的顺序存储表示和实现5．3矩阵的压缩存储5．3．1特殊矩阵对称矩阵对角矩阵5．3．2稀疏矩阵稀疏矩阵的类型定义1、三元组顺序表师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号14周次7日期课时安排2课题稀疏矩阵的存储结构、广义表的定义和存储结构教材的重点、难点分析重点：(1)广义表的定义及其运算教学目标(1)掌握稀疏矩阵的存储结构(2)熟悉广义表的有关概念和运算(3)掌握广义表的两种存储结构教学方法和教学手段教学过程教学内容安排与板书设计：2、行逻辑链接的顺序表3、十字链表5．4广义表的定义教学过程广义表的类型定义广义表举例广义表的特点5．5广义表的存储结构讨论：M元多项式的表示广义表的递归算法师生双边活动：提问：举例：演示实验：教具准备：课后作业,教学后记编号15周次8日期课时安排2课题树的定义和基本术语、二叉树的定义教材的重点、难点分析重点：(1)树的基本术语(2)二叉树的定义教学目标(1)掌握树的定义和有关术语(2)熟悉二叉树的递归定义，有关术语及基本概念教学方法和教学手段教学过程教学内容安排与板书设计：第六章 树和二叉树6．1树的定义和基本术语树的类型定义基本术语教学过程6．2二叉树6．2．1二叉树的定义二叉树的类型定义二叉树的基本形态师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号16周次8日期课时安排2课题二叉树的性质和和存储结构教材的重点、难点分析重点：(1)二叉树的存储结构难点：(1)二叉树的性质教学目标(1)熟练掌握二叉树的性质及证明方法(2)熟练掌握二叉树的顺序和链式存储结构及特点教学方法和教学手段讲授法教学过程教学内容安排与板书设计：6．2．2二叉树的性质性质1性质2性质3性质4性质5教学过程6．2．3二叉树的存储结构顺序存储结构链式存储结构师生双边活动：提问：举例：演示实验：教具准备：课后作业,教学后记编号17周次9日期课时安排2课题遍历二叉树和线索二叉树教材的重点、难点分析重点：(1)二叉树的遍历算法及其相关应用难点：(1)二叉树的非递归遍历算法教学目标(1)熟练掌握二叉树的各种遍历(2)能灵活运用遍历算法实现二叉树的基本运算(3)掌握二叉树的线索化及相应算法教学方法和教学手段教学过程教学内容安排与板书设计：6．3遍历二叉树和线索二叉树6．3．1遍历二叉树遍历二叉树的递归算法先序遍历中序遍历后序遍历教学过程遍历二叉树的非递归算法遍历二叉树的其他算法二叉树的其他操作6．3．2线索二叉树线索二叉树及其存储结构二叉树的线索化师生双边活动：提问：举例：演示实验：教具准备：课后作业,,教学后记编号18周次9日期课时安排2课题树和森林教材的重点、难点分析重点：(1)树的存储结构难点：(1)森林、树与二叉树之间的转换教学目标(1)掌握树的存储结构及其特点(2)熟练掌握森林、树与二叉树之间的转换方法(3)掌握森林和树的遍历教学方法和教学手段教学过程教学内容安排与板书设计：6．4树和森林6．4．1树的存储结构双亲表示法孩子表示法孩子兄弟表示法教学过程6．4．2森林与二叉树的转换森林与二叉树的对应关系二叉树与森林的对应关系6．4．3树和森林的遍历先序遍历森林中序遍历森林师生双边活动：提问：举例：演示实验：教具准备：课后作业,教学后记编号19周次10日期课时安排2课题赫夫曼树及其应用教材的重点、难点分析重点：(1)赫夫曼编码难点：(1)赫夫曼编码教学目标(1)掌握最优化二叉树的特性、熟练掌握建立最优二叉树的方法(2)熟练掌握哈夫曼编码的方法教学方法和教学手段讲授法教学过程教学内容安排与板书设计：6．6赫夫曼树6．6．1最优二叉树最优二叉树的概念构造赫夫曼树最优判定算法6．6．2赫夫曼编码教学过程求赫夫曼编码师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号20周次10日期课时安排2课题习题课教材的重点、难点分析教学目标教学方法和教学手段讲授法教学过程教学内容安排与板书设计：教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号21周次11日期课时安排2课题图的定义和术语、图的存储结构教材的重点、难点分析重点：(1)图的存储教学目标(1)熟悉图的有关术语和概念(2)熟练掌握图的四种存储结构和建立算法教学方法和教学手段教学过程教学内容安排与板书设计：第七章 图7．1图的定义和术语图的类型定义图的分类连通图、连通分量、生成树教学过程7．2图的存储结构7．2．1数组表示法图的邻接矩阵网及其邻接矩阵7．2．2邻接表图的邻接表存储表示邻接表和逆邻接表师生双边活动：提问：举例：演示实验：教具准备：课后作业,教学后记编号22周次11日期课时安排2课题十字链表、邻接多重表、图的遍历教材的重点、难点分析重点：(1)图的遍历难点：(1)图的遍历非递归算法教学目标(1)熟练掌握图的四种存储结构和建立算法(2)熟练掌握图的深度优先遍历和广度优先遍历教学方法和教学手段教学过程教学内容安排与板书设计：7．2．3十字链表有向图的十字链表存储表示构造有向图7．2．4邻接多重表无向图的邻接多重表教学过程7．3图的遍历7．3．1深度优先搜索7．3．2广度优先搜索师生双边活动：提问：举例：演示实验：教具准备：课后作业,教学后记编号23周次12日期课时安排2课题图的连通性问题教材的重点、难点分析重点：(1)最小生成树的构造教学目标掌握最小生成树的两种构造方法教学方法和教学手段教学过程教学内容安排与板书设计：7．4图的连通性问题7．4．1无向图的连通分量和生成树7．4．2有向图的强连通分量教学过程7．4．3最小生成树Prim算法Kruskal算法7．4．3关节点和重连通分量师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号24周次12日期课时安排2课题有向无环图及其应用教材的重点、难点分析重点：(1)拓扑排序(2)求关键路径难点：(1)求关键路径教学目标(1)掌握拓扑排序的方法(2)掌握关键路径的求法教学方法和教学手段教学过程教学内容安排与板书设计：7．5有向无环图及其应用DAG7．5．1拓扑排序7．5．2关键路径AOE网关键路径教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号25周次13日期课时安排2课题最短路径教材的重点、难点分析重点：(1)求最短路径难点：(1)求每一对顶点之间的最短路径教学目标熟练掌握从某个源点到其余各顶点的最短路径的求法掌握求每一对顶点之间的最短路径的求法教学方法和教学手段教学过程教学内容安排与板书设计：7．6最短路径7．6．1从某个源点到其余各顶点的最短路径Dijkstra算法7．6．2每一对顶点之间的最短路径教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号26周次13日期课时安排2课题静态查找表教材的重点、难点分析重点：(1)顺序查找(2)折半查找教学目标(1)熟练掌握静态查找的各种方法教学方法和教学手段教学过程教学内容安排与板书设计：第八章 查找查找表与静态查找表和动态查找表关键字与主关键字和次关键字查找与成功和不成功教学过程8．1静态查找表静态查找表的类型定义8．1．1顺序表的查找顺序查找平均查找长度8．1．2有序表的查找折半查找折半查找的性能分析8．1．3静态树表的查找8．1．4索引顺序表的查找表其索引表分块查找师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号27周次14日期课时安排2课题二叉排序树和平衡二叉树教材的重点、难点分析重点：(1)动态查找表及查找算法(2)二叉排序树难点：(1)二叉排序树教学目标(1)熟练掌握二叉排序树的构造方法及查找过程(2)掌握AVL树的构造教学方法和教学手段教学过程教学内容安排与板书设计：8．2动态查找表动态查找表的类型定义8．2．1二叉排序树和平衡二叉树1、二叉排序树及其查找过程二叉排序树教学过程2、二叉排序树的插入和删除二叉排序树的构造二叉排序树的删除3、二叉排序树的查找分析4、平衡二叉树平衡二叉树与不平衡的二叉树平衡树的生成过程二叉排序树的平衡旋转二叉排序树的类型定义5、平衡树查找的分析师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号28周次14日期课时安排2课题B-树和B+树教材的重点、难点分析教学目标(1)掌握B-树和B+树的构造和查找(2)了解键树的构造方法教学方法和教学手段教学过程教学内容安排与板书设计：8．2．2B-树和B+树1、B-树及其查找2、B-树查找分析教学过程3、B-树的插入和删除4、B+树8．2．3键树师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号29周次15日期课时安排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周次15日期课时安排2课题排序概述、插入排序教材的重点、难点分析重点：(1)希尔排序教学目标(1)深刻理解插入排序的基本思想及其特点(2)熟练掌握插入排序方法的排序过程(3)掌握插入排序算法时间复杂度的分析方法并熟记其分析结论教学方法和教学手段教学过程教学内容安排与板书设计：第九章 排序9．1排序概述排序排序方法的稳定性内部排序与外部排序教学过程9．2插入排序9．2．1直接插入排序9．2．2其他插入排序1、折半插入排序2、2-路插入排序3、表插入排序9．2．3希尔排序师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号31周次16日期课时安排2课题快速排序、选择排序教材的重点、难点分析重点：(1)快速排序(2)堆排序难点：(1)快速排序(2)堆排序教学目标(1)深刻理解快速排序的基本思想及其特点(2)熟练掌握快速排序方法的排序过程(3)掌握快速排序算法时间复杂度的分析方法并熟记其分