数据结构学习培训课件.ppt

1、数 据 结 构第一章第一章 绪绪 论论1.1 什么是数据结构什么是数据结构1.2 有关概念和术语有关概念和术语1.3 算法和算法分析算法和算法分析 1.3.1 算法算法 1.3.2 算法设计的要求算法设计的要求 1.3.3 算法效率的度量算法效率的度量 1.3.4 算法的存储空间的需求算法的存储空间的需求第一章第一章 绪绪 论论 计算机是一门研究利用计算机进行信息表示和处理的科学。计算机是一门研究利用计算机进行信息表示和处理的科学。涉及：涉及：信息的表示信息的表示 信息的处理信息的处理 而信息的表示和组织又直接关系到处理信息的程序的效率。而信息的表示和组织又直接关系到处理信息的程序的效率。随着

2、计算机的普及，信息量的增加，信息范围的拓宽，使许多系随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个写出一个“好好”的程序，必须分析待处理的对象的特征及各对象的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。之间存在的关系，这就是数据结构这门课所要研究的问题。1.1 什么是数据结构什么是数据结构 众所周知，计算机的程序是对信息进行处理。在大众所周知，计算机的程序是对信息进行处理。在大多数情况下，这些信息并不是没有组织的，信息

3、（数多数情况下，这些信息并不是没有组织的，信息（数据）之间往往具有重要的结构关系，这就是数据结构据）之间往往具有重要的结构关系，这就是数据结构的内容。什么是数据结构呢？的内容。什么是数据结构呢？例子：例子：例例1、电话号码查询系统、电话号码查询系统 设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了N个人的名字和其个人的名字和其相应的电话号码，假定按如下形式安排：相应的电话号码，假定按如下形式安排：(a1，b1)(a2，b2)(an，bn)其中其中(ai，bi)(i=1，2n)分别表示某人的名字和对应分别表示某人的名字和对应的电话号码。要求设计一个算法，当给定任何一个人的电话号码。要求设

4、计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的信息。没有这个人的信息。数据结构含义：数据结构含义：就是研究数据的逻辑结构和物理结构以及它们就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来且确保经过这些运算后所得到的新结构仍然是原来的结构类型。的结构类型。所有能所有能被输入被输入到计算机中，且能被计

5、算机到计算机中，且能被计算机处理的符号处理的符号的集合。的集合。数据数据:是是计算机操作的对象计算机操作的对象的总称。的总称。是计算机处理的是计算机处理的信息的信息的某种特定的符号某种特定的符号表表示形式示形式。1.2 1.2 有关概念和术语有关概念和术语是数据（集合）中的一个是数据（集合）中的一个“个体个体”数据元素数据元素:是数据结构中讨论的是数据结构中讨论的基本基本单位单位数据结构主要指逻辑结构和物理结构数据结构主要指逻辑结构和物理结构 数据之间的相互关系称为逻辑结构。通常分数据之间的相互关系称为逻辑结构。通常分为四类基本结构：为四类基本结构：一、一、集合集合 结构中的数据元素除了同属于

6、一种结构中的数据元素除了同属于一种类型外，别无其它关系。类型外，别无其它关系。二、二、线性结构线性结构 结构中的数据元素之间存在一结构中的数据元素之间存在一对一的关系。对一的关系。三、三、树型结构树型结构 结构中的数据元素之间存在结构中的数据元素之间存在一对多的关系。一对多的关系。四、四、图状结构或网状结构图状结构或网状结构 结构中的数据元素结构中的数据元素之间存在多对多的关系。之间存在多对多的关系。一个数据元素可由若干个数据项组成。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据项是数据的不可分割的最小单位。数据对象数据对象(Data Object)：是性质相同的数据

7、是性质相同的数据元素的集合。是数据的一个子集。元素的集合。是数据的一个子集。数据结构数据结构(Data Structure)：是相互之间存是相互之间存在一种或多种特定关系的数据元素的集合在一种或多种特定关系的数据元素的集合。数据在计算机中的表示称为数据的数据在计算机中的表示称为数据的物理物理结构结构，又称为，又称为存储结构存储结构。数据对象可以是有限的，也可以是无限的。数据对象可以是有限的，也可以是无限的。数据结构不同于数据类型，也不同于数据对数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系

