下载掌阅APP，畅读海量书库
立即打开
本节将介绍线性表的概念、顺序存储和链式存储及相应的基本操作实现。
线性表是一种简单的、最基本的线性结构。线性表的特点：数据元素之间仅具有单一前驱和后继关系，在一个线性表中数据元素的类型是相同的。
在实际应用中，线性表是一种常见的数据类型，如字符串“Data structure”是一个线性表，表中数据元素的类型为字符型；又如，学生情况信息表是一个线性表，表中数据元素的类型为由学号、姓名、性别、年龄、专业等组成的结构体类型。
从上面的例子可以看出，线性表是由具有相同数据类型的 n （ n ≥0）个数据元素组成的有限序列，通常记为
L =（ a 1 ， a 2 ，…， a i -1 ， a i ， a i +1 ，…， a n ）
式中， a i 是序号为 i 的数据元素（ i =1，2，…， n ）。 a 1 称为表头元素， a n 称为表尾元素。
线性表中所含数据元素的个数 n 称为线性表的长度， n =0时称该线性表为空表。
线性表中相邻元素之间存在着顺序关系， a i -1 称为 a i 的直接前趋（以下简称为前驱）， a i +1 称为 a i 的直接后继（以下简称为后继）。
非空线性表的特点如下：
1）有且仅有一个表头结点 a 1 ，它没有前趋，仅有一个后继 a 2 。
2）有且仅有一个表尾结点 a n ，它没有后继，仅有一个前趋 a n -1 。
3）其余的结点 a i （2≤ i ≤ n -1）都有且仅有一个前趋 a i -1 和一个后继 a i +1 。
线性表的长度可以根据需要加长或缩短，即对线性表的数据元素不仅可以访问，还可以进行插入和删除等操作。
线性表有两种存储结构：顺序存储和链式存储。下面分别讨论这两种存储结构以及各自的基本操作。
1. 顺序存储结构
线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表又称为顺序表。
因为内存中的地址空间是线性的，所以用物理上的相邻关系来实现数据元素之间的逻辑相邻关系既简单又自然。
在C/C++程序设计语言中，一维数组在内存中占用的存储空间是一组连续的存储区域，因此用一维数组来表示顺序表是一种简单而合适的方法。因为顺序表的长度是可以变化的，所以通常将一维数组和顺序表的长度封装成一个结构体来描述顺序表。
考虑到对整数操作的简单性，下面给出数据元素为整型数的顺序表类型描述。
其中，MAXSIZE表示数组的最大容量。由于顺序表要进行插入、删除等操作，因此顺序表中实际元素的个数是可变的，可用一个变量length来记录当前顺序表中元素的个数，以方便对顺序表的操作控制。顺序表的存储结构示意图如图2-2所示。
图2-2 顺序表的存储结构示意图
注意：C/C++语言中数组下标从0开始，因此顺序表中序号为 i 的元素，存储在数组中的下标为 i -1。
2. 顺序表基本操作的实现
针对图2-2所示顺序表存储结构上的 整型 数据元素，顺序表的基本操作通常包括初始化、遍历、查看实际长度、查找元素、插入元素、删除元素等操作。各操作算法函数名中包含了“_Seq”以表明是顺序表（Sequence List）相关操作。
（1）初始化操作
本节为顺序表提供了两个用以初始化的函数，一个函数用于创建一个空表，另一个函数用于创建长度为 n 、元素为数组 a 中元素的顺序表。下面分别给出这两个函数的具体描述。
算法2-1 创建空表
算法2-2 创建长度为 n 的顺序表
（2）遍历顺序表
遍历操作只需依次输出数组data中的元素即可，如算法2-3所示。
算法2-3 遍历顺序表
（3）求顺序表的长度
由于在顺序表的类型定义中，成员变量length用于记录当前线性表中元素的个数，因此要求顺序表长度，直接返回length即可，如算法2-4所示。
算法2-4 求顺序表的长度
（4）查找元素
将待查找的整型值 e 与顺序表中的元素依次进行比较，如果查找到具有 e 值的元素时，则返回该元素的序号（下标值+1）；否则返值0，表明查找失败，如算法2-5所示。
算法2-5 顺序表的查找元素
（5）插入
顺序表的插入是指在表的第 i 个位置上插入一个值为 e 的新元素，插入后使原长度为 n 的顺序表变成长度为 n +1的表，如图2-3所示。
图2-3 顺序表中的插入
算法步骤如下：
1）检查顺序表的存储空间是否已到最大值（被占满），若是则停止插入，并给出提示；否则执行步骤2）。
2）检查插入位置 i 是否合法，若不合法，则停止插入，并给出提示；否则执行步骤3）。
3）从最后一个元素（下标为length-1）向前直至第 i 个元素（下标为 i -1）为止，将每一个元素均后移一个存储单元，将第 i 个元素的存储位置空出。
4）将新元素 e 写入到第 i 个元素处，即下标为 i -1的位置。
5）将顺序表的长度加1。
顺序表插入算法的具体实现如算法2-6所示。
算法2-6 顺序表的插入
从算法2-6可以看出，顺序表上的插入运算时间主要消耗在数据的移动上。对于一个长度为 n 的顺序表（ a 1 ， a 2 ，…， a i -1 ， a i ， a i +1 ，…， a n ），在第 i 个位置上插入 e ，需要将 a i ～ a n 都向后移动一个位置，共需要移动 n-i +1个元素，而 i 的取值范围为1≤ i ≤ n +1，即有 n +1个位置可以插入。设在第 i 个位置上插入的概率为 P i ，则平均移动数据元素的次数
设 P i =1/（ n +1），即为等概率情况，则
这说明在顺序表上进行插入操作，需移动表中一半的数据元素。该算法的时间复杂度为 O （ n ）。
（6）删除
顺序表的删除运算是指将表中第 i 个元素从线性表中去掉，删除后线性表的长度由 n 变成 n -1，如图2-4所示。
算法步骤如下：
1）检查删除位置 i 是否合法，若不合法，则给出提示；否则执行步骤2）。
2）取出被删除元素。
3）从第 i +1个元素（下标为 i ）向后直至最后一个元素为止，将每一个元素均前移一个存储位置。
4）将顺序表的长度减1。
顺序表删除算法的具体实现如算法2-7所示。
算法2-7 顺序表的删除
图2-4 顺序表中的删除
与插入操作相同，顺序表的删除操作时间主要消耗在移动表中元素上。对于一个长度为 n 的顺序表（ a 1 ， a 2 ，…， a i -1 ， a i ， a i +1 ，…， a n ），删除第 i 个元素时，其后面的元素 a i +1 ～ a n 都要向前移动一个位置，共移动了 n-i 个元素，所以平均移动数据元素的次数为
在等概率情况下， P i =1/ n ，则
这说明顺序表上进行删除操作，大约需要移动表中一半的元素。该算法的时间复杂度为 O （ n ）。
注意：以上算法描述中，利用了C++提供的引用来传递函数的结果，而没有采用return语句。
请尝试总结C++中引用参数的优点。如有困难，请用手机扫描右侧的二维码查看介绍。
3. 顺序表基本操作的优化
至此，数据元素为整型数的顺序表类型定义及基本操作已完成，但这样的顺序表在完成本章案例时存在什么缺陷呢？
首先，在不同的应用场景下，线性表的数据元素类型可能是任意的，上述实现将数据元素限定在整型数，显然缺乏通用性，如对于本章导学问题形成的线性表的数据元素类型就应是结构体类型；其次，如果面对不同数据规模的信息管理系统，在线性表定义时，就固定了存储数据元素的data数组的大小，会由于应用场景的需求不同，造成数组空间浪费或不足，显然缺乏灵活性；再次，即使data数组的大小不是在定义时就固定，但若不能提供扩展机制，则在应用场景需求增大时，依然会造成空间不足的情况，从而缺乏适用性。
为此，需要对上述顺序表基本操作的实现进行优化，具体方法见表2-3。
表2-3 顺序表的优化
（续）
（续）
读者可根据上表给出的方法，完成课后应用实战第1题。
注意：以上优化算法描述中，利用了C++中提供的new和delete动态创建和释放数组。
请尝试总结C++中new/delete与C语言中的malloc/free的区别。如有困难，请用手机扫描右侧的二维码查看介绍。
1. 链式存储结构
线性表的链式存储结构又称为链表，它用一组物理上不一定相邻的存储单元来存储线性表中的数据元素。
为了建立起数据元素之间的逻辑关系，对线性表中的每个数据元素 a i ，除了存放数据元素的自身信息外，还需要存储其后继元素所在的地址信息，这个地址信息称为指针。数据元素自身信息和指针组成了数据元素的存储映像，称为结点。一般地，一个结点可以包含一个或多个指针。含有一个指针使其指向后继的称为单链表，含有两个指针分别指向前驱和后继的称为双向链表。
（1）单链表
在单链表中，每个数据元素由一个结点表示，该结点包含两部分信息：数据元素自身的信息和该元素后继的存储地址。存放数据元素信息的称为数据域，存放其后继地址的称为指针域，如图2-5所示。图2-6是线性表（ a 1 ， a 2 ， a 3 ， a 4 ， a 5 ， a 6 ）对应的单链表可能的存储示意图。
在单链表中，每个结点的存储地址存放在其前驱结点的next域中，因而第1个结点是没有前驱结点的，它的地址就是整个链表的开始地址，因此必须将第1个结点的地址放到一个指针变量（如图2-6所示的head）中，该指针变量称为头指针。这样就可以从头指针开始，依次找到每个结点。通常用头指针来标识一个单链表。最后一个结点没有后继，其指针域必须置空（NULL），表明该单链表到此结束。
在单链表中，为了方便操作，有时在链表的第一个结点前加入一个“头结点”，头结点的类型与其他数据结点相同，链表的头指针变量head中存放该头结点的地址，这样即使是空表，头指针变量head也不为空了。头结点的加入使得单链表无论是否为空，头指针始终指向头结点，因此空表和非空表的处理可以用统一的语句实现。
图2-5 单链表结点结构
图2-6 单链表存储示意图
头结点的数据域可以不存放任何信息，也可以存放有关链表的整体信息，如表长；指针域中存放的是第一个数据元素结点的地址，空表时其中为空（NULL）。
图2-7a、图2-7b分别是带头结点的空单链表和非空单链表的示意图。
图2-7 带头结点的单链表
a）空单链表 b）非空单链表
数据元素为整型数的单链表结点类型定义如下：
可以用LinkList定义一个表头结点的指针，该指针就代表了一个单链表，如：
（2）循环链表
如果将单链表最后一个结点的指针域指向头结点，就使得整个链表形成了一个环，这种链表称为单循环链表，简称循环链表，如图2-8所示。
图2-8 带头结点的单循环链表
a）空循环链表 b）非空循环链表
循环链表的操作基本与单链表相类似，区别仅在于判断单链表结束的条件是指针是否为空，而判断循环链表结束的条件是指针是否指向头结点。
在单链表中只能从头结点开始遍历（依次访问）整个链表，但在循环链表中则可以从任意结点开始遍历整个链表。不仅如此，如果需要对链表常做的操作是在表尾进行，那么可以改变一下链表的标识方法，不用头指针而用一个指向表尾结点的指针来标识，这有助于提高操作效率。
（3）双向链表
上述循环链表尽管可以从任意结点出发访问到其他任何结点，但是由于结点中只有一个指向其后继结点的指针域next，因此如果已知某结点的指针为p，其后继结点的指针则为p-＞next，而要找其前驱则只能顺着各结点的next域进行。也就是说，找后继的时间复杂度是 O （1），找前驱的时间复杂度是 O （ n ），如果希望找前驱的时间复杂度也能达到 O （1），则只能付出空间的代价，为每个结点再加一个指向前驱的指针域，结点的结构如图2-9所示。用这种结点组成的链表称为双向链表。
图2-9 双向链表结点结构
与单链表类似，双向链表通常也是用头指针标识，增加头结点同样可以简化双向链表的操作。图2-10所示是带头结点的双向链表的示意图。
图2-10 带头结点的双向链表
a）空双向链表 b）非空双向链表
从图2-10可以看到，如果已知某结点的指针为p，则其后继结点的指针是p-＞next，其前驱结点的指针是p-＞prior。
在实际应用中，还经常使用到带头结点的双向循环链表，即在双向链表的基础上，将头结点的前驱指针指向最后一个结点，同时将最后一个结点的后继指针指向头结点。读者可自行给出带头结点的双向循环链表的示意图。
2. 单链表基本操作的实现
针对图2-7所示的带头结点的单链表存储结构，其上的基本操作通常包括初始化、遍历、求长度、查找元素、插入元素、删除元素以及销毁等。各操作算法函数名中包含了“_L”以表明是链表（Link List）相关操作。
（1）初始化操作
本节为单链表提供两个初始化操作，一个用于创建带头结点的空单链表，一个用于数组中含有的 n 个元素创建带头结点的单链表。下面分别给出这两个函数的具体描述。
算法2-8 创建空的单链表
算法2-9 用数组 a 中的 n 个元素创建单链表
算法2-9采用的是头部插入法，即每次新生成的结点均插在头结点的后面。还可以采用尾部插入法来创建单链表，即每次生成的新结点均插入在链表的尾部。为了操作简单，可在链表中设计一个尾指针，让其一直指向当前单链表的最后一个结点。请读者完成课后习题“四、算法设计题”的第6题，用尾部插入法创建单链表的程序。
（2）遍历单链表
设置一个指针，从单链表第一个数据结点开始向后扫描，直至单链表结束。每扫描到一个数据结点，就将该结点数据域输出，如算法2-10所示。
算法2-10 遍历单链表
（3）求单链表长度
可仿照上述遍历算法，只需将“输出结点数据域”改为“计数”即可，如算法2-11所示。
算法2-11 求单链表长度
（4）按值查找
将待查找的值 e 与单链表中的每个结点元素依次进行比较，如果查找到具有 e 值的元素时，则返回该元素的序号；否则返回值0，表明查找失败。具体实现如算法2-12所示。
算法2-12 单链表的按值查找
上述函数在使用时有一定的局限性，只能返回查找不成功，或查找成功时元素在链表中的序号，而无法根据序号在链表中直接获取元素。可对上述函数略加修改，即返回指向查找到的元素的指针，就可访问到该元素。
（5）插入
插入操作是指将值为 e 的新结点插入到单链表第 i 个位置上。根据插入的方法，可以分为后插和前插两种，下面介绍这两种方法。
1）后插法。
如图2-11所示，设p指向单链表中某结点，s指向待插入的值为 e 的新结点，将结点s插入到结点p的后面，即为后插法。
对应图2-11中的序号，后插法的操作步骤如下：
①s-＞next=p-＞next；
②p-＞next=s；
注意：两个操作顺序不能交换。
2）前插法。
如图2-12所示，设p指向链表中某结点，s指向待插入的值为 e 的新结点，将结点s插入到结点p的前面，即为前插法。
图2-11 在结点p之后插入结点s
图2-12 在结点p之前插入结点s
与后插法不同的是，前插法首先要找到结点p的前驱结点q，然后再完成在结点q之后插入结点s。设单链表头指针为head，对应图2-12中的序号，操作步骤如下：
①q=head；
while（q-＞next！=p） //找结点p的直接前驱
q=q-＞next；
②s-＞next=q-＞next；
③q-＞next=s；
从上述分析可以看出，后插的效率比前插高，后插操作的时间复杂性为 O （1），前插操作的时间复杂度为 O （ n ）。
因此，在设计将值为 e 的新结点插入到单链表第 i 个位置的算法时，可采用后插法，即要插入在第 i 个位置转化为：插入到第 i -1个位置的后面。算法中首先需要找到第 i -1个结点的位置。算法步骤如下：
1）工作指针p初始化，累加器 j 清零。
2）查找第 i -1个结点，并将指针p指向该结点。
3）若p为空，即查找不成功，则抛出插入位置非法异常；否则，生成元素值为 e 的新结点s，并按后插法将其插入到结点p的后面。
具体实现如算法2-13所示。
算法2-13 单链表的插入
（6）删除
设q指向单链表中某结点，删除结点q的操作如图2-13所示。
图2-13 删除结点q
从图2-13可知，要实现对结点q的删除，首先要找到结点q的前驱结点p，然后完成指针的操作即可。指针的操作步骤如下：
下面给出删除第 i 个结点的算法。
从上述分析可以看出，要删除第 i 个结点，必须先找到第 i -1个结点。算法步骤如下：
1）工作指针p初始化，累加器 j 清零。
2）查找第 i -1个结点，并将指针p指向该结点。
3）若p为空或p不存在后继结点，则抛出删除位置非法异常；否则删除结点p的后一个结点。
具体实现如算法2-14所示。
算法2-14 单链表的删除
（7）单链表的销毁
单链表类中由new运算符生成的结点空间无法自动释放，因此需要有专门的函数将单链表的存储空间加以释放，具体实现如算法2-15所示。
算法2-15 单链表的销毁
