《数据结构》教案教学文案Word格式.docx

1、3：掌握各种算法的时空效率的分析方法，学会在实际应用中选择合适的算法。4：掌握各种查找和排序的算法以及效率，并将其应用在程序设计中。三、课程教学内容体系第一章：概论1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表现与实现1.4 算法和算法分析教学要求：理解数据、数据元素、数据项的概念；掌握逻辑结构和存储结构的关系；理解算法的基本概念；学会分析算法的时间复杂性和空间复杂性。第二章：线性表2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现（静态查找表不讲）2.4 一元多项式的表示及相加理解线性表的定义和特点；掌握顺序表和链表的特点，掌握在这两种

2、存储结构上各种基本运算的实现算法以及效率的分析，并学习在这两种存储结构上进行算法设计的方法； 以达到利用基本算法进行较复杂算法设计的目的。第三章：栈、队列3.1 栈3.2 栈的应有和举例3.2.1 数制转换3.3.4 迷宫求解3.3 栈与递归的实现3.4 队列理解栈和队列的定义、特点，学习它们的各种组织方式及算法；掌握它们的空和满的判断条件；并学会它们的简单应用。第四章：串4.1 串类型的定义4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.3 串的块链存储表示4.3 串的模式匹配算法 4.3.1 求字串位置的定位函数了解串的概念，掌握串的基本运算，学习串运算在不同存储结构下的实现

3、过程。第五章：多维数组和广义表5.1 数组的定义5.2 数组的顺序表现和实现5.3 矩阵的压缩存储领会数组的定义，数组的两种顺序存储结构，并领会几种特殊矩阵和稀疏矩阵的压缩存储方法。第六章：树6.1 树的定义和基本术语6.2 二叉树6.2.1 二叉树的定义6.2.2 二叉树的性质6.2.3 二叉树的存储结构6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树6.4 树和森林6.4.1 树的存储结构6.4.2 森林与二叉树的转换6.4.3 树和森林的遍历6.6 赫夫曼树及其应用6.6.1 最优二叉树（赫夫曼树）6.6.2 赫夫曼编码理解树型结构的概念和术语，领会二叉树的定义、形态、性质和存储结构

4、，掌握二叉树的各种遍历算法极其实现过程，了解树和森林及其相互转换；掌握哈夫曼树极其应用。第七章：图7.1 图的定义和术语7.2 图的存储结构7.2.1 数组表示法7.2.2 邻接表7.2.3 十字链表7.2.4 邻接多重表7.3 图的遍历7.3.1 深度优先搜索7.3.2 广度优先搜索7.4 图的连通性问题7.4.1 无向图的连通分量和生成树7.4.3 最小生成树7.5 有向无环图及其应用7.5.1 拓扑排序7.5.2 关键路径7.6 最短路径7.6.1 从某个源点到其余各顶点的最短路径 教学要求：理解图型结构的概念和术语，掌握图的邻接矩阵和邻接表两种存储形式，理解图的遍历的基本思想，掌握图的

5、两种遍历的方法和其实现的过程，学会图在最小生成树、拓扑排序、最短路径、关键路径中的应用。第九章：查找9.1 静态查找表9.1.1 顺序表的查找9.1.2 有序表的查找9.1.4 索引顺序表的查找9.3 哈希表9.3.1 什么是哈希表9.3.2 哈希函数的构造方法9.3.3 处理冲突的方法教学要求：掌握查找表的定义和分类，熟练掌握顺序查找和二分查找的思想，了解二叉排序树及其查找，了解散列查找的思想和有关方法。第十章：内部排序10.1 概述10.2 插入排序10.2.1 直接插入排序10.2.2 其他插入排序（表的插入排序不讲）10.2.3 希尔排序10.3 快速排序10.4 选择排序10.4.1

6、 简单选择排序10.5 归并排序熟练掌握各种排序方法的思想和特点，如：插入排序、交换排序、选择排序、分配排序等，学会分析它们的优点和缺点以及时空性能，并学会选择和应用各种排序方法解决实际问题。四、学时分配章节内容讲授学时上机学时习题学时一概 论4二61三四2五数组和广义表六树和二叉树8七九十60课时44五、推荐教材及教学参考书1. 教材数据结构；严蔚敏编著；清华大学出版社2. 教学参考书算法与数据结构（C语言版）， 范策等编著，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004数据结构

