数据结构课程教案-20170330

安徽大学本科教学课程教案课程代码：ZJ36007课程名称：数据结构授课专业：计算机科学与技术授课教师：邹海职称/学位：副教授/博士开课时间：二○一六至二○一七学年第二学期第1次课程教学方案周次1课时数2教学章节第一章、绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析目标要求（1）掌握数据、数据元素、数据对象、数据结构、存储结构和数据类型等基本概念，特别是逻辑结构与存储结构之间的关系；（2）了解抽象数据类型的定义、表示和实现方法；（3）理解算法的基本要素及含义；（4）掌握算法的时间复杂度和空间复杂度分析。重点难点（1）数据结构包含的逻辑结构、存储结构和运算三方面的相互关系；（2）各种逻辑结构即线性结构、树形结构和图形结构之间的差别；（3）数据结构和数据类型的差别和联系；（4）算法的时间复杂度和空间复杂度分析。教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源□文字教材√电子教案□录像材料□录音材料□直播课堂√CAI课件□IP课件□其他资源：课后作业（1）数据的逻辑结构和存储结构有什么不同？（2）数据类型和抽象数据类型有什么不同？（3）算法和程序有什么不同？（4）为什么要进行算法的时间复杂度分析？板书设计1、什么是数据结构指数据以及数据元素相互之间的联系。可以看作是相互之间存在着某种特定关系的数据元素的集合。也可看成是带结构的数据元素的集合。逻辑结构的类型：线性结构、树型结构、图状结构、集合2、基本概念与术语1）数据；2）数据元素；3）数据对象3、抽象数据类型的表示与实现1）数据对象2）数据关系3）基本操作4、算法和算法分析（1）算法：对特定问题求解步骤的一种描述。（2）算法的5个重要特征：有穷性，确定性，可执行性，输入，输出。（3）算法设计的目标：1）正确性；2）可读性；3）健壮性；4）效率与低存储量需求

第1次教学活动设计教学环节内容设计与手段导入新课从计算机科学课程体系设置情况，导入数据结构这门课程所处的地位：承上启下。先修课程：计算机基础、高级语言程序设计、离散数学。后期课程：操作系统、编译原理、数据库原理、软件工程等。数据结构课程的主要研究内容。学习和讲授的方法：演译法和归纳法。讲授内容1、什么是数据结构指数据以及数据元素相互之间的联系。可以看作是相互之间存在着某种特定关系的数据元素的集合。也可看成是带结构的数据元素的集合。逻辑结构的类型：线性结构、树型结构、图状结构、集合2、基本概念与术语1）数据；2）数据元素；3）数据对象4）逻辑结构与存储结构的区别与联系3、抽象数据类型的表示与实现1）数据对象2）数据关系3）基本操作4、算法和算法分析归纳总结1、数据结构的定义，数据结构包含的逻辑结构、存储结构和运算三方面的相互关系。2、各种逻辑结构即线性结构、树形结构和图形结构之间的差别。3、数据结构和数据类型的差别和联系。4、算法的定义及其特性。5、算法的时间复杂度和空间复杂度分析。第2次课程教学方案周次1课时数2教学章节第二章、线性表2.1线性表的基本概念2.2线性表的抽象类型定义2.3线性表的顺序表示与实现目标要求（1）掌握线性表的逻辑特征；（2）掌握顺序表的类型定义；（3）熟练掌握顺序表基本操作的实现算法及其时间复杂度分析。重点难点（1）顺序表的类型定义；（2）线性表（逻辑结构）到顺序表（存储结构）的具体映射方式；（3）顺序表基本操作的实现算法及其时间复杂度分析。教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源□文字教材√电子教案□录像材料□录音材料□直播课堂√CAI课件□IP课件□其他资源：课后作业（1）顺序存储结构下，线性表中数据关系是如何表示的？（2）设计一个算法，将一个顺序存储的线性表实现逆转置？板书设计1、线性表的基本概念线性表：n（n>=0）个具有相同类型的数据元素所组成的有限序列。线性表的特征：1）除了第一个元素之外，每个元素有唯一的前驱元素；2）除了最后一个元素之外，每个元素有唯一的后继元素。2、线性表的抽象类型定义1）数据对象：2）数据关系：3）基本操作：3、线性表的顺序表示与实现（顺序表）（1）顺序表的类型定义与表示（2）顺序表的主要特征：连续的存储单元；逻辑相邻则物理相邻。（3）基本操作的实现1）初始化操作：2）插入操作：3）删除操作：

第2次教学活动设计教学环节内容设计与手段导入新课由前一讲的数据的逻辑结构分类：线性结构、树型结构、图状结构、集合。导入本章所要讲述的主要内容：线性结构首先讨论线性表的主要逻辑特征。其次，引导学生思考，这种逻辑结构在计算机中如何来表示、存储及其操作？讲授内容1、线性表的基本概念线性表：n（n>=0）个具有相同类型的数据元素所组成的有限序列。线性表的特征：1）除了第一个元素之外，每个元素有唯一的前驱元素；2）除了最后一个元素之外，每个元素有唯一的后继元素。2、线性表的抽象类型定义1）数据对象：2）数据关系：3）基本操作：3、线性表的顺序表示与实现（顺序表）（1）顺序表的类型定义（2）顺序表的主要特征：连续的存储单元；逻辑相邻则物理相邻。（3）基本操作的实现：1）初始化操作；2）插入操作；3）删除操作等。归纳总结1、顺序表的主要特征：采用一组地址连续的存储单元依次的存储从表头到表尾的元素，逻辑上相邻的两个元素其物理上也相邻。2、顺序表的类型定义：1）*elem：一组地址连续的存储单元；2）length：线性表的长度；3）listsize;线性表当前分配的存储容量3、顺序表中其插入和删除操作，主要借助数据元素的移动来实现。对于插入操作，最好情况下，当i=n+1时，移动次数为0，最坏情况下，当i=1时，需要移动n次，平均移动次数为n/2。对于删除操作，最好情况下，当i=n时，移动次数为0，最坏情况下，当i=1时，需要移动n-1次，平均移动次数为（n-1）/2。

