第4章数据结构与算法

第4章数据结构与算法本章学习目标与要求基本要求：掌握算法的基本概念、算法复杂度的概念和意义（时间复杂度与空间复杂度）；了解数据结构的定义，数据的逻辑结构与存储结构，数据结构的图形表示，线性结构与非线性结构的概念；掌握线性表的定义，线性表的顺序存储结构及其插入与删除运算；掌握栈和队列的定义，栈和队列的顺序存储结构及其基本运算；了解线性单链表、双向链表与循环链表的结构及其基本运算；掌握树的基本概念，二叉树的定义及其存储结构，二叉树的前序、中序和后序遍历；了解顺序查找与二分法查找算法，基本排序算法（交换类排序、选择类排序、插入类排序）。重点：

算法的时间复杂度；栈和队列；二叉树基本性质；树和二叉树；二叉树的遍历。难点：

算法的时间复杂度；线性链表；二叉树的遍历；查找和排序算法。

4.1算法4.1.1算法的基本概念1、算法的基本特征计算机求解问题的一般步骤：问题分析：准确、完整地理解和描述问题是解决问题的第一步。建立数学模型：用计算机解决问题必须有合适的数学模型。算法设计与选择：算法设计是指设计求解某一特定类型问题的一系列步骤，并且这些步骤可以通过计算机的基本操作来实现。算法设计要同时结合数据结构的设计，数据结构的设计就是选取合适的存储方式（简单描述）。算法分析：算法分析的目的，首先为了对算法的某些特定输入，估算该算法所需的内存空间和运行时间；其次是为了建立衡量算法优劣的标准，用以比较同一类问题的不同算法，通常将时间和空间的增长率作为衡量的标准。算法表示：对于复杂的问题，确定算法后可以通过图形（一般是流程图）准确地表示算法。算法实现：根据选用的程序设计语言，要解决下列一些问题：有哪些变量，它们是什么类型？需要多少数组，规模有多大？用什么结构来组织数据？需要哪些子算法？等等。算法的实现方式对运算速度和所需内存容量都有很大影响。程序测试：算法测试的实质是对算法应完成任务的实验证实，同时确定算法的使用范围。测试方法一般有两种：白盒测试对算法的各个分支进行测试；黑盒测试检验对给定的输入是否有指定输出。算法问题求解过程：正确性证明分析算法设计程序理解问题精确解或近似解建立数学模型，选择数据结构算法设计策略设计算法理解问题，进行问题陈述：用科学规范的语言，对所求解的问题作准确描述。建立数学模型：通过对问题的分析，找出其中所有的操作对象及操作对象之间的关系并用数学语言加以描述。算法设计：根据数学模型设计问题的计算机求解算法。算法的正确性证明：证明算法对一切合法输入均能在有限次计算后产生正确输出（但是目前研究很不完善）。算法分析：对执行该算法所消耗的计算机资源进行估算。算法的程序实现：将算法正确地编写成计算机语言程序。算法（Algorithm）：求解一类问题的一种特殊方法或一个过程，是对特定问题求解的一个步骤，是若干指令的有限序列。算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定的规范输入，在有限时间内获得所要求的输出。注意：不同的算法可能用不同的时间、空间或效率来完成同样的任务。如果一个算法有缺陷，或者不适合于某个问题，执行这个算法将不会解决这个问题。一个算法的优劣可以用时间复杂度与空间复杂度来衡量。算法具有下列特征：输入项（Input）：算法有零个或多个外部输入量。输出项（Output）：算法至少产生一个输出量，没有输出的算法是毫无意义的。确定性（Definiteness）：算法的每条指令（每一步）都有确切含义、没有二义性。能行性（可行性，Effectiveness）：算法的每条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现。原则上，算法可以由人用纸和笔在有限时间内精确地完成。有限性（有穷性，Finiteness）：算法必须总能在执行有限步之后终止，算法中每条指令的执行次数有限，执行每条指令的时间也有限。算法必须有输出：getsum(intnum)

{

inti,sum=0;

for(i=1;i<=num;i++)

sum+=i;

}

//无输出的算法没有任何意义算法必须有确定性：floataverage(int*a,intnum)

{inti;longsum=0;

for(i=0;i<num;i++)sum+=*(a++);

returnsum/num;

}

//缺少对num==0的处理

main()

{intscore[10]={1,2,3,4,5,6,7,8,9,0};

printf("%f",average(score,10));

}

算法必须有有穷性：haha()

{

//onlyajoke,donothing.

}

main()

{

printf(“请稍等...您将知道世界的未日...”);

while(1)haha();

}2、算法的基本要素（1）对数据对象的运算和操作计算机可以执行的基本操作是以指令的形式描述的，一个计算机系统的基本运算和操作有以下四类：算术运算：加、减、乘、除等运算逻辑运算：与、或、非等运算关系运算：大于、小于、等于、不等于等运算数据传输：输入、输出、赋值等运算（2）算法的控制结构算法的控制结构：一个算法的功能不仅仅取决非于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的的框架，它不仅决定了算法中各操作的执行顺序，也直接反映了算法的设计是否符合结构化原则。一个算法一般都以顺序、选择和循环3种基本控制结构组合而成。描述算法的工具通常有传统流程图、N-S结构化流程图和算法描述语言等。3、算法设计的基本方法

