数据结构教案(共76页).doc

《数据结构教案(共76页).doc》由会员分享，可在线阅读，更多相关《数据结构教案(共76页).doc（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上滁州学院计算机科学与技术系课程教案课程名称：数据结构授课教师：王精明学习对象：07网络工程任课时间：2009年2月-2009年7月滁州学院计算机科学与技术系2009年2月一、学生情况分析数据结构是计算机专业的一门核心专业课程。学生在前期的学习中已经学习了C语言程序设计课程。通过本课程学习使学生对提高编写程序的能力以及解决实际问题的能力。二、课程教学目标数据结构是计算机学科中一门核心专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养

2、基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。三、课程教学内容1、教学重点和难点教学重点掌握常用的各种数据结构以及相关的算法。 教学难点算法的设计与分析。2、知识范围及与相关课程的关系本课程是计算机专业的重要专业课之一，要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。本课程主要讲授数据结构的相关概念及简单算法分析、线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、排序等内容。先修课程：C语言程序设计3、课程内容及学时分配课时安排：按18周计共72课时，理论54个课时，实验18个课时，。各章课时分配如

3、下：第一章 绪论教学内容：1） 什么是数据结构2） 抽象数据类型概念；数据类型；数据抽象与抽象数据类型；用于描述数据结构的语言3） 数据结构的抽象层次4） 算法定义5）性能分析与度量；算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；教学要求： 了解：数据结构基本概念及数据结构的抽象层次 了解：抽象数据类型概念 了解：算法的定义及算法特性 掌握：算法的性能分析与度量方法第二章 线性表教学内容：1） 线性表的定义和特点2） 线性表的顺序存储及查找、插入和删除操作3） 线性表的链式存储及查找、插入和删除操作4） 使用线性表的实例教学要求：了解：

4、线性表的定义和特点熟练掌握：线性表的顺序存储结构的查找、插入和删除等基本操作熟练掌握：单链表、循环链表及双向链表的定义及实现掌握：熟练掌握单链表的应用方法第三章 栈和队列教学内容：1） 栈：栈的抽象数据类型；栈的顺序存储表示；栈的链式存储表示2） 队列：队列的抽象数据类型；队列的顺序存储表示；队列的链式存储表示3） 队列的应用举例教学要求：熟练掌握：栈的定义及实现熟练掌握：队列的定义及实现掌握：能运用栈和队列解决简单实际问题第四章 串教学:内容：1) 字符串的抽象数据类型2) 字符串操作的实现3) 字符串的模式匹配教学要求：熟练掌握：字符串的定义方式熟练掌握：字符串的各种操作的实现了解：字符串

5、的模式匹配算法第五章 数组和广义表教学:内容：1) 数组的定义和初始化2) 作为抽象数据类型的数组的顺序存储方式教学要求：了解：作为抽象数据类型的数组的定义熟练掌握：顺序表的数组定义方式及实现第六章 树和二叉树教学内容：1) 树和森林的概念：树的定义；树的术语；树的抽象数据类型；森林的概念2) 二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型3) 二叉树的表示：数组表示；链表存储表示4) 二叉树的遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的实例；二叉树的中序非递归算法5) 线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化6) 树与森林：树的存储表示；森林与二叉树的转换；

6、树的遍历；森林的遍历7) 二叉树的计数8) 霍夫曼树：路径长度；霍夫曼树；霍夫曼树编码教学要求：了解：树和森林的概念掌握：二叉树的概念、性质及二叉树的表示熟练掌握：二叉树的遍历方法掌握：线索化二叉树的特性及寻找某结点的前驱和后继的方法掌握：树和森林的实现及遍历方法掌握：二叉树的计数方法及从二叉树遍历结果得到二叉树的方法掌握：霍夫曼树的实现方法及霍夫曼编码的概念第七章 图教学内容：1）图的基本概念：图的基本概念；图的抽象数据类型2）图的存储表示：邻接矩阵；邻接表；邻接多重表3）图的遍历与连通性；深度优先搜索；广度优先搜索；连通分量4）最小生成树：克鲁斯卡尔算法；普里姆算法5）活动网络：用顶点表示