第3次课程教学方案周次2课时数2教学章节第二章、线性表2.4线性表的链式表示与实现2.4.1线性表的链式存储2.4.2单链表目标要求（1）掌握单链表的结点结构（2）掌握头结点、头指针和首元结点的概念；（3）单链表中数据关系的表示方法；（4）单链表的特点；（5）掌握线性表链式存储结构下基本操作的实现。重点难点（1）单链表的类型定义；（2）头指针与头结点的概念；（3）单链表存储结构下，线性表基本操作的实现。教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源□文字教材√电子教案□录像材料□录音材料□直播课堂√CAI课件□IP课件□其他资源：课后作业（1）链表与顺序表的区别？（2）采用带头结点的单链表与不带头结点的单链表相比，有哪些优点？（3）设计算法，将单链表的尾结点修改为首元结点？板书设计1、线性表的链式存储结点是构成链表的基本单位。结点的结构：数据域和指针域。其中数据域存储元素本身的信息，指针域用来存储数据元素之间的逻辑关系。存储密度=结点数据本身占用的空间/结点占用的空间总量由于每个结点带有指针域，导致存储密度降低。2、单链表（1）什么是单链表由于顺序表中的每个元素至多只有一个前驱元素和一个后继元素，即数据元素之间是一对一的逻辑关系，所以当进行链式存储时，一种最简单也最常用的方法是:在每个节点中除包含有数据域外，只设置一个指针域，用以指向其后继节点，这样构成的链接表称为线性单向链接表，简称单链表。（2）头结点与头指针：对于一个单链表头结点不是必需的，但头指针是必需的。带头结点的单链表与不带头结点的单链表，一般情况下，指带头结点。（3）单链表的类型定义（4）单链表的基本操作实现

第3次教学活动设计教学环节内容设计与手段导入新课针对上一讲的线性表的顺序存储，引导学生总结顺序存储的优点：结构简单，易于理解；方便随机访问表中的每个元素；不需要再为表示元素间的逻辑关系而增加额外的存储空间等。指出顺序表的缺点：（1）顺序表的存储空间不易扩充；（2）顺序表易造成存储空间的利用率低，且不利于分散的存储单元的使用；（3）顺序表在插入和删除操作时，需要大量的移动数据元素。针对顺序表的上述缺点，导入线性表的另外一种存储结构—链式存储结构。讲授内容1、线性表的链式存储采用随机的存储单元，并利用指针域来存储数据元素之间的逻辑关系。注意与顺序表的主要区别。2、单链表（1）什么是单链表由于顺序表中的每个元素至多只有一个前驱元素和一个后继元素，即数据元素之间是一对一的逻辑关系，所以当进行链式存储时，一种最简单也最常用的方法是:在每个节点中除包含有数据域外，只设置一个指针域，用以指向其后继节点，这样构成的链接表称为线性单向链接表，简称单链表。（2）头结点与头指针：对于一个单链表头结点不是必需的，但头指针是必需的。带头结点的单链表与不带头结点的单链表，一般情况下，指带头结点。（3）单链表的类型定义（4）单链表的基本操作实现归纳总结1、与顺序表不同，链式存储结构采用随机的存储单元来存储线性表的元素，需要额外的存储空间（指针域）来表示数据元素间的线性关系；2、单链表的头指针非常重要，它是访问单链表的入口，用来标识该链表。3、利用单链表来存储线性表时，在进行插入和删除操作时不再需要移动数据元素，而只要调整指针。在插入操作时，需要修改2个指针；在删除操作时，需要修改1个指针。4、单链表的特点：在单链表中，由于每个节点只包含有一个指向后继节点的指针，所以当访问过一个节点后，只能接着访问它的后继节点，而无法访问它的前驱节点。5、根据单链表的特点，往往在单链表操作时，一般将工作指针设置在待处理结点的前驱结点上。

第4次课程教学方案周次2课时数2教学章节2.4线性表的链式表示与实现2.4.3双向链表目标要求（1）掌握双向链表结点的结构；（2）掌握双向链表的特点；（3）掌握双向链表与单链表的区别与联系；（4）掌握双向链表基本操作的实现。重点难点（1）双向链表的结构及其特征；（2）双向链表与单向链表的异同及其适用条件；（3）双向链表的类型定义；（4）双向链表基本操作的实现。教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源□文字教材√电子教案□录像材料□录音材料□直播课堂√CAI课件□IP课件□其他资源：课后作业（1）什么情况下使用双向链表？（2）双向链表与单链表相比有什么不同？（3）双向链表的主要优缺点是什么？板书设计1、什么是双向链表在单链表中，当访问过一个节点后，只能接着访问它的后继节点，而无法访问它的前驱节点。为了解决上述问题：在每个节点中除包含有数值域外,设置有两个指针域，分别用以指向其前驱节点和后继节点，这样构成的链接表称之为线性双向链接表，简称双向链表。带头结点的双向链表示意图2、双向链表的特点：1）在双链表中，由于每个节点既包含有一个指向后继节点的指针，又包含有一个指向前驱节点的指针，所以当访问过一个节点后，既可以依次向后访问每一个节点，也可以依次向前访问每一个节点。2）求任意结点p的后继操作的时间复杂度为O(1)，前驱操作操作的时间复杂度也为O(1)。3、双向链表的类型定义typedefstructDNode｛//声明双链表节点类型 ElemTypedata;structDNode*prior;//指向前驱节点 structDNode*next;//指向后继节点}DLinkList;4、双向链表的基本操作

第4次教学活动设计教学环节内容设计与手段导入新课简要回顾上一讲单向链表的主要特征：在单链表中，由于每个节点只包含有一个指向后继节点的指针，所以当访问过一个节点后，只能接着访问它的后继节点，而无法访问它的前驱节点。在某些情况下，既需要进行求后继操作，又要进行求前驱操作。为了便于访问过一个节点后，既可以依次向后访问每一个节点，也可以依次向前访问每一个节点。需要修改链表中结点的结构，引入双向链表的定义。讲授内容1、什么是双向链表在每个节点中除包含有数值域外，,设置有两个指针域，分别用以指向其前驱节点和后继节点，这样构成的链接表称之为线性双向链接表，简称双向链表。双向链表与单向链表的区别与联系？2、双向链表的特点1）在双链表中，由于每个节点既包含有一个指向后继节点的指针，又包含有一个指向前驱节点的指针，所以当访问过一个节点后，既可以依次向后访问每一个节点，也可以依次向前访问每一个节点。2）求任意结点p的后继操作的时间复杂度为O(1)，前驱操作操作的时间复杂度也为O(1)。3、双向链表的类型定义4、双向链表的基本操作1）初始化操作2）插入操作3）删除操作归纳总结1、双向链表的结点结构包括一个数据域和两个指针域，其中一个指向前驱结点，另一个指向后继结点。2、双向链表特征：由于每个节点既包含有一个指向后继节点的指针，又包含有一个指向前驱节点的指针，所以当访问过一个节点后，既可以依次向后访问每一个节点，也可以依次向前访问每一个节点。3、双向链表的插入操作需要修改4个指针域，删除操作需要修改2个指针域。