计算机算法设计有着不同于人工处理的方法，常用的算法设计的各种方法之间往往存在着一定的联系。列举法列举法的的思想是根据提出的问题，列举所有可能的情况并用问题中给定的条件检测哪些是需要的，哪些是不需要的。列举法常用于解决“是否存在”或“有多少种可能”等类型的问题。归纳法归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。

递推递推是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。递推本质上也属于归纳法，许多递推关系式实际上是通过对实际问题的分析与归纳而得到的，因此，递推关系式往往是归纳的结果。递归人们在解决一些复杂问题时，为了降低问题的复杂程度（如问题的规模等），一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来的分解的逆过程逐步进行综合，这就是递归的基本思想。递归分为直接递归与间接递归两种。递归方法举例（求n的阶乘）intfactorial(intn){if(n==0)return1;returnn*factorial(n-1);}减半递推技术实际问题的复杂程度往往与问题的规模有着密切的联系，因此利用分治法解决这类实际问题是有效的。计算机上常用的分治法就是一种减半递推技术。“减半”是指将问题的规模减半，而问题的性质不变；“递推”是指重复“减半”的过程。回溯法有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题一种有效的方法是“试”。通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，就得到问题的解；若试探失败，就逐步回退，换其他路线再逐步试探。算法设计的要求——衡量算法优劣的标准通常设计一个“好”的算法应考虑达到以下目标：（1）正确性（Correctness）：算法应当满足具体问题的需求。“正确”一词的含义在通常的用法中有很大差别，可分为以下四个层次：A、程序不含语法错误；B、程序对于几组输入数据能够得出满足规格说明要求的结果；C、程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能得出满足规格说明要求的结果；D、程序对于一切合法的输入数据都能产生满足规格说明要求的结果。（2）可读性（Readability）：算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解；晦涩难懂的程序易于隐藏较多的错误，并难以调试和修改。（3）健壮性（Robustness）：当输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫明其妙的输出结果。（4）效率与低存储量需求：效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。效率与低存储量需求这两者都与问题的规模有关。4.1.2算法复杂度算法复杂度主要包括时间复杂度和空间复杂度。算法复杂度是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂度，需要的空间资源的量称为空间复杂度。算法复杂度是一个只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。1、算法时间复杂度算法时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n的函数f(n)，算法的时间复杂度也因此记做T(n)=O(f(n)),n，f(n)是自变量为n的某个具体的整函数表达式，例如f(n)=n2。它表示随着问题规模n的增大，算法执行时间的增长率与f(n)的增长率相同，这称作算法的渐近时间复杂度（AsymptoticTimeComplexity），简称时间复杂度。例如，交换i和j的内容。temp=i;i=j;j=temp;以上3条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度就是O(1)。例如，在下列三个程序段中：{++x；s=0；}for(i=1；i<=n；++i){++x；s+=x；}for(i=1；i<=n；++i)

for(k=1；k<=n；++k){++x；s+=x；}含基本操作“++x”的语句的频度分别为1、n和n2，则这三个程序段的时间复杂度分别为O(1)、O(n)和O(n2)，分别称为常量阶、线性阶和平方阶。用渐进时间复杂度评价算法时间性能

评价一个算法的时间性能主要用算法时间复杂度的数量级（即算法的渐近时间复杂度）。例如，有两个算法A1和A2求解同一问题，时间复杂度分别是T1(n)=100n2，T2(n)=5n3，作如下分析：（1）当输入量n＜20时，有T1(n)＞T2(n)，后者花费的时间较少。（2）但是随着问题规模n的增大，两个算法的时间开销之比5n3/100n2=n/20亦随着增大。即当问题规模较大时，算法A1比算法A2要有效得多。这两个算法的渐近时间复杂度O(n2)和O(n3)从宏观上评价了这两个算法在时间方面的质量，显然算法A1要好。在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。定理：若A(n)=amnm

+am-1nm-1+…+a1n+a0是一个m次多项式，则T(n)=O(nm)。

例如，for(i=2;i<=n;++i)for(j=2;j<=i-1;++j){++x;a[i,j]=x;}

