自学考试：数据结构考点复习.doc

第一章概论数据（data）是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的原料。随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图像和声音等。数据元素 data element是数据的基本单位。数据元素也称元素、结点、顶点、记录。一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。数据项是具有独立含义的最小标识单位。数据结构（data structure） 指的是数据之间的相互关系，即数据的组织形式。1数据结构一般包括以下三方面内容：数据元素之间的逻辑关系，也称数据的逻辑结构（logical structure）；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据元素及其关系在计算机存储器内的表示，称为数据的存储结构storage structure数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。数据的运算，即对数据施加的操作。 数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作，是指我们只知道这些操作是做什么，而无须考虑如何做。只有确定了存储结构之后，才考虑如何具体实现这些运算。2数据的逻辑结构分类在不产生混淆的前提下，常将数据的逻辑结构简称为数据结构。数据的逻辑结构有两大类：（1）线性结构 线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表是一个典型的线性结构。栈、队列、串等都是线性结构。（2）非线性结构 非线性结构的逻辑特征是：一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。3数据的四种基本存储方法数据的存储结构可用以下四种基本存储方法得到：（1）顺序存储方法该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构（sequential storage structure），通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。（2）链接存储方法该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（linked storage structure）,通常借助于程序语言的指针类型描述。（3）索引存储方法该方法通常在储存结点信息的同时，还建立附加的索引表。索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（dense index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引(spare index)。索引项的一般形式是：(关键字、地址)关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。（4）散列存储方法该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。4数据结构三方面的关系数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。数据类型（datatype）所谓数据类型是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。按值是否可分解，可将数据类型划分为两类：原子类型：其值不可分解。通常是由语言直接提供。【例】c语言的整型、字符型等标准类型及指针等简单的导出类型；结构类型：其值可分解为若干个成分（或称为分量）。是用户借助于语言提供的描述机制自己定义的，它通常是由标准类型派生的，故它也是一种导出类型。例: c的数组、结构等类型。抽象数据类型（abstracttype简称adt）adt是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。adt adt-name data:/数据说明 数据元素之间逻辑关系的描述 operations:/操作说明 operation1:/操作1，它通常可用c或c的函数原型来描述 input:对输入数据的说明 preconditions:执行本操作前系统应满足的状态/可看作初始条件 process:对数据执行的操作 output:对返回数据的说明 postconditions:执行本操作后系统的状态/系统可看作某个数据结构 operation2:/操作2 /adt抽象数据类型可以看作是描述问题的模型，它独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在adt里定义的某些操作来访问其中的数据，从而实现了信息隐藏。在c中，我们可以用类（包括模板类）的说明来表示adt，用类的实现来实现adt。因此，c中实现的类相当于是数据的存储结构及其在存储结构上实现的对数据的操作。adt和类的概念实际上反映了程序或软件设计的两层抽象：adt相当于是在概念层（或称为抽象层）上描述问题，而类相当于是在实现层上描述问题。此外，c中的类只是一个由用户定义的普通类型，可用它来定义变量（称为对象或类的实例）。因此，在c中，最终是通过操作对象来解决实际问题的，所以我们可将该层次看作是应用层。例如，main程序就可看作是用户的应用程序。由于c语言中没有提供类这一数据类型，因此无法实现adt，故我们不采用adt的形式来描述数据结构，以节省篇幅。大家只要记住，它实际上等价于我们定义的数据的逻辑结构以及在逻辑结构上定义的抽象操作。学习数据结构的意义各种应用问题可以大致分为数值计算问题和非数值计算问题两大类。1处理数值计算问题时，数据元素之间的相互关系一般用数学方程式加以描述；2处理非数值性问题时，要设计出合适的数据结构，才能有效地解决问题。算法分析1评价算法好坏的标准求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的算法呢？ 选用的算法首先应该是正确的。此外，主要考虑如下三点：执行算法所耗费的时间；执行算法所耗费的存储空间，其中主要考虑辅助存储空间；算法应易于理解，易于编码，易于调试等等。2算法性能选择一个占存储空间小、运行时间短、其它性能也好的算法是很难做到的。原因是上述要求有时相互抵触：要节约算法的执行时间往往要以牺牲更多的空间为代价；而为了节省空间可能要耗费更多的计算时间。因此我们只能根据具体情况有所侧重：若该程序使用次数较少，则力求算法简明易懂；对于反复多次使用的程序，应尽可能选用快速的算法；若待解决的问题数据量极大,机器的存储空间较小,则相应算法主要考虑如何节省空间3算法的时间性能分析（1）算法耗费的时间和语句频度一个算法所耗费的时间=算法中每条语句的执行时间之和每条语句的执行时间=语句的执行次数(即频度(frequencycount)语句执行一次所需时间 算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。（2）问题规模和算法的时间复杂度算法求解问题的输入量称为问题的规模(size),一般用一个整数表示。一个算法的时间复杂度(timecomplexity,也称时间复杂性)t(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度t(n)的数量级(阶)称为算法的渐进时间复杂度。这表明，当n充分大时，t(n)和n3之比是一个不等于零的常数。即t(n)和n3是同阶的，或者说t(n)和n3的数量级相同。记作t(n)=o(n3)是算法matrixmultiply的渐近时间复杂度。数学符号o的严格的数学定义：若t(n)和f(n)是定义在正整数集合上的两个函数，则t(n)=o(f(n)表示存在正的常数c和n0，使得当nn0时都满足0t(n)cf(n)。（3）渐进时间复杂度评价算法时间性能主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能【例37】有两个算法a1和a2求解同一问题，时间复杂度分别是t1(n)=100n2，t2(n)=5n3。（1）当输入量n20时，有t1(n)t2(n)，后者花费的时间较少。（2）随着问题规模n的增大，两个算法的时间开销之比5n3/100n2=n/20亦随着增大。即当问题规模较大时，算法a1比算法a2要有效地多。它们的渐近时间复杂度o(n2)和o(n3)从宏观上评价了这两个算法在时间方面的质量。在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度t(n)=o(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是o(1)。一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。（4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。（5）最坏时间复杂度和平均时间复杂度最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。显然，时间复杂度为指数阶0(2n)的算法效率极低，当n值稍大时就无法应用。类似于时间复杂度的讨论，一个算法的空间复杂度(spacecomplexity)s(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。算法的时间复杂度和空间复杂度合称为算法的复杂度。第二章线性表线性表的逻辑定义 线性表（linearlist）是由n（n0）个数据元素（结点）a1，a2，an组成的有限序列。数据元素的个数n定义为表的长度（n=0时称为空表）。将非空的线性表（n0）记作：（a1，a2，an）数据元素ai（1in）只是个抽象符号，其具体含义在不同情况下可以不同。线性表的逻辑结构特征对于非空的线性表:有且仅有一个开始结点a1，没有直接前趋，有且仅有一个直接后继a2有且仅有一个终结结点an，没有直接后继，有且仅有一个直接前趋an-1其余的内部结点ai（2in-1）都有且仅有一个直接前趋ai-1和一个ai+1常见的线性表的基本运算1initlist（l）构造一个空的线性表l，即表的初始化。2listlength（l）求线性表l中的结点个数，即求表长。3getnode（l，i）取线性表l中的第i个结点，这里要求1ilistlength（l）4locatenode（l，x）在l中查找值为x的结点，并返回该结点在l中的位置。若l中有多个结点的值和x相同，则返回首次找到的结点位置；若l中没有结点的值为x，则返回一个特殊值表示查找失败。5insertlist（l，x，i）在线性表l的第i个位置上插入一个值为x的新结点，使得原编号为i，i+1，n的结点变为编号为i+1，i+2，n+1的结点。这里1in+1，而n是原表l的长度。插入后，表l的长度加1。6deletelist（l，i）删除线性表l的第i个结点，使得原编号为i+1，i+2，n的结点变成编号为i，i+1，n-1的结点。这里1in，而n是原表l的长度。删除后表l的长度减1。注意：以上所提及的运算是逻辑结构上定义的运算。只要给出这些运算的功能是做什么，至于如何做等实现细节，只有待确定了存储结构之后才考虑。顺序存储结构 顺序表1顺序表的定义(1)顺序存储方法即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。(2)顺序表（sequentiallist） 用顺序存储方法存储的线性表简称为顺序表。2结点ai的存储地址假设表中每个结点占用c个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点a1的存储地址（简称为基地址）是loc（a1），那么结点ai的存储地址loc（ai）可通过下式计算：loc（ai）=loc（a1）+（i-1）*c1in注意：在顺序表中，每个结点ai的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址。是一种随机存取结构。3顺序表类型定义#define listsize 100 /表空间的大小可根据实际需要而定，这里假设为100 typedef int datatype; /datatype的类型可根据实际情况而定，这里假设为int typedef struct datatype datalistsize；/向量data用于存放表结点 int length；/当前的表长度 seqlist；注意：用向量这种顺序存储的数组类型存储线性表的元素外，顺序表还应该用一个变量来表示线性表的长度属性，因此用结构类型来定义顺序表类型。存放线性表结点的向量空间的大小listsize应仔细选值，使其既能满足表结点的数目动态增加的需求，又不致于预先定义过大而浪费存储空间。由于c语言中向量的下标从0开始，所以若l是seqlist类型的顺序表，则线性表的开始结点a1和终端结点an分别存储在ldata0和ldatallength-1中。若l是seqlist类型的指针变量，则a1和an分别存储在l-data0和l-datal-length-1中。4顺序表的特点顺序表是用向量实现的线性表，向量的下标可以看作结点的相对地址。因此顺序表的的特点是逻辑上相邻的结点其物理位置亦相邻。顺序表上实现的基本运算1.表的初始化void initlist（seqlist*l）顺序表的初始化即将表的长度置为0l-length=0；2.求表长int listlength（seqlist*l）求表长只需返回l-lengthreturn l-length;3.取表中第i个结点datatypegetnode（l，i） 取表中第i个结点只需返回和l-datai-1即可if (il-length-1)error(positionerror)；return l-datai-1；4.查找值为x的结点5.插入（1）插入运算的逻辑描述线性表的插入运算是指在表的第i（1in+1）个位置上，插入一个新结点x，使长度为n的线性表：（a1，ai-1，ai，an）变成长度为n+1的线性表：（a1，ai-1，x，ai，an）注意：由于向量空间大小在声明时确定，当l-lengthlistsize时，表空间已满，不可再做插入操作 当插入位置i的值为in或i1时为非法位置，不可做正常插入操作 （2）顺序表插入操作过程在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n，n-1，i上的结点，依次后移到位置n+1，n，i+1上，空出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，才无须移动结点，直接将x插入表的末尾。（3）具体算法描述 void insertlist(seqlist *l，datatype x，int i) /将新结点x插入l所指的顺序表的第i个结点ai的位置上 int j; if (il-length+1) error(position error);/非法位置，退出运行 if (l-length=listsize) error(overflow); /表空间溢出，退出运行 for(j=l-length-1;j=i-1;j-) l-dataj+1=l-dataj;/结点后移 l-datai-1=x; /插入x l-length+; /表长加1 （4）算法分析问题的规模 表的长度l-length（设值为n）是问题的规模。移动结点的次数由表长n和插入位置i决定算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。当i=n+1：移动结点次数为0，即算法在最好时间复杂度是0(1)当i=1：移动结点次数为n，即算法在最坏情况下时间复杂度是0(n)移动结点的平均次数其中：在表中第i个位置插入一个结点的移动次数为n-i+1pi表示在表中第i个位置上插入一个结点的概率。不失一般性，假设在表中任何合法位置（1in+1）上的插入结点的机会是均等的，则p1=p2=pn+1=1/(n+1)因此，在等概率插入的情况下，e=n/2即在顺序表上进行插入运算，平均要移动一半结点。6删除（1）删除运算的逻辑描述线性表的删除运算是指将表的第i（1in）个结点删去，使长度为n的线性表（a1，ai-1，ai，ai+1，an）变成长度为n-1的线性表（a1，ai-1，ai+1，an）注意：当要删除元素的位置i不在表长范围（即i1或il-length）时，为非法位置，不能做正常的删除操作（2）顺序表删除操作过程在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。若i=n，则只要简单地删除终端结点，无须移动结点；若1in-1，则必须将表中位置i+1，i+2，n的结点，依次前移到位置i，i+1，n-1上，以填补删除操作造成的空缺。（3）具体算法描述void deletelist(seqlist *l,int i) /从l所指的顺序表中删除第i个结点ai int j; if(il-length) error(position error); /非法位置 for(j=i;jlength-1;j+) l-dataj-1=l-dataj; /结点前移 l-length-; /表长减小 （4）算法分析结点的移动次数由表长n和位置i决定：i=n时，结点的移动次数为0，即为0(1)i=1时，结点的移动次数为n-1，算法时间复杂度分别是0(n)移动结点的平均次数ede(n)其中：删除表中第i个位置结点的移动次数为n-ipi表示删除表中第i个位置上结点的概率。不失一般性，假设在表中任何合法位置（1in）上的删除结点的机会是均等的，则p1=p2=pn=1/n因此，在等概率插入的情况下，e=(n-1)/2顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是0(n)。链式存储结构单链表1、链接存储方法链接方式存储的线性表简称为链表（linked list）。链表的具体存储表示为：用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）注意：链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。2、链表的结点结构data域-存放结点值的数据域datanextnext域-存放结点的直接后继的地址(位置)的指针域(链域注意：链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。每个结点只有一个链域的链表称为单链表（single linked list）。3、头指针head和终端结点指针域的表示单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。注意：链表由头指针唯一确定，单链表可以用头指针的名字来命名。终端结点无后继，故终端结点的指针域为空，即null。4、单链表的一般图示法5、单链表类型描述typedef char datatype; /假设结点的数据域类型为字符 typedef struct node /结点类型定义 datatype data; /结点的数据域 struct node *next;/结点的指针域 listnode; typedef listnode *linklist; listnode *p; linklist head;注意：linklist和listnode*是不同名字的同一个指针类型（命名的不同是为了概念上更明确）linklist类型的指针变量head表示它是单链表的头指针listnode*类型的指针变量p表示它是指向某一结点的指针6、指针变量和结点变量 指针变量 结点变量 定义 在变量说明部分显式定义 在程序执行时，通过标准 函数malloc生成 取值 非空时，存放某类型结点 实际存放结点各域内容 的地址 操作方式 通过指针变量名访问 通过指针生成、访问和释放 生成结点变量的标准函数p=(listnode*)malloc(sizeof(listnode)； /函数malloc分配一个类型为listnode的结点变量的空间,并将其首地址放入指针变量p中释放结点变量空间的标准函数free(p)；/释放p所指的结点变量空间结点分量的访问利用结点变量的名字*p访问结点分量方法一：(*p).data和(*p).next 方法二：p-data和p-next指针变量p和结点变量*p的关系指针变量p的值结点地址 结点变量*p的值结点内容(*p).data的值p指针所指结点的data域的值(*p).next的值*p后继结点的地址*(*p).next)*p后继结点注意：若指针变量p的值为空（null），则它不指向任何结点。此时，若通过*p来访问结点就意味着访问一个不存在的变量，从而引起程序的错误。有关指针类型的意义和说明方式的详细解释， 单链表的运算1、建立单链表假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符n为输入条件结束标志符。动态地建立单链表的常用方法有如下两种：（1）头插法建表 算法思路从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。注意：该方法生成的链表的结点次序与输入顺序相反。具体算法实现linklist creatlistf(void) /返回单链表的头指针 char ch; linklist head;/头指针 listnode *s; /工作指针 head=null; /链表开始为空 ch=getchar(); /读入第1个字符 while(ch!=n) s=(listnode *)malloc(sizeof(listnode);/生成新结点 s-data=ch; /将读入的数据放入新结点的数据域中 s-next=head; head=s; ch=getchar(); /读入下一字符 return head; （2）尾插法建表算法思路从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志为止。注意：采用尾插法建表，生成的链表中结点的次序和输入顺序一致必须增加一个尾指针r,使其始终指向当前链表的尾结点具体算法实现 linklist creatlistr(void) /返回单链表的头指针 char ch; linklist head;/头指针 listnode *s,*r; /工作指针 head=null; /链表开始为空 r=null;/尾指针初值为空 ch=getchar(); /读入第1个字符 while(ch!=n) s=(listnode *)malloc(sizeof(listnode);/生成新结点 s-data=ch; /将读入的数据放入新结点的数据域中 if (head!=null) head=s;/新结点插入空表 else r-next=s;/将新结点插到*r之后 r=s;/尾指针指向新表尾 ch=getchar(); /读入下一字符 /endwhileif (r!=null) r-next=null;/对于非空表，将尾结点指针域置空head=s; return head;注意：开始结点插入的特殊处理 由于开始结点的位置是存放在头指针(指针变量)中,而其余结点的位置是在其前趋结点的指针域中，插入开始结点时要将头指针指向开始结点。空表和非空表的不同处理 若读入的第一个字符就是结束标志符,则链表head是空表,尾指针r亦为空,结点*r不存在;否则链表head非空,最后一个尾结点*r是终端结点,应将其指针域置空。（3）尾插法建带头结点的单链表头结点及作用头结点是在链表的开始结点之前附加一个结点。它具有两个优点:由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理;无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。带头结点的单链表注意：头结点数据域的阴影表示该部分不存储信息。在有的应用中可用于存放表长等附加信息。尾插法建带头结点链表算法 linklist creatlistr1(void) /用尾插法建立带头结点的单链表 char ch; /生成头结点 linklist head=(listnode *)malloc(sizeof(listnode); listnode *s,*r; /工作指针 r=head; /尾指针初值也指向头结点 while(ch=getchar()!=n) s=(listnode *)malloc(sizeof(listnode);/生成新结点 s-data=ch; /将读入的数据放入新结点的数据域中 r-next=s; r=s; r-next=null;/终端结点的指针域置空，或空表的头结点指针域置空 return head; 注意：上述算法里，动态申请新结点空间时未加错误处理，这对申请空间极少的程序而言不会出问题。但在实用程序里，尤其是对空间需求较大的程序，凡是涉及动态申请空间，一定要加入错误处理以防系统无空间可供分配。（4）算法时间复杂度 以上三个算法的时间复杂度均为0(n)。2.单链表的查找运算（1）按序号查找链表不是随机存取结构在链表中，即使知道被访问结点的序号i，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。查找的思想方法计数器j置为0后，扫描指针p指针从链表的头结点开始顺着链扫描。当p扫描下一个结点时，计数器j相应地加1。当j=i时，指针p所指的结点就是要找的第i个结点。而当p指针指为null且ji时，则表示找不到第i个结点。注意：头结点可看做是第0个结点。具体算法实现 listnode* getnode(linklist head,int i) /在带头结点的单链表head中查找第i个结点，若找到（0in）， /则返回该结点的存储位置，否则返回null。 int j; listnode *p; p=head;j=0;/从头结点开始扫描 while(p-next&jnext为null或i=j为止 p=p-next; j+; if(i=j) return p;/找到了第i个结点 else return null;/当i0时，找不到第i个结点 算法分析算法中，while语句的终止条件是搜索到表尾或者满足ji，其频度最多为i，它和被寻找的位置有关。在等概率假设下，平均时间复杂度为：o(n) （2）按值查找思想方法从开始结点出发，顺着链逐个将结点的值和给定值key作比较，若有结点的值与key相等，则返回首次找到的其值为key的结点的存储位置；否则返回null。具体算法实现 listnode* locatenode (linklist head,datatype key) /在带头结点的单链表head中查找其值为key的结点listnode *p=head-next;/从开始结点比较。表非空，p初始值指向开始结点 while(p&p-data!=key)/直到p为null或p-data为key为止 p=p-next;/扫描下一结点 return p;/若p=null，则查找失败，否则p指向值为key的结点 算法分析该算法的执行时间亦与输入实例中key的取值相关，其平均时间复杂度分析类似于按序号查找，为o(n)。3.插入运算（1）思想方法插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。具体步骤：（1）找到ai-1存储位置p（2）生成一个数据域为x的新结点*s（3）令结点*p的指针域指向新结点（4）新结点的指针域指向结点ai。（2）具体算法实现 void insertlist(linklist head,datatype x,int i) /将值为x的新结点插入到带头结点的单链表head的第i个结点的位置上 listnode *p; p=getnode(head,i-1);/寻找第i-1个结点 if (p=null)/in+1时插入位置i有错 error(position error)； s=(listnode *)malloc(sizeof(listnode); s-data=x;s-next=p-next;p-next=s; （3）算法分析 算法的时间主要耗费在查找操作getnode上，故时间复杂度亦为o(n)。4.删除运算（1）思想方法删除运算是将表的第i个结点删去。具体步骤：（1）找到ai-1的存储位置p（因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中）（2）令p-next指向ai的直接后继结点（即把ai从链上摘下）（3）释放结点ai的空间，将其归还给存储池。（2）具体算法实现 void deletelist(linklist head,int i) /删除带头结点的单链表head上的第i个结点 listnode *p,*r; p=getnode(head,i-1);/找到第i-1个结点 if (p=null|p-next=null)/in时，删除位置错 error(position error);/退出程序运行 r=p-next;/使r指向被删除的结点ai p-next=r-next;/将ai从链上摘下 free(r);/释放结点ai的空间给存储池 注意：设单链表的长度为n，则删去第i个结点仅当1in时是合法的。当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p！=null）且*p不是终端结点（即p-next！=null）时，才能确定被删结点存在。（3）算法分析算法的时间复杂度也是o（n）。链表上实现的插入和删除运算，无须移动结点，仅需修改指针。循环链表（circularlinkedlist）循环链表是一种首尾相接的链表。1、循环链表（1）单循环链表在单链表中，将终端结点的指针域null改为指向表头结点或开始结点即可。（2）多重链的循环链表-将表中结点链在多个环上2、带头结点的单循环链表注意：判断空链表的条件是head=head-next3、仅设尾指针的单循环链表用尾指针rear表示的单循环链表对开始结点a1和终端结点an查找时间都是o(1)。而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。带尾指针的单循环链表可见下图。注意：判断空链表的条件为rear=rear-next;4、循环链表的特点循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。分析：若在单链表或头指针表示的单循环表上做这种链接操作，都需要遍历第一个链表，找到结点an，然后将结点b1链到an的后面，其执行时间是o(n)。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是o(1)。相应的算法如下： linklist connect(linklist a,linklist b) /假设a，b为非空循环链表的尾指针 linklist p=a-next;/保存a表的头结点位置 a-next=b-next-next;/b表的开始结点链接到a表尾 free(b-next);/释放b表的头结点 b-next=p;/ return b;/返回新循环链表的尾指针 注意：循环链表中没有null指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。双链表1、双向链表（doublelinkedlist）双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。注意：双链表由头指针head惟一确定的。带头结点的双链表的某些运算变得方便。将头结点和尾结点链接起来，为双（向）循环链表。2、双向链表的结点结构和形式描述结点结构形式描述 typedef struct dlistnode datatype data; struct dlistnode *prior,*next; dlistnode; typedef dlistnode *dlinklist; dlinklist head;3、双向链表的前插和删除本结点操作由于双链表的对称性，在双链表能能方便地完成各种插入、删除操作。双链表的前插操作void dinsertbefore(dlistnode *p,datatype x) /在带头结点的双链表中，将值为x的新结点插入*p之前，设pnull dlistnode *s=malloc(sizeof(dlistnode);/ s-data=x;/ s-prior=p-prior;/ s-next=p;/ p-prior-next=s;/ p-prior=s;/ 双链表上删除结点*p