第5次课程教学方案周次3课时数2教学章节2.4线性表的链式表示与实现2.4.4循环链表目标要求（1）掌握循环链表的类型定义；（2）掌握循环链表为空的条件；（3）深刻理解循环链表的特征及与非循环链表之间的差异。重点难点（1）循环链表的结构及其特征；（2）循环链表与非循环链表的差异；（3）循环链链表的类型定义；（4）循环链表基本操作的实现。教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源□文字教材√电子教案□录像材料□录音材料□直播课堂√CAI课件□IP课件□其他资源：课后作业（1）循环链表的主要特点是什么？（2）循环链表判空的条件是什么？（3）循环链表的操作与非循环的单链表在操作上相比，主要有什么不同？板书设计1、什么是循环链表循环链表是一种首尾相边的链表。链表的最后一个结点的指针域指向头指针，则使得链表的头尾相边，构成循环链表。2、循环链表特点在单链表中，只有单向指针（指向其直接后继），从某个结点出发只能查找其后的那些结点。如果要查找它前面的结点，就必须从表头结点开始搜索。而利用循环链表，在不增加存储空间的同时，可以实现从表中任意结点出发，访问表中其他所有结点，不必借助头指针。3、循环链表的类型定义在循环链表中，结点的存储结构与单链表中完全相同。因此，其类型定义与链表相同。typedefstructDLode｛//声明双链表节点类型 ElemTypedata;structLNode*prior;//指向前驱节点 structLNode*next;//指向后继节点}CLinkList;4、循环链表的操作在循环链表中，结点的存储结构与单链表中完全相同。其基本操作的实现也与单链表基本一致，其差别在于，判断当前结点是否为表中最后结点的条件，由原来的看后继指针是否为空，改为看其后继指针是否等于头指针。

第5次教学活动设计教学环节内容设计与手段导入新课在单链表中，只有单向指针（指向其直接后继），从某个结点出发只能查找其后的那些结点。如果要查找它前面的结点，就必须从表头结点开始搜索。在单链表中，由于最后一个结点没有后继，因此，最后一个结点的指针域为空。在不增加存储空间的同时，如果将其指向头指针，则使得链表的头尾相边，构成循环链表。在循环链表中可以实现从表中任意结点出发，访问表中其他所有结点，不必借助头指针。讲授内容1、什么是循环链表2、循环链表特点3、循环链表的类型定义4、循环链表的操作5、循环链表的应用归纳总结1、循环链表的特点：从表中任何一个结点开始都可以遍历整个链表，而对于单链表只能从头结点开始才能遍历链表中的所有结点。2、循环链表的类型定义：在循环链表中，结点的存储结构与单链表中完全相同。因此，其类型定义与链表相同，且不需要增加额外的存储空间。3、循环链表的操作：其基本操作的实现也与单链表基本一致，其差别在于，判断当前结点是否为表中最后结点的条件，由原来的看后继指针是否为空，改为看其后继指针是否等于头指针。

第6次课程教学方案周次3课时数2教学章节2.4线性表的链式表示与实现2.4.5链表的应用目标要求（1）通过实例讲解和讨论，使学生掌握链表操作的技巧；（2）通过实例讲解和讨论，提高学生的算法设计技能；（3）算法的时间复杂度和空间复杂度分析。重点难点（1）如何让学生掌握链表操作的一般步骤和使用技巧；（2）如何提高学生算法设计的技能；（4）如何让学生掌握算法的时间复杂度和空间复杂度分析。教学方式√课堂讲授□小组活动□实验演示√难点答疑□提问√作业讲评□实践教学□考试测验□其他活动习题课媒体资源□文字教材√电子教案□录像材料□录音材料□直播课堂√CAI课件□IP课件□其他资源：课后作业（1）设有一带头结点的单链表，编程将链表颠倒过来，要求不用另外的数组或结点完成。（2）给定(已生成)一个带表头结点的单链表，设head为头指针，结点的结构为(data,next),data为整型元素，next为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。(要求：不允许使用数组作辅助空间)。（3）设计算法将两个有序的单链表合并为一个有序的单链表。板书设计实例1、设计一个算法采用头插法构造一个带头结点的单链表。实例2、设计一个算法采用尾插法构造一个带头结点的单链表。实例3、已知一个带有表头节点的单链表，节点结构为：（data,link）假设该单链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。要求：（1）描述算法的基本设计思想；（2）描述算法的详细实现步骤；（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C语言实现），关键之处请给出简要注释。实例4、假定采用带头节点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”，如下图所示。设str1和str2分别指向两个单词所在单链表的头节点，链表节点结构为：(data，next)。请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在节点的位置p）。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键为之处给出注释。（3）说明你所设计算法的时间复杂度。以上4个实例的算法，均采用PPT演示。

