《数据结构》教案

1、PAGE PAGE 49课程简介人们在运用程序设计语言编写程序的过程中发现所有的数据都可以抽象为三种结构，而对这些数据的所有操作都可以转化为对这三种数据的几种基本操作，而大多数的程序设计技巧都可以抽象为一些最基本的算法。于是人们逐步发展了一门称为数据结构（或数据结构与算法）的计算机科学，它广泛应用于计算机领域。数据结构是信息与计算专业的核心基础课程之一。数据是计算机处理的对象，本课程研究的数据是非数值性、结构性的数据。学习本课程要求掌握各种主要数据结构的特点、计算机内的表示方法，以及处理数据的算法，对于算法所花费的时间和空间代价的分析也要求有一定程度的了解和掌握。通过本课程的学习，使学生透彻地

2、理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养基本的良好的程序设计能力。本课程主要包括如下三个方面的内容：1基本数据结构： 线性表、栈、队列、串、数组和广义表，掌握它们的特点、表示和实现，对静态结构要求非常熟练的编程上机实现，对动态结构要求逐步熟悉链表的表示，通过模仿实验教程中的例子，掌握编程技巧。强调类 C语言的书写规范，特别注意参数的区别，输入输出的方式和错误处理方式，以及抽象数据类型的表示和实现。能熟练完成以下的应用：多项式的计算、语法检查、回朔算法、递归算法、表达式求值、离散事件模拟、文字的编辑和稀疏矩阵进行矩阵运算采用的处理方法。2复杂数据结构： 树、二叉树、图。

3、掌握它们的定义和特点、表示和实现，特别注意与基本数据结构的区别，掌握各种遍历的递归和非递归算法，能熟练完成以下的应用：最优树、Huffman编码、拓扑排序、关键路径和最短路径问题。 3数据结构的应用： 查找和内部排序。熟练掌握静态查找表的查找方法和实现，了解哈希表的构造和查找方法。掌握各种内部排序方法的基本思想、算法特点、排序过程以及它们的时间复杂度分析。数据结构教学大纲课程名称：数据结构课程编号：014100028 适用专业：计算机、信息管理总学时数：60 学分数： 4 一、课程的性质、目的与任务数据结构是计算机科学技术、信息管理等专业的核心课程之一，是一门理论与工程实践密切相关的综合性课程

4、，在计算机学科教学中具有十分重要的作用。大力加强数据结构课程的建设，提高数据结构课程的教学质量，有利于教学改革和教育创新，有利于高级应用型人才和创新人才的培养。数据结构课程是计算机专业的专业基础课程，介绍计算机领域的常用数据结构以及各种查找和排序的算法，是计算机专业学生必修的一门技术基础课程，也是计算机专业的核心课程。数据结构是计算机专业的一门重要的专业基础课，主要解决数据的表示和数据的处理，系统介绍三大数据结构及其实现，为操作系统等课程提供必要的知识基础，为计算机人员提供必要的基本技能。二、课程教学基本要求本课程介绍常用数据结构之间的逻辑结构、存储结构和对其施加的运算，如：线性表、栈、队列、

5、串、数组、广义表、树、图等。同时还介绍各种查找和排序的算法。通过本门课程的学习，应使学生掌握以下几个方面的知识：1：系统学习常用基本数据结构及其在不同存储方式下的实现，掌握分析、选择不同的数据结构和存储结构的原则和方法。2：学习和掌握在各种存储结构上实现的各种算法及其设计思想，从而学习各种分析问题和解决问题的能力。3：掌握各种算法的时空效率的分析方法，学会在实际应用中选择合适的算法。4：掌握各种查找和排序的算法以及效率，并将其应用在程序设计中。三、课程教学内容体系第一章：概论1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表现与实现1.4 算法和算法分析教学要求：理解数据、数

6、据元素、数据项的概念；掌握逻辑结构和存储结构的关系；理解算法的基本概念；学会分析算法的时间复杂性和空间复杂性。第二章：线性表2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现（静态查找表不讲）2.4 一元多项式的表示及相加教学要求：理解线性表的定义和特点；掌握顺序表和链表的特点，掌握在这两种存储结构上各种基本运算的实现算法以及效率的分析，并学习在这两种存储结构上进行算法设计的方法； 以达到利用基本算法进行较复杂算法设计的目的。第三章：栈、队列3.1 栈3.2 栈的应有和举例3.2.1 数制转换3.3.4 迷宫求解3.3 栈与递归的实现3.4 队列教学要求：理解

