数据结构教案课程

1、2015至2016学年第二学期数据结构 课程 教 案课程编码： 1261D03总学时/周学时：80/5开课时间：2016年2月24日第1周至第16周授课年级、专业、班级： 15级网工程2班使用教材 严蔚敏.数据结构（C语言版）M北京：清华大学出版社， 2011.系别/教研室：信息工程学院/物联网工程授课教师：刘波教学目标：数据结构是物联网工程专业的一门专业必修课。用计算机解决任何问题都需要进行数据表示和数 据处理，而数据表示和数据处理正是数据结构要研究的内容。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程教学，使学生了解数据结构的基本概念，理

2、解数据结构的逻辑结构和物理结构的基本概念以及有关算法，掌握算法描述及算法的评价标准，熟悉在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会，旨在培养学生基本的、良好的程序设计技能，编制高效可靠的程序，并为学生日后学习操作系统和数据库等后续课程奠定基础。教学要求 :本课程主要是以抽象数据类型的观点来组织和讲解线性表、栈、队列、树、二叉树、图等各种主要的数学模型并定义为相应的抽象数据类型，给出各种物理表示法和有关算法，关于数据处理技术介绍几种主要的排序和查找算法。学生通过学习该课程后主要应掌握以下内容：1 了解数据结构及有关的基本概念；2 了解各种抽象数据类型的性质；3 掌握各种抽象

3、数据类型的实现和基本算法；4 对算法的时间和空间复杂性有一定的分析能力；5 能够选择适当的数据结构和存储结构以及设计有效的算法，解决实际问题；6 掌握数据结构在排序和查找等常用算法中的应用。教学重点：抽象数据类型、顺序表、单链表、循环链表、栈、队列、数组、特殊矩阵、树和二叉树、最小生成树、拓扑排序、查找、内部排序教学难点：单链表、栈、循环队列、特殊矩阵、二叉树、关键路径、最短路径教学方法与手段：1 理论部分以讲授法为主，结合讨论及课堂练习实现教学目的。2 传统教学手段与多媒体等现化手段相结合。3 重视实验教学，要求学生利用一切可利用的时间和机会去实验室，实现并验证书本上的各种算法，达到真正实现

4、教学目的。考核与成绩评定方式：本课程为考试科目，课程结束后采用闭卷考试。考核总成绩中，平时成绩占 30% （出勤占 10% ，实验10% ，书面作业占10% ），期末考试占70% ；考核范围为教学大纲规定的基本要求教学内容。教材与主要参考书目：1 .教材严蔚敏、吴伟民.数据结构（C语言版）M北京：清华大学出版社，2011.2 .主要参考书目严蔚敏、李冬梅、吴伟民，数据结构（C语言版）M北京：人民邮电出版社，2011.周次授课章节及主要内容实践教学环节内容实验或课程设计等学时作业主要参考书目11.11.4数据结构基本概念和 术语及ADT,算法和算法分析2.12.2线性表的定义，顺序 实现422.

5、3链式实现；2.4 一元多项式 相加433.13.2栈的定义和应用443.3栈与递归3.4队列454.14.4串的定义和实现模式 匹配，串的应用；5.15.2数组的定义和实现复习C语言的基本操作： 函数实现665.35.5矩阵的压缩存储，广义 表；6.16.2树和二叉树的定 义，二叉树的性质顺序表的操作676.26.3二叉树存储，遍历和线 索二叉树；6.4树和森林单链表的操作686.6赫夫曼树和赫夫曼编码单链表的操作697.1 7.2图的定义、存储；7.3图的遍历栈的应用：括号匹配6107.4图的连通性；7.5拓扑排序、 关键路径队列的应用：模拟病人看 病6117.6最短路径；9.1静态查找表

6、二叉树的遍历及应用6129.2动态查找表；9.3哈希表二叉树的遍历及应用61310.110.4插入、希尔、快速排序图的遍历61410.410.7选择、归并、基数排序，各种排序的比较图的遍历615查找算法设计与实现216排序算法设计与实现217181920第一讲：绪论（一）周次：第1周，第1次授课章节第1章绪论1.11.4任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求1 . 了解数据结构的发展及所处的地位2 .深刻理解数据结构的基本概念和术语3 . 了解抽象数据类型的定义、表示和实现方法4 .掌握算法描述及算法的评价标准5 .理解算法五个要素的确切含义6 .掌握计