8、。要描述数据对象各元素之间的相互关系。数据类型数据类型：在一种程序设计语言中，变量所具有的数：在一种程序设计语言中，变量所具有的数据种类。据种类。例例1、在在FORTRAN语言中，变量的数据类型有整型语言中，变量的数据类型有整型、实型、和复数型、实型、和复数型 例例2、在、在C+语言中语言中数据类型：基本类型和构造类型数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定构造类型：数组、结构、联合、指针、枚举型、自定义义数据对象数据对象：某种数据类型元素的集合。：某种数据类型元素的集合。例例3、整数的数据对象是、整

9、数的数据对象是-3，-2，-1，0，1，2，3，英文字符类型的数据对象是英文字符类型的数据对象是A，B，C，D，E，F，1.3 算法和算法分析算法和算法分析1.3.1 算法：算法：是对特定问题求解步骤的一种描述，是指令的有限序列，其中是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。每一条指令表示一个或多个操作。算法具有以下五个特性：算法具有以下五个特性：（1）有穷性有穷性 一个算法必须总是在执行有穷步之后结束，且每一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。一步都在有穷时间内完成。（2）确定性确定性 算法中每一条指令必须有确切的含义。不

10、存在二义算法中每一条指令必须有确切的含义。不存在二义性。性。（3）可行性可行性 一个算法是可行的。即算法描述的操作都是可以通一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。过已经实现的基本运算执行有限次来实现的。（4）输入输入 一个算法有零个或多个输入，这些输入取自于某个特一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。定的对象集合。（5）输出输出 一个算法有一个或多个输出，这些输出是同输入有着一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。某些特定关系的量。1.3.2 1.3.2 算法设计的要求算法设计的要求设计算法时，通常应考

11、虑达到以下目标：设计算法时，通常应考虑达到以下目标：1 1正确性正确性2.2.可读性可读性3 3健壮性健壮性4 4高效率与低存储量需求高效率与低存储量需求1 1正确性正确性 首先，首先，算法应当满足以特定的算法应当满足以特定的“规格规格说明说明”方式给出的需求。方式给出的需求。其次，其次，对算法是否对算法是否“正确正确”的理解可的理解可以有以下四个层次：以有以下四个层次：a a程序中不含语法错误；程序中不含语法错误；b b程序对于几组输入数据能够得出程序对于几组输入数据能够得出满足要求的结果；满足要求的结果；c c程序对于精心选择的、典型、苛刻且程序对于精心选择的、典型、苛刻且带有刁难性的几组

12、输入数据能够得出满足带有刁难性的几组输入数据能够得出满足要求的结果；要求的结果；通常以通常以第第 c c 层层意义的正确性作意义的正确性作为衡量一个算法是否合格的标准。为衡量一个算法是否合格的标准。d d程序对于一切合法的输入数据都能得程序对于一切合法的输入数据都能得出满足要求的结果；出满足要求的结果；2.2.可读性可读性 算法主要是为了人的阅读与交流，算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该其次才是为计算机执行，因此算法应该易易于人的理解于人的理解；另一方面，晦涩难读的程序；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。易于隐藏较多错误而难以调试。3 3健壮性健

13、壮性 当当输入的数据非法输入的数据非法时，算法应当恰当时，算法应当恰当地作出反映或地作出反映或进行相应处理进行相应处理，而不是产，而不是产生莫名奇妙的输出结果。并且，处理出生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。以便在更高的抽象层次上进行处理。4 4高效率与低存储量需求高效率与低存储量需求通常，效率指的是通常，效率指的是算法执行时间算法执行时间；存储量指的是算法执行过程中存储量指的是算法执行过程中所需的所需的最大存储空间最大存储空间，