语句频度为：1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=(n2-3n+2)/2∴时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。算法的渐进复杂度的阶对于算法的效率有着决定性的意义。算法可按计算时间分成两类：凡渐近时间复杂度有多项式时间限界的算法称多项式时间算法，凡渐近时间复杂度为指数函数限界的算法称指数时间算法。多项式阶算法（有效算法）：时间复杂度与规模N的幂同阶。常见的多项式阶关系为：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指数阶算法：时间复杂度与规模N的一个指数函数同阶。指数时间的关系为：O(2n)<O(n!)<O(nn)时间复杂度函数变化曲线时间复杂度为指数阶O(2n)的算法效率极低，当n值稍大时就无法应用。当n取值很大时，指数时间算法与多项式时间算法在所需时间上对比非常悬殊。因此，要尽可能将现有算法中的时间复杂度为指数的任何一个算法转化为多项式的时间复杂度。有时，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。一种解决的办法是计算它的平均值，即考虑它对所有可能的输入数据集的期望值，此时相应的时间复杂度为算法的平均时间复杂度。平均时间复杂度是所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。另一种更可行也更常用的办法是讨论算法在最坏情况下的时间复杂度，即分析最坏情况以估算算法执行时间的一个上界。最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何输入实例更长。例如，查找算法在最坏情况下的时间复杂度为T(n)=O(n)，它表示对于任何输入实例，该算法的运行时间不可能大于O(n)。例如，在数值A[0..n-1]中查找给定值K的算法大致如下：(1)i=n-1;

(2)while(i>=0&&(A[i]!=k))

(3)i--;(4)returni;此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关：①若A中没有与K相等的元素，则语句(3)的频度f(n)=n；②若A的最后一个元素等于K，则语句(3)的频度f(n)是常数0。例如：voidbubble-sort(inta[],intn)

//将a中整数序列重新排列成自小到大有序的整数序列

for(i=n-1;change=TURE;i>1&&change;--i){change=false;for(j=0;j<i;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];change=true;}}当a中初始序列为自小到大有序时，基本操作的执行次数为0，故最好情况：0次；当a中初始序列为自大到小有序时，基本操作的执行次数为1+2+3+…+n-1=n(n-1)/2，故最坏情况的时间复杂度为：O(n2)2、算法的空间复杂度

算法的空间复杂度是指执行算法所需要的内存空间。一个算法所占用的存储空间包括：算法程序所占的空间；输入的初始数据所占的存储空间；算法执行过程中所要的额外空间，其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地（inplace）工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以减少不必要的额外空间。4.2数据结构的基本概念例如，设计一程序满足如下需求：记录计算机系每位学生的个人信息，提供基本操作以满足教学管理的需要。数据如下：结构1：线性结构——按学号顺序结构2：树型结构——按管理组织方式班长1组组长1组组员1组组员1组组员2组组长2组组员2组组员3组组长3组组员3组组员Algorithm+DataStructures=Programs（NiklausWirth）程序设计：为计算机处理问题编制一组指令集算法：处理问题的策略数据结构：问题的数学模型4.2.1什么是数据结构数据（Data）：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。它是计算机程序加工的“原料”。例如，一个利用数值分析方法解代数方程的程序，其处理对象是整数和实数；一个编译程序或文字处理程序的处理对象是字符串。因此，对计算机科学而言，数据的含义极为广泛，如图像、声音等都可以通过编码而归之于数据的范畴。数据元素（DataElement）：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据元素也称元素、结点、顶点，具有完整确定的实际意义。例如，在学生表中，为了便于处理，把其中的每一行（代表一位同学）作为一个基本单位来考虑。一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。数据项是数据不可分割的、具有独立含义的最小标识单位。例如，在学生表所示的学生数据中，每个数据元素都由学号、姓名这两个数据项构成。数据对象（DataObject）：是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N={0,±1,±2,…}，字母字符数据对象是集合C={‘A’,‘B’,…,‘Z’}。数据的（逻辑）结构数据结构（DataStructure）：相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构（Structure）。数据结构包括以下三个方面内容：数据元素之间的逻辑关系——数据的逻辑结构（LogicalStructure）：数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

数据元素及其关系在计算机存储器内的表示——数据的存储结构（StorageStructure）：数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。但是，一般只在高级语言的层次上讨论存储结构。数据的运算——对数据施加的操作：数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算，实际上只是在抽象的数据上所施加的一系列抽象的操作。抽象的操作，是指只知道这些操作是“做什么”，而无须考虑“如何做”。只有确定了存储结构之后，才考虑如何具体实现这些运算。数据的结构包括逻辑结构和物理结构（存储结构）两个层次。其中逻辑结构是对数据元素之间逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示。逻辑关系——数据元素之间的关联方式，或称邻接关系。逻辑结构——数据元素之间逻辑关系的整体，抽象反映数据元素的逻辑关系。数据的逻辑结构分类在不产生混淆的前提下，常将数据的逻辑结构简称为数据结构。数据的逻辑结构有两大类：（1）线性结构线性结构的逻辑特征：如果结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表是一个典型的线性结构。栈、队列、串等都是线性结构。（2）非线性结构非线性结构的逻辑特征：一个结点可能有多个直接前趋和直接后继。广义表、树和图等结构都是非线性结构。根据数据元素间关系的基本特性，两大类结构有4种基本数据逻辑结构：（集合）——数据元素间除“同属于一个集合”外，无其他关系。线性结构——结构中的数据元素之间存在一对一的关系，如线性表、栈、队列。树形结构——结构中的数据元素之间存在一对多的关系，如树。图形结构——结构中的数据元素之间存在多对多的关系，如图。关于数据的逻辑结构，需要注意：逻辑结构与数据元素本身的形式、内容无关；逻辑结构与数据元素的相对位置无关；逻辑结构与所含结点的个数无关。数据结构的形式定义：数据结构是一个二元组

