《数据结构》教案8

1、安庆师范学院教案（课时计划）课程名称：数据结构 授课班级: 授课地点: 主讲教师：程玉胜2015-2016学年第2学期01、数据结构的概念及相关术语02、抽象数据类型的表示与实现、算法和算法分析03、线性表的类型定义、线性表的顺序表示和实现04、线性表的链式表示和实现（线性链表）05、循环链表、双向捷表、一元多项式的表示及相加06、栈、栈应用举例（数制转换、括号匹配、行编辑）07、迷宫求解、表达式求值、栈与递归的实现08、队列09、机动10、习题课“、串类型的定义、串的表示和实现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课题数据结构的概念及相关术语教材重点：数据结构的逻辑结构的重(2)数据结构的存储结构抽象数据类型

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

4、一Triplet程师生双边活动：提问：什么是数据类型？举例：演示实验：教具准备：课后1.2,1.19作业教学后记教材：严蔚敢吴悌民编苦：数据结构(C语言版)，清华大学出版社，1997年参考书目：ipX'irth N: Algurithms-Datn Structurcs=Programs, Prcnucc-Hall Inc., 19760美S巴斯：计算机算法：设计和分析引论，亘旦大学出版社，1985编号2周次1日期9,6课时安排 2课题抽象数据类型的表示与实现、算法和算法分析教材的重点、难点分析重点：算法宣杂度的分析方法难点：算法算杂度的分析方法教学B标理解数据抽象的意义熟悉类C语言掌