7、算语句频度和估算算法时间复杂度的方法教学内容1 .什么是数据结构2 .基本概念和术语3 .抽象数据类型的表示与实现4 .算法设计的要求基本概念和术语5 .算法效率的度量6 .算法的存储空间需求7 .第1章总结与复习及例题讲解教学重点数据结构的概念和术语抽象数据类型的表示与实现算法的五个要素计算语句频度和估算算法时间复杂度教学难点数据结构的意义及数据结构的基本内容 数据结构及数据、数据元素等相关概念 算法描述的方法算法时间复杂度的计算作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授

8、课的详细内容参见讲稿第二讲：线性表（一）周次：第1周，第2次授课章节第2章线性表2.12.2任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求1 .理解线性表的概念、存储结构2 .深刻理解线性表的顺序存储结构的特点、类型描述，熟练掌握插入、删除、查找操作的算法实现教学内容1 .线性表的类型定义2 .线性表的顺序表示和实现教学重点线性表的定义及逻辑上的特点顺序表上插入、删除和定位运算的实现教学难点线性表与线性结构的联系与区别线性表的顺序存储结构及其运算作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结

9、构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第三讲：线性表（二）周次：第2周，第1次授课章节第2章线性表2.3任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求熟练掌握线性表的链式存储结构的特点、类型描述，插入、删除、查找操作的算法实现教学内容线性表的链式表示和实现单链表教学重点单链表的结构特点及类型说明头指针和头结点的作用及区别和指针操作插入、删除、查找运算在单链表上的实现教学难点头结点在链表中的作用和指针的操作单链表存储结构定义，插入、删除运算中的指针操作顺序作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，20

10、11参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第四讲：线性表（三）周次：第2周，第2次授课章节第2章线性表2.3任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求掌握循环链表、双向链表及其基本操作的算法教学内容1 .线性表的链式表示和实现一一循环链表2 .线性表的链式表示和实现一一双向链表3 . 兀多项式的表小及相加教学重点循环链表插入与删除运算的实现双向链表的结构特点及其插入与删除运算的实现教学难点循环链表、双向链表上指针的操作顺序及其相关运算作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华

11、大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第五讲：线性表（四）周次：第3周，第1次授课章节第2章线性表2.3任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求第2章 总结与复习及习题讲解教学内容1 .线性表的链式表示和实现循环链表2 .线性表的链式表示和实现一一双向链表教学重点线性表各存储结构定义，插入、删除等运算的应用教学难点线性表各存储结构定义，插入、删除等运算的应用作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（

12、C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第六讲：栈和队列（一）周次：第3周，第2次授课章节第3章 栈和队列3.13.2任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求1 .理解栈的概念、逻辑特点及存储结构2 .熟练掌握顺序存储和链式存储两种结构下的进栈、出栈的算法教学内容1 .栈的定义2 .栈的应用举例（数制转换，括号匹配）教学重点栈的顺序存储结构进栈、出栈等运算在顺序栈上的实现教学难点顺序栈基本运算的实现顺序栈的溢出判断条件作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结

13、构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第七讲：栈和队列（二）周次：第4周，第1次授课章节第3章 栈和队列3.2, 3.3任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求掌握利用栈实现表达式求值的算法；理解递归算法执行过程中栈的状态变化过程，了解将递归程序转换为非递归程序的方法。教学内容1 .栈的应用举例，如迷宫求解和表达式求值。2 .栈与递归的实现，递归程序转换为非递归程序的方法。教学重点递归算法执行过程中栈的状态变化过程教学难点递归算法执行过程中栈的状态变化过程作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版

14、社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第八讲：栈和队列（三）授课章节第3章栈和队列3.4任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求1.理解队列的概念、存储结构2,熟练掌握顺序存储和链式存储两种结构下的入队、出队的算法教学内容1 .队列的定义2 .链队列队列的链式表示和实现3 .循环队列 一一队列的顺序表示和实现4 .第3章总结与复习及例题讲解教学重点队列的定义及逻辑特点入队、出队等基本运算在顺序、链式队列上的实现教学难点循环队列的队空、队满判断条件；循环队列上的插入、删除操作作业布置课堂