7、栈和队列的定义、特点，学习它们的各种组织方式及算法；掌握它们的空和满的判断条件；并学会它们的简单应用。第四章：串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

8、 二叉树的定义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 图

9、的遍历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 什么是哈希表

10、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 归并排序教学要求：熟练掌握各种排序方法的思想和特点，如：插入排序、交换排序、选择排序、分配排序等，学会分析它们的优点和缺点以及时空性能，并学会选择和应用各种排序方法解决实际问题。四、学时分配章节内容讲授学时上

11、机学时习题学时一概 论400二线性表611三栈、队列611四串211五数组和广义表411六树和二叉树811七图811九查找211十内部排序411总学时数：60课时4488五、推荐教材及教学参考书1. 教材数据结构；严蔚敏编著；清华大学出版社2. 教学参考书算法与数据结构（C语言版）， 范策等编著，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004数据结构实用教程（第二版），徐孝凯编著，清华大学出版社 2006数据结构辅导与提高实用教程（第二版），徐孝凯，清华大学出版社 2003数据结构

12、，谢楚屏等，人民邮电出版社，2001算法与数据结构C语言描述，张乃孝等，高等教育出版社，2002数据结构，殷人昆，清华大学出版社，2001计算机算法设计与分析，苏德富，电子工业出版社，2001算法与数据结构，傅清祥，王哓冬，电子工业出版社，1998数据结构C+与面向对象的途径，张乃孝，裘宗燕，高等教育出版社，2001数据结构用面向对象方法与C+描述，殷人昆等清华大学出版社算法设计与分析，梁田贵，张鹏编著，冶金工业出版社，2004六、考核办法和成绩评定标准根据教学要求进行期末考试，由任课教师根据完成情况进行评定，并最终结合平时成绩的考核给出综合成绩。 制定：制定日期：教案（首页） 授课时间 教案

13、编写时间 课程名称数据结构课程代码总学时讲课： 学时上机： 学时实习： 周学 分课程性质必修课（） 选修课（ ）理论课（） 实验课（ ）任课教师职称授课对象专业： 年级： 班级： 教材和主要参考资料选用教材： 数据结构， 严蔚敏编著 清华大学出版社主要参考书：算法与数据结构（C语言版）， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004数据结构实用教程（第二版），徐孝凯编著，清华大学出版社 2006数据结构辅导与提高实用教程（第二版），徐孝凯，清华大学出

14、版社 2003数据结构，谢楚屏等，人民邮电出版社，2001算法与数据结构C语言描述，张乃孝等，高等教育出版社，2002数据结构，殷人昆，清华大学出版社，2001计算机算法设计与分析，苏德富，电子工业出版社，2001算法与数据结构，傅清祥，王哓冬，电子工业出版社，1998数据结构C+与面向对象的途径，张乃孝，裘宗燕，高等教育出版社，2001数据结构用面向对象方法与C+描述，殷人昆等清华大学出版社算法设计与分析，梁田贵，张鹏编著，冶金工业出版社，2004教学目的和教学要求通过本门课程的学习，应使学生掌握以下几个方面的知识：1 系统学习常用基本数据结构及其在不同存储方式下的实现，掌握分析、选择不同的

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

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章 ：2.3 （2）2.4 一元多项式的表示及相加第3章 栈和队列：3.1、3.2.1第3章 栈和队列：3.2.4、3.2.5、3.3第3章 栈和队列：3.4综合习题课（1）：前3章的相关内容综合实验课（1）：前3章的

17、相关内容第4章 串：4.1、4.2.1、4.2.2、4.2.3、4.3.1第5章 数组和广义表：5.1、5.2第5章 数组和广义表：5.3综合实验课（2）：第4-5章的相关内容第6章 树和二叉树：6.1、6.2第6章 树和二叉树：6.3、6.4.1第6章 树和二叉树：6.4.2、6.6第6章 树和二叉树：综合习题课（2）：树的相关内容第7章 图：7.1、7.2第7章 图：7.3、7.4.1、7.4.3第7章 图：7.6第7章 图：综合习题课（3）：图的相关内容第9章 查找：9.1、9.3综合实验课（3）：第9章的相关内容第10章 内部排序：10.1、10.2第10章 内部排序：10.3、10.