5、握抽象数据类型的表示和实现方法(4)掌握算法描述和算法分析的方法教学方法和教学手段教学内容安与排板书设计：教1. 3抽象数据类型的表示和实现学数据抽象的意义类C语言过抽象数据类型的表示和实现举例程1. 4算法和算法分析算法教算法的定义算法的特性：有穷性、确定性、可行性、输入、输出学算法设计的要求正确性、可读性、健壮性、效率与低存储呈需求算法效率的度呈过时间度皇的方法分析时间红杂度T(n) = O(f(n)程时间复:杂度的计算算法的存储空间需求S(n) = Q(f(n)师生双边活动：提问：举例：演示实验：教具准备：课后作业1.4,1.20教学后记编号3周次2日期9.10课时安排2课题线性表的类型

6、定义、线性表的顺序表示和实现教材的重点、难点分析重点：顺序表的基本运算(2)WD字表上实现的各种算法的时间性能分析教理解线性表的逻辑结构特征学目熟练掌握顺序表的描述方法、特点及有关概念(3)熟练掌握顺序表的基本运算标教学方法和教学手段教学内容安排与板书设计：教第二章线性表学过线性结构的特点2. 1线性表的类型定义线性表的定义及具表不程线性表的类型定义线性表操作举例：用线性表表不集合、线性表的合并教2. 2线性表的顺序表示和实现线索性表的顺序表示线性表的顺序存储结构的定义及其特征学顺序表的基本运算顺序表的初始化顺序表的插入操作过程顺序表的删除操作顺序表的合并顺序表基本操作的时间曾杂度计算师生双边

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

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

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

10、活动：提问：举例：演示实验：教具准备：课后作业3.15教学后记编号7周次4日期9.24课时安排2课题迷宫求解、表达式求值、栈与递归的实现教材的重点、难点分析我 学 H 标能应用栈解决一些实际问题(2) 了解递归算法执行过程中栈的变化过程教学方法和教学手段教 学 过S教学内容安排与板书设计：3. 2. 4迷宫求解3. 2. 5表达式求值3. 3栈与递归的实现学过若&师生双边活动：提问：举例：演示实验：教具准备：课后 3.19,3.25作业教学后记编号8周次4日期9.27课时安排 2课题队列教材的重点、难点分析重点：队列在两种存储结构上实现的基本运算，难点：循环队列(注意队满队空的条件及它

11、们的描述)教 学H标(1)掌握队列这种数据结构的特点熟悉队列与线性表的关系掌握循环队列和链式队列的五种基本运算(4)能应用队列解决一些实际问题教学方法和教学手段教教学内容安排与板书设计：3. 4队列学3. 4. 1抽象数据类型队列的定义队列的定义(FIFO)过队列的类型定义程3. 4. 2链队列一队列的住式表不和实现单链队列的定义单链队列的操作3. 4. 3循环队列一队列的顺序表不和实现教队列的顺序存储结构循环队列的基本操作学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业3.29教学后记编号9周次. 日期10.1课时安排2课题机动教材的重点、难点分析教学B标教学方法和教学手段教学内

12、容安排与板书设计：教学过程教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号10周次3日期10.4课时安排2课题习题课教材的重点、难点分析教学B标教学讲授法方法和教学手段教学内容安排与板书设计：教学过程教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号11周次6日期10.8课时安排2课题串类型的定义、串的表示和实现教材重点：串的基本运算的重点、难点难点：串的动态存储结构分析敦熟悉串的有关概念，串与线性表的关系掌握串的静态存储结构与动态存储结构和它们的优缺点学熟练掌握串的基本运算B标教学方法和教学手段教学内容安排与板书设计：教第四章串学4. 1串类

13、型的定义串的概念过串类型的定义程4. 2串的表示和实现4. 2. 1定长顺序存储表示串的定长顺序存储表示串联接教求于串4. 2. 2堆分配存储表示串的堆分配存储表示学堆的基本操作4. 2. 3串的块链存储表示过程师生双边活动：提问：举例：演示实验：教具准备：课后4.17,4.22/4.24作业教学后记编号12周次6日期10.11课时安排2课题串的模式匹配算法、串操作应用举例教材的重点、难点分析教理解串的模式匹配算法了解串的应用学B标教学方法和教学手段教学内容安排与板书设计：教4. 3串的模式匹配算法学4. 3. 1求子串位童的定位函数4. 3. 2模式匹配的一种改进算法过KMP算法程4. 4串

14、操作应用举例4. 4. 1文本编辑教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业4.8教学后记编号13周次7日期10.15课时安排2课题教组的定义、顺序表示和实现、矩阵的压缩存储教材的重点、难点分析重点：多维数组的存储方式矩阵的压缩存储方式难点：稀吭矩阵的压缩存储表示下实现的算法教熟悉数组的按行（列）优先顺序的存储结构中的地址计算方法熟悉特殊矩阵在压缩存储时的下标变换学理解稀政矩阵的三兀组和十字链表两种压缩存储表不目标教学方法和教学手段教学内容安排与板书设计：教第五章数组和广义表学5. 1数组的定义数组的类型定义过二维数组程教5. 2数组的顺序表示和实现一维数组的存储方式教组的

15、顺序存储表示和实现学5. 3矩阵的压缩存储过5. 3. 1特殊矩阵对称矩阵程对角矩阵5. 3.2稀疏矩阵稀琉矩阵的类型定义1、二兀组顺序表师生双边活动：提问：举例：演示实验：教具准备：课后作业5.21教学后记编号14周次7日期10.18课时安排 2课题稀疏矩阵的存储结构、广义表的定义和存储结构教材重点：广义表的定义及其运算的重点、难点分析我 学 H 标掌握稀城矩阵的存储结构熟悉广义表的有关概念和运算掌握广义表的两种存储结构教学方法和教学手段教 学 过S教学内容安排与板书设计：2、行逻辑链接的顺序表3、十字链表5. 4广义表的定义广义表的类型定义广义表举例广义表的特点教5. 5广义表的存储结构学

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

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

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

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

20、讲授法方法和教学手段教学内容安排与板书设计：教6. 6赫夫曼树学6. 6. 1最优二叉树是优二叉树的概念过构造赫夫曼树程是优判定算法6. 6. 2赫夫曼编码求赫夫曼编码教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业6.26教学后记编号20周次10日期11.8课时安排2课题习题课教材的重点、难点分析教学a标教学讲授法万延和教学手段教学内容安排与板书设计：教学过程学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号21周次11日期11.12课时安排2课题图的定义和术语、图的存储结构教材重点：图的存储的重点、难点分析教熟悉图的有关术语和概念(2)熟练掌握图的四种存

21、储结构和建立算法学B标教学方法和教学手段敦教学内容安排与板书设计：第七章图学7. 1图的定义和术语过图的类型定义图的分类程连通图、连通分皇、生成树7. 2图的存储结构7. 2. 1数组表示法图的邻接矩阵网及其邻接矩阵教7. 2. 2邻接表rrst 9 J 人一|/ -八 I - 图的邻接表存储表不邻接表和逆邻接表学过程师生双边活动：提问：举例：演示实验：教具准备：课后7.14J.15作业教学后记编号22周次11日期11.15课时安排2课题十字捱表、把接多重表、图的遍历教材的重点、难点分析重点：图的遍历难点：图的遍历非递归算法教学目标熟练掌握图的四种存储结构和建立算法熟练掌握图的深度优先遍历和广

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

23、4. 3是小生成树Prim算法Kruskal 算法学7. 4. 3关节点和重,连通分皇过程师生双边活动：提问：举例：演示实验：教具准备：课后作业7.32教学后记教材编号24周次12日期11.22课时安排2课题有向无环图及其应用重点：拓扑排序的重(2)求关键踣径点、难点难点：求关键脂径分析我掌握拓扑排序的方法掌握关键跖径的求法学H标教学方法和教学手段教学内容安排与板书设计：教7. 5有向无环图及其应用学DAG7. 5. 1拓扑排序过7. 5. 2关键跖径SAOE网关键跆径学过程师生双边活动：提问：举例：演示实验：教具准备：课后7.36作业教学后记编号25周次13日期11.26课时安排2课题最短跆

24、径教材重点:求昊短蹈径的重点、难点难点：求每一对顶点之间的最短跖径分析效练掌握从某个源点到其余各顶点的悬短跆径的求法教掌握求每一对顶点之间的悬短跖径的求法学H标教学方法和教学手段教教学内容安排与板书设计：7. 6星短跖径学7. 6. 1从某个源点到其余各顶点的是短跖径Dijkstra 算法过程7. 6. 2每一对顶点之间的晟短跖径教学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业7.42教学后记编号26周次13日期11.29课时安排2课题静态查找表教材的重点、难点分析重点：顺序查找(2)折半查找教熟练掌握静态查找的各种方法B标教学和教学手段教学内容安排与板书设计：教第八章查找学查找

25、表与静态且找表和动态查找表关键字与主关键字和次关键字过查找与成功和不成功程教8. 1静态查找表静态查找表的类型定义8. 1. 1顺序表的查找学顺序查找平均查找长度8. 1. 2有序表的查找过折半查找折半查找的性能分析8. 1. 3静态树表的查找程8. 1. 4索引顺序表的查找表具索引表分块查找师生双边活动：提问：举例：演示实验：教具准备：课后作业9.29教学后记编号27周次14日期12.3课时安排2课题二叉排序树和平衡二叉树教材的重重点：动态查找表及查找算法二叉排序树点、难点分析难点：二叉排序树教学目标熟练掌握一叉排序树的构造方法及查找过程掌握AVL树的构造教学 方法 和教学手段教学过程教学内

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

27、. 2B.树和B+树过1、B.树及其查找程2、B.树查找分析3、B.树的插入和删除4、B+树教8.2. 3键树学过程师生双边活动：提问：举例：演示实验：教具准备：课后作业教学后记编号29周次15日期12.10课时安排2课题哈希表教材的重点、难点分析难点：哈希表及查找算法教学B标熟练掌握哈希表的建表方法、冲突的处理及查找过程理解哈希表与其它存储结构的表的本质区别熟练掌握哈希表的平均查找长度的计算（等概率）教学方法相教学手段教学内容安排与板书设计：教8. 3哈希表学8.3.1什么是哈希表哈希函教过冲突程散列8. 3. 2哈希函数的构造方法1、直接定址法教2、数字分析法3、平方取中法学4、折叠法5、

28、除留余数法6、随机数法过8. 3. 3处理冲突的方法1、开放定址法2、再哈希法程3、链地址法4、建立一个公共溢出区8. 3. 4哈希表的查找及其分析师生双边活动：提问：举例：演示实验：教具准备：课后作业9.46教学后记编号30周次15日期12.13课时安排2课题排序概述、插入排序教材重点：希尔排序的重点、难点分析教深刻理解插入排序的基本思想及其特点学熟练掌握插入排序方法的排序过程目掌握插入排序算法时间复杂度的分析方法并熟记其分析结论标教学方法和教学手段教学内容安排与板书设计：教第九章排序学过9. 1排序概述排序排序方法的稳定性程内部排序与外部排序教9. 2插入排序9. 2. 1直接插入排序学9. 2. 2其他插入排序1、折半插入排序2、2-跖插入排序过程3、表插入排序9. 2. 3希尔排序师生双边活动：提问：举例：演示实验：教具准备：课后作业10.25教学后记编号31周次16日期12.17课时安排2课题快速排序、选择排序教材重点：快速排序的重(2)堆排序点、难点难点：快速排序(2)堆排序分析教深刻理解快速排序的基本思想及其特点(2)熟练掌握快速排序方法的排序过程学掌握快速排序算法时间使杂度的分析方法并熟记其分析结论B(4)