Data_Structure=(D,S)

其中，D是数据元素的有限集（或者是“结点”，可能还含有“数据项”或“数据域”），S是D上（或其他集合）关系的有限集，S={R|R:D×D×...}，称之为元素的逻辑结构。集合：L=(N,R)，N={a,b,c,d,e}，R={r}，

r={}aecdb线性结构：L=(N,R)，N={a,b,c,d,e}，R={r}，r={<a,b>,<b,c>,<c,d>,<d,e>}

abcde

树形结构：L=(N,R)，N={k1,k2,…,k9}，R={r}，r={<k1,k2>,<k1,k3>,<k1,k4>,<k1,k7>,<k1,k8>,<k4,k5>,<k4,k6>,<k8,k9>}k1k2k3k4k7k8k5k6k9数据结构存储实现逻辑结构在计算机存储器中的表示（又称映象）称为数据的物理结构，又称存储结构，它包括数据元素的表示与关系的表示。计算机中表示信息的最小单位是二进制数的一位，叫做位（bit）。在计算机中，可以用一个由若干位组合起来形成的一个位串表示一个数据元素（如用一个字长的位串表示一个整数，用8位2进制位表示一个字符等），通常称这个位串为元素（Element）或结点（Node）。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域（DataField）。因此，元素或结点可看成是数据元素在计算机中的映象。一个存储结构包括三个主要部分：存储结点（简称结点），每个存储结点存放一个数据元素；数据元素之间关联方式的表示，也就是逻辑结构的计算机表示；附加设施，如为便于运算实现而设置的“哑结点”等等。其中，前两个部分是一切存储结构都必须具备的，第三个部分则根据需要而决定是否设置。由于假定数据元素内部的组织形式比较简单，存储结点本身的组织也比较简单。因此，存储结构的主要部分是数据元素之间关联方式的表示。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象非顺序映象并由此得到4种不同的存储结构：顺序（sequential）存储结构链式（linked）存储结构索引（indexed）存储结构散列（hashing）存储结构4种存储结构与4种逻辑结构组合，理论上可以得到4×4种可能的物理数据结构，但并非所有的可能组合都合理。顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。例如，假设用两个字长的位串表示一个实数，则可以用地址相邻的4个字长的位串表示一个复数。该存储方法主要应用于线性的数据结构。但是某些非线性的数据结构也可以通过某种线性化的方法实现顺序存储。元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+(n-1)*m存储地址存储内容Loc(元素i)=Lo+(i-1)*m顺序存储链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系，通常利用程序设计语言的指针类型描述。该存储方法不要求逻辑上相邻的结点在物理位置上也相邻。1536元素21400元素11346元素3^元素41345h存储地址

存储内容指针1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346h索引存储方法

这种方法通常在存储结点信息的同时，还建立附加的索引表。

索引表由若干索引项组成：若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（DenseIndex）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引（SpareIndex）。索引项的一般形式是：（关键字,地址）。关键字是能唯一标识一个结点的数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。散列存储方法

该存储方法的基本思想：根据结点的关键字直接计算出该结点的存储地址。散列方法是索引方法的一种延伸和扩展，利用一种称为散列函数（hashfunctions）进行索引值的计算，然后通过索引表求出结点的地址。散列函数是将字符串s映射到非负整数z的一类函数

h:SZ，对任意的s∈S，散列函数h(s)=z，z∈Z。四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。数据的逻辑结构和存储结构是密切相关的两个方面：算法设计→数据（逻辑）结构算法实现→存储结构

好的数据结构：如果一个数据结构可以通过某种“线性规则”被转化为线性的数据结构（如线性表），则称它为好的数据结构，好的数据结构通常对应于高效的算法。这是由计算机的计算能力决定的，因为计算机本质上只能存取逻辑连续的内存单元，所以如果没有线性化的结构逻辑上是不可计算的。例如，对一个图进行操作，要访问图的所有结点，则要按照某种顺序来依次访问所有结点（形成一个偏序），必须通过某种方式将图固有的非线性结构转化为线性结构才能对图进行操作。数据结构的三个方面：

数据的逻辑结构

数据的存储结构

数据的运算：检索、排序、插入、删除、修改等

线性结构

非线性结构

顺序存储

链式存储线性表栈队树形结构图形结构

索引存储