7、实用教程（第二版），徐孝凯编著，清华大学出版社 2006数据结构辅导与提高实用教程（第二版），徐孝凯，清华大学出版社 2003数据结构，谢楚屏等，人民邮电出版社，2001算法与数据结构C语言描述，张乃孝等，高等教育出版社，2002数据结构，殷人昆，清华大学出版社，2001计算机算法设计与分析，苏德富，电子工业出版社，2001算法与数据结构，傅清祥，王哓冬，电子工业出版社，1998数据结构C+与面向对象的途径，张乃孝，裘宗燕，高等教育出版社，2001数据结构用面向对象方法与C+描述，殷人昆等清华大学出版社算法设计与分析，梁田贵，张鹏编著，冶金工业出版社，2004六、考核办法和成绩评定标准根据教学

8、要求进行期末考试，由任课教师根据完成情况进行评定，并最终结合平时成绩的考核给出综合成绩。 制定：制定日期：教案（首页） 授课时间 教案编写时间 课程名称课程代码总学时讲课： 学时上机：实习： 周学 分课程性质必修课（） 选修课（ ）理论课（） 实验课（ ）任课教师职称授课对象专业： 年级： 班级：教材和主要参考资料选用教材： 数据结构， 严蔚敏编著 清华大学出版社主要参考书：算法与数据结构（C语言版）， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004教学目的和教学要求1 系统学习常用基本数据结构及其在不同存储方式下的实现，掌握分析、选择不同的数据结构和存储结构的原则和方法。2 学习和

9、掌握在各种存储结构上实现的各种算法及其设计思想，从而学习各种分析问题和解决问题的能力。3 掌握各种算法的时空效率的分析方法，学会在实际应用中选择合适的算法。4 掌握各种查找和排序的算法以及效率，并将其应用在程序设计中。教学重点和教学难点重点掌握数据结构之间的逻辑结构、存储结构和对其施加的运算，如：应掌握各种查找和排序的算法。难点章节：树和第七章：图。教学进程第1次课第2次课第3次课第4次课第5次课第6次课第7次课第8次课第9次课第10次课第11次课第12次课第13次课第14次课第15次课第16次课第17次课第18次课第19次课第20次课第21次课第22次课第23次课第24次课第25次课第26次

10、课第27次课第28次课第29次课第30次课授课章节第1章 绪论：1.1 什么是数据结构、1.2 基本概念和术语第1章：1.3 抽象数据类型的表现与实现1.4 算法和算法分析第2章 线性表：2.1 线性表的类型定义2.2 线性表的顺序表示第2章 ：2.3 线性表的链式表示和实现（1）2.3 （2）2.4 一元多项式的表示及相加第3章 栈和队列：3.1、3.2.13.2.4、3.2.5、3.33.4综合习题课（1）：前3章的相关内容综合实验课（1）：第4章 串：4.1、4.2.1、4.2.2、4.2.3、4.3.1第5章 数组和广义表：5.1、5.25.3综合实验课（2）：第4-5章的相关内容第6

11、章 树和二叉树：6.1、6.26.3、6.4.16.4.2、6.6综合习题课（2）：树的相关内容第7章 图：7.1、7.27.3、7.4.1、7.4.37.6综合习题课（3）：图的相关内容第9章 查找：9.1、9.3综合实验课（3）：第9章的相关内容第10章 内部排序：10.1、10.210.3、10.4第9、10章的相关内容综合实验课（4）：第10章的相关内容学 时备 注教案（分教案）课次：1 学时：章 节教学目的了解数据结构的课程性质、内容、应用领域及其与其他学科的关系；掌握数据结构的相关概念和术语；掌握四类基本的数据关系。教学重 点难 点教学重点： 数据结构的相关概念和术语教学难点： 四