7、活动的网络；用边表示活动的网络教学要求：掌握：图的基本概念和图的存储表示熟练掌握：图的两种遍历方法与求解连通性问题的方法掌握：构造最小生成树的Prim和Kruskal方法熟练掌握：活动网络的拓扑排序方法掌握：求解关键路径的方法第九章 查找教学内容：1) 静态查找表：顺序表的查找；有序表的查找；索引顺序表的查找2) 二叉排序树：二叉排序树上的搜索、插入和删除3) 哈希表：哈希表的定义；哈希函数的构造方法；处理冲突的方法；哈希表的查找及其分析教学要求：熟练掌握：静态搜索表的顺序搜索和折半搜索方法熟练掌握：二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法熟练掌握：哈希法：包括哈希函数的构造、解

8、决冲突的方法和哈希表的查找及分析第十章 内部排序 教学内容：1) 概述2) 插入排序：直接插入排序；对分插入排序；链表插入排序；希尔排序3) 交换排序：起泡排序；快速排序4) 选择排序：直接选择排序；堆排序5) 归并排序：归并；迭代的归并排序算法；递归的表归并表示6) 基数排序：多关键码排序教学要求：掌握：排序的基本概念和性能分析方法掌握：插入排序、交换排序、选择排序、归并排序等内排序的方法及性能分析方法了解：基数排序方法及性能分析方法了解：多路平衡归并等外排序方法 四、教学方法“数据结构”课程是一门理论与实践并重的课程，是一门核心专业课程。1)课堂讲授：本课程的理论以课堂讲授为主，采用板书教

9、学。2)实验教学：理论教学与课程实践有机结合,将上机实践题目与理论教学的知识点紧密结合，理论教学结束之后立即启动上机实验，使得理论学习与课程实践同步。3)作业：每章安排一定的概念题、编程题和综合分析题，巩固理论和方法的掌握。单元名称：第 一 讲：绪论 一、教学目标 1.了解数据结构课程的体系结构2.掌握本章介绍的各种基本概念和术语3.了解数据结构的二元组表示4.掌握逻辑结构与物理结构之间的映像关系。二、学生情况分析 数据结构是一门强调理论和实践相结合的课程，学生需要使用已有的C语言程序设计课程的相关知识来学习本课程。三、教学内容分析 本讲介绍数据结构相关概念和术语，抽象数据类型、算法以及算法分

10、析等内容，通过学习让学生掌握相关概念与术语，了解抽象数据类型的表示与实现为以后的学习奠定基础，掌握算法以及算法分析方法。四、重点与难点重点：数据结构的基本概念；逻辑结构与物理结构之间的映像关系。难点：逻辑结构与物理结构之间的映像关系。五、教学过程的具体安排介绍本学期课程的内容及安排本课程是计算机专业的重要专业课之一，主要介绍常用的数据结构以及相关算法。本课程主要讲授线性表、栈和队列、串、数组、树和二叉树、图、查找、排序等内容。成绩考核方式为：期末成绩+平时成绩，其中期末成绩占70%，平时成绩占30%，平时成绩为：作业成绩+出勤率+上机成绩。讲授新课1.1 什么是数据结构 讲解：（数据结构课程的

11、研究背景）从计算机最初以数值计算为主到大量非数值计算出现引出数据结构。讲解：（数据结构课程的研究对象）例1-1图书馆的书目检索系统自动化问题。1-2计算机和人机对奕问题1-3多叉路口交通灯的管理问题总结：从以上三个例子可以看出，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如线性表、树和图等之类的数据结构，这些都是数据结构课程的研究对象。因此，简单地说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。介绍数据结构课程的发展以及与其他课程之间的关系。1.2基本概念和术语基本概念：数据、数据元素、数据项、数据对象、数据结构、结构（1）常见基本