散列存储4.3线性表及其顺序存储结构线性结构是n（n≥0）个结点的有限序列。如果将线性表表示为(a1,…,ai-1,ai,ai+1,…,an)，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素，i称为ai在线性表中的序号或位置。不含任何结点的线性结构记为()或ø。当i=1,2,…,n-1时（终端结点除外），ai有且仅有一个直接后继；当i=2,3,…,n时（起始结点除外），ai有且仅有一个直接前驱。直接前驱和直接后继从不同角度刻画了结点之间的逻辑关系（邻接关系）。在线性结构中，这种邻接关系是1对1，即每个结点至多只有一个直接前驱和一个直接后继。线性结构中的一个结点代表一个数据元素。同一线性表中的元素必定具有相同特性（数据项的个数相同、类型相同），即属同一数据对象，相邻数据元素之间存在着序偶关系。在复杂的线性结构中，一个数据元素可以由若干个数据项（Item）组成。在这种情况下，常把数据元素称为记录（Record），含有大量记录的线性表又称文件（File）。线性结构定义图示：线性表线性表的逻辑结构是线性结构，所含结点的个数称为线性表的长度（表长），表长为0的线性表是空表。线性表的典型运算（6种）：初始化INITIATE(L)，构造一个空的线性表L，加工型运算。求表长LENGTH(L)，结果是线性表L的长度，引用型运算。读表元GET(L,i)，若1≤i≤LENGTH(L)，其结果是L的第i个结点，否则为一特殊值，引用型运算。定位（按值查找）LOCATE(L,X)，如果L中存在一个或多个值与X相同的结点，运算结果为这些结点序号的最小值，否则，运算结果为0，引用型运算。插入INSERT(L,X,i)，在L的第i个位置增加一个以X为值的新结点，使L由(a1,…,ai-1,ai,…,an)变为(a1,…,ai-1,X,ai,…,an)，1≤i≤n+1，加工型运算。删除DELETE(L,i)，删除L的第i个结点，使L变为(a1,…,ai-1,ai+1,…,an)，加工型运算。通过这6种基本运算可以实现线性表的其他运算。线性表基本操作图示：4.3.2线性表的顺序存储结构顺序表：线性表的顺序存储结构或顺序映象。逻辑结构中相邻的结点在存储结构中仍然相邻。线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。每一个数据元素的存储位置都和线性表的起始位置相差一个与数据元素在线性表中的位序成正比的常数。假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)与第i个数据元素的存储位置LOC(ai)之间满足下列关系：LOC(ai+1)=LOC(ai)+L一般情况下，线性表的第i个数据元素ai的存储位置为：

LOC(ai)=LOC(a1)+(i-1)*L

LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。因此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。所有数据元素的存储位置均取决于第一个数据元素的存储位置。【图示】用一组地址连续的存储单元依次存放线性表中的数据元素：

a1a2

…ai-1ai

…an线性表的起始地址，称作线性表的基地址。由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。另外，由于线性表的长度可变，且所需最大存储空间随问题不同而不同，例如，在C语言中可用动态分配的一维数组来表示。基本运算在顺序表上的实现1、插入运算在第i位置插入元素时，线性表的逻辑结构发生什么变化？

(a1,…,

ai-1,ai,…,an)

变为(a1,…,ai-1,X,ai,…,an)在第i（1≤i≤n）个元素之前插一个元素时，需将第n至第i（共n-i+1）个元素向后移动一个位置，依次后移到n+1,n,…,i+1位置上，空出第i个位置，然后在该位置上插入新元素X。当插入位置i=n+1时，无须移动结点，直接将X插入表的末尾。注意：①由于向量空间大小在声明时确定，当L.length≥ListSize时，表空间已满，不可再做插入操作；②当插入位置i的值为i＞n+1或i＜1时为非法位置，不可做正常插入操作。内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1XInsert_SqList(SqListL,ElemTypex,inti){//在顺序线性表L中第i个位置元素之前插入新的元素x，i的合法值为1≤i≤ListLength_Sq(L)+1

if((i<1)||(i>L.length+1))returnERROR；//i值不合法

if(L.length>=L.listsize)exit(OVERFLOW);//存储分配失败

for(j=L.length-1;j>=i-1;j--)

L.data[j+1]=L.data[j];//插入位置及之后的元素后移

L.data[i-1]=x;//插入x

++L.length;//表长增1

returnOK;}

顺序表插入算法时间复杂度T(n)：问题规模：表的长度L.length（设值为n）是问题的规模。移动结点的次数由表长n和插入位置i决定。算法的时间主要花费在for循环中的结点后移语句上，该语句的执行次数是n-i+1。当i=n+1：移动结点次数为0，即算法在最好时间复杂度是O(1)；当i=1：移动结点次数为n，即算法在最坏情况下时间复杂度是O(n)。设在第i个元素之前插入一个元素的概率是Pi，则在长度为n的线性表中插入一个元素所需移动的元素次数的平均次数为：即在顺序表上进行插入运算，平均要移动一半结点。2、删除操作线性表删除操作是指将第i个元素（1in）删除，使得长度为n的线性表(a1,…,ai-1,

ai,

ai+1,…,an)变为长度为n-1的线性表(a1,…,

ai-1,ai+1,…,an)。需将第i+1至第n共n-i个元素前移。若i=n，则只要删除终端结点，无需移动。注意：当要删除元素的位置i不在表长范围（即i＜1或i＞L.length）时，为非法位置，不能做正常的删除操作。内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2顺序表删除操作过程：在顺序表上实现删除运算必须移动结点，才能反映出结点间逻辑关系的变化。若i=n，则只要简单地删除终端结点，无须移动结点；若1≤i≤n-1，则必须将表中位置i+1,i+2,…,n的结点，依次前移到位置i,i+1,…,n-1上，以填补删除操作造成的空缺。ListDelete_Sq(SqListL,inti){//在顺序线性表l中删除第i个元素，i的合法值为1≤i≤ListLength_Sq(L)

if((i<1)||(i>L.length))returnERROR;//删除位置不合法

for(j=i;j<=L.1ength-1;j++)

L.elem[j-1]=L.elem[j];

//被删除元素之后的元素前移

L.1ength--；//表长减1

returnOK；

}顺序表删除算法时间复杂度T(n)：结点的移动次数由表长n和位置i决定：i=n时，结点的移动次数为0，算法时间复杂度是O(1)；i=1时，结点的移动次数为n-1，算法时间复杂度是O(n)。移动结点的平均次数Ede(n)：设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：

