《数据结构》教案教学文案Word格式.docx
《《数据结构》教案教学文案Word格式.docx》由会员分享，可在线阅读，更多相关《《数据结构》教案教学文案Word格式.docx（64页珍藏版）》请在冰点文库上搜索。
3：
掌握各种算法的时空效率的分析方法，学会在实际应用中选择合适的算法。
4：
掌握各种查找和排序的算法以及效率，并将其应用在程序设计中。
三、课程教学内容体系
第一章：
概论
1.1什么是数据结构
1.2基本概念和术语
1.3抽象数据类型的表现与实现
1.4算法和算法分析
教学要求：
理解数据、数据元素、数据项的概念；
掌握逻辑结构和存储结构的关系；
理解算法的基本概念；
学会分析算法的时间复杂性和空间复杂性。
第二章：
线性表
2.1线性表的类型定义
2.2线性表的顺序表示和实现
2.3线性表的链式表示和实现（静态查找表不讲）
2.4一元多项式的表示及相加
理解线性表的定义和特点；
掌握顺序表和链表的特点，掌握在这两种存储结构上各种基本运算的实现算法以及效率的分析，并学习在这两种存储结构上进行算法设计的方法；
以达到利用基本算法进行较复杂算法设计的目的。
第三章：
栈、队列
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求字串位置的定位函数
了解串的概念，掌握串的基本运算，学习串运算在不同存储结构下的实现过程。
第五章：
多维数组和广义表
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赫夫曼编码
理解树型结构的概念和术语，领会二叉树的定义、形态、性质和存储结构，掌握二叉树的各种遍历算法极其实现过程，了解树和森林及其相互转换；
掌握哈夫曼树极其应用。
第七章：
图
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从某个源点到其余各顶点的最短路径
教学要求：
理解图型结构的概念和术语，掌握图的邻接矩阵和邻接表两种存储形式，理解图的遍历的基本思想，掌握图的两种遍历的方法和其实现的过程，学会图在最小生成树、拓扑排序、最短路径、关键路径中的应用。
第九章：
查找
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简单选择排序
10.5归并排序
熟练掌握各种排序方法的思想和特点，如：
插入排序、交换排序、选择排序、分配排序等，学会分析它们的优点和缺点以及时空性能，并学会选择和应用各种排序方法解决实际问题。
四、学时分配
章节内容
讲授学时
上机学时
习题学时
一
概论
4
二
6
1
三
四
2
五
数组和广义表
六
树和二叉树
8
七
九
十
60课时
44
五、推荐教材及教学参考书
1.教材
《数据结构》；
严蔚敏编著；
清华大学出版社
2.教学参考书
《算法与数据结构（C语言版）》，范策等编著，机械工业出版社，2004
《数据结构（C语言版）》，严蔚敏等编著，清华大学出版社2004
《数据结构与算法》，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004
《数据结构实用教程（第二版）》，徐孝凯编著，清华大学出版社2006
《数据结构辅导与提高实用教程（第二版）》，徐孝凯，清华大学出版社2003
《数据结构》，谢楚屏等，人民邮电出版社，2001
《算法与数据结构－C语言描述》，张乃孝等，高等教育出版社，2002
《数据结构》，殷人昆，清华大学出版社，2001
《计算机算法设计与分析》，苏德富，电子工业出版社，2001
《算法与数据结构》，傅清祥，王哓冬，电子工业出版社，1998
《数据结构－C++与面向对象的途径》，张乃孝，裘宗燕，高等教育出版社，2001
《数据结构－用面向对象方法与C++描述》，殷人昆等清华大学出版社
《算法设计与分析》，梁田贵，张鹏编著，冶金工业出版社，2004
六、考核办法和成绩评定标准
根据教学要求进行期末考试，由任课教师根据完成情况进行评定，并最终结合平时成绩的考核给出综合成绩。
制定：
制定日期：
教案（首页）
授课时间教案编写时间
课程名称
课程代码
总学时
讲课：
学时
上机：
实习：
周
学分
课程性质
必修课（√）选修课（）
理论课（√）实验课（）
任课教师
职称
授课对象
专业：
年级：
班级：
教材
和
主要参考资料
选用教材：
《数据结构》，严蔚敏编著清华大学出版社
主要参考书：
《算法与数据结构（C语言版）》，范策，周世平，胡哓琨等编著，机械工业出版社，2004
教学目的和
教学要求
1．
系统学习常用基本数据结构及其在不同存储方式下的实现，掌握分析、选择不同的数据结构和存储结构的原则和方法。
2．
学习和掌握在各种存储结构上实现的各种算法及其设计思想，从而学习各种分析问题和解决问题的能力。
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次课
第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.1
3.2.4、3.2.5、3.3
3.4
综合习题课
（1）：
前3章的相关内容
综合实验课
（1）：
第4章串：
4.1、4.2.1、4.2.2、4.2.3、4.3.1
第5章数组和广义表：
5.1、5.2
5.3
综合实验课
（2）：
第4-5章的相关内容
第6章树和二叉树：
6.1、6.2
6.3、6.4.1
6.4.2、6.6
综合习题课
（2）：
树的相关内容
第7章图：
7.1、7.2
7.3、7.4.1、7.4.3
7.6
综合习题课（3）：
图的相关内容
第9章查找：
9.1、9.3
综合实验课（3）：
第9章的相关内容
第10章内部排序：
10.1、10.2
10.3、10.4
第9、10章的相关内容
综合实验课（4）：
第10章的相关内容
学时
备注
教案（分教案）
课次：
1学时：
章节
教学目的
了解数据结构的课程性质、内容、应用领域及其与其他学科的关系；
掌握数据结构的相关概念和术语；
掌握四类基本的数据关系。
教 学
重点
难点
教学重点：
数据结构的相关概念和术语
教学难点：
四类基本的数据关系
（含章节
教学内容、学时分配、
教学方法、辅助手段）
教学进程：
计算机的应用不再局限于科学计算，更多地用于控制，管理，数据处理等非数值计算的处理工作。
计算机加工处理的对象：
数值，字符，表格，图形声音，图象等具有一定结构的数据。
进行程序设计时必须分析待处理的对象的特性及各对象之间存在的关系———产生背景。
1.2数据结构的基本概念和术语
1.数据（Data）
2.数据元素（DataElement）
3.数据对象（DataObject）
4.结构（DataStructure）存储结构、抽象数据类型
抽象数据类型（AbstractDataType）
ADT的定义格式不唯一,我们采用下述格式定义一个ADT:
ADT抽象数据类型名{
数据对象:
<
数据对象的定义>
数据关系:
结构关系的定义>
基本操作:
基本操作的定义>
}ADT抽象数据类型名
教学方法、课堂讲解、例题演示，课件演示
辅助手段：
电脑、投影仪、教科书
作 业
图1.5：
要求理解和掌握四类基本的数据关系；
并在日常生活中举例进行说明。
主要
参考资料
课后自我总结分析
备注
2学时：
理解抽象数据类型的表示及实现；
对算法、算法要求、算法效率的度量进行有效的分析。
抽象数据类型的表示及实现；
算法、算法要求；
算法效率的度量及有效的分析；
1.3抽象数据类型的表示和实现
1.4算法
1.算法（Algorithm）的定义
Algorithmisafinitesetofruleswhichgivesasequenceofoperationforsolvingaspecifictypeofproblem.（算法是规则的有限集合，是为解决特定问题而规定的一系列操作。
）是指令的有限序列，其中每一条指令表示一个或多个操作。
2.算法的特性
3.算法设计的要求
１）算法的正确性
（1）所设计的程序没有语法错误；
（2）所设计的程序对于几组输入数据能够得出满足要求的结果；
（3）所设计的程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得到满足要求的结果。
（4）程序对于一切合法的输入数据都能产生满足要求的结果。
2）可读性
3）健壮性
4）高效率和低存储量、算法、语言和程序的关系
时间复杂度
1:
图1.5、P13：
算法的5个特征；
2:
P15：
两段程序的语句的频度的分析
3学时：
掌握顺序表以达到利用基本算法进行较复杂算法设计的目的。
线性表的定义和特点；
线性表的顺序表示
线性结构的特点：
在数据元素的非空有限集中，
•存在唯一的一个被称为“第一个”的数据元素；
•存在唯一的一个被称为“最后一个”的数据元素；
•除第一个元素之外，集合中的每个元素均只有一个前驱；
•除最后一个元素之外，集合中的每个元素均只有一个后继。
2.1.1线性表的逻辑结构
2.1.2线性表的抽象数据类型定义
2.2线性表的顺序表示和实现
2.2.1线性表的顺序存储结构
2.2.2线性表顺序存储结构上的基本运算
1.初始化操作2.插入操作3.删除操作
算法2.1
算法2.3
算法2.1、图2.2、算法2.4
算法2.5、算法2.6
4学时：
理解线性表的链表的特点，掌握在这种存储结构上各种基本运算的实现算法以及效率的分析，并学习在这种存储结构上进行算法设计的方法；
线性表的链式表示和实现；
单链表的插入、删除、查找和归并操作；
2.3线性表的链式表示和实现
2.3.1单链表
线性表的链式存储：
图2.6单链表的逻辑状态
图2.7带头结点单链表图示
2.3.2单链表上的基本运算
1.建立单链表
2.查找
3.单链表插入操作
4.删除
5．合并单链表：
图2.5、图2.8、图2.9
算法2.8、算法2.9、算法2.10、算法2.11
5学时：
理解线性表的链表的特点，掌握在这种存储结构上各种基本运算的实现算法以及效率的分析；
掌握一元多项式的表示及相加的方法与算法。
循环链表、双向链表及其算法；
一元多项式的表示及相加的方法与算法；
双向链表及其算法、一元多项式相加的方法；
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.23
6学时：
3.1栈、3.2.1数制转换
理解栈的定义、特点，学习它的各种组织方
升级会员 