第6次教学活动设计教学环节内容设计与手段导入新课1、本章小结。（1）理解线性表的逻辑结构特性。（2）深入掌握线性表的两种存储方法，即顺序表和链表。体会这两种存储结构之间的差异。（3）重点掌握顺序表和链表上各种基本运算的实现。（4）综合运用线性表这种数据结构解决一些复杂的实际问题。2、通过实例讲解线性表的应用，体会算法设计的规范及设计技巧。讲授内容实例1、设计一个算法采用头插法构造一个带头结点的单链表。实例2、设计一个算法采用尾插法构造一个带头结点的单链表。实例3、已知一个带有表头节点的单链表，节点结构为：（data,link）假设该单链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。实例4、假定采用带头节点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”，如下图所示。设str1和str2分别指向两个单词所在单链表的头节点，链表节点结构为：(data，next)。请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在节点的位置p）。归纳总结本章小结：（1）理解线性表的逻辑结构特性。（2）深入掌握线性表的两种存储方法，即顺序表和链表。体会这两种存储结构之间的差异。（3）重点掌握顺序表和链表上各种基本运算的实现。（4）注意在单链表操作时，工作指针一般应设在待处理结点的前驱结点上。（5）综合运用线性表这种数据结构解决一些复杂的实际问题。第7次课程教学方案周次4课时数2教学章节第三章：栈和队列----栈目标要求栈的定义栈的存储栈的基本操作的实现重点难点栈的基本操作的实现教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源√文字教材√电子教案□录像材料□录音材料□直播课堂□CAI课件□IP课件□其他资源：课后作业简述现实生活中运用栈的实例，请至少找出3种实例。板书设计1.栈的基本概念栈(Stack)、栈顶(Top)、栈底(Bottom)、空栈。2.栈的抽象数据类型定义ADTStack{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n，n≥0}数据关系：R={<ai-1,ai>|ai-1，ai∈D,i=2,3,…,n}，且约定：an端为栈顶，a1端为栈底基本操作：初始化、进栈、出栈、取栈顶元素等（pp.45）}ADTStack3.栈的动态顺序存储表示采用动态一维数组来存储栈。所谓动态，指的是栈的大小可以根据需要增加。◆用base表示栈底指针，栈底固定不变；栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶。◆用top=base作为栈空的标记。用top指向栈顶数组中的下一个存储位置。◆结点进栈：首先将数据元素保存到栈顶(top所指的当前位置)，然后执行top加1，使top指向栈顶的下一个存储位置;◆结点出栈：首先执行top减1，使top指向栈顶元素的存储位置，然后将栈顶元素取出。4.动态顺序栈的类型定义typedefstruct{SElemType*base;/*栈不存在时值为NULL*/SElemType*top;/*栈顶指针*/intstacksize;/*当前已分配空间，以元素为单位*/}SqStack;5.动态顺序栈的基本操作和实现栈的初始化获取栈顶元素压栈(元素进栈)弹栈(元素出栈)6.栈的链式存储表示简述第7次教学活动设计教学环节内容设计与手段导入新课通过栈在实际问题中的应用，引入学习栈的意义。讲授内容1.栈的基本概念2.栈的抽象数据类型定义3.栈的动态顺序存储表示4.动态顺序栈的类型定义5.动态顺序栈的基本操作和实现6.栈的链式存储表示简述归纳总结总结栈的基本定义；栈的adt；栈的存储结构；针对不同存储结构，栈的基本操作的实现。第8次课程教学方案周次4课时数2教学章节第三章：栈和队列----栈的应用目标要求应用栈实现数制转换、括号匹配；利用栈理解递归。重点难点栈与递归的实现教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源√文字教材√电子教案□录像材料□录音材料□直播课堂□CAI课件□IP课件□其他资源：课后作业请给出求N！的非递归算法。板书设计1.数制转换十进制整数N向其它进制数d(二、八、十六)的转换是计算机实现计算的基本问题。转换法则：该转换法则对应于一个简单算法原理:n=(ndivd)*d+nmodd//n是待转换的十进制数，d=2，8,16。其中：div为整除运算,mod为求余运算采用静态顺序栈方式实现voidconversion(intn,intd)/*将十进制整数N转换为d(2或8)进制数*/{SqStackS;S=Init_Stack();while(n>0){k=n%d;push(S,k);n=n/d;}/*求出所有的余数，进栈*/while(S.top!=0)/*栈不空时出栈，输出*/{pop(S,e);printf(“%1d”,*e);}}2.括号匹配问题在文字处理软件或编译程序设计时，常常需要检查一个字符串或一个表达式中的括号是否相匹配?匹配思想：从左至右扫描一个字符串(或表达式)，则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时，就将它与栈顶的左括号(如果存在)相匹配，同时从栈顶删除该左括号。算法思想：设置一个栈，当读到左括号时，左括号进栈。当读到右括号时，则从栈中弹出一个元素，与读到的左括号进行匹配，若匹配成功，继续读入；否则匹配失败，返回FLASE。#defineTRUE0#defineFLASE-1SqStackS;S=Init_Stack();/*堆栈初始化*/intMatch_Brackets(){charch,x;scanf(“%c”,&ch);while(asc(ch)!=13){//VT:垂直制表符if((ch==‘(’)||(ch==‘[’))push(S,ch);elseif(ch==‘]’){x=pop(S);if(x!=‘[’){printf(“‘[’括号不匹配”);returnFLASE;}}elseif(ch==‘)’){x=pop(S);if(x!=‘(’){printf(“’(’括号不匹配”);returnFLASE;}}}if(S.top!=0){printf(“括号数量不匹配!”);returnFLASE;}elsereturnTRUE;}3.栈与递归的实现栈的另一个重要应用是在程序设计语言中实现递归调用。递归调用：一个函数(或过程)直接或间接地调用自己本身，简称递归(Recursive)。递归是程序设计中的一个强有力的工具。因为递归函数结构清晰，程序易读，正确性很容易得到证明。为了使递归调用不至于无终止地进行下去，实际上有效的递归调用函数(或过程)应包括两部分：递推规则(方法)；终止条件。Hanoi问题：voidhanoi(intn,charx,chary,charz)//算法3.5//将塔座x上按直径由小到大且至上而下编号为1至n的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。//搬动操作move(x,n,z)可定义为：(c是初值为0的全局变量，对搬动计数)printf("%i.Movedisk%ifrom%cto%c\n",++c,n,x,z);1{2if(n==1)3move(x,1,z);//将编号为１的圆盘从x移到z4else{5hanoi(n-1,x,z,y);6move(x,n,z);//将编号为n的圆盘从x移到z7hanoi(n-1,y,x,z);//将y上编号为１至n-1的圆盘移到z,x作辅助塔8}9}

第8次教学活动设计教学环节内容设计与手段导入新课回顾栈的基本定义和存储结构，引入栈在实际问题中的应用。讲授内容1.数制转换2.括号匹配问题3.栈与递归的实现归纳总结数字转换问题中，栈是如何应用的；栈在括号匹配问题的所扮演的角色；递归程序是如何借助栈来实现的。第9次课程教学方案周次5课时数2教学章节第三章：栈和队列----队列目标要求队列及其基本概念；队列的存储结构及其实现重点难点循环队列教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源√文字教材√电子教案□录像材料□录音材料□直播课堂□CAI课件□IP课件□其他资源：课后作业请给出循环队列所涉及操作的C语言的代码实现。板书设计1.队列及其基本概念队列(Queue)、队首(front)、队尾(rear)2.队列的抽象数据类型定义ADTQueue{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n>=0}数据关系：R={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n}约定a1端为队首，an端为队尾。基本操作：pp.59}ADTQueue3.队列的链式表示和实现队列的链式存储表示:队列的链式存储结构简称为链队列，它是限制仅在表头进行；删除操作和表尾进行插入操作的单链表。需要两类不同的结点：数据元素结点，队列的队首指针和队；尾指针的结点。数据元素结点类型定义：typedefstructQnode{QElemTypedata;structQnode*next;}QNode,*QueuePtr;指针结点类型定义：typedefstructlink_queue{QueuePtrfront;QueuePtrrear;}LinkQueue;链队列的基本操作的实现：链队列的初始化；链队列的入队操作；链队列的出队操作；链队列的撤消。4.队列的顺序表示和实现利用一组连续的存储单元(一维数组)依次存放从队首到队尾的各个元素，称为顺序队列。对于队列，和顺序栈相类似，也有动态和静态之分。本部分介绍的是静态顺序队列，其类型定义如下：#defineMAX_QUEUE_SIZE100typedefstructqueue{ElemTypeQueue_array[MAX_QUEUE_SIZE];intfront;intrear;}SqQueue;设立一个队首指针front，一个队尾指针rear，分别指向队首和队尾元素.队满：rear=MAX_QUEUE_SIZE-1。顺序队列中存在“假溢出”现象。因为在入队和出队操作中，头、尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际元素个数可能远远小于数组大小，但可能由于队尾巳不能做入队操作。该现象称为假溢出。设队列大小为5=MAX_QUEUE_SIZE，即rear和front的变化范围为0~MAX_QUEUE_SIZE-1（4）为充分利用向量空间，克服上述“假溢出”现象的方法是：将为队列分配的向量空间看成为一个首尾相接的圆环，并称这种队列为循环队列(CircularQueue)。在循环队列中进行出队、入队操作时，队首、队尾指针仍要加1，朝前移动。只不过当队首、队尾指针指向向量上界(MAX_QUEUE_SIZE-1)时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：if(i==MAX_QUEUE_SIZE-1)i=0;elsei++;其中：i代表队首指针(front)或队尾指针(rear)用模运算可简化为：i=(i+1)%MAX_QUEUE_SIZE;循环队列的基本操作循环队列的初始化；入队操作；出队操作。