其中：删除表中第i个位置结点的移动次数为n-i，Qi表示删除表中第i个位置上结点的概率。不失一般性，假设在表中任何合法位置（1≤i≤n）上的删除结点的机会是均等的，则Q1=Q2=…=Qn=1/n。因此，在等概率插入的情况下，顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度是O(n)。

在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上（换句话说，移动元素的操作为预估算法时间复杂度的基本操作），而移动元素的个数取决于插入或删除元素的位置。所以在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低。4.4栈和队列栈与队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限制的线性表。因此，可称为限定性的数据结构。4.4.1栈及其基本运算栈（Stack）：限定只能在表的一端（一般是表尾）进行插入或删除操作的线性表。对栈来说，表尾端有其特殊含义，称为栈顶（top），表头端称为栈底（bottom）。不含元素的空表称为空栈。假设栈S=(a1,a2,…,an)，则称a1为栈底元素，an为栈顶元素。栈中元素按a1,a2,…,an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（LastInFirstOut）的线性表（简称LIFO结构，也可称为先进后出FILO）。元素是以a1,a2,…,an的顺序进栈，出栈的次序却是an,an-1,…,a1。ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)栈的基本操作：

InitStack(&S)

操作结果：构造一个空栈S。StackEmpty(S)

初始条件：栈S已存在。

操作结果：若栈S为空栈，则返回TRUE，否则FALSE。StackTop(S,x)

初始条件：栈S已存在且非空。

操作结果：用x返回S的栈顶元素。Push(S,x)

初始条件：栈S已存在。

操作结果：插入元素x为新的栈顶元素。Pop(S,x)

初始条件：栈S已存在且非空。

操作结果：删除S的栈顶元素，并用x返回其值。栈的基本操作图示：栈的顺序存储栈有两种存储表示方法——顺序实现和链接实现。顺序栈：栈的顺序存储结构，是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。#defineSTACK_INIT_SIZE100//存储空间初始分配量typedefstruct{SElemType*base;//在构造之前和销毁之后，base值NULLSElemType*top;//栈顶指针

intstacksize;//当前已分配的存储空间

}SqStack;其中，stacksize指示栈的当前可使用的最大容量。栈的初始化操作为：按设定的初始分配量进行第一次存储分配。base称为栈底指针，在顺序栈中，它始终指向栈底的位置。若base的值为NULL，则表明栈结构不存在。top为栈顶指针，其初值指向栈底，即top==base可作为栈空的标记。顺序栈的类型定义举例：#defineStackSize100

//预分配的栈空间最多为100个元素

typedefcharDataType;

//栈元素的数据类型为字符型

typedefstruct{DataTypedata[StackSize];inttop;}SeqStack;注意：顺序栈中元素用向量存放；栈底位置是固定不变的，可设置在向量两端的任意一个端点；栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置。

顺序栈的基本操作前提条件：设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即S->data[0]是栈底元素。1）进栈操作进栈时，需要将指针S->top加1，注意：S->top==StackSize-1表示栈满“上溢”现象——当栈满时，再作进栈运算产生空间溢出的现象。上溢是一种出错状态，应设法避免。2）退栈操作退栈时，需将指针S->top减1，注意：S->top<0表示空栈“下溢”现象——当栈空时，作退栈运算产生的溢出现象。下溢是正常现象，常用作程序控制转移的条件。顺序栈进栈和退栈的操作演示：4.4.2队列及其基本运算与栈相反，队列（Queue）是一种先进先出（FirstinFirstOut，FIFO）的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这与日常的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端叫做队尾（rear），允许删除的一端则称为队头（front）。假设队列为q=(a1,a2,…,an)，则a1是队头元素，an是队尾元素。队列中的元素是按照a1,a2,…,an的顺序进入的，退出队列也只能按照这个次序依次退出，也就是说，只有在a1,a2,…,an-1都离开队列之后，an才能退出队列。队列演示队列在程序设计中经常出现。一个最典型的例子就是操作系统中的作业排队，在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就要按请求输出的先后次序排队。凡是申请输出的作业都从队尾进入队列。每当通道传输完毕可以接受新的输出任务时，队头作业先从队列中退出。队列的顺序实现与顺序栈相类似，在队列Q的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，还需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。初始化建空队列时，一般令front=rear=0。每当插入新的队列尾元素时，尾指针增1；每当删除队列头元素时，头指针增1。顺序队列的头、尾指针两种设置方法（1）非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的后一个位置。不足：假设当前为队列分配的最大空间为6，则当队列处于图(d)状态时不可再继续插入新的队尾元素，否则会因数组越界而报错。然而此时又不宜如顺序栈那样，进行存储再分配扩大数组空间，因为队列的实际可用空间并未占满。顺序队列操作演示—设置1（2）头指针始终指向队列首元素的前一个位置，而尾指针始终指向队列尾元素的位置。front=-1rear=-1123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front、rear，约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1空队列条件：front==rear入队列：sq[++rear]=e;出队列：e=sq[++front];rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront存在问题，设数组维数为M，则：当front=0、rear=M时，再有元素入队发生上溢——真上溢。当front0、rear=M时，再有元素入队发生上溢——假上溢：由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。解决方案：队首固定，每次出队剩余元素向下移动——浪费时间。循环队列：基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M，则令rear=0。循环队列实现：利用模运算。入队：rear=(rear+1)%M;sq[rear]=e;出队：front=(front+1)%M;e=sq[front];