15、练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第九讲：串（一）周次：第5周，第1次授课章节第4章串任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求1 .掌握串的定义、存储方式和常用的串运算2 .熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法3 . 了解串的堆存储结构及块链存储结构4 .掌握串的模式匹配算法的基本算法和改进算法教学内容1 .串类型的定义2 .串的表示和实现3 .串的模式匹配算法4 .串操作应用举例5 .第4章总结与复习

16、及例题讲解教学重点串的两种存储方式字符串的运算串的模式匹配算法教学难点串的模式匹配算法作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第十讲：数组和广义表（一）周次：第5周，第2次授课章节第5章数组和广义表5.15.2任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求掌握多维数组的结构特点和在内存中的两种顺序存储方式教学内容1 .数组的定义2 .数组的顺序表示和实现教学重点多维组的逻辑结构，两种顺序存储方式计算给定元素在存储区中的地

17、址教学难点数组的两种存储表示方法，数组在以行为主的存储结构中的地址计算方法作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第十一讲：数组和广义表（二）周次：第6周，第1次授课章节第5章 数组和广义表5.35.5任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求1 .掌握对特殊矩阵进行压缩存储时的下标变换公式；2 .领会稀疏矩阵的压缩方式和简单运算3 . 了解广义表的定义、表示及存储教学内容1 .矩阵的压缩存储2 .广义表的定义及存储

18、结构3 .第5章总结与复习及例题讲解教学重点对称矩阵、三角矩阵的压缩存储方式稀疏矩阵的二兀组表表小方法了解广义表的定义、表示及存储教学难点稀疏矩阵的压缩存储表示下的运算的实现稀疏矩阵的三类压缩存储方法的特点和适用范围，以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法广义表的结构特点及其存储表示方法作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据结构参考书：严蔚敏、李冬梅.清华大学出版社，2011.数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第十二讲：树和二叉树（一）周次：第6周，第2次授课章节第6章 树和二叉树 6.16.2任课教师严小燕教学方法 与手段多媒

19、体教学与板书相结合课时安排2教学目的与 要求1 .理解树的定义和基本术语2 .深刻理解二叉树的定义、性质及其存储方法3,熟练掌握二叉树的顺序存储方式、结点结构和类型定义教学内容1 .树的定义和基本术语2 .二叉树的定义和性质教学重点二叉树的定义、性质、逻辑特点及五种基本形态、基本运算教学难点二叉树的递归定义作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第十三讲：树和二叉树（二）周次：第7周，第1次授课章节第6章 树和二叉树 6.26.3任课教师严小燕教学方法

20、 与手段多媒体教学与板书相结合课时安排2教学目的与 要求1,熟练掌握二叉树的链式存储方式、结点结构和类型定义2.理解并掌握二叉树的三种遍历算法教学内容1 .二叉树的链式存储结构2 .遍历二叉树教学重点二叉树的链式存储结构及组织方式二叉树的三种遍历方法及其算法教学难点二叉树链式存储结构的组织方式三种遍历的主要区别作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第十四讲：树和二叉树（三）周次：第7周，第2次授课章节第6章 树和二叉树 6.36.4任课教师严小燕教学

21、方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求1 .灵活运用二叉树的遍历方法解决相关的应用问题2 .理解并掌握二叉树的线索化方法3 .熟练掌握森林与二叉树间的相互转换4 . 了解树的简单应用教学内容1 .二叉树的遍历方法的应用2 .线索二叉树3 .树的存储结构4 .森林与二叉树的转换教学重点以遍历为基础在二叉树上实现的几种运算中序线索化森林与二叉树的转换教学难点二叉树上的复杂运算森林与二叉树的转换作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第

22、十五讲：树和二叉树（四）周次：第8周，第1次授课章节第6章树和二叉树6.6任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求掌握哈夫曼树的构造方法教学内容1 .赫夫曼树的定义2 .赫夫曼树的构造教学重点哈夫曼树的构造方法教学难点哈夫曼树的构造方法作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第十六讲：树和二叉树（五）周次：第8周，第2次授课章节第6章树和二叉树6.6任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学