第9次教学活动设计教学环节内容设计与手段导入新课介绍队列在实际生活及编程中的应用，引入学习队列的意义。讲授内容1.队列及其基本概念2.队列的抽象数据类型定义3.队列的链式表示和实现4.队列的顺序表示和实现归纳总结队列的基本定义；队列的两种不同的存储结构；循环队列。

第10次课程教学方案周次5课时数2教学章节第四章串—串的定义及基本操作目标要求串的定义及基本操作串的存储重点难点串的存储教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源√文字教材√电子教案□录像材料□录音材料□直播课堂□CAI课件□IP课件□其他资源：课后作业请解释OFFICE办公软件中WORD文字编辑器中所用到的串的操作。板书设计1.串的基本概念串(字符串)、串值、串长、空串、空格串(空白串)、子串(substring)、子串的序号。2.串的抽象数据类型定义ADTString{数据对象：D={ai|ai∈CharacterSet,i=1,2,…,n,n≥0}数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n}基本操作：pp.71}3.串的存储表示和实现串是一种特殊的线性表，其存储表示和线性表类似，但又不完全相同。串的存储方式取决于将要对串所进行的操作。串在计算机中有3种表示方式：定长顺序存储表示：将串定义成字符数组，利用串名可以直接访问串值。用这种表示方式，串的存储空间在编译时确定，其大小不能改变。堆分配存储方式：仍然用一组地址连续的存储单元来依次存储串中的字符序列，但串的存储空间是在程序运行时根据串的实际长度动态分配的。块链存储方式：是一种链式存储结构表示。4.串的定长顺序存储表示及基本操作的实现这种存储结构又称为串的顺序存储结构。是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先确定。定长顺序存储结构定义为：#defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];//总共256个单元（0~255），可以存放的字符数为255，0号单元存放串的长度基本操作有：串的联结操作；求子串操作；

第10次教学活动设计教学环节内容设计与手段导入新课介绍串在实际生活及编程中的应用，引入学习串的意义。讲授内容1.串的基本概念2.串的抽象数据类型定义3.串的存储表示和实现4.串的定长顺序存储表示及基本操作的实现归纳总结串的基本定义；串的抽象数据类型定义；串的存储结构及其基本操作的实现。

第11次课程教学方案周次6课时数2教学章节第四章串—模式匹配目标要求熟悉理解KMP算法重点难点KMP算法教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源√文字教材√电子教案□录像材料□录音材料□直播课堂□CAI课件□IP课件□其他资源：课后作业请用C语言编程实现KMP算法。板书设计串的定长顺序存储结构定义为：#defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];//总共256个单元（0~255），可以存放的字符数为255，0号单元存放串的长度1.朴素的模式匹配算法采用定长顺序存储结构，可以写出不依赖于其他串操作的匹配算法：intIndex(SStringS,SStringT,intpos){//算法4.5：定长顺序存储//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。//其中，T非空，1≤pos≤StrLength(S)。inti=pos;intj=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}//继续比较后继字符else{//指针后退到原先主串i的位置是：i-j+1i=i-j+2;//原先主串i的位置的下一个位置为：i-j+2j=1;}}if(j>T[0])//每次S中的第i个字符和T中的第j个字符，比较相等后均+1；//故如果在S中找到和T相等的子串，则S和T在比较了最后一个相等的字符//后，均+1。此时j=T[0]+1(即存在子串的条件：j>T[0]))。returni-T[0];//由于i也+1，与T相等的子串在S中的位置:i-T[0]elsereturn0;}//Index具体模拟过程如下：此处假设pos=1该算法简单，易于理解。在一些场合的应用里，如文字处理中的文本编辑，其效率较高。该算法的时间复杂度为O(n*m)，其中n、m分别是主串和模式串的长度。通常情况下，实际运行过程中，该算法的执行时间近似于O(n+m)。理解该算法的关键点：每次匹配不成功时，都要将i退回到主串原先位置的下一个位置；将j退回到模式串的第1个位置。2.改进的模式匹配算法—KMP该改进算法是由D.E.Knuth，J.H.Morris和V.R.Pratt提出来的，简称为KMP算法。其改进在于：每当一趟匹配过程出现字符不相等时，主串指示器不用回溯，而是利用已经得到的“部分匹配”结果，将模式串的指示器向右“滑动”尽可能远的一段距离后，继续进行比较。设主串S为：‘s1s2s3……sn’,模式串T为‘p1p2p3……pm’。为了实现改进算法，需要解决如下问题：当匹配过程中产生“失配”（即si≠pj）时，模式“向右滑动”可行的距离有多远。换句话说，当主串的第i个字符与模式的第j个字符“失配”（即比较不相等）时，主串的第i个字符（i指针不回溯）应与模式中的哪个字符再比较?由以上分析可得KMP算法：(1)当匹配过程中产生失配时，指针i不变，指针j退回到next[j]所指示的位置上重新进行比较；(2)并且，当指针j退至0时，指针i和j同时加1。即若主串中的第i个字符和模式的第1个字符不相等，应从主串的第i+1个字符和模式的第1个字符重新进行匹配。intIndex_KMP(SStringS,SStringT,intpos){//T非空，1≤pos≤StrLength(S)。//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(j==0||S[i]==T[j]){++i;++j;}//继续比较后继字符elsej=next[j];//模式串向右移动}if(j>T[0])returni-T[0];//匹配成功elsereturn0;}//Index_KMP算法4.6,算法4.6是在模式串各个位置的next已知的情况下才能进行。故如何高效地求出next值呢？

第11次教学活动设计教学环节内容设计与手段导入新课模式匹配(模范匹配)：子串在主串中的定位称为模式匹配或串匹配(字符串匹配)。其中：子串称为模式串。模式匹配成功：是指在主串S中能够找到模式串T，否则，称模式串T在主串S中不存在。模式匹配的应用在非常广泛。例如，在文本编辑程序中，我们经常要查找某一特定单词在文本中出现的位置。显然，解此问题的有效算法能极大地提高文本编辑程序的响应性能。讲授内容1.朴素的模式匹配算法2.改进的模式匹配算法—KMP归纳总结next的自动化求解：next[1]=0;若next[j]=k;则next[j+1]:若:pj=pk,则next[j+1]=next[j]+1否则:next[j+1]=next[k]+1