12、结构（逻辑结构）：集合、线性结构、树形结构、图状结构或网状结构数据结构的形式定义： 数据结构一般用一个二元组来表示：Data_Structure=(D,S)其中：D是数据元素的有限集，S是D上的关系的有限集表示一种数据结构，它由数据元素集合K和在K上定义的一种二元关系的集合R所组成。其中：是数据元素的有限集合，n为中数据元素的个数。是K上关系的有限集合，m为K上关系的个数，通常情况下m的取值为1。K上任何一个二元关系Rj是序偶的集合。对于Rj中的任一序偶（x，yK），称x为第一个元素（或y的前驱），y为第二个元素（或x的后继）。数据结构中的数据元素和数据元素之间的关系还可以用图形直观地表示出来

13、。图形中的每个结点对应一个数据元素，两结点之间带箭头的连线对应二元关系中的一个序偶，其中序偶的第一个元素称为弧尾，第二个元素称为弧头。举例讲解：例 数据结构line=K，R，其中K=01，02，03，04，05，06，07，08，09，10，R=r，r=，,，。例数据结构tree=K，R，其中K=01，02，03，04，05，06，07，08，09，10，R=r，r=，。例 数据结构graph=K，R，其中K=01，02，03，04，05，R=r，r=，。介绍常见数据结构（集合、线性结构、树型结构、图型结构）具体表示方式(2) 逻辑结构上述数据结构的定义是对操作对象的一种数学描述，是从操作对象

14、抽象出来的数学模型。结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。根据这种逻辑关系通常将数据结构划分为线性结构和非线性结构，其中非线性结构又分为树型结构和图型结构。(3) 物理结构数据结构在计算机中的表示（存储映象）称为数据的物理结构或存储结构，它涉及到数据元素及其相互关系在计算机内部的表示形式。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。根据数据元素相互之间的关系在计算机中的表示形式将数据的物理结构划分为顺序结构和链式结构。顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像的特点是借助指示元素存储地

15、址的指针表示数据元素之间的逻辑关系。注意：数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据的逻辑结构，而算法的实现依赖于采用的存储结构。（4）数据结构一般包括三方面内容： 数据的逻辑结构、数据的存储结构、数据的运算 （举例讲解）小结：总结本讲的主要内容参考资料和深入学习途径教材：数据结构 严蔚敏，吴伟民等编著，清华大学出版社。六、作业布置见习题集七、后记 第二讲 抽象数据类型和算法分析一、教学目标1掌握数据类型和抽象数据类型的概念；2了解算法的特性和算法的设计原则；3重点掌握估算时间复杂度的方法；4了解估算空间复杂度的方法。二、学生情况分析 数据结构是一门强调理

16、论和实践相结合的课程，学生需要使用已有的C语言程序设计课程的相关知识来学习本课程。三、教学内容分析 本讲介绍数据结构相关概念和术语，抽象数据类型、算法以及算法分析等内容，通过学习让学生掌握相关概念与术语，了解抽象数据类型的表示与实现为以后的学习奠定基础，掌握算法以及算法分析方法。二、重点与难点分析1教学重点：数据类型和抽象数据类型；估算时间复杂度的方法。2教学难点：估算时间复杂度的方法。三、教学内容与教学过程数据类型数据类型是一个值的集合和定义在这个值集合上的一组操作总称，它决定了该类型数据的取值范围、在计算机内存中如何表示以及可以参加哪些运算。数据结构中讨论的数据结构是通过高级语言中的数据类

17、型来实现的。在高级程序设计语言中，数据类型可分原子类型和结构类型。原子类型的值是不可分解的。如C语言中整型、字符型、浮点型、双精度型等基本类型，分别用保留字int、char、float、double标识。结构类型的值是由若干成分按某种结构组成的，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的。例如，数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。在某种意义上，数据结构可以看成是“一组具有相同结构的值”，而数据类型则可被看成是由一种数据结构和定义在其上的一组操作所组成的。抽象数据类型抽象数据类型是一种描述用户和数据之间接口的抽象模型，它定义了数据的取值范围和表现结构以及对