12、类基本的数据关系（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：计算机的应用不再局限于科学计算，更多地用于控制，管理，数据处理等非数值计算的处理工作。计算机加工处理的对象：数值，字符，表格，图形声音，图象等具有一定结构的数据。进行程序设计时必须分析待处理的对象的特性及各对象之间存在的关系产生背景。1.2 数据结构的基本概念和术语 1. 数据（Data） 2. 数据元素（Data Element）3. 数据对象（Data Object） 4. 结构（Data Structure）存储结构、抽象数据类型抽象数据类型 （Abstract Data Type） ADT的定义格式不唯一, 我

13、们采用下述格式定义一个ADT: ADT 抽象数据类型名 数据对象: 数据关系:结构关系的定义 基本操作:基本操作的定义 ADT 抽象数据类型名教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业图1.5：要求理解和掌握四类基本的数据关系；并在日常生活中举例进行说明。主要参考资料课后自我总结分析备注2 学时：理解抽象数据类型的表示及实现；对算法、算法要求、算法效率的度量进行有效的分析。 抽象数据类型的表示及实现；算法、算法要求； 算法效率的度量及有效的分析；1.3 抽象数据类型的表示和实现1.4 算 法 1. 算法（Algorithm）的定义 Algorithm is a f

14、inite set of rules which gives a sequence of operation for solving a specific type of problem. （算法是规则的有限集合， 是为解决特定问题而规定的一系列操作。） 是指令的有限序列，其中每一条指令表示一个或多个操作。2. 算法的特性3. 算法设计的要求） 算法的正确性 （1） 所设计的程序没有语法错误； （2） 所设计的程序对于几组输入数据能够得出满足要求的结果； （3） 所设计的程序对于精心选择的典型、 苛刻而带有刁难性的几组输入数据能够得到满足要求的结果。 （4） 程序对于一切合法的输入数据都能产生

15、满足要求的结果。2） 可读性 3） 健壮性 4） 高效率和低存储量 、算法、 语言和程序的关系 时间复杂度1:图1.5、P13：算法的5个特征；2:P15：两段程序的语句的频度的分析3 学时：掌握顺序表以达到利用基本算法进行较复杂算法设计的目的。线性表的定义和特点；线性表的顺序表示线性结构的特点：在数据元素的非空有限集中， 存在唯一的一个被称为“第一个”的数据元素； 存在唯一的一个被称为“最后一个”的数据元素； 除第一个元素之外，集合中的每个元素均只有一个前驱； 除最后一个元素之外，集合中的每个元素均只有一个后继。2.1.1 线性表的逻辑结构2.1.2 线性表的抽象数据类型定义2.2 线性表的

16、顺序表示和实现 2.2.1 线性表的顺序存储结构2.2.2 线性表顺序存储结构上的基本运算1. 初始化操作 2. 插入操作 3. 删除操作算法2.1算法2.3算法2.1、图2.2、算法2.4算法2.5、算法2.64 学时：理解线性表的链表的特点，掌握在这种存储结构上各种基本运算的实现算法以及效率的分析，并学习在这种存储结构上进行算法设计的方法；线性表的链式表示和实现；单链表的插入、删除、查找和归并操作；2.3 线性表的链式表示和实现 2.3.1 单链表线性表的链式存储：图2.6 单链表的逻辑状态图2.7 带头结点单链表图示2.3.2 单链表上的基本运算 1. 建立单链表2. 查找3. 单链表插

17、入操作4. 删除5合并单链表：图2.5、图2.8、图2.9算法2.8、算法2.9、算法2.10、算法2.115 学时：理解线性表的链表的特点，掌握在这种存储结构上各种基本运算的实现算法以及效率的分析；掌握一元多项式的表示及相加的方法与算法。 循环链表、双向链表及其算法；一元多项式的表示及相加的方法与算法；双向链表及其算法、一元多项式相加的方法；2.3.3 循环链表2.3.4 双向链表1. 双向链表的前插操作2. 双向链表的删除操作2.3.6 顺序表和链表的比较 1. 基于空间的考虑、2. 基于时间的考虑、3. 基于语言的考虑图2.12、图2.14、图2.15、图2.16、图2.17、图2.18算法2.18、算法2.19、算法2.236 学时：3.1 栈、3.2.1 数制转换理解栈的定义、特点，学习它的各种组织方