如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；0M-11frontrear…...…...循环队列的插入和删除循环队列的基本操作（1）队列的初始化（构造一个空队列）voidInitQueue(CyQueue

*sq)

{

sq->front=sq->rear=0;

sq->count=0;//计数器置0

}（2）判队空int

QueueEmpty(CyQueue

*sq)

{

if(sq->front==sq->rear)return

1;

elsereturn0;}int

QueueEmpty(CyQueue

*sq)

{

return

sq->count==0;}（3）判队满int

QueueFull(CyQueue

*sq)

{

return

sq->count==MaxQueuesize;}（4）返回队列的元素个数，即队列的长度。intQueueLength(CyQueue&Q){

return(Q.rear–Q.front+MaxQueuesize)%MaxQueuesize;}（5）取队头元素Datatype

QueueFront(CyQueue

*sq)

{

if(QueueEmpty(sq))error(“queue

is

empty”);

return

sq->data[sq->front];

}（6）入队void

EnQueue(CyQueue

&sq,DataType

x)

{//插入元素x为sq的新的队尾元素

if(QueueFull(sq))

error(“queue

overfolw”);

sq.count++;

sq.data[sq.rear]=x;

sq.rear=(sq.rear+1)%MaxQueuesize;

}（7）出队Datatype

DeQueue(CyQueue

*sq)

{//若队列不空，删除sq的队头元素，用x返回其值

DataType

x;if(QueueEmpty(sq))

error(“queue

underflow”);

x=sq->data[sq->front];

sq->count--;

sq->front=(sq->front+1)%MaxQueuesize;

returnx;

}循环队列边界条件处理：循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是“空”还是“满”。解决这个问题的方法有三种：另设一布尔变量以区别队列的空和满。少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）。使用一个计数器记录队列中元素的总数（即队列长度）。012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front==rear队满：front==rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：

队空：front==rear

队满：(rear+1)%M==front循环队列理解4.5线性链表线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素，它的存储位置可用一个简单、直观的公式来表示。然而，从另一方面来看，这个特点也铸成了这种存储结构的弱点：在作插入或删除操作时，需要移动大量元素。由此提出线性表的另一种表示方法——链式存储结构，由于它不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但同时也失去了顺序表可随机存取的优点。4.4.2线性链表的基本概念线性表的链式存储结构的特点：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。因此，为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素ai的存储映象，称为结点（Node）。结点包括两个域：存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域，指针域中存储的信息称作指针（Pointer）或链（Link）。n个结点（ai(1≤i≤n)的存储映象）链接成一个链表，即为线性表（a1,a2,…,an）的链式存储结构。又由于此链表的每个结点中只包含一个指针域，所以又称线性链表或单链表。Data域——存放结点值的数据域；Next域——存放结点的直接后继的地址（位置）的指针域（链域）。注意：链表是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的；每个结点只有一个链域的链表称为单链表（SingleLinkedList）。

Data

Next头指针：指向单链表第一个结点的指针。链表由头指针唯一确定，单链表可用头指针的名称来命名。例如，头指针名为head的链表可称为表head。整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点（即第一个数据元素的存储映象）的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”（NULL）。ZHAOQIANSUNLIZHOUWUZHENGWANG^H43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331Head头指针Head例如，图示为线性表（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG）的线性链表存储结构。单链表和指针图示双向链表以上讨论的链式存储结构的结点中只有一个指示直接后继的指针域，因此从某个结点出发只能往后寻查其他结点。若要寻查结点的直接前驱，则须从表头指针出发。换句话说，在单链表中，NextElem的执行时间为O(1)，而PriorElem的执行时间为O(n)。为了克服单链表这种单向性的缺点，可利用双向链表（DoubleLinkedList）。在双向链表的结点中有两个指针域：其一指向直接后继，另一指向直接前驱。priorelementnext栈的链式实现