18、数据的操作集。在C+语言中使用用户定义的类(class)类型来表示抽象的数据类型。抽象数据类型可以用三元组表示(D, R, P)其中：D是数据元素集合，R是D上的关系集合，P是对D的基本操作集。本书采用以下格式表示抽象数据类型：ADT 抽象数据类型名 数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义 ADT 抽象数据类型名其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：基本操作名（参数表）初始条件：初始条件描述操作结果：注意：基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。初始条件描述了操作执行之前数

19、据结构和参数应满足的条件下，若条件不满足，则操作失败并返回相应的出错信息。操作结果说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。算法和算法分析计算机专家N.Wirth提出一个著名的公式：程序数据结构算法，这个公式揭示了数据结构与算法两者的重要性和统一性。算法是指对特定问题求解步骤的一种抽象描述，与具体的计算机无关；而程序是指在特定的计算机上执行的算法。1、算法特性(1)有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即算法中的每个步骤都能在有限时间内完成。(2)确定性 算法中的每一条指令必须有确切的含义。读者理解时不会产生二义性。并且在任何条

20、件下，算法都只有一条执行路径，即对于相同的输入只能得出相同的输出。(3)可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算执行有限次来实现。(4)有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。(5)有输出它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。2、算法设计的原则设计算法时，评介算法的好坏的标准通常应考虑达到以下目标：(1)正确性首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以

21、下四个层次：a程序中不含语法错误；b程序对于几组输入数据能够得出满足要求的结果；c程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果；d程序对于一切合法的输入数据都能得出满足要求的结果。通常以第c层的正确性作为衡量一个算法是否合格的标准。(2)可读性算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。(3)健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的

22、抽象层次上进行处理。(4)高效率与低存储量需求效率指的是算法执行时间；存储量需求指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。3、算法效率的衡量 (1) 算法效率的度量方法(A) 事后统计法缺点：1必须运行根据算法编写程序；2计算机的软硬件环境等因素掩盖算法本质。(B) 事前分析估算法和算法执行时间相关的因素： a. 算法选用的策略；b. 问题的规模；c. 编写程序的语言；d. 编译程序产生的机器代码的质量；e. 计算机执行指令的速度。撇开与计算机软硬件有关的因素，可以认为一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数

23、。为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。(2) 算法效率的度量准则算法的“运行工作量”通常是随着问题规模的增长而增长，因此比较不同算法的优劣主要可以其“增长的趋势”为准则。假如，随着问题规模n的增长，算法执行时间的增长率和的增长率相同，则可记作：称T(n)为算法的渐近时间复杂度，简称时间复杂度。显然，被称做问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作，多数情况下是最深层循环内的语句中的原操作，它的执行次数和包含它的语句频度相同。语句频度指的是该语

24、句重复执行的次数。设Dn是问题规模大小为n的集合，i是Dn中的一个数据元素，P(i)是数据元素i出现的概率，而T(i)是算法在处理数据元素i时所需要基本运算的执行次数，则：算法的平均时间复杂度定义为：算法的最坏时间复杂度定义为：本书中所给出的大多数算法将进行最坏情形分析，当说到一个算法的时间复杂性时，除非特别说明外，否则指的是最坏情形时间复杂度。通常，表示时间复杂度的阶有常数阶O(1)，对数阶O(logn)，线性阶O(n)，平方阶O(n2)，多项式阶O(nk)以及指数阶O(2n)。我们应该尽可能地选用多项式阶而不希望使用指数阶去设计算法。计算。long factor_sum(int n)for

25、 (sum=0, i=1; i=n; i+)w=1;for (j=1; j=i; j+) w=wi; sum = sum+w; return(sum)；时间复杂度分析：。分析算法的目的之一是为了改进算法。改进算法的思路是：首先寻求改进的方法能够降低工作量的阶，然后关心那些可以减少工作量但不影响阶的细节问题。下面改进例2中的算法，改进之后的算法描述如下：long update_factor_sum(int n)for(sum=0, w=1, i=1; i=n; i+) w=wi; sum=sum+w; return (sum);时间复杂度分析：。4、算法的存储空间需求算法的空间复杂度S(n) =