18、4综合习题课（3）：第9、10章的相关内容综合实验课（4）：第10章的相关内容学 时222222222222222222222222222222备 注教案（分教案）课次：1 学时：2章 节第1章 绪论：1.1 什么是数据结构、1.2 基本概念和术语教学目的和教学要求了解数据结构的课程性质、内容、应用领域及其与其他学科的关系；掌握数据结构的相关概念和术语；掌握四类基本的数据关系。教学重 点难 点教学重点： 数据结构的相关概念和术语教学难点： 四类基本的数据关系教学进程（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：计算机的应用不再局限于科学计算，更多地用于控制，管理，数据处理等非数值

19、计算的处理工作。计算机加工处理的对象：数值，字符，表格，图形声音，图象等具有一定结构的数据。进行程序设计时必须分析待处理的对象的特性及各对象之间存在的关系产生背景。1.1 什么是数据结构1.2 数据结构的基本概念和术语 1. 数据（Data）2. 数据元素（Data Element）3. 数据对象（Data Object） 4. 结构（Data Structure）存储结构、抽象数据类型抽象数据类型 (Abstract Data Type) ADT的定义格式不唯一, 我们采用下述格式定义一个ADT: ADT 抽象数据类型名 数据对象: 数据关系: 基本操作: ADT 抽象数据类型名教学方法、课

20、堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业图1.5：要求理解和掌握四类基本的数据关系；并在日常生活中举例进行说明。主要参考资料算法与数据结构（C语言版）， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析备注教案（分教案）课次：2 学时：2章 节第1章：1.3 抽象数据类型的表现与实现1.4 算法和算法分析教学目的和教学要求理解抽象数据类型的表示及实现；对算法、算法要求、算法效率的度量进行有效的分析。教学重 点难 点教学

21、重点： 抽象数据类型的表示及实现；算法、算法要求；教学难点： 算法效率的度量及有效的分析；教学进程（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：1.3 抽象数据类型的表示和实现1.4 算 法 1. 算法（Algorithm）的定义 Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. (算法是规则的有限集合， 是为解决特定问题而规定的一系列操作。) 是指令的有限序列，其中每一条指令表示一个或多个操作。2. 算法的特

22、性3. 算法设计的要求） 算法的正确性 (1) 所设计的程序没有语法错误； (2) 所设计的程序对于几组输入数据能够得出满足要求的结果； (3) 所设计的程序对于精心选择的典型、 苛刻而带有刁难性的几组输入数据能够得到满足要求的结果。 (4) 程序对于一切合法的输入数据都能产生满足要求的结果。2） 可读性 3） 健壮性 4） 高效率和低存储量 、算法、 语言和程序的关系时间复杂度教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业1:图1.5、P13：算法的5个特征；2:P15：两段程序的语句的频度的分析主要参考资料算法与数据结构（C语言版）， 范策，周世平，胡哓琨 等编著

23、，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析备注教案（分教案）课次：3 学时：2章 节第2章 线性表：2.1 线性表的类型定义2.2 线性表的顺序表示教学目的和教学要求理解线性表的定义和特点；掌握顺序表以达到利用基本算法进行较复杂算法设计的目的。教学重 点难 点教学重点：线性表的定义和特点；线性表的顺序表示教学难点：线性表的顺序表示教学进程（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：线性结构的特点：在数据元素的非空有限集中， 存在唯一的一个被称为

24、“第一个”的数据元素； 存在唯一的一个被称为“最后一个”的数据元素； 除第一个元素之外，集合中的每个元素均只有一个前驱； 除最后一个元素之外，集合中的每个元素均只有一个后继。 2.1 线性表的类型定义2.1.1 线性表的逻辑结构2.1.2 线性表的抽象数据类型定义2.2 线性表的顺序表示和实现 2.2.1 线性表的顺序存储结构2.2.2 线性表顺序存储结构上的基本运算1. 初始化操作 2. 插入操作 3. 删除操作算法2.1算法2.3教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业1：算法2.1、图2.2、算法2.42：算法2.5、算法2.6主要参考资料算法与数据结构（