14、两者都与问题的规模，两者都与问题的规模有关。有关。1.3.3 1.3.3 算法效率的度量算法效率的度量通常有两种衡量算法效率的方法通常有两种衡量算法效率的方法:事后统计法事后统计法事前分析估算法事前分析估算法缺点：缺点：1 1必须执行程序必须执行程序 2 2其它因素掩盖算法本质其它因素掩盖算法本质和算法执行时间相关的因素：和算法执行时间相关的因素：1 1算法选用的策略算法选用的策略2 2问题的规模问题的规模3 3编写程序的语言编写程序的语言4 4编译程序产生的机器代码的质量编译程序产生的机器代码的质量5 5计算机执行指令的速度计算机执行指令的速度 一个特定一个特定算法的算法的“运行工作量运行工

15、作量”的大小，只依赖于的大小，只依赖于问题的规模问题的规模（通常用整数量通常用整数量n n表示），或者说，表示），或者说，它是问题规模的函数。它是问题规模的函数。假如，随着问题规模假如，随着问题规模 n n 的增长的增长，算法执行时间的增长率和，算法执行时间的增长率和 f(nf(n)的的增长率相同，则可记作：增长率相同，则可记作：T(n)=O(f(n)称称T(nT(n)为算法的为算法的(渐近渐近)时间复杂度时间复杂度。如何估算如何估算 算法的时间复杂度？算法的时间复杂度？算法算法=控制结构控制结构+原操作原操作 （固有数据类型的操作）（固有数据类型的操作）算法的执行时间算法的执行时间=原操作原

16、操作(i)i)的执行次数原操作的执行次数原操作(i)i)的执行时间的执行时间 算法的执行时间算法的执行时间 与与 原操作执行次数之和原操作执行次数之和 成正比成正比 从算法中选取一种对于所研究的从算法中选取一种对于所研究的问题来说是问题来说是 基本操作基本操作 的原操作，以的原操作，以该基本操作该基本操作 在算法中重复执行的次在算法中重复执行的次数数 作为算法运行时间的衡量准则。作为算法运行时间的衡量准则。void mult(int a,int b,int c)for(i=1;i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;/fo

17、r/mult基本操作:乘法乘法操作时间复杂度:O(n3)例例1例例 +x;s=0;将将x自增看成是基本操作，则语句频度为，即时间复杂度为自增看成是基本操作，则语句频度为，即时间复杂度为(1)如果将如果将s=0也看成是基本操作，则语句频度为也看成是基本操作，则语句频度为1，其时间复杂度，其时间复杂度仍为仍为(1)，即常量阶。，即常量阶。例例 for(i=1;i=n;+i)+x;s+=x;语句频度为：语句频度为：n其时间复杂度为：其时间复杂度为：O(n)即时间复杂度为线性阶。即时间复杂度为线性阶。i=0:赋值次赋值次i=1:赋值赋值 2 次次i=2:赋值赋值3次次i=n-1:赋值赋值n次次.+1+

18、2+3+n=(1+n)n/2=n2/2+n/2例例 for(i=1;i=n;+i)for(j=1;j=n;+j)+x;s+=x;语句频度为：语句频度为：n2其时间复杂度为：其时间复杂度为：O(n2)即时间复杂度为平方阶。即时间复杂度为平方阶。例例 for(i=0;i=n-1;+i)for(j=0;j1=n0，n为正整数为正整数时，时，xn+1xn，所以：所以：|an|*|xn|+|an-1|*|xn-1|+|a1|*|x1|+|a0|*|x0|an|*|xn|+|an-1|*|xn|+|a1|*|xn|+|a0|*|xn|=(|an|+|an-1|+|a1|+|a0|)|xn|=c|xn|其中

19、：其中：n0=1,c=|an|+|an-1|+|a1|+|a0|,g(n)=xn 一个算法时间为一个算法时间为O(1)的算法，它的基本运算执行的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为次多项式）来限界。而一个时间为O(n2)的算法则由一的算法则由一个二次多项式来限界。个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其以下六种计算算法时间的多项式是最常用的。其关系为：关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间的关系为：指数时间的关系为：O(2

20、n)O(n!)0;i-)for(j=0;jaj+1)aj aj+1;最好情况：最好情况：0次次 最坏情况：每次都换，最坏情况：每次都换，(n2)例例7 7：递归程序的分析递归程序的分析int fact(int n)if(n=1)return 1;else return n*fact(n-1);f(n)=c+f(n-1)=c+(c+f(n-2)=2c+f(n-2)=(n-1)c+f(1)=(n-1)c+c01.3.4 1.3.4 算法的存储空间的需求算法的存储空间的需求算法的空间复杂度定义为算法的空间复杂度定义为:表示随着问题规模表示随着问题规模 n n 的增大，算法运的增大，算法运行所需存储量

21、的增长率与行所需存储量的增长率与 g(ng(n)的增长率相的增长率相同。同。S(nS(n)=)=O(g(nO(g(n)算法的存储量包括算法的存储量包括:1输入数据输入数据所占空间2程序本身程序本身所占空间3辅助变量辅助变量所占空间 若输入数据所占空间只取决于问题本身，和算若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析法无关，则只需要分析除输入和程序之外的辅助变除输入和程序之外的辅助变量所占额外空间量所占额外空间。若所需额外空间相对于输入数据量来说是常数，则若所需额外空间相对于输入数据量来说是常数，则称此算法为称此算法为原地工作原地工作。若所需存储量依赖于特定的输入，则通常按最坏情

22、若所需存储量依赖于特定的输入，则通常按最坏情况考虑。况考虑。注意：时间与空间往往是对矛盾，要综合考虑。注意：时间与空间往往是对矛盾，要综合考虑。作业：作业：.计算时间复杂度计算时间复杂度 sum=1;for(i=0;sumn;i+)sum+=i;2.设给定若干设给定若干n值，比较两函数值，比较两函数n2和和50nlog2n的增长趋势，的增长趋势，并确定在并确定在什么范围内，函数什么范围内，函数n2的值大于的值大于50nlog2n的值。的值。答案答案:(自做自做)1.sum=0+1+2+m=m*(m+1)/2n m*(m+1)2n m*m2n m 50nlog2n=n 50log2n=2 n n

23、50=n439 第二章第二章 线性表线性表2.1 线性表的类型定义线性表的类型定义2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 线性表的链式表示和实现线性表的链式表示和实现 2.3.1 线性链表线性链表 2.3.2 循环链表循环链表 2.3.3 双向链表双向链表 2.4 一元多项式的表示及相加一元多项式的表示及相加2.1 线性表的逻辑结构线性表的逻辑结构 线性表线性表：由由n(n0)个数据元素个数据元素(结点结点)a1，a2，an组成的有限序列。其中数据元素的个数组成的有限序列。其中数据元素的个数n定义为表的定义为表的长度。当长度。当n=0时称为空表，常常将非空的线性表时称为空表

24、，常常将非空的线性表(n0)记作：记作：(a1，a2，an)这里的数据元素这里的数据元素ai(1in)只是一个抽象的符号，只是一个抽象的符号，其具体含义在不同的情况下可以不同。其具体含义在不同的情况下可以不同。例例1、26个英文字母组成的字母表个英文字母组成的字母表 （A，B，C、Z）例例2、某校从某校从1978年到年到1983年各种型号的计算机拥有年各种型号的计算机拥有量的变化情况。量的变化情况。（6，17，28，50，92，188）.神经衰弱神经衰弱 17 男男790634张立立张立立 健康健康 21 男男790633刘建平刘建平 一般一般 20 女女790632陈陈 红红 健康健康 18

25、 男男790631王小林王小林 健康情况健康情况年龄年龄性性 别别学学 号号姓姓 名名例例3 3、学生健康情况登记表如下：、学生健康情况登记表如下：从以上例子可看出线性表的逻辑特征是：从以上例子可看出线性表的逻辑特征是：(1)对非空的线性表，有且仅有一个开始结点对非空的线性表，有且仅有一个开始结点a1，它没有直接前它没有直接前趋，而仅有一个直接后继趋，而仅有一个直接后继a2；(2)有且仅有一个终端结点有且仅有一个终端结点an，它没有直接后继，而仅有一个直它没有直接后继，而仅有一个直接前趋接前趋a n-1；(3)其余的内部结点其余的内部结点ai(2in-1)都有且仅有一个直接前趋都有且仅有一个直

26、接前趋a i-1和一个直接后继和一个直接后继ai+1。线性表是一种典型的线性结构。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。在存储结构上进行的。2.2 线性表的顺序存储结构线性表的顺序存储结构2.2.1 线性表线性表 把线性表的结点按逻辑顺序依次存放在一组地址连续的把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。存储单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用假设线性表的每个元素需占用m m个存储单元，并以所占的个存

27、储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置作为参考点第一个单元的存储地址作为数据元素的存储位置作为参考点。则线性表中第。则线性表中第i+1i+1个数据元素的存储位置个数据元素的存储位置Loc(aLoc(ai+1i+1)和第和第i i个个数据元素的存储位置数据元素的存储位置Loc(aLoc(ai i)之间满足下列关系：之间满足下列关系：Loc(aLoc(ai+1i+1)=)=Loc(aLoc(ai i)+m)+m a ai ia ai+1i+1Loc(aLoc(ai+1i+1)m m个字节个字节Loc(aLoc(ai i)线性表的第线性表的第i个数据元素个数据元素ai的存储位置

28、为的存储位置为 :a1a2aianLoc(a1)i-1个元素个元素Loc(ai)=(i-1)*m+Loc(a1)=Loc(a1)-m+i*m由于由于Loc(a1)和和m都是已知的都是已知的所以：所以：V0=Loc(a1)-mLoc(ai)=V0+i*m 由于在高级语言中的一维数组也是采用顺序存储表由于在高级语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，利用来表示线性表的长度属性，利用C+C+语

29、言的结构类型来语言的结构类型来定义顺序表类型。定义顺序表类型。#define ListSize 100 /表容量表容量 typedef int DataType;/以以int为例为例 struct Sqlist DataType dataListSize;int lenth;/当前表中元素数当前表中元素数 ;lenthlenth.SqlistdatadataListSizeListSize个个2.2.2 顺序表上实现的基本操作顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性表的一些操作，如在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第线性表的构造、第i个元素的访问

30、。个元素的访问。注意：注意：C/C+语言中的数组下标从语言中的数组下标从“0”开始，因此，若开始，因此，若L是是Sqlist类型的顺序表，则表中第类型的顺序表，则表中第i个元素位置是个元素位置是L.datai-1。线性表的插入和删除两种运算。线性表的插入和删除两种运算。1、插入、插入 线性表的插入运算是指在表的线性表的插入运算是指在表的i(1in+1)个位置上，插入个位置上，插入一个新结点一个新结点x，使长度为使长度为n的线性表的线性表 (a1，a i-1，ai，an)变成长度为变成长度为n+1的线性表的线性表 (a1，a i-1，x，ai，an)注：注：可用可用memmove(L.data+

31、i+1,L.dada+i,(L.lenth-i+1)*sizeof(DataType)代替代替for循环（包含文件：循环（包含文件：string.h,一般格式一般格式格式：格式：memmove(目的地址，源地址，移动字节数目的地址，源地址，移动字节数)void InsertList(L,x,i)/在线性表在线性表L中第中第i个个位置插入元素位置插入元素x if(iL.length+1)cout“插入序号错误插入序号错误”=ListSize)溢出处理；溢出处理；else for(j=L.length-1;j=i-1;j-)/第第i个元素（下标为个元素（下标为i-1)开始开始 L.dataj+1=

32、L.dataj;/顺序后移顺序后移 L.datai-1=x;L.length+;memcpymemcpy(目的地址目的地址,源地址，字节数）源地址，字节数）memsetmemset(目的地址目的地址,字符，字节数）字符，字节数）intint a5050,b5050;a5050,b5050;a a清清0 0for(ifor(i=0;i50;i+)=0;i50;i+)for(jfor(j=0;j50;j+)=0;j50;j+)aijaij=0;=0;拷贝：拷贝：for(ifor(i=0;i50;i+)=0;i50;i+)for(jfor(j=0;j50;j+)=0;j最好情况；最好情况；当当=1时

33、，需移动表中所有结点时，需移动表中所有结点-最坏情况最坏情况，a1，a i-1，ai，anx x移动数据：移动数据：n-i+1n-i+1算法的平均移动算法的平均移动 由于插入可能在表中任何位置上进行，在长度为由于插入可能在表中任何位置上进行，在长度为n的线性表中第的线性表中第i个位置上插入一个结点，令个位置上插入一个结点，令Eis(n)表示表示移动结点的期望值（即移动的平均次数），则在第移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为个位置上插入一个结点的移动次数为n-i+1。Pi代表代表在第在第i个位置插入概率，则个位置插入概率，则 Eis(n)=p1*n+p2

34、*(n-1)+.+pn*1+pn+1*0 若表中任何位置若表中任何位置(1in+1)上插入结点的概率是上插入结点的概率是均等的，则均等的，则 p1=p2=p3=p n+1=1/(n+1)因此，在等概率插入的情况下：因此，在等概率插入的情况下：Eis(n)=1/(n+1)n+(n-1)+1+0=n/2a1，a i-1，ai，an可能的插入点有可能的插入点有n+1n+1处处结论：在顺序表上做插入运算，平均要结论：在顺序表上做插入运算，平均要移动表上一半结移动表上一半结点点。当表长。当表长 n较大时，算法的效率相当低。虽然较大时，算法的效率相当低。虽然Eis(n)中中n的的系数较小，但就数量级而言，

35、它仍然是线性阶的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为的。因此算法的平均时间复杂度为O(n)。2、删除删除 线性表的删除运算是指将表的第线性表的删除运算是指将表的第i(1in)结点删结点删除，使长度为除，使长度为n的线性表：的线性表：(a1，a i-1，ai，a i+1，an)变成长度为变成长度为n-1的线性表的线性表 (a1，a i-1，a i+1，an)void deleteList(L,i)/表L中删除第i个元素 if(iL.length)cout“删除序号错”endl;return ERROR;for(j=i;jch;while(ch!=$)p=new

36、 LNode;pdata=ch;pnext=h;h=p;cin ch;LNode*CreateList()char ch;LNode*h,*p;h=NULL;cinch;while(ch!=$)p=new LNode;pdata=ch;pnext=h;h=p;cin ch;return h;#include struct LNode char data;LNode*next;LNode*CreateList()char ch;LNode*h,*p;h=NULL;cinch;while(ch!=$)p=new LNode;pdata=ch;pnext=h;h=p;cin ch;return h;

37、void CreateList1(LNode *&h)char ch;LNode*p;h=NULL;cinch;while(ch!=$)p=new LNode;pdata=ch;pnext=h;h=p;cin ch;void print(LNode*h)LNode*p;while(p!=NULL)coutdatanext;coutch;while(ch!=$)p=new LNode;pdata=ch;if(head=NULL)head=p;else r-next=p;r=p;cinch;if(r!=NULL)r-next=NULL;return head;头结点（哨兵结点）引入：头结点（哨兵结

38、点）引入：增加一个表头结点，数据域可根据需要使用或不用。增加一个表头结点，数据域可根据需要使用或不用。特点：特点：a a、表中第一个结点和在表的其它位置上的操作一致，无需进表中第一个结点和在表的其它位置上的操作一致，无需进行特殊处理；行特殊处理；b b、无论链表是否为空，其头指针是指向头结点。因此空表和无论链表是否为空，其头指针是指向头结点。因此空表和非空表的处理统一。非空表的处理统一。NULLhead有头结点的空表有头结点的空表head=无头结点的空表无头结点的空表LNode*creat()LNode*r,*h;char ch;h=new LNode;r=h;cinch;while(ch!=

39、$)r-next=new LNode;r=r-next;r-data=ch;cinch;r-next=NULL;上述算法里动态申请新结点空间时未加错误处理，上述算法里动态申请新结点空间时未加错误处理，在实际使用时间，可作下列判定与处理：在实际使用时间，可作下列判定与处理：p=new LNode;if(p=NULL)错误处理；错误处理；二、查找运算二、查找运算 1 1、按序号查找、按序号查找 在链表中，即使知道被访问结点的序号在链表中，即使知道被访问结点的序号i i，也不也不能象顺序表中那样直接按序号能象顺序表中那样直接按序号i i访问结点，而只能从访问结点，而只能从链表的头指针出发，顺链域链表

40、的头指针出发，顺链域nextnext逐个结点往下搜索逐个结点往下搜索，直到搜索到第，直到搜索到第i i个结点为止。因此，个结点为止。因此，链表不是随机链表不是随机存取结构。存取结构。设单链表的长度为设单链表的长度为n n，要查找表中第要查找表中第i i个结点，个结点，仅当仅当1=1=i=ninext&jnext;j+;if(i=j)return p;else return NULL;2 2、按值查找、按值查找 按值查找是在链表中，查找是否有结点值等于给定值按值查找是在链表中，查找是否有结点值等于给定值keykey的结点，若有，则返回首次找到的其值为的结点，若有，则返回首次找到的其值为keyke

41、y的结点的存储位的结点的存储位置；否则返回置；否则返回NULLNULL。查找过程从开始结点出发，顺着链表逐查找过程从开始结点出发，顺着链表逐个将结点的值和给定值个将结点的值和给定值keykey作比较。其算法如下：作比较。其算法如下：LNode*locatenode(head，key)p=headnext;while(p&pdata!=key)p=pnext;return p;该算法的执行时间亦与输入实例中的的取值该算法的执行时间亦与输入实例中的的取值keykey有关，其有关，其平均时间复杂度的分析类似于按序号查找。平均时间复杂度的分析类似于按序号查找。三、插入运算三、插入运算 插入运算是将值为

42、插入运算是将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位置上个结点的位置上，即插入到，即插入到a ai-1i-1与与a ai i之间。因此，必须首先找到之间。因此，必须首先找到a ai-1i-1的存储位置的存储位置p p，然后生成一个数据域为然后生成一个数据域为x x的新结点，并令的新结点，并令q q指针指向该指针指向该新结点，新结点，新结点的指针域指向结点新结点的指针域指向结点a ai i。从而实现三个结点从而实现三个结点a ai-1i-1，x x和和a ai i之间之间的逻辑关系的变化的逻辑关系的变化x xa ai-1i-1a ai i三、插入运算三、插入运算 插入运

43、算是将值为插入运算是将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位置上个结点的位置上，即插入到，即插入到a ai-1i-1与与a ai i之间。因此，必须首先找到之间。因此，必须首先找到a ai-1i-1的存储位置的存储位置p p，然后生成一个数据域为然后生成一个数据域为x x的新结点，并令的新结点，并令q q指针指向该指针指向该新结点，新结点，新结点的指针域指向结点新结点的指针域指向结点a ai i。从而实现三个结点从而实现三个结点a ai-1i-1，x x和和a ai i之间之间的逻辑关系的变化的逻辑关系的变化a ai-1i-1a ai ix x三、插入运算三、插入运

44、算 插入运算是将值为插入运算是将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位置上个结点的位置上，即插入到，即插入到a ai-1i-1与与a ai i之间。因此，必须首先找到之间。因此，必须首先找到a ai-1i-1的存储位置的存储位置p p，然后生成一个数据域为然后生成一个数据域为x x的新结点，并令的新结点，并令q q指针指向该指针指向该新结点，新结点，新结点的指针域指向结点新结点的指针域指向结点a ai i。从而实现三个结点从而实现三个结点a ai-1i-1，x x和和a ai i之间之间的逻辑关系的变化的逻辑关系的变化a ai-1i-1a ai ix x三、插入运算

45、三、插入运算 插入运算是将值为插入运算是将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位置上个结点的位置上，即插入到，即插入到a ai-1i-1与与a ai i之间。因此，必须首先找到之间。因此，必须首先找到a ai-1i-1的存储位置的存储位置p p，然后生成一个数据域为然后生成一个数据域为x x的新结点，并令的新结点，并令q q指针指向该指针指向该新结点，新结点，新结点的指针域指向结点新结点的指针域指向结点a ai i。从而实现三个结点从而实现三个结点a ai-1i-1，x x和和a ai i之间之间的逻辑关系的变化的逻辑关系的变化a ai-1i-1a ai ix xp

46、 pq qq-next=p-next;q-next=p-next;三、插入运算三、插入运算 插入运算是将值为插入运算是将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位置上个结点的位置上，即插入到，即插入到a ai-1i-1与与a ai i之间。因此，必须首先找到之间。因此，必须首先找到a ai-1i-1的存储位置的存储位置p p，然后生成一个数据域为然后生成一个数据域为x x的新结点，并令的新结点，并令q q指针指向该指针指向该新结点，新结点，新结点的指针域指向结点新结点的指针域指向结点a ai i。从而实现三个结点从而实现三个结点a ai-1i-1，x x和和a ai i

47、之间之间的逻辑关系的变化的逻辑关系的变化a ai-1i-1a ai ix xp pq qq-next=p-next;q-next=p-next;p-next=q;p-next=q;三、插入运算三、插入运算 插入运算是将值为插入运算是将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位置上个结点的位置上，即插入到，即插入到a ai-1i-1与与a ai i之间。因此，必须首先找到之间。因此，必须首先找到a ai-1i-1的存储位置的存储位置p p，然后生成一个数据域为然后生成一个数据域为x x的新结点，并令的新结点，并令q q指针指向该指针指向该新结点，新结点，新结点的指针域指向

48、结点新结点的指针域指向结点a ai i。从而实现三个结点从而实现三个结点a ai-1i-1，x x和和a ai i之间之间的逻辑关系的变化的逻辑关系的变化a ai-1i-1a ai ix xp pq qq-next=p-next;q-next=p-next;p-next=q;p-next=q;三、插入运算三、插入运算 插入运算是将值为插入运算是将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位置上个结点的位置上，即插入到，即插入到a ai-1i-1与与a ai i之间。因此，必须首先找到之间。因此，必须首先找到a ai-1i-1的存储位置的存储位置p p，然后生成一个数据域为

49、然后生成一个数据域为x x的新结点，并令的新结点，并令q q指针指向该指针指向该新结点，新结点，新结点的指针域指向结点新结点的指针域指向结点a ai i。从而实现三个结点从而实现三个结点a ai-1i-1，x x和和a ai i之间之间的逻辑关系的变化的逻辑关系的变化a ai-1i-1a ai ix xp pq qq-next=p-next;q-next=p-next;p-next=q;p-next=q;定位定位a ai-1i-1并将指针并将指针p p指向它；指向它；三、插入运算三、插入运算 插入运算是将值为插入运算是将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位置上个结

50、点的位置上，即插入到，即插入到a ai-1i-1与与a ai i之间。因此，必须首先找到之间。因此，必须首先找到a ai-1i-1的存储位置的存储位置p p，然后生成一个数据域为然后生成一个数据域为x x的新结点，并令的新结点，并令q q指针指向该指针指向该新结点，新结点，新结点的指针域指向结点新结点的指针域指向结点a ai i。从而实现三个结点从而实现三个结点a ai-1i-1，x x和和a ai i之间之间的逻辑关系的变化的逻辑关系的变化a ai-1i-1a ai ix xp pq qq=new q=new LNodeLNode;q-data=x;q-data=x;q-next=p-nex