26、 O(g(n)表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。算法的存储量包括：a) 输入数据所占空间;b) 程序本身所占空间；c) 辅助变量所占空间。若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。小结：本讲主要介绍了数据类型和抽象数据类型的概念，算法的特性和算法设计原则，估算算法时间复杂度和空间复杂度的方法。四、作业1. 描述数据类型和抽象数据类型之间的关系。2. 值传递、地址传递和引用传递之间的区别。3.

27、比较两函数n2和50nlog2n的增长趋势，并确定n在什么范围内，函数的值n2大于50nlog2n的值。五、后记单元名称：第 三 讲：线性表 （一）一、教学目标 掌握线性表的顺序表示和实现二、学生情况分析在已有程序设计的基础上学习线性表学生理解较容易，主要是理解抽象数据类型表示是难点。三、教学内容分析 本讲介绍线性表以及线性表的顺序表示与实现，线性表是最常见且最简单的一种数据结构，学习难度不大。通过本讲学习使学生理解抽象数据类型线性表定义，掌握基本操作的实现。四、重点与难点线性表的顺序表示和实现。五、教学过程的具体安排讲授新课2.1线性表的类型定义 线性表的定义：一个线性表是n 个数据元素的有

28、限序列。其中每个数据元素的具体含义，在不同的情况下各不相同，但是同一线性表中的元素必定具有相同特性，即属于同一数据对象。例如：26个英文字母表；学生健康情况登记表（图2.1）等。 例如线性表（a1,ai-1,ai,ai+1,an），称ai-1是ai的直接前驱元素， ai+1是 ai的直接后继。引导学生自己总结线性结构的特点。线性表的长度：线性表中元素的个数（n0），n=0为空表。 线性表中数据元素的位序（如数据元素ai在线性表中的位序为i）。抽象数据类型线性表的定义：讲解定义中的数据对象，数据关系以及基本操作（教材P19），重点讲解常用的基本操作含义。通过示例2-1，2-2讲解更复杂的基本操作

29、，并分析时间复杂度。2.2 线性表的顺序表示和实现（1）线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的数据元素。（2）顺序储存的地址关系：假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC( a i+1)和第i个数据元素的存储位置LOC(a i)之间满足下列关系：LOC(a i+1)=LOC(a i)+l 线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l，其中LOC(a1)为线性表的基地址。（3）顺序表及其特点, 顺序储存结构是一种随机存取的存储结构。（4）

30、线性表的动态分配顺序存储结构。 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 Typedef struct ElemType *elem;int length;int listsize;SqList;(1) 基于顺序存储结构的基本操作的实现主要介绍下面的基本操作并且分析时间复杂度。InitList_Sq(SqList &L);ListInsert_Sq(SqList &L, int i, ElemType e); ListDelete_Sq(SqList &L, int i, ElemType &e);LocateElem_Sq(SqL

31、ist L, ElemType e, Status (*compare)(ElemType, ElemType);MergeList_Sq(SqList La,SqList Lb, SqList &Lc);重点讲解：顺序存储结构上实现线性表的插入操作设线性表，为了保证线性表的有序性，当在位置i之前插入一个新的数据元素x时，需要将第i个到第n个数据元素均向后移动一个位置，然后将数据元素x存储到第i个位置上并改变线性表的长度。Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序线性表L的第i个元素之前插入新的元素e，/ i的合法值为1iL

32、istlength_Sq(L)+1if (i L.length+1) return ERROR; / 插入位置不合法if (L.length = L.listsize) / 当前存储空间已满，增加分配 newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) exit(OVERFLOW); / 存储分配失败L.elem = newbase; / 新基址L.listsize += LISTINCREMENT; / 增加存储容量q = &(L.elemi-1); /

33、 q指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;/ 插入位置及之后的元素右移*q = e; / 插入e+L.length; / 表长增1return OK; / ListInsert_Sq平均时间复杂度分析： 顺序存储结构上实现线性表的删除操作设线性表 ，为了保证线性表的有序性,当删除第个位置上的元素后，需要将第i+1个到第n个数据元素均向前移动一个位置并改变线性表的长度。Status ListDelete_Sq(SqList &L, int i, ElemType &e) / 在顺序线性表L中删除第i个元素，并用e返回