第12次课程教学方案周次6课时数2教学章节第五章、数组与广义表5.1数组的定义5.2数组的顺序表示和实现目标要求1.了解数组的两种存储表示方法。2.掌握数组在以行为主序的存储结构中的地址计算方法。重点难点1.多维数组和广义表的逻辑结构特征：它们是复杂的非线性结构。一个数据元素可能有多个直接前趋和多个直接后继。2.多维数组的两种顺序存储方式：行优先顺序和列优先顺序。这两种存储方式下的地址计算方法。教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源□文字教材√电子教案□录像材料□录音材料□直播课堂√CAI课件□IP课件□其他资源：课后作业(1)C中二维数组floata[5][4]的起始地址为2000，且每个数组元素长度为32位（即4个字节），求数组元素a[3][2]的内存地址。（2）数据A[1..8,-2..6,0..6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4个字节，试求元素A[4,2,3]的存储首地址。板书设计5.1数组的定义5.1.1数组的定义数组的特点是每个数据元素可以又是一个线性表结构。数组定义：若线性表中的数据元素为非结构的简单元素，则称为一维数组，即为向量；若一维数组中的数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组二维数组可以看成是这样一个定长线性表：它的每个数据元素也是一个定长的线性表。5.1.2数组的基本操作数组结构一般在创建时就确定了组成该结构的行向量数目和列向量数目，因此，在数组结构中不存在插入、删除元素的操作。给定一组下标，修改该位置元素的内容Assign(A,item,index1,index2)给定一组下标，返回该位置的元素内容Value(A,item,index1,index2)5.2数组的顺序表示和实现数组一般采用顺序存储结构。从理论上讲，数组结构也可以使用两种存储结构，即顺序存储结构和链式存储结构。一般的数组结构不使用链式存储结构。数组的存储表示：组成数组结构的元素可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。对于数组，一旦规定了它的维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置。在C语言中数组的存储采用以行序为主序的存储结构。假设每个数据元素占L个存储单元，则上述二维数组A中任一元素aij的存储位置可由下式确定：LOC(i,j)=LOC(0,0)+(n*i+j)*L

第12次教学活动设计教学环节内容设计与手段导入新课前面几章中，讨论的线性表中的元素主要为简单数据类型。当线性表中的元素又为一个线性表时，如何处理？导入新课：线性表的推广：数组和广义表。讲授内容5.1数组的定义5.1.1数组的定义5.1.2数组的基本操作5.2数组的顺序表示和实现归纳总结（1）理解数组和一般线性表之间的差异。（2）重点掌握数组的顺序存储结构和元素地址计算方法。对一个已知以行序为主序的计算机系统中,当二维数组第一个数据元素a1,1的存储地址LOC(a1,1)和每个数据元素所占用的存储单元k确定后,则该二维数组中任一数据元素ai,j的存储地址可由下式确定：LOC(ai,j)=LOC(a1,1)+[(i-1)*n+(j-1)]*k其中n为列数。同理可推出在以列序为主序的计算机系统中有：LOC(ai,j)=LOC(a1,1)+[(j-1)*m+(i-1)]*k其中m为行数。

第13次课程教学方案周次7课时数2教学章节第五章数组和广义表5.3特殊矩阵的压缩存储5.4稀疏矩阵的压缩存储目标要求（1）掌握各种特殊矩阵如对称矩阵、上、下三角矩阵和对角矩阵的压缩存储方法；（2）掌握稀疏矩阵的各种存储结构以及基本运算实现算法。重点难点（1）几种特殊矩阵的特征及其压缩存储地址对应关系。（2）稀疏矩阵的三元组存储表示方法；（3）稀疏矩阵的压缩存储及以及矩阵转置运算的实现算法。。教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源□文字教材√电子教案□录像材料□录音材料□直播课堂√CAI课件□IP课件□其他资源：课后作业（1）为什么特殊矩阵可以采用压缩存储？（2）对于一个m╳m的对称，若采用压缩存储，则需要多少个存储单元？（3）已知b对角矩阵（aij）m*n，以行为主序将b对角线上的非零元存储在一维数组中，每个数据元素占L个存储单元，存储基地址为S，请用i，j表示出aij的存储位置。板书设计5.3矩阵的压缩存储5.3.1特殊矩阵1.对称矩阵:对称矩阵的特点是aij=aji2.下（上）三角矩阵特点是以主对角线为界的上（下）半部分是一固定值，下（上）半部分元素值没有任何规律。3.对角矩阵:特点是所有的非零元素都集中在以主对角线为中心的带状区域中。5.3.2特殊矩阵压缩方法（1）对称矩阵在对称矩阵中有n(n-1)/2个元素可以通过其他获得。压缩方法是将二维关系映射成一维关系，并存储其中必要的n(n+1)/2个（主对角线和下三角）元素，这些元素的存储顺序以行为主序。（2）下（上）三角矩阵下三角矩阵的压缩存储与上面讲述的对称矩阵的压缩存储一样，只是将上三角部分的常量值存储在0单元，下三角和主对角上的元素从1号单元开始存放。（3）对角矩阵对于对角矩阵，压缩存储的主要思路是只存储非零元素。这些非零元素按以行为主序的顺序，从下标为1的位置开始依次存放在一维数组中，而0位置存放数值0。5.4稀疏矩阵的压缩存储若一个m×n的矩阵含有t个非零元素，且t远远小于m*n，则我们将这个矩阵称为稀疏矩阵。(1)稀疏矩阵的压缩存储方法——三元组表示法。矩阵中的每个元素都是由行序号和列序号唯一确定的。因此，我们需要用三项内容表示稀疏矩阵中的每个非零元素，即形式为：(i,j,value)其中，i表示行序号，j表示列序号，value表示非零元素的值，通常将它称为三元。(2)矩阵的转置：两种转置实现算法。

第13次教学活动设计教学环节内容设计与手段导入新课在大量的工程应用中，涉及到矩阵及其运算。对于特殊矩阵，在计算机中如何来进行存储？根据矩阵的特殊性，能否采用压缩存储？如何对特殊矩阵进行压缩存储？对矩阵的运算又会带来哪些影响？讲授内容5.3矩阵的压缩存储5.3.1特殊矩阵1.对称矩阵:对称矩阵的特点是aij=aji2.下（上）三角矩阵3.对角矩阵:特点是所有的非零元素都集中在以主对角线为中心的带状区域中。5.3.2特殊矩阵压缩方法（1）对称矩阵（2）下（上）三角矩阵（3）对角矩阵5.4稀疏矩阵的压缩存储(1)稀疏矩阵的压缩存储方法——三元组表示法。(2)矩阵的转置：两种转置实现算法。归纳总结（1）各种特殊矩阵如对称矩阵、上、下三角矩阵和对角矩阵的压缩存储方法；（2）稀疏矩阵的各种存储结构（三元组表示方法）以及基本运算（稀疏矩阵的转置运算）实现算法。

第14次课程教学方案周次7课时数2教学章节第五章数组和广义表5.5广义表的定义5.6广度表的存储结构目标要求（1）掌握广义表的定义和广义表的链式存储结构；（2）掌握广义表的基本运算，包括创建广义表、输出广义表、求广义表的长度和深度。重点难点（1）广义表的定义和广义表的链式存储结构；（2）掌握广义表的二种重要运算，取头和取尾操作。（3）能画出广义表的图形表示法。教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源□文字教材√电子教案□录像材料□录音材料□直播课堂√CAI课件□IP课件□其他资源：课后作业（1）假设采用以下两种结点的链表作为广义表的存储结构，表结点：（tag=1,hp,tp），元素结点：(tag=0,data)。请画了下列广义表的存储结构图，并求出它的深度和长度。（（），（（（）），（（（）））））。（2）GetHead(GetTail(GetHead(((a,b,c),(d,e)))))。板书设计5.5广义表1.广义表的定义广义表是线性表的推广的概念。广义表一般记作：LS=(a1,a2,…,an)其中LS为广义表的名称，n是长度。在线性表的定义中，ai只限于是单个元素，而在广义表的定义中，ai可是单个元素，也可广义表，分别称为LS的原子和子表。当广义表非空时，第一个元素称为LS的表头，称其余元素组成的表为LS的表尾。2.广义表的特点（1）广义表的元素可以是子表，而子表的元素还可以是子表。广义表是一个多层次的结构。（2）广义表可以其他广义表所共享，其可以通过子表的名称来引用。（3）广义表可以是一个递归的表，即广义表也可以是其本身的一个子表。（4）任何一个非空的广义表其表头可能是原子，也可能是子表，而其表尾必定为子表。5.6广义表的存储结构(1)广义表的链式存储结构由于广义表中的元素可具有不同的结构，因此难以采用顺序存储结构表示，而通常采用链式存储结构，每个元素可用一个结点表示。(2)结点结构=1\*GB3①表结点 =2\*GB3②原子结点 (3)类型定义

第14次教学活动设计教学环节内容设计与手段导入新课复习旧课：简要的回顾解特殊矩阵的压缩存储和稀疏矩阵的压缩及矩阵的转置运算。讨论的线性表中的元素主要为简单数据类型。当线性表中的元素又为一个线性表时，如何处理？导入新课：线性表的推广：广义表。广义表在计算机中如何表示与存储？讲授内容5.5广义表1.广义表的定义2.广义表的特点（1）广义表的元素可以是子表，而子表的元素还可以是子表。广义表是一个多层次的结构。（2）广义表可以其他广义表所共享，其可以通过子表的名称来引用。（3）广义表可以是一个递归的表，即广义表也可以是其本身的一个子表。（4）任何一个非空的广义表其表头可能是原子，也可能是子表，而其表尾必定为子表。5.6广义表的存储结构(1)广义表的链式存储结构(2)结点结构(3)类型定义归纳总结本章小结：（1）理解数组和一般线性表之间的差异。（2）重点掌握数组的顺序存储结构和元素地址计算方法。（3）掌握各种特殊矩阵如对称矩阵、上、下三角矩阵和对角矩阵的压缩存储方法。（4）掌握稀疏矩阵的各种存储结构以及基本运算实现算法。（5）掌握广义表的定义和广义表的链式存储结构。（6）掌握广义表的基本运算,包括创建广义表、输出广义表、求广义表的长度和深度。第15次课程教学方案周次8课时数2教学章节第六章树和二叉树6.1树的定义和基本术语6.2.1目标要求（1）掌握树的定义和基本术语；（2）掌握二叉树的定义和性质。重点难点（1）二叉树的性质教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源□文字教材√电子教案□录像材料□录音材料□直播课堂√CAI课件□IP课件□其他资源：课后作业数据结构习题集6.1，6.2，6.3，6.5板书设计1.树的概念树是一个有n个节点的有限集合。在任意一棵非空树中：有且仅有一个根节点；其余节点可以分为若干个互不相交的有限集合；每个集合本身也是一棵树。（画出几个图，判断是否是树）树的特点：连通：各个节点之间均可以沿着边互达；无环：从任何一个节点出发，沿着树的边最多经过其它节点一次，不会回到出发点。一个有n个节点的树，一共有n-1条边。2.树的基本术语画图介绍树的基本术语3.二叉树的定义：二叉树是一棵树，每个节点的度不超过2，并且二叉树的子树有左右之分。画出几种树，判断是否是二叉树。4.二叉树的性质：性质1.在二叉树的第i层上至多有2i-1个节点(i>=1)性质2.深度为k的二叉树至多有2k-1个节点性质3.对任何二叉树，如果终端节点数为n0，度为2的节点数为n2，则n0=n2+1。性质4.具有n个节点的完全二叉树的深度为[log2n]+1

第15次教学活动设计教学环节内容设计与手段导入新课我们已经学习了线性表等结构，这些都是线性结构。今天我们学习一种非线性结构：树型结构。讲授内容树的基本概念和术语：二叉树的概念二叉树的性质归纳总结树的基本定义和相关术语二叉树的定义二叉树的性质

第16次课程教学方案周次8课时数2教学章节第六章树和二叉树6.2.3二叉树的存储结构6.3.1遍历二叉树目标要求（1）掌握二叉树的存储结构；（2）掌握二叉树的遍历算法重点难点（1）二叉链表；（2）二叉树的遍历算法及其非递归实现。教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源□文字教材√电子教案□录像材料□录音材料□直播课堂√CAI课件□IP课件□其他资源：课后作业数据结构习题集6.12，6.14，板书设计1.顺序存储结构如何把非线性的逻辑结构映射到线性的物理地址空间？把一个任意二叉树补足为一棵完全二叉树，对完全二叉树进行遍历可以得到线性序列。（画出6.4所示二叉树的补足结果以及线性存储结果）2.链式存储结构除叶子节点之外，每个节点都有最多两个孩子节点每个节点保存两个指针域，分别指向两个孩子节点二叉链表（画出图6.8所示二叉树的二叉链表）（写出二叉链表的ADT）3.二叉树的遍历按照某种规则依次访问二叉树的每一个节点。先序遍历（画出6.8所示二叉树的先序遍历结果）（写出先序遍历的递归算法）中序遍历（画出6.8所示二叉树的中序遍历结果）（写出中序遍历的非递归算法）后序遍历（画出6.8所示二叉树的后序遍历结果）（写出后序遍历的非递归算法）

第16次教学活动设计教学环节内容设计与手段导入新课上次课讨论了二叉树的概念与性质，本次课我们研究如何在物理上实现二叉树的存储，以及如何遍历二叉树的各个元素。讲授内容二叉树的存储结构顺序存储结构、二叉链表结构二叉树的遍历算法先序遍历、中序遍历、后序遍历归纳总结二叉树的顺序存储二叉树的链式存储二叉树的遍历算法

第17次课程教学方案周次9课时数2教学章节第六章树和二叉树6.3.2线索二叉树目标要求（1）掌握线索链表存储结构；（2）掌握二叉树线索化方法。重点难点（1）二叉树的线索化方法教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源□文字教材√电子教案□录像材料□录音材料□直播课堂√CAI课件□IP课件□其他资源：课后作业数据结构习题集6.15，6.16板书设计1.二叉树的线索画出图6.11中的二叉树，讲解什么是线索。2.线索链表结构写出线索链表的结构3.线索化算法书写并讲解算法6.5，6.6

第17次教学活动设计教学环节内容设计与手段导入新课回顾二叉树的遍历引入：如何把遍历结果记录在二叉树中？讲授内容二叉树的线索线索链表存储结构线索化算法归纳总结二叉树的线索线索链表存储结构线索化算法第18次课程教学方案周次9课时数2教学章节第六章树和二叉树6.4树和森林目标要求（1）掌握树的存储结构；（2）掌握森林与二叉树的转换；（3）掌握树和森林的遍历算法。重点难点（1）树的存储结构；（2）森林与二叉树的转换教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源□文字教材√电子教案□录像材料□录音材料□直播课堂√CAI课件□IP课件□其他资源：课后作业数据结构习题集6.19，6.20，6.21，6.22。板书设计1.树的存储结构1）双亲表示法：每个节点记录双亲节点。（画出6.13，介绍双亲表示法）（写出双亲表示法的结构体）2）孩子表示法：每个节点记录孩子节点。（画出6.14，介绍孩子链表表示法）3）孩子兄弟表示法：把树转换为二叉树，用二叉链表存储。（画出6.15，讲解树转换为二叉树的过程）2.森林与二叉树的转换引入一个虚拟的根节点，把森林变成一棵树转换为二叉树去掉根节点，得到森林的二叉树表示。（画出图6.16，6.17，演示森林与二叉树之间的转换）3.树和森林的遍历1）先序遍历森林：访问森林中第一棵树的根节点先序遍历第一个树根的子树森林先序遍历剩余的树构成的森林（画出图6.17的先序遍历结果）2）中序遍历森林：中序遍历森林中第一棵树根的子树森林访问第一棵树的根节点中序遍历剩余的树构成的森林（画出图6.17的中序遍历结果）

第18次教学活动设计教学环节内容设计与手段导入新课复习二叉树的基本概念讲授内容1.树的存储结构2.森林与二叉树的转换3.树与森林的遍历归纳总结1.树的存储结构2.森林与二叉树的转换3.树与森林的遍历

第19次课程教学方案周次10课时数2教学章节第六章树和二叉树6.6哈夫曼树及其应用目标要求（1）掌握路径、路径长度、带权路径长度的概念（2）掌握最优二叉树的构建方法（3）理解前缀编码的定义与性质，掌握哈夫曼编码的算法（4）掌握哈夫曼树和哈夫曼编码的存储结构（5）学会编写哈夫曼编码算法重点难点（1）哈夫曼树的构造方法（1）哈夫曼编码算法（2）用c语言实现哈夫曼编码算法教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源□文字教材√电子教案□录像材料□录音材料□直播课堂√CAI课件□IP课件□其他资源：课后作业数据结构习题集第六章6.26板书设计6.6.1.最优二叉树1.路径长度（画出图6.22的二叉树），讲解路径、路径长度、带权路径长度的概念2.最优二叉树（哈夫曼树）由n个权值构造一个带有n个叶子节点的二叉树，每个叶子节点的权值为wi，其中带权路径长度最小的二叉树。3.如何构造一个哈夫曼树？通过实例讲解。6.6.2哈夫曼编码1.前缀编码例：假设需要传送的电文只有A、B、Ｃ、Ｄ四个字符，如何设计这四个字符的编码？可能的设计方案：Ａ:00,B:01,C:11,D:10;特点：任何一个字符的编码都不会构成另一个字符的前缀，在接收端可以正确解码。符合这种特点的编码叫做前缀编码。2.编码长度第i个字符的编码长度为li，某电文中第i个字符出现的次数为ni,则电文的总编码长度为L=sum_i{ni*li};按照上述编码方案，电文“AACCDBBBBB”的编码长度为L=20;如何设计合适的编码方案使得电文的平均编码长度最小？平均编码长度L=sum_i{wi*li},wi是第i个字符在电文中出现的概率。3.哈夫曼编码把li看作是一棵二叉树的树根到第i个叶子节点的路径长度，wi表示这个叶子节点的权重，则平均编码长度恰好是树的带权路径长度。最小平均编码长度最小带权路径长度最短二进制前缀编码方案以字符出现概率wi做权，设计一个哈夫曼树称这样得到的二进制前缀编码为哈夫曼编码（举例）课本例6-2在黑板上逐步构造出哈夫曼树，并设计出哈夫曼编码；4.哈夫曼编码的程序实现定义哈夫曼树结构：typedefstruct_HTNode{unsignedintw;unsignedinparent,lchild,rchild;}HTNode,*HuffmanTree;讲解算法6.12,6.13

第19次教学活动设计教学环节内容设计与手段导入新课回顾二叉树的有关概念。引入新课：二叉树的应用？讲授内容1.路径长度2.哈夫曼树3.哈夫曼树的构造方法4.前缀编码前缀编码的特点，及其原因。5.编码长度编码长度的概念，如何计算编码长度，平均编码长度的概念。6.哈夫曼编码平均编码长度与二叉树的带权路径长度之间的对应关系；最短平均编码长度与哈夫曼树的带权路径长度之间的对应关系；利用哈夫曼树构造哈夫曼编码；同一个字符集，可以有多种不同的哈夫曼编码7.编写哈夫曼编码程序归纳总结1.哈夫曼树的概念和构造方法；2.前缀编码的特点；3.平均编码长度的概念和计算4.哈夫曼编码的原理5.哈夫曼编码程序第20次课程教学方案周次10课时数2教学章节第六章树和二叉树6.7回溯法与树的遍历目标要求（1）理解回溯法的思想（2）学会利用回溯法解决简单的搜索问题重点难点（1）理解回溯法教学方式√课堂讲授□小组活动□实验演示□难点答疑□提问□作业讲评□实践教学□考试测验□其他活动媒体资源□文字教材√电子教案□录像材料□录音材料□直播课堂√CAI课件□IP课件□其他资源：课后作业编写程序求解八皇后问题板书设计1.幂集（