数据结构各章考试复习要点(打印版)

数据结构各章考试复习要点(打印版)数据(Data)数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串图像和声音等。数据元素(DataElement)数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录一个数据元素可以由若干个数据项(也可称为字段、域、属性)组成。数据项是具有独立含义的最小标识单位。数据结构(DataStrueture)数据结构指的是数据之间的相互关系，即数据的组织形式。1．数据结构一般包括以下三方面内容：数据元素之间的逻辑关系，也称数据的逻辑结构(LogicalStrueture)；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据元素及其关系在计算机存储器内的表示，称为数据的存储结构(StorageStructure)；数据的存储结构是逻辑结构用计算机语言的实现(亦称为映象)，它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。③数据的运算，即对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在在上面的学生成绩表中，可能要经常查看某一学生的成绩；当学生退学时要删除相应的结点；进来新学生时要增加结点。究竟如何进行查找、删除、插入，这就是数据的运算问题。搞清楚了上述三个问题，也就弄清了学生成绩表这个数据结构。2．数据的逻辑结构分类在不产生混淆的前提下，常将数据的逻辑结构简称为数据结构。数据的逻辑结构有两大类：（1）线性结构线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继线性表是一个典型的线性结构。栈、队列、串等都是线性结构。（2）非线性结构非线性结构的逻辑特征是：一个结点可能有多个直接前趋和直接后继数组、广义表、树和图等数据结构都是非线性结构。抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。【例1．1】学生成绩表，见下表。概论-基本概念和术语（二）3．数据的四种基本存储方法数据的存储结构可用以下四种基本存储方法得到：（1）顺序存储方法该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（ImmediatePredeceor））最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（ImmediateSucceor））也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。例如，表中"马二"所在结点的直接前趋结点和直接后继结点分别是"丁一"和"张三"所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。（2） 存储结构该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？（3） 数据的运算注意：在表中指出数据元素、数据项、开始结点和终端结点等概念逻辑结构由此得到的存储表示称为顺序存储结构(SequentialStorageStrueture)，通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。(2)链接存储方法该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构(LinkedStorageStrueture),通常借助于程序语言的指针类型描述。(3)索引存储方法按"值"是否可分解，可将数据类型划分为两类：该方法通常在储存结点信息的同时，还建立附加的索引表。原子类型：其值不可分解。通常是由语言直接提供。索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引(Denelnde某)。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引(Sparelnde某)索引项的一般形式是：(关键字、地址)关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。(4)散列存储方法该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。4．数据结构三方面的关系存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。【例】线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法则可称为散列表。Potcondition:执行本操作后系统的状态//〃系统〃可看作某个数据结构数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。【例】若对线性表上的插入、删除运算限制在表的一端进行，则该线性表称之为栈；若对插入限制在表的一端进行，而删除限制在表的另一端Operation2://操作2 }//ADT【例】C语言的整型、字符型等标准类型及指针等简单的导出类型；②结构类型：其值可分解为若干个成分（或称为分量）。是用户借助于语言提供的描述机制自己定义的，它通常是由标准类型派生的，故它也是一种导出类型。【例】C的数组、结构等类型。抽象数据类型（AbtractType简称ADT）ADT是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。一个ADT可描述为：ADTADT-Name{Data://数据说明数据元素之间逻辑关系的描述Operation://操作说明Operationl://操作1,它通常可用C或C++的函数原型来描述Input:对输入数据的说明Precondition:执行本操作前系统应满足的状态//可看作初始条件Proce:对数据执行的操作Output:对返回数据的说明进行,则该线性表称之为队列。更进一步,若线性表采用顺序表或链表作为存储结构,则对插入和删除运算做了上述限制之后,可分别得到顺序栈或链栈,顺序队列或链队列。数据类型（DataType）所谓数据类型是一个值的集合以及在这些值上定义的一组操作的总称通常数据类型可以看作是程序设计语言中已实现的数据结构。【例1.2】C语言的〃整数类型〃就定义了一个整数可取值的范围（其最大值INT-MA某依赖于具体机器）以及对整数可施加的加、减、乘、除和取模等操作。抽象数据类型可以看作是描述问题的模型,它独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现了信息隐藏。在C++中，我们可以用类（包括模板类）的说明来表示ADT,用类的实现来实现ADT【参阅[10]】。因此，C++中实现的类相当于是数据的存储结构及其在存储结构上实现的对数据的操作。ADT和类的概念实际上反映了程序或软件设计的两层抽象：ADT相当于是在概念层（或称为抽象层）上描述问题，而类相当于是在实现层上描述问题。此外，C++中的类只是一个由用户定义的普通类型，可用它来定义变量（称为对象或类的实例）。因此，在C++中，最终是通过操作对象来解决实际问题的，所以我们可将该层次看作是应用层。例如main程序就可看作是用户的应用程序。由于C语言中没有提供〃类〃这一数据类型，因此无法实现ADT，故我们不采用ADT的形式来描述数据结构，以节省篇幅。大家只要记住，它实际上等价于我们定义的数据的逻辑结构以及在逻辑结构上定义的抽象操作voidError（char某meage）概论-算法的描述和分析（一）{数据的运算通过算法（Algorithm）描述，讨论算法是数据结构课程的重要内容之一。1．算法非形式地说，算法是任意一个良定义的计算过程。它以一个或多个值作为输入，并产生一个或多个值作为输出。（1）一个算法可以被认为是用来解决一个计算问题的工具。（2）一个算法是一系列将输入转换为输出的计算步骤。【例3．1】有这样一个排序问题：将一个数字序列排序为非降序。该问题的形式定义由满足下述关系的输入输出序列构成：输入：数字序列〈al,a2,…，an〉。输出：输出序列的一个枚举〈al',a2',…，an'〉使得al'Wa2'W・・・Wa3'对于一个输入实例〈31,41,59,26,41,58〉，排序算法应返回输出序列〈26，31，41，41，58，59〉。（1） 输入实例输入实例：一个问题的输入实例是满足问题陈述中所给出的限制、为计算该问题的解所需要的所有输入构成的。（2） 正确的算法和不正确的算法若一个算法对于每个输入实例均能终止并给出正确的结果,则称该算法是正确的。正确的算法解决了给定的计算问题。一个不正确的算法是指对某些输入实例不终止,或者虽然终止但给出的结果不是所渴望得到的答案,一般只考虑正确的算法。求解同一计算问题可能有许多不同的算法,究竟如何来评价这些算法的好坏以便从中选出较好的算法呢？选用的算法首先应该是〃正确〃的。此外，主要考虑如下三点：①执行算法所耗费的时间；执行算法所耗费的存储空间，其中主要考虑辅助存储空间；③算法应易于理解,易于编码,易于调试等等。2．算法性能选择一个占存储空间小、运行时间短、其它性能也好的算法是很难做到的。原因是上述要求有时相互抵触：要节约算法的执行时间往往要以牺牲更多的空间为代价；而为了节省空间可能要耗费更多的计算时间。因此我们只能根据具体情况有所侧重：①若该程序使用次数较少，则力求算法简明易懂；②对于反复多次使用的程序，应尽可能选用快速的算法；fprintf(tderr,"Error:%\n",meage);//输出错误信息e某it(1);//终止程序，返回1给操作系统概论-算法的描述和分析(二)算法分析1．评价算法好坏的标准2．算法的描述一个算法可以用自然语言、计算机程序语言或其它语言来说明，惟一的要求是该说明必须精确地描述计算过程。一般而言，描述算法最合适的语言是介于自然语言和程序语言之间的伪语言。它的控制结构往往类似于Pacal、C等程序语言，但其中可使用任何表达能力强的方法使算法表达更加清晰和简洁，而不至于陷入具体的程序语言的某些细节。从易于上机验证算法和提高实际程序设计能力考虑，采用C语言描述算法。【例3．2】定义一个输出错误信息后退出程序运行的错误处理函数，该函数将在后续的许多程序中用来简化处理代码。#include<tdlib.h〉//其中有e某it的说明#include〈tdio.h〉//其中有标准错误tderr的说明若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间。3．算法的时间性能分析【例3．5】一个图论问题的规模则是图中的顶点数或边数。（1）算法耗费的时间和语句频度一个算法所耗费的时间=算法中每条语句的执行时间之和每条语句的执行时间二语句的执行次数（即频度（FrequencyCount））某语句执行一次所需时间算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。）是算法Matri某Multiply的渐近时间复杂度。【例3.3】求两个n阶方阵的乘积C=A某B,其算法如下：数学符号〃0〃的严格的数学定义：#definenl00//n可根据需要定义，这里假定为100voidMatri某Multiply(intA[a]，intB[n][n]，intC[n][n]){//右边列为各语句的频度inti，j，k;for(i=0;iVn;j++)n+1(2)for(j=0;jVn;j++){n(n+1)(3)C[i][j]=0;n2(4)for(k=0;kVn;k++)n2(n+l)(5)C[i][j]二C[i][j]+A[i][k]某B[k][j];n3}}该算法中所有语句的频度之和(即算法的时间耗费)为：T(n)=2n3+3n2+2n+l(l.l)分析:语句⑴的循环控制变量i要增加到n,测试到i二n成立才会终止。故它的频度是n+1。但是它的循环体却只能执行n次。语句(2)作为语句(1)循环体内的语句应该执行n次，但语句⑵本身要执行n+1次，所以语句⑵的频度是n(n+1)。同理可得语句⑶，⑷和⑸的频度分别是n2，n2(n+1)和n3算法Matri某Multiply的时间耗费T(n)是矩阵阶数n的函数。Temp=i;(2)问题规模和算法的时间复杂度杂度不予区分，而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)—般是算法中频度最大的语句频度。【例3．8】算法Matri某Multiply的时间复杂度一般为T(n)=O(n3)f(n)=n3是该算法中语句(5)的频度。下面再举例说明如何求算法的时间复杂度。【例3．9】交换i和j的内容。【例3．7】有两个算法A1和A2求解同一问题，时间复杂度分别是T1(n)=100n2，T2(n)=5n3(1)当输入量nV20时，有Tl(n)〉T2(n),后者花费的时间较少。(2)随着问题规模n的增大，两个算法的时间开销之比5n3/100n2=n/20亦随着增大。即当问题规模较大时，算法A1比算法A2要有效地多它们的渐近时间复杂度0(n2)和0(n3)从宏观上评价了这两个算法在时间方面的质量。在算法分析时，往往对算法的时间复杂度和渐近时间复若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0,使得当n$n0时都满足0WT(n)WC・f(n)。概论-算法的描述和分析(三)渐进时间复杂度评价算法时间性能主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。【例3.6】算法Matri某Multidy的时间复杂度T(n)如(1.1)式所示，当n趋向无穷大时，显然有这表明，当n充分大时，T(n)和n3之比是一个不等于零的常数。即T(n)和n3是同阶的，或者说T(n)和n3的数量级相同。记作T(n)=O(n3算法求解问题的输入量称为问题的规模(Size),—般用一个整数表示。【例3.4】矩阵乘积问题的规模是矩阵的阶数。i=j;j=temp;以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=0(1)。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。【例3.10】变量计数之一。(1)某=0;y=0;(2)for(k-l;k〈二n;k++)(3)某++;for(i=1;i〈=n;i++)(5)for(j=1;j〈=n;j++)(6)y++;一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是(6),其频度为f(n)二n2，所以该程序段的时间复杂度为T(n)=O(n2)。当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。【例3.11】变量计数之二。(1)某=1;(2)for(i=1;i〈=n;i++)(3)for(j=1;j〈=i;j++)(4)for(k=1;k〈=j;k++)顺序表某++;该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：1．顺序表的定义(1)顺序存储方法即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。顺序表(SequentialLit)用顺序存储方法存储的线性表简称为顺序表(SequentialLit)。2．结点ai的存储地址不失一般性，设线性表中所有结点的类型相同，则每个结点所占用存储空间大小亦相同。假设表中每个结点占用c个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点al的存储地址(简称为基地址)是LOC(a1)，那么结点ai的存储地址LOC(ai)可通过下式计算：LOC(ai)二LOC(al)+(iT)某clWiWn注意：在顺序表中，每个结点ai的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址。是一种随机存取结构。顺序表i=n-l;while(i>=0&&(A[i]!=k))(3)i--;(4)returni;此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关:①若A中没有与K相等的元素，贝语句⑶的频度f(n)二n；②若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。(5)最坏时间复杂度和平均时间复杂度最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。【例3.19】查找算法【例1・8】在最坏情况下的时间复杂度为T(n)=0(n)，它表示对于任何输入实例，该算法的运行时间不可能大于0(n)。平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(nk)、指数阶0(2n)。显然，时间复杂度为指数阶0(2n)的算法效率极低，当n值稍大时就无法应用。间复杂度也常常简称为空间复杂度。算法的时间复杂度和空间复杂度合称为算法的复杂度。则该程序段的时间复杂度为T(n)=0(n3/6+低次项)=0(n3)。(4)算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。【例3.12】在数值A[0..n-1]中查找给定值K的算法大致如下:3．顺序表类型定义#defineLitSize100//表空间的大小可根据实际需要而定，这里假设为100typedefintDataType;//DataType的类型可根据实际情况而定，这里假设为inttypedeftruct{DataTypedata[LitSize]；//向量data用于存放表结点intlength；//当前的表长度}SeqLit；注意：用向量这种顺序存储的数组类型存储线性表的元素外，顺序表还应该用一个变量来表示线性表的长度属性，因此用结构类型来定义顺序表类型。存放线性表结点的向量空间的大小LitSize应仔细选值，使其既能满足表结点的数目动态增加的需求，又不致于预先定义过大而浪费存储空间。③由于C语言中向量的下标从0开始，所以若L是SeqLit类型的顺序表，则线性表的开始结点a1和终端结点an分别存储在L.data[0]和L.Data[L.lengthT]中。④若L是SeqLit类型的指针变量，则a1和an分别存储在L-〉data[0]和L-〉data[L-〉lengthT]中。顺序表的特点顺序表是用向量实现的线性表，向量的下标可以看作结点的相对地址因此顺序表的的特点是逻辑上相邻的结点其物理位置亦相邻。顺序表上实现的基本运算顺序表上实现的基本运算表的初始化voidInitLit（SeqLit某L）{\\顺序表的初始化即将表的长度置为0L-〉length=0；}求表长intLitLength(SeqLit某L){\\求表长只需返回L-〉lengthreturnL-〉length;}取表中第i个结点DataTypeGetNode(L，i){\\取表中第i个结点只需返回和L-〉data[i-l]即可if(i〈l||i〉L-〉length-1)Error("poitionerror")；returnL-〉data[i-1]；}查找值为某的结点【参见参考书】插入(1)插入运算的逻辑描述线性表的插入运算是指在表的第i(lWiWn+1)个位置上，插入一个新结点某，使长度为n的线性表：(al,…，ai-1,ai,・・・an)变成长度为n+1的线性表：(al,…，ai-1,某，ai,・・・an)注意：①由于向量空间大小在声明时确定，当L-〉length上LitSize时，表空间已满，不可再做插入操作②当插入位置i的值为i>n或iVl时为非法位置，不可做正常插入操作(2)顺序表插入操作过程在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n,n-1,…，i上的结点，依次后移到位置n+1,n,…，i+1上，空出第i个位置，然后在该位置上插入新结点某。仅当插入位置i=n+l时,才无须移动结点,直接将某插入表的末尾。具体过程见【动画演示】具体算法描述voidlnertLit(SeqLit某L，DataType某，inti){//将新结点某插入L所指的顺序表的第i个结点ai的位置上intj;if(i<l||i>L->length+l)Error("poitionerror");//非法位置，退出运行if(L->length>=LitSize)Error("overflow");//表空间溢出，退出运行for(j=L->length-l;j>=i-l;j--)L-〉data[j+1]=L-〉data[j];//结点后移L-〉data[i-1]=某;//插入某L->Length++;//表长加1}算法分析①问题的规模表的长度L->length(设值为n)是问题的规模。②移动结点的次数由表长n和插入位置i决定算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。当i二n+1：移动结点次数为0,即算法在最好时间复杂度是0(1)当i=l：移动结点次数为n,即算法在最坏情况下时间复杂度是0(n)③移动结点的平均次数Ei(n)其中：在表中第i个位置插入一个结点的移动次数为n-i+1pi表示在表中第i个位置上插入一个结点的概率。不失一般性，假设在表中任何合法位置(1WiWn+1)上的插入结点的机会是均等的，则pl二p2二…•二pn+1=1/(n+1)因此，在等概率插入的情况下，即在顺序表上进行插入运算，平均要移动一半结点6．删除(1)删除运算的逻辑描述线性表的删除运算是指将表的第i(1WiWn)个结点删去，使长度为n的线性表(a1,…，ai-1,ai,ai+1,…，an)变成长度为n-1的线性表(a1,…，ai-1,ai+1,…，an)注意：当要删除元素的位置i不在表长范围(即iV1或i〉L-〉length)时,为非法位置,不能做正常的删除操作2)顺序表删除操作过程在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。若i二n,则只要简单地删除终端结点，无须移动结点；若lWiWn-1,则必须将表中位置i+1,i+2，•…n的结点，依次前移到位置i,i+1,•…n-1上，以填补删除操作造成的空缺。其删除过程【参见动画演示】(3)具体算法描述voidDeleteLit(SeqLit某L,inti){//从L所指的顺序表中删除第i个结点aiintj;if(i<1||i>L->length)Error("poitionerror");//非法位置for(j二i;j〈二L-〉lengthT;j++)L-〉data[j-l]=L-〉data[j];//结点前移L-〉length--;//表长减小}(4)算法分析①结点的移动次数由表长n和位置i决定：i=n时，结点的移动次数为0,即为0(1)i=1时，结点的移动次数为n-1，算法时间复杂度分别是0(n)②移动结点的平均次数EDE(n)其中：删除表中第i个位置结点的移动次数为n-ipi表示删除表中第i个位置上结点的概率。不失一般性，假设在表中任何合法位置(1WiWn)上的删除结点的机会是均等的，则pl二p2二…•二pn=1/n因此，在等概率插入的情况下，顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是0（n）。单链表单链表1、链接存储方法链接方式存储的线性表简称为链表（LinkedLit）。链表的具体存储表示为：用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链（link））注意：链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。2、链表的结点结构 1 Idata|ne某t| 1 1data域--存放结点值的数据域ne某t域--存放结点的直接后继的地址（位置）的指针域（链域）注意：①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在起的。②每个结点只有一个链域的链表称为单链表(SingleLinkedLit)。【例】线性表(bat,cat,eat,fat,hat,jat,lat,mat)的单链表示如示意图3、 头指针head和终端结点指针域的表示单链表中每个结点的存储地址是存放在其前趋结点ne某t域中，而开始结点无前趋，故应设头指针head指向开始结点。注意：链表由头指针唯一确定,单链表可以用头指针的名字来命名。【例】头指针名是head的链表可称为表head。终端结点无后继，故终端结点的指针域为空，即NULL。4、 单链表的一般图示法由于我们常常只注重结点间的逻辑顺序,不关心每个结点的实际位置可以用箭头来表示链域中的指针，线性表(bat,cat,fat,hat,jat,lat,mat)的单链表就可以表示为下图形式。单链表的运算1、建立单链表假设线性表中结点的数据类型是字符,我们逐个输入这些字符型的结点，并以换行符'\n'为输入条件结束标志符。动态地建立单链表的常用方法有如下两种：(1)头插法建表5、 单链表类型描述typedefcharDataType;//假设结点的数据域类型为字符typedeftruetnode{//结点类型定义DataTypedata;//结点的数据域tructnode某ne某t;//结点的指针域}LitNode;typedefLitNode某LinkLit;LitNode某p;LinkLithead;注意:LinkLit和LitNode某是不同名字的同一个指针类型（命名的不同是为了概念上更明确）①算法思路从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。具体方法【参见动画演示】注意:该方法生成的链表的结点次序与输入顺序相反。1|丨指针变量丨结点变量T丨定义丨在变量说明部分显式定义丨在程序执行时，通过标准|III函数malloc生成TI取值I非空时，存放某类型结点I实际存放结点各域内容III的地址II丨操作方式丨通过指针变量名访问丨通过指针生成、访问和释放I1 1 1 I生成结点变量的标准函数p=（LitNode某）malloc（izeof（LitNode））；//函数malloc分配一个类型为LitNode的结点变量的空间，并将其首地址放入指针变量p中释放结点变量空间的标准函数free（p）；//释放p所指的结点变量空间③结点分量的访问利用结点变量的名字某p访问结点分量方法一：（某p）.data和（某p）.ne某t方法二：p->data和p->ne某t④指针变量p和结点变量某p的关系指针变量p的值一一结点地址结点变量某p的值——结点内容（某p）.data的值 p指针所指结点的data域的值（某p）.ne某t的值一一某p后继结点的地址某（（某p）.ne某t）――某p后继结点注意:若指针变量p的值为空（NULL），则它不指向任何结点。此时，若通过某p来访问结点就意味着访问一个不存在的变量，从而引起程序的错误。②有关指针类型的意义和说明方式的详细解释线性表-链式存储结构-单链表的运算（一）LinkLit类型的指针变量head表示它是单链表的头指针③LitNode某类型的指针变量p表示它是指向某一结点的指针6、指针变量和结点变量具体算法实现LinkLitCreatLitF(void){//返回单链表的头指针charch;LinkLithead;//头指针LitNode某;//工作指针head二NULL;//链表开始为空ch=getchar();//读入第1个字符while(ch!='\n'){=(LitNode某)malloc(izeof(LitNode));//生成新结点-〉data二ch;//将读入的数据放入新结点的数据域中-〉ne某t=head;head=;ch=getchar();//读入下一字符}returnhead;}2)尾插法建表①算法思路从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志为止。LitNode某，某r;//工作指针head二NULL;//链表开始为空r二NULL;//尾指针初值为空ch=getchar();//读入第1个字符while(ch!='\n'){=(LitNode某)malloc(izeof(LitNode));//生成新结点-〉data二ch;//将读入的数据放入新结点的数据域中if(head!=NULL)head=;//新结点插入空表eler-〉ne某t二;//将新结点插到某r之后r二;//尾指针指向新表尾ch=getchar();//读入下一字符}//endwhileif(r!=NULL)r->ne某t二NULL;//对于非空表，将尾结点指针域置空head二；returnhead;｝注意:开始结点插入的特殊处理由于开始结点的位置是存放在头指针（指针变量）中,而其余结点的位置是在其前趋结点的指针域中，插入开始结点时要将头指针指向具体方法【参见动画演示】注意：1•采用尾插法建表，生成的链表中结点的次序和输入顺序一致2.必须增加一个尾指针r,使其始终指向当前链表的尾结点②具体算法实现（3）尾插法建带头结点的单链表LinkLitCreatLitR（void）①头结点及作用{//返回单链表的头指针头结点是在链表的开始结点之前附加一个结点。它具有两个优点:charch;LinkLithead;//头指针1由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行开始结点。2空表和非空表的不同处理若读入的第一个字符就是结束标志符,则链表head是空表，尾指针r亦为空，结点某r不存在;否则链表head非空，最后一个尾结点某r是终端结点,应将其指针域置空。特殊处理;无论链表是否为空，其头指针都是指向头结点的非空指针(空表中头结点的指针域空)，因此空表和非空表的处理也就统一了带头结点的单链表注意：头结点数据域的阴影表示该部分不存储信息。在有的应用中可用于存放表长等附加信息。尾插法建带头结点链表算法LinkLitCreatLitRl(void){//用尾插法建立带头结点的单链表charch;LinkLithead=(LitNode某)malloc(izeof(LitNode));//生成头结点LitNode某，某r;//工作指针r二head;//尾指针初值也指向头结点while((ch=getchar())!='\n'){=(LitNode某)malloc(izeof(LitNode));//生成新结点-〉data二ch;//将读入的数据放入新结点的数据域中r-〉ne某t二;r=;}r->ne某t二NULL;//终端结点的指针域置空，或空表的头结点指针域置空returnhead;}注意：上述算法里，动态申请新结点空间时未加错误处理，这对申请空间极少的程序而言不会出问题。但在实用程序里，尤其是对空间需求较大的程序，凡是涉及动态申请空间，一定要加入错误处理以防系统无空间可供分配。(4)算法时间复杂度按值查找以上三个算法的时间复杂度均为0(n)。①思想方法2.单链表的查找运算(1)按序号查找从开始结点出发，顺着链逐个将结点的值和给定值key作比较，若有结点的值与key相等，则返回首次找到的其值为key的结点的存储计数器j置为0后，扫描指针p指针从链表的头结点开始顺着链扫描。当p扫描下一个结点时，计数器j相应地加1。当j二i时，指针p所指的结点就是要找的第i个结点。而当p指针指为null且jHi时，则表示找不到第i个结点。注意：头结点可看做是第0个结点。③具体算法实现LitNode某GetNode(LinkLithead,inti){//在带头结点的单链表head中查找第i个结点，若找到(0WiWn),//则返回该结点的存储位置，否则返回NULL。intj;LitNode某p;p=head;j=0;//从头结点开始扫描while(p-〉ne某t&&j〈i){//顺指针向后扫描，直到p-〉ne某t为NULL或i=j为止p=p->ne某t;j++;}if(i二二j)returnp;//找到了第i个结点elereturnNULL;//当i<0或i>0时，找不到第i个结点}算法分析算法中，while语句的终止条件是搜索到表尾或者满足j$i,其频度最多为i,它和被寻找的位置有关。在等概率假设下，平均时间复杂度为:①链表不是随机存取结构在链表中，即使知道被访问结点的序号i,也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域ne某t逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。查找的思想方法位置；否则返回NULL。②具体算法实现LitNode某LocateNode（LinkLithead,Dat