34、其值。/ i的合法值为1iListLength_Sq(L)if (i L.length) return ERROR; / 删除位置不合法p = &(L.elemi-1); / p为被删除元素的位置e = *p; / 被删除元素的值赋给eq = L.elem+L.length-1; / 表尾元素的位置for (+p; p next = NULL; / 先建立一个带头结点的单链表for (i = n; i 0; -i ) p = (LinkList) malloc (sizeof (LNode); / 生成新结点scanf(&p-data); / 输入元素值p-next = L-next; L-n

35、ext = p; / 插入到表头 / CreateList_L注：从头部插入元素建立单向链表得到的线性序列为输入序列的逆序列。(2) 建立单链表（要求从尾部插入）void CreateList_L(LinkList &L, int n) /正位序输入n个元素的值，建立带表头结点的单链线性表L。L = (LinkList) malloc (sizeof (LNode); r = L;L-next = NULL; / 先建立一个带头结点的单链表for (i = n; i 0; -i ) p = (LinkList) malloc (sizeof (LNode); / 生成新结点scanf(&p-d

36、ata); / 输入元素值p-next=r-next; r-next=p; r = p; / 插入到表尾 / CreateList_L (3) 在带头结点的单链表中插入结点分析：设在结点a和结点b之间插入数据为x的结点，通过图来分析则插入前和插入后的情况。Status ListInsert_L(LinkList L, int i, ElemType e) / 在带头结头的单链表L中第i位置之前插入元素ep = L; j = 0;while (p & j next; +j; / 寻找第i-1个结点if (!p | j i-1) return ERROR; / i小于1或者大于表长s = (Lin

37、kList) malloc ( sizeof (LNode); / 生成新结点s-data = e; s-next = p-next; / 插入L中p-next = s;return OK; / LinstInsert_L(4) 在带头结点的单链表中删除结点Status ListDelete_L(LinkList L, int i, ElemType &e) p = L; j = 0;while (p-next & j next; +j; /寻找第i个结点并令p指向其前趋if (!(p-next) | j i-1) return ERROR; / 删除位置不合理q = p-next; p-ne

38、xt = q-next; / 删除并释放结点e = q-data; free(q);return OK; / ListDelete_L注：上述两个算法的时间复杂度均为O(n)。单链表的优点：它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间插入、删除操作方便单链表的缺点：指针占用额外存储空间不能随机存取，查找速度慢小结：本讲主要介绍了单链表的存储结构，以及的基本操作（建立、插入和删除）的实现。参考资料和深入学习途径教材：数据结构 严蔚敏，吴伟民等编著，清华大学出版社。六、作业布置见习题集实验作业见实验指导。七、后记 第五讲 线性表 （三）一、教学目标 1了解循环链表和双向链表的基本概

39、念；2掌握双向链表的插入和删除操作；3掌握一元多项式的表示及加法在链式存储结构上的实现。二、学生情况分析 通过实践练习加深对链式表示和实现的理解。三、教学内容分析 本讲介绍线性表的链式表示与实现，重点需要掌握几种链表的存储方式和基本操作实现。四、重点与难点双向链表的存储结构和基本操作实现。五、教学过程的具体安排讲授新课单向循环链表设指针p指向单向链表中最后一个结点，则p-next的值是0，表示该结点是单向链表的最后一个结点。如果将单向链表中的最后一个结点的指针域改为存放单向链表中第一个结点的地址值，使得整个线性链表构成一个环，则称这种线性链表为单向循环链表。设p指向单向循环链表中的最后一个结点，则p-next的值不是0而是等于指向循环链表中的第一个结点head的值。双向链表如果链表中的每个结点都有两个指针域，分别指向其前驱结点和后继结点，则称这种链表为双向链表。双向链表中的结点类型描述如下：typedef struct DuLNode ElemType data; / 数据域struct DuLNode *prior; / 指向前驱的指针域struct DuLNode *next; / 指向后