链栈：栈的链式表示。由于栈的操作是线性表操作的特例，则链栈也是单链表的特例，是运算受限的单链表，其操作易于实现。^…...topdatanext栈底链栈存储方式：与一般单链表的存储结构完全相同，但是应该确定链表的哪端对应于栈顶。如果链表尾作为栈顶，则入、出栈操作的时间复杂性为O(n)。如果链表头作为栈顶，则入、出栈操作的时间复杂性为O(1)，所以，一般把链表头作为栈顶。^…...Ldatanext栈顶^…...topdatanext栈底链栈的特点：链栈的栈顶指针就是链表的头指针；进栈操作就是在该链表第一个元素结点之前插入一个新结点，出栈操作就是删除链表的第一个元素结点。链栈可以减小溢出，提高空间利用率。只有系统没有空间了，链栈才会溢出。DatanextS栈顶栈底an-1a1an队列的链接实现用链表表示的队列简称为链队列，它是限制仅能在表头删除和表尾插入的单链表。一个链队列需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。这里，与单链表一样，为了操作方便，也可以给链队列添加一个头结点，并令头指针指向头结点。由此，空的链队列的判断条件为头指针和尾指针均指向头结点。链队列的操作即为单链表的插入和删除操作的特殊情况，只是还需修改尾指针或头指针。链队列结点定义：typedefstructQNode{QDataTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;

//队头指针

QNode*rear;

//队尾指针

}LinkQueue;头结点^…...front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾frontrearx入队^xfrontreary入队x^yfrontrearx出队x^yfrontrear空队^frontreary出队^4.5.2线性链表的基本运算1、定位查找定位又称按值查找，即在链表中，查找是否有结点的数据域值等于给定值x的结点。若有的话，则返回首次找到的其值为给定值结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的数据域值与给定值x作比较。Lnode*locatenode(LKListhead,DataTypex){Lnode*p=head–>next;while(p&&p–>data!=x)p=p–>next;//直到p为NULL或p->data为x为止

returnp;//若p=NULL，则查找失败，否则p指向值为x的结点

}2、插入假设要在单链表的两个数据元素a和b之间插入一个结点x，已知p为指向元素a的指针。为插入x，首先要生成一个数据域为x的结点，然后插入在单链表中。根据插入操作的逻辑定义，还需要修改结点a的指针域，令其指向结点x，而结点x的指针域应指向结点b，从而实现3个元素a、b和x之间逻辑关系的变化。插入后的单链表如图所示，设s为指向结点x的指针：pabxss->next=p->next;p->next=s;前插结点：设p指向单链表中某结点，s指向待插入的值为X的新结点，将*s插入到*p的前面。

q=L;①while(q->next!=p)q=q->next;②s->next=q->next;③q->next=s;

Xs①②qp③3、删除在单链表中删除第i个元素，基本操作为：找到单链表中第i-1个元素，修改其指向后继的指针，有序对<ai-1,ai>与<ai,ai+1>修改为<ai-1,ai+1>。如图，在单链表中删除元素b时，要实现元素a、b和c之间逻辑关系的变化，仅需修改元素a中的指针域。设p为指向元素a的指针，则修改指针的语句如图所示：pabcp->next=p->next->next;具体步骤：

（1）找到ai-1的存储位置p（因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中）；（2）令p->next指向ai的直接后继结点（即把ai从链上摘下）；（3）释放结点ai的空间。ListDelete_L(LkList&L,inti,DataTypee){//在带头结点的单链表L中，删除第i个结点，并由e返回其值

LNode*p,*q;

p=L;j=0;

while(p->next&&j<i-1){

p=p->next;++j;}//找第i个结点，并令p指向其前驱

if(!(p->next)||j>i-1)returnERROR；//删除位置不合理

q=p->next;

p->next=q->next;

//删除q并释放结点

e=q->data;

free(q);

returnOK；

}算法的时间复杂度为：O(ListLength(L))4.5.3循环链表及其基本运算循环链表时一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得链表处理更加方便灵活。循环链表（CircularlinkedList）的特点是链表中最后一个结点的指针域指向头（或首）结点，整个链表形成一个环。由此从链表中任一结点出发均可找到链表中其他结点。循环链表的操作与线性单链表基本一致，差别仅在于算法中的判断条件不是p或者p->next是否为空，而是它们是否等于头指针。⑴非空循环链表⑵空循环链表带头结点的循环链表，判断空链表的条件是：head==head->next;

a1

an

….head循环链表中由于没有NULL指针，所以涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p->next是否为空，而是判断它们是否等于某一指定指针，如头指针或尾指针等。…^L…L…head

线性链表循环链表带头结点的循环链表p->next==NULLp->next==Lp->next==headPPP循环链表常用操作（1）在表头插入元素：

s->next=head->next;head->next=s;

（2）在表尾插入元素：

s->next=head;rear->next=s;rear=s;（3）在表头删除元素：

head->next=s->next;free(s);（4）在表尾删除元素：

p=head->next;q=rear;while(p->next!=rear)p=p->next;p->next=head;rear=p;free(q);