25、C语言版）， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析备注教案（分教案）课次：4 学时：2章 节第2章 ：2.3 线性表的链式表示和实现（1）教学目的和教学要求理解线性表的链表的特点，掌握在这种存储结构上各种基本运算的实现算法以及效率的分析，并学习在这种存储结构上进行算法设计的方法； 以达到利用基本算法进行较复杂算法设计的目的。教学重 点难 点教学重点：线性表的链式表示和实现；教学难点：单链表的插入、删除、查找和归并操作；教学进程

26、（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：2.3 线性表的链式表示和实现 2.3.1 单链表线性表的链式存储：图2.6 单链表的逻辑状态图2.7 带头结点单链表图示2.3.2 单链表上的基本运算 1. 建立单链表2. 查找3. 单链表插入操作4. 删除5合并单链表：教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业1：图2.5、图2.8、图2.92：算法2.8、算法2.9、算法2.10、算法2.11主要参考资料算法与数据结构（C语言版）， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社 20

27、04数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析备注教案（分教案）课次：5 学时：2章 节第2章 ：2.3 （2）2.4 一元多项式的表示及相加教学目的和教学要求理解线性表的链表的特点，掌握在这种存储结构上各种基本运算的实现算法以及效率的分析；掌握一元多项式的表示及相加的方法与算法。教学重 点难 点教学重点： 循环链表、双向链表及其算法；一元多项式的表示及相加的方法与算法；教学难点：双向链表及其算法、一元多项式相加的方法；教学进程（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：2.3.3 循环链表2.3.4 双向链表1. 双向链表的前插操作

28、2. 双向链表的删除操作2.3.6 顺序表和链表的比较 1. 基于空间的考虑、2. 基于时间的考虑、3. 基于语言的考虑2.4 一元多项式的表示及相加教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业1：图2.12、图2.14、图2.15、图2.16、图2.17、图2.182：算法2.18、算法2.19、算法2.23主要参考资料算法与数据结构（C语言版）， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析备注教案（分

29、教案）课次：6 学时：2章 节第3章 栈和队列：3.1 栈、3.2.1 数制转换教学目的和教学要求理解栈的定义、特点，学习它的各种组织方式及算法；掌握它的空和满的判断条件；并学会它的简单应用。教学重 点难 点教学重点： 栈的定义、特点，学习它的各种组织方式及算法；教学难点： 栈的简单应用；教学进程（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：3.1 栈 3.1.1 栈的定义3.1.2 栈的表示和实现 1. 顺序栈顺序栈基本操作的实现:初始化、(2) 取栈顶元素、(3) 入栈、(4) 出栈2. 链栈3.2 栈的应用举例 1. 数制转换教学方法、课堂讲解、例题演示，课件演示辅助手段：

30、电脑、投影仪、教科书作业1：图3.1、3.22：P47：栈基本操作的算法描述、算法3.1主要参考资料算法与数据结构（C语言版）， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析备注教案（分教案）课次：7 学时：2章 节第3章 栈和队列：3.2.4 迷宫求解、3.3 栈与递归的实现教学目的和教学要求了解迷宫求解的算法思路、了解计算机图形学中的种子填充苏算法；掌握汉诺塔算法及其过程。教学重 点难 点教学重点： 迷宫求解的算法思路、汉诺塔算法

31、及其过程；教学难点： 汉诺塔算法及其过程；教学进程（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：4. 迷宫求解（拓展：填充算法） 3.3 栈与递归的实现1. 递归特性问题 1) 递归函数 2）汉诺塔算法三个盘子搬动时hanoi(3, A, B, C) 递归调用过程： hanoi(2,A,C,B): hanoi(1,A,B,C) move(A-C) 1号搬到C move(A-B) 2号搬到B hanoi(1,C,A,B) move(C-B) 1号搬到B move(A-c) 3号搬到C hanoi(2,B,A,C): hanoi(1,B,C,A) move(B-A) 1号搬到A mo

32、ve(B-c) 2号搬到C hanoi(1,A,B,C) move(A-C) 1号搬到C教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业1：图3.72：算法3.5、种子填充算法、两种算法求解n!主要参考资料算法与数据结构（C语言版）， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析备注教案（分教案）课次：8 学时：2章 节第3章 栈和队列：3.4 队列教学目的和教学要求掌握队列的数据结构和链队列的相关操作；掌握循