23、目的与 要求掌握哈夫曼编码算法教学内容1 .赫夫曼树的应用2 .第6章总结与复习及例题讲解教学重点哈夫曼编码算法教学难点哈夫曼编码算法作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第十七讲：图（一）周次：第9周，第1次授课章节第7章图7.17.2任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求1 .掌握图的基本概念及术语2 .掌握图的两种存储结构（邻接矩阵和邻接表）的表示方法教学内容1 .图的定义和术语2 .图的存储结构教学重点

24、理解图的定义、术语及其含义各种图的邻接矩阵表示法及其类型说明教学难点正确理解与区别图的常用术语区别图的两种存储结构的不同点及其应用场合作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第十八讲：图（二）周次：第9周，第2次授课章节第7章图7.27.3任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求掌握图的遍历（深度优先搜索遍历和广度优先搜索遍历）算法教学内容1 .图的存储结构2 .图的遍历教学重点图的按深度优先搜索遍历方法和按广度优

25、先搜索遍历方法教学难点图的按深度优先搜索遍历方法和按广度优先搜索遍历方法作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第十九讲：图（三）周次：第10周，第1次授课章节第7章图7.4任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求1 .理解连通分量、生成树和强连通分量的含义2 .掌握最小生成树的构造教学内容1 .无向图的连通分量和生成树2 .有向图的强连通分量3 .最小生成树教学重点生成树和最小生成树的概念由Prim算法思想构造最

26、小生成树教学难点由Prim算法思想构造最小生成树作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第二十讲：图（四）周次：第11周，第1次授课章节第7章图7.5任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求1 .掌握拓扑排序的算法2 .掌握关键路径的算法教学内容1 .拓扑排序2 .关键路径教学重点拓扑排序、关键路径的算法思想教学难点关键路径的算法思想作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，20

27、11参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第二十一讲：图（五）授课章节第7章图7.6任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求掌握最短路径的算法教学内容1 .从某个源点到其余各顶点的最短路径2 .每一对顶点之间的最短路径3 .第7章总结与复习及例题讲解最短路径教学重点最短路径的算法思想教学难点最短路径的算法思想作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第二十二

28、讲： 查找（一）周次：第11周，第2次授课章节第9章查找9.1任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求1 .掌握查找的基本思想及查找成功和不成功的概念2 .掌握在顺序表、有序表上的查找方法和算法教学内容1 .顺序表的查找2 .有序表的查找教学重点查找表的基本概念及查找原理；顺序存储结构、顺序表及其类型说明查找运算在查找表和有序表上的实现教学难点理解查找表的逻辑结构是集合，它的运算以查找为核心作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的

29、详细内容参见讲稿第二十三讲：查找（二）周次：第12周，第1次授课章节第9章 查找9.29.3任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求1 .掌握二叉排序树、平衡二叉树的概念和有关算法2 .掌握哈希表的构造方法教学内容1 .索引顺序表的查找2 .二叉排序树和平衡二叉树3 .什么是哈希表4 .哈希函数的构造方法教学重点平衡二叉排序树的概念哈希表及哈希存储教学难点二叉排序树上的插入算法平衡二叉树的旋转平衡算法作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.

30、备注授课的详细内容参见讲稿第二十四讲：查找（三）周次：第12周，第2次授课章节第9章查找9.3任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求1.掌握哈希表中处理冲突的方法教学内容1 .处理冲突的方法2 .哈希表的查找及其分析3 .第9章 总结与复习及例题讲解教学重点各种哈希表的组织、解决冲突的方法教学难点哈希表上解决冲突的方法作业布置课堂练习使用教材和 主要参考书教材：严蔚敏.数据2构.清华大学出版社，2011参考书：严蔚敏、李冬梅 .数据结构（C语言版）人民邮电出版社，2011.备注授课的详细内容参见讲稿第二十五讲：排序（一）周次：第13周，第1次授课章节第10章排序10.110.2任课教师严小燕教学方法 与手段多媒体教学与板书相结合课时安排2教学目的与 要求1.掌握排序的基本思想和基本概念2,掌握插入排序的基本思想、步骤及算法教学内容1 .排序概述2 .直接插入排序3 .其他插