33、环队列的相关内容；教学重点、难点教学重点： 列的数据结构和链队列的相关操作；教学难点： 循环队列的相关操作；教学进程（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：3.4 队 列3.4.1 队列的定义 队列 (Queue)是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出(Fist In Fist Out， 缩写为FIFO)的特性。在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。3.4.2 队列的表示和实现 链队列: （1） 初始化操作、（2）销毁队列、（3） 入队操作、（4） 出队操作3.4.3：循环

34、队列如何区分队列“空”和“满”另设一个标志位以区分队列是空还是满；少用一个元素空间，当队列头指针在队列尾指针的下一个位置上时为“满”。当Q.front=Q.rear时队空；Q.front+1=Q.rear时队满 循环队列满足条件 (Q.rear+1)%MAXQSIZE= Q.front 队满教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业1：图3.8、图3.10、图3.11、图3.14；2：P62：队列的基本操作算法、P64：循环队列的基本操作算法；主要参考资料算法与数据结构（C语言版）， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004数据结构（C语言版），

35、严蔚敏等编著， 清华大学出版社 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析备注教案（分教案）课次：9 学时：2章 节综合习题课（1）：前3章的相关内容教学目的和教学要求要求掌握栈的应用及递归算法教学重 点难 点教学重点： 教学难点： 教学进程（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：1：求N！的递归算法；2：求N！的栈的算法；3：数制转换算法的具体实现；4：种子填充算法的具体过程：四向连通填充算法：a） 种子像素压入栈中；b） 如果栈为空，则转e)；否则转c)；c） 弹出一个像素，并将该像素置成填充色；并判断该像素相邻的四连

36、通像素是否为边界色或已经置成多边形的填充色，若不是，则将该像素压入栈；d） 转b）；e） 结束。 教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业主要参考资料算法与数据结构（C语言版）， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析备注教案（分教案）课次：10 学时：2章 节综合实验课（1）：前3章的相关内容教学目的和教学要求1：求N！的递归算法；2：求N！的栈的算法；3：数制转换算法的具体实现；教学进程（含章

37、节教学内容、学时分配、教学方法、 辅助手段）教学进程：1：求N！的递归算法；2：求N！的栈的算法；3：数制转换算法的具体实现；#include stdio.h#include stdlib.h#define size 20typedef struct int *base; int *top; int ssize;ss;void ist(ss &s) s.base=(int *)malloc(size*sizeof(int); s.top=s.base; s.ssize=size;void main() long n,m; ss w;ist(w);printf(请输入N的值(1-32768)：)

38、; scanf(%d,&n);m=n; while(n) *w.top+=n%8; n=n/8; printf(转换为8进制以后的值：n(%d)10=(,m); while(w.top!=w.base) printf(%d,*-w.top); printf()8n); 教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书主要参考资料算法与数据结构（C语言版）， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析教案（分教案）

39、课次：11 学时：2章 节第4章 串：4.1 串的定义、4.2.1 定长顺序存储表示 4.2.3 串的块链存储表示4.3.1 求子串位置的定位函数教学目的和教学要求掌握串的定义、定长顺序存储表示；了解串的块链存储表示；掌握求子串位置的定位函数（模式匹配算法）；教学重 点难 点教学重点： 串的定义、定长顺序存储表示；串的块链存储表示；教学难点：求子串位置的定位函数（模式匹配算法）；教学进程（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：4.1 串的定义 串(String)是零个或多个字符组成的有限序列。 一般记为： S= a1a2.an (n0)4.2 串的表示和实现 4.2.1 定

40、长顺序存储表示串1.串联接Concat(& T , S1, S2) 2. 求子串SubString ( & Sub , S , pos , len )4.2.3串的块链存储表示4.3 串的模式匹配算法 4.3.1 求子串位置的定位函数 Index( S, T ,pos)int Index （SString S, SString T, int pos ） /返回子串T在主串中第 pos个字符之后的位置。如不存在，则函数值为0。其中：T 非空，1=pos=Strlength( S )。 i = pos ; j = 1 ; while ( i=S 0 & j T 0 ) return i - T 0

41、 ; else return 0 ; / Index 算法：4.5教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业1：P73：串的链接操作；图4.1；2：算法4.5：串的模式匹配算法、图4.3；主要参考资料算法与数据结构（C语言版）， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析备注教案（分教案）课次：12 学时：2章 节第5章 数组和广义表：5.1 数组的定义、5.2 数组的顺序表示和实现教学目的和教学要求掌

42、握数组的定义、数组的顺序表示和实现；教学重 点难 点教学重点： 数组的定义、数组的顺序表示和实现教学难点： 数组的顺序表示和实现教学进程（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：5.1 数组的定义数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种线性表。对于数组的操作一般只有两类： (1） 获得特定位置的元素值； (2） 修改特定位置的元素值。5.2 数组的顺序表示和实现 数组一般不做插入和删除操作，因此采用顺序存储结构。由于存储单元是一维结构，而数组是多维结构，则用一组连续存储单元存放数组的数据元素就有个次序约定问题。 数组的顺序存储结构有两种：一

43、种是按行序存储，另一种是按列序存储。Loci, j=Loc1, 1+n(i-1)+(j-1)Loci, j, k=Loc1, 1, 1+(i-1)mn+(j-1)n+(k-1)对于维数组A(c1d1, c2d2，, cndn)，我们只要把上式推广，就可以容易地得到维数组中任意元素aj1j2jn的存储地址的计算公式: LOC(aj1j2jn)=LOC(a000)+(b2*b3*bn*j1+b3*bn*j2+bn*jn-1+jn)*lLOC(aj1j2jn)= LOC(a000)+( = LOC(a000)+其中 cn=L,ci-1=bi*ci教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、

44、投影仪、教科书作业计算1-3维数组的任意元素的存储地址；主要参考资料算法与数据结构（C语言版）， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析备注教案（分教案）课次：13 学时：2章 节第5章 数组和广义表：5.3 矩阵的压缩存储 5.3.1 特殊矩阵、5.3.2 稀疏矩阵教学目的和教学要求掌握特殊矩阵和稀疏矩阵的存储方法；掌握稀疏矩阵的转置算法；教学重 点难 点教学重点： 特殊矩阵和稀疏矩阵的存储方法；稀疏矩阵的转置算法；教学难点：

45、稀疏矩阵的转置算法；教学进程（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：5.3 矩阵的压缩存储 压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配空间。特殊矩阵：值相同的元素或零元素在矩阵中的分布有一定的规律。稀疏矩阵：矩阵中元素分布没有规律，但零元素较多。 5.3.1 特殊矩阵 三角矩阵大体分为三类：下三角矩阵、上三角矩阵和对称矩阵Loci, j=Loc1, 1+i(i-1)/2+j-1带状矩阵5.3.2 稀疏矩阵方法一：按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。方法二：按照a.data 中三元组的次序进行转置，并将转置后的三元组

46、置入b 中的恰当位置。教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业1：下三角、对称、带状矩阵的数据元素的下标地址的计算方法；2：稀疏矩阵的两个转置算法；主要参考资料算法与数据结构（C语言版）， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析备注教案（分教案）课次：14 学时：2章 节综合实验课（2）：第4、5章的相关内容教学目的和教学要求要求编程实现串的模式匹配算法、稀疏矩阵的两个转置算法；教学进程（含章节教

47、学内容、学时分配、教学方法、 辅助手段）教学进程：1：串的模式匹配算法；2：稀疏矩阵的转置算法（一）；3：稀疏矩阵的转置算法（二）；#include stdio.hvoid main() char sa7=a,b,c,d,e,f,g; char sb3=e,f,g; int i=0,j=0;while(i=6 & j2) printf(找到了!在第%d个位置。n,i-3+1); else printf(抱歉,没有找到!n);#include stdio.h#define mu 3#define nu 8#define tu 8void main() int M83=1,2,12,1,3,9,3

48、,1,-3,3,6,14,4,3,24,5,2,18,6,1,15,6,4,-7; int T83; int q=0,col,p,i,j; printf(转换之前的矩阵为：n);for(i=0;i=7;i+) for(j=0;j=2;j+) printf( %d ,Mij);printf(n) for(col=1;col=nu;+col)for(p=0;p=tu-1;+p)if(Mp1=col) Tq0=Mp1;Tq1=Mp0; Tq2=Mp2;+q; printf(转换之后的矩阵为：n);for(i=0;i=7;i+) for(j=0;j0时， 该集合满足如下条件： (1) 其中必有一个称为

49、根（root）的特定结点，它没有直接前驱，但有零个或多个直接后继。 (2) 其余n-1个结点可以划分成m（m0）个互不相交的有限集T1，T2，T3，Tm，其中Ti又是一棵树，称为根root的子树。 每棵子树的根结点有且仅有一个直接前驱，但有零个或多个直接后继。6.2 二叉树的定义 6.2.1 二叉树的定义 定义：我们把满足以下两个条件的树形结构叫做二叉树（Binary Tree）： （1） 每个结点至多只有二棵子树（即度都不大于2）； （2）二叉树的子树有左右之分，其次序不能任意颠倒。 6.2.2 二叉树的性质满二叉树：完全二叉树：深度为k，结点数为n的二叉树，如果其结点1n的位置序号分别与满

50、二叉树的结点1n的位置序号一一对应，则为完全二叉树。教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业1：图6.3二叉树的基本形态；2：二叉树的五个性质；主要参考资料算法与数据结构（C语言版）， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析备注教案（分教案）课次：16 学时：2章 节第6章 树和二叉树：6.2.3 二叉树的存储结构、6.3.1 遍历二叉树；教学目的和教学要求熟练掌握二叉树的两种存储结构；熟练掌握二

51、叉树的三种遍历方法；教学重 点难 点教学重点：二叉树的两种存储结构、二叉树的三种遍历方法； 教学难点：二叉树的三种遍历方法； 教学进程（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：6.2.3 二叉树的存储结构 二叉树的结构是非线性的， 每一结点最多可有两个后继。 二叉树的存储结构有两种： 顺序存储结构和链式存储结构。 1： 顺序存储结构2. 链式存储结构 对于任意的二叉树来说，每个结点只有两个孩子，一个双亲结点。我们可以设计每个结点至少包括三个域：数据域、 左孩子域和右孩子： 二叉树的遍历三种遍历方法的递归定义。 先序遍历（DLR）操作过程： 若二叉树为空， 则空操作， 否则依次

52、执行如下3个操作： (1) 访问根结点； (2) 按先序遍历左子树； (3) 按先序遍历右子树。 中序遍历（LDR）操作过程： 若二叉树为空， 则空操作， 否则依次执行如下3个操作： (1) 按中序遍历左子树； (2) 访问根结点； (3) 按中序遍历右子树。 后序遍历（LRD）操作过程： 若二叉树为空， 则空操作， 否则依次执行如下3个操作： (1) 按后序遍历左子树； (2) 按后序遍历右子树； (3) 访问根结点。教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业1：对一些特殊样式的二叉树进行顺序存储；2：对二叉树进行三种遍历操作；课后自我总结分析备注教案（分教案）

53、课次：17 学时：2章 节第6章 6.4 树和森林：6.4.1 树的存储结构、6.4.2 森林与二叉树的转换、6.4.3 树和森林的遍历教学目的和教学要求熟练掌握树的三种存储结构；熟练掌握森林与二叉树的转换；熟练掌握树和森林的遍历；教学重 点难 点教学重点：树的三种存储结构、森林与二叉树的转换； 教学难点：树和森林的遍历； 教学进程（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：6.4 树和森林6.4.1 树的存储结构树的主要存储方法有以下三种： 双亲表示法、2. 孩子表示法、3. 孩子兄弟表示法6.4.2 森林与二叉树的转换 1. 树转换为二叉树将一棵树转换为二叉树的方法是： (

54、1) 树中所有相邻兄弟之间加一条连线。 (2) 对树中的每个结点，只保留其与第一个孩子结点之间的连线， 删去其与其它孩子结点之间的连线。 (3) 以树的根结点为轴心，将整棵树顺时针旋转一定的角度， 使之结构层次分明。2. 森林转换为二叉树 森林是若干棵树的集合。树可以转换为二叉树， 森林同样也可以转换为二叉树。因此，森林也可以方便地用孩子兄弟链表表示。森林转换为二叉树的方法如下： （1） 将森林中的每棵树转换成相应的二叉树。 （2） 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子， 当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树

55、。3. 二叉树还原为树或森林6.4.3 树的遍历 1. 树的遍历：树的遍历方法主要有以下两种： 1） 先根遍历、2） 后根遍历2. 森林的遍历：森林的遍历方法主要有以下三种： 1） 先序遍历、2） 中序遍历、3） 后序遍历教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业1：把树用三种方法存储；2：把树和森林与二叉树进行相互转换；3：对树和森林进行遍历；课后自我总结分析备注教案（分教案）课次：18 学时：2章 节第6章6.6 赫夫曼树及其应用、6.6.1 最优二叉树（赫夫曼树）、6.6.2 赫夫曼编码教学目的和教学要求熟练掌握哈夫曼树的构造方法；熟练掌握哈夫曼编码的编码方

56、法；教学重 点难 点教学重点：哈夫曼树的构造方法； 教学难点：哈夫曼编码的编码方法； 教学进程（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：6.6 赫夫曼树及其应用 6.6.1 最优二叉树 1. 路径和路径长度2. 结点的权和带权路径长度3. 树的带权路径长度构造赫夫曼算法的步骤如下： （1）用给定的n个权值w1, w2, , wn对应的n个结点构成n棵二叉树的森林F=T1, T2, , Tn，其中每一棵二叉树Ti(1in)都只有一个权值为wi的根结点，其左、右子树为空。 （2）在森林F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、右子树，标记新二叉树的根结点权值为其左

57、右子树的根结点权值之和。 （3）从F中删除被选中的那两棵二叉树， 同时把新构成的二叉树加入到森林F中。 （4）重复（2）、（3）操作， 直到森林中只含有一棵二叉树为止， 此时得到的这棵二叉树就是赫夫曼树。6.6.2 赫夫曼编码前缀编码：任一个字符的编码都不是另一个字符编码的前缀，可利用二叉树设计前缀编码。6.6.3 赫夫曼编码算法的实现教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业1：构造哈夫曼树；2：生成哈夫曼编码；主要参考资料算法与数据结构（C语言版）， 范策，周世平，胡哓琨 等编著，机械工业出版社， 2004数据结构（C语言版）， 严蔚敏等编著， 清华大学出版社

58、 2004数据结构与算法，许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析备注教案（分教案）课次：19 学时：2章 节综合习题（三）：树与二叉树的相关内容；教学目的和教学要求要求熟练掌握树、二叉树、森林的相关存储、遍历、转换的知识；能够构造哈夫曼树、哈夫曼编码；教学进程（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：1：已知某二叉树的先序遍历和中序遍历分别为：先序：18 14 7 3 11 22 35 27中序：3 7 11 14 18 22 27 35；求该二叉树。2：已知某二叉树的先序遍历和中序遍历分别为：先序：E B A D C F H G I K J中

59、序：A B C D E F G H I J K；画出该二叉树。3已知某树的先根遍历和后根遍历分别为：先根：G F K D A I E B C H J后根：D I A E K F C J H B G、画出该树。4：数据传输中的二进制编码：要传送数据state、seat、act、tea、cat、set、a、eat；如何使传送的长度最短。（构造哈夫曼树、求出各个数据的哈夫曼编码。）5：假设有一台机器共有7种不同的指令，其使用频率如表所示：求出各个指令的哈夫曼编码。6：求出满足下列条件的所有二叉树：1：先序和后序相同；2：中序和后序相同；3：先序和中序相同；7：假设用于用于通讯的电文由8个字母组成，字

60、母在电文中出现的频率分别为： 0.07、0.19、0.02、0.06 0.32、0.03、0.21、0.10；请为这8个字母设计哈夫曼编码。8：画出和下列数对应的二叉树：9：已知某二叉树的先序建立时读入的数据为：A B C D E F G H ；请求出该二叉树。课后自我总结分析教案（分教案）课次：20 学时：2章 节第7章 图：7.1 图的定义和术语教学目的和教学要求熟练掌握和理解有关图的各种定义和术语；教学重 点难 点教学重点：图的各种定义和术语； 教学难点：图的生成树、图的连通性； 教学进程（含章节教学内容、学时分配、教学方法、 辅助手段）教学进程：7.1 图的定义与基本术语 7.1.1