1.2.1　线性表

线性表（Linear List）是n（n≥0）个相同类型的元素a0，a1，a2，a3，…，an所构成的有限线性序列，通常表示为（a0，a1，a2，a3，…，an），其中，n为线性表的长度。ai（0≤i≤n）是线性表中第i个序号的数据元素。ai是抽象表示符号，在不同的情况下含义不同。例如，一个整数序列（7，8，9，10，11，12，34）是一个线性表，表中每一个元素ai均为整数，表长为7。

以上每个数据元素包括一个数据项，而1.1.2节中的学生成绩表数据，对于每一位学生student1、student2、student3…每个数据元素均包括多个数据项。

1.线性表的概念

简单地说，线性表就是n个数据元素的有限序列。线性表具有如下特点：存在唯一的被称为“第一个”的数据元素；存在唯一的被称为“最后一个”的数据元素；除第一个数据元素之外，线性表中的每个数据元素均只有一个前驱；除最后一个数据元素之外，线性表中的每个数据元素均只有一个后继。

在线性表中，一个元素可以由若干数据项组成，在这种情况下的数据元素称为记录，而含有大量记录的线性表又称为文件。线性表中元素的个数n定义为线性表的长度，n≥0。

同一个线性表中的元素必定具有相同特性，即属于同一数据对象，相邻数据元素之间存在序偶关系，即数据元素是“一个接一个地排列在一起”：

（a1，…，ai-1，ai，ai+1，…，an）

其中，ai-1为ai的直接前驱，ai+1为ai的直接后继，ai是第i个元素，称i为数据元素ai在线性表中的位序。

线性表是相当灵活的一种数据结构，如长度可根据需要增减，元素也可以增删。

线性表的基本操作有以下几种：

①Initiate（L）{初始化}：设定一个空的线性表。

②Length（L）{求表长}：对给定的线性表L，函数返回值为其数据元素的个数。

③Get（L，i）{取元素}：若给定的数据元素序号i满足1≤i≤Length（L），则函数返回值为给定线性表L的第i个元素ai，否则返回空元素。

④Locate（L，x）{定位}：对给定值，若线性表L中存在某个数据元素ai等于x，则函数返回索引号最小的i的值；若L中不存在等于x的数据元素，则函数返回一个特殊值（比如-1），以说明不存在的位置。

⑤Insert（L，i，x）{插入}：对给定的线性表L，若索引号i满足1≤i≤Length（L）+1，则在线性表的第i个位置上插入一个新的数据元素x，使原来表长度为n的线性表变为表长为n+1的线性表，并使函数返回值为true，否则函数返回值为false。

⑥Delete（L，i）{删除}：对给定的线性表，若索引号i满足1≤i≤Length（L），则把线性表中第i个元素ai删除，使原来表长为n的线性表变成表长为n-1的线性表，并使函数返回值为true，否则函数返回值为false。

对于线性表的其他有关操作，如线性表的合并、排序等操作，都可以通过以上基本操作来实现。

2.线性表的抽象数据类型的定义

上述是线性表抽象数据类型的定义，其中只是一些基本操作，也可以更复杂，如将两个线性表合并等。

3.线性表的顺序存储结构及其实现——顺序表

线性表的存储结构有多种类型，如顺序存储结构和链式存储结构，因此线性表可以采用使用顺序存储结构的顺序表和有序顺序表来实现，也可以采用链式存储结构的单链表、双链表和循环链表等来实现。

（1）顺序表的定义

①顺序存储结构：即把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元中的方法。

②顺序表（Sequential List）：用顺序存储结构实现的线性表简称顺序表。按数据元素的值无序或有序存放，顺序表又可分为无序顺序表和有序顺序表两种。

（2）数据元素的存储地址

设线性表中所有数据元素的类型相同，则每个数据元素所占用的存储空间大小也相同。当把线性表的数据元素存入存储空间后，称这样的一种存储空间为一个“结点”。假设表中每个结点占用c个存储单元，并设表中第一个结点a1的存储地址（简称基地址）是Loc（a1），那么结点ai的存储地址Loc（ai）可通过下式计算：

Loc（ai）=Loc（a1）+（i-1）×c　（1≤i≤n）

在顺序表中，每个结点ai的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址，因此顺序表是一种随机存取存储的结构。

（3）顺序表类型定义

①除了用数组这种顺序存储的类型存储线性表的元素外，顺序表还应该用一个变量来表示线性表的长度属性，因此用结构体类型来定义顺序表类型。

②存放线性表结点的数组空间的大小ListSize应仔细选值，使其既能满足表结点的数目动态增加的需求，又不至于浪费存储空间。

③由于C语言中数组的下标从0开始，所以若L是SeqList类型的顺序表，则线性表的开始结点a1和终端结点an分别存储在L.data[0]和L.Data[L.length-1]中。

④若L是SeqList类型的指针变量，则a1和an分别存储在L->data[0]和L->data[L->length-1]中。

（4）顺序表的特点

顺序表是用顺序存储结构实现的线性表，具有以下优点：

①存储方式简单：几乎所有的程序设计语言都支持数组，因此用一维数组表示顺序表是最简单的实现方式。数组的下标可以看作数据元素的相对地址，因此在顺序表中逻辑上相邻的数据元素，其物理位置也相邻。

②顺序表便于随机访问，访问效率高。顺序表第i个元素的地址可表示为：

Loc（ai）=Loc（a1）+（i-1）×c　（1≤i≤n）

因此，只要知道顺序表的首地址和每个数据元素所占存储单元的大小即可求出第i个数据元素的地址。

但顺序表也具有一些缺点：

①扩充不方便：顺序表一般采用数组实现，而定义数组时必须指明大小，该大小一旦确定，在程序运行过程中一般不允许修改，因此对于表中数据元素个数需要增加的情况，存储空间不易扩充。

②插入和删除操作不方便：由于顺序表一般采用数组实现，因此在顺序表中插入或删除某个数据元素时，需要移动数组中的元素，从而占用较大的存储空间和较多的运行时间，致使插入和删除效率低。

（5）顺序表上实现的基本运算

①表的初始化：

②求表长：

③取表中第i个结点：

④插入：

a.插入运算的逻辑描述：线性表的插入运算是指在表的第i（1≤i≤n+1）个位置上，插入一个新结点x，使长度为n的线性表：

（a1，…，ai-1，ai，…，an）

变成长度为n+1的线性表：

（a1，…，ai-1，x，ai，…，an）

由于向量空间大小在声明时已确定，当L-＞length≥ListSize时，表空间已满，不可再进行插入操作；当插入位置i的值为i＞n或i＜1时为非法位置，不可进行正常插入操作。

b.顺序表插入操作过程：在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n，n-1，…，i上的结点，依次后移到n+1，n，…，i+1位置上，空出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，不需要移动结点，直接将x插入表的末尾。

c.具体算法描述如下：

d.算法分析：

●　问题的规模：表的长度L->length（设值为n）是问题的规模。

●　移动结点的次数由表长n和插入位置i决定。

●　算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。当i=n+1时，移动结点次数为0，即算法在最好情况下时间复杂度是O（1）；当i=1时，移动结点次数为n，即算法在最坏情况下时间复杂度是O（n）。

4.线性表的链式存储结构及其实现——链表

（1）链式存储结构

由于顺序表存在占用连续存储空间且不易动态扩充以及插入和删除操作效率低的缺点，对于数据元素个数动态变化，需要频繁插入和删除操作的应用场合，必须考虑其他存储结构，例如链式存储结构。采用链式存储结构的线性表简称链表（Linked List）。链表的具体存储结构表示为：

①用一组任意存储单元存放线性表的数据元素（这组存储单元既可以是连续的，也可以是不连续的）。

②采用链式存储结构的线性表中，数据元素的逻辑次序和物理次序不一定相同。为了能正确表示数据元素间的逻辑关系，在存储每个数据元素（ai）值（Data）的同时，还必须存储指示其后继数据元素（ai+1）的地址（或位置）信息，称为指针（Pointer）或链（Link），这两部分组成一个结构体，称为一个“结点”，其结构如图1-3所示。

链式存储结构是最常用的存储方式之一，不仅可用来表示线性表，还可用来表示各种非线性的数据结构（如树、图等），其存储结构灵活多样，包括单链表、循环链表和双链表等，其特点是对线性表进行插入和删除运算时不需要移动数据元素，且允许表长任意扩充。

（2）单链表的结点结构

采用链式存储结构的线性表，每一个数据元素占一个结点（Node）。一个结点由两个域组成，一个域存放数据元素data，称为数据域，其数据类型由应用问题决定；另一个域存放一个指向该链表中下一个结点的指针next，称为指针域，它给出了下一个结点的开始存储地址。

图1-3中data域为存放结点值的数据域，next域为存放结点的直接后继的地址（位置）的指针域（链域）。链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起，每个结点只有一个链域的链表称为单链表。

【例1-1】一个线性表（a0，a1，a2，…，an-1）的单链表结构如图1-4所示，其中，first为指向单链表中第一个结点的指针，last为指向单链表中最后一个结点的指针。

（3）头指针head和终端结点指针域的表示

单链表中每个结点的存储地址是存放在其前驱结点的next域中的，而开始结点（a0）无前驱，为了让开始结点也具有前驱，可以另设一个结点，该结点的data域不存放值，其next域指向开始结点（a0），这个结点称为“头结点”，再设一个头指针head指向头结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。头指针名是head的链表可称为表head。终端结点无后继，故终端结点的指针域为空，即NULL，或者简记为∧，如图1-5所示。

（4）单链表类型描述

由于单链表中所有结点的存储结构都相同，当需要向线性表中新增加一个数据元素时，只需要申请一个结点的存储空间，向该结点的data域存入数据元素的值，再把该结点插入链表中即可。单链表的结点类型描述如下：

5.单链表的运算

（1）建立单链表

假设线性表中结点的数据类型是字符，逐个输入这些字符型的结点，并以换行符'\n'为输入条件结束标志符。动态地建立单链表的常用方法有如下两种：

①头插法建立单链表。

算法思路：从一个空表开始，重复读入数据，生成新结点，将读入的数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。该方法生成的链表的结点次序与输入顺序相反。具体算法实现如下：

②尾插法建立单链表。

算法思路：从一个空表开始，重复读入数据，生成新结点，将读入数据存放在新结点的数据域中，然后将新结点插入到当前链表的表尾，直到读入结束标志为止。尾插法建立链表时，头指针固定不动，故必须设立一个搜索指针，向链表右边延伸，则整个算法中应设立三个链表指针，即头指针head、搜索指针r、申请单元指针s。尾插法最先得到的是头结点，生成的链表的结点次序与输入顺序相同。具体算法实现如下：

（2）单链表的插入运算

在单链表中插入一个结点时，仅需要修改指针而不需要移动元素，如此能高效地实现插入操作。例如，要在单链表（a0，a1，a2，…，an-1）的数据ai结点之前插入一个新元素x，插入操作如图1-6所示。

要在带头结点的单链表head中第i个数据元素之前插入数据元素x，首先需要在单链表中寻找到第i-1个结点并用指针p指示，然后申请一个由指针s指示的结点空间，并置x为其数据域值，最后修改第i-1个结点的指针指向x结点，并使x结点的指针指向第i个结点，其插入过程如图1-7所示。

单链表插入算法如下：

若单链表中有n个结点，插入位置i允许的取值范围为1≤i≤n+1。当i=n+l时，即为在链尾插入一个结点，算法中用条件（p！=NULL&&j<i-1）使p指向第i-1个结点，从而使新结点插在第n个结点之后。

（3）单链表的删除运算

如果希望删除链表中第i个结点，应当先让第i-1个结点的指针域指向第i+1个结点，通过重新拉链，把第i个结点从链表中分离出来，然后再删去，如图1-8所示（注意：图中×表示该指针关系不再存在。）。

要在带头结点的单链表head中删除第i个结点，首先计数寻找第i个结点并使指针p指向其前驱第i-1个结点，再删除第i个结点并释放被删除的结点空间，其操作过程如图1-9所示。

单链表删除算法如下：

与插入算法不同的是，删除算法中用条件（p->next ！=NULL&&j<i-1）寻找第i个结点是否存在并使指针p指向其前驱，这是因为删除算法中i的取值范围为1＜i＜n。当i＞n时，由条件p->next！=NULL限制；若此处用插入算法的条件p！=NULL&j＜i-1，则会出现指针悬空的错误。

插入算法和删除算法的时间复杂度均为O（n）。这是因为链式存储结构不是随机存储结构，即不能直接读取单链表中的某个结点，而是从单链表的头结点开始一个一个地计数寻找。因此，虽然在单链表中插入或删除结点时不需要移动别的数据元素，但算法中寻找单链表的第i-1个或第i个结点的时间复杂度为O（n）。

6.循环链表

循环链表（Circular Linked List）是另一种形式的链式存储结构，是单链表的一种特殊情况，即单链表中最后一个结点的next指针不为空（NULL），而是指向了表的前端，即循环链表是一种首尾相接的链表。

（1）循环链表

①单循环链表：是另一种形式的表示线性聚集的链表，其结点结构与单链表相同，不同的是，单循环链表中表尾结点的指针域NULL改为指向表头结点或开始结点即可，如图1-10所示。

②多重链的循环链表：将表中结点链在多个环上。

（2）带头结点的单循环链表

循环链表与单链表一样，可以有表头结点，这样能够简化链表操作的实现，统一空表与非空表的运算，如图1-11所示。

注意：判断空链表的条件是head==head->next。

（3）仅设尾指针的单循环链表

用尾指针last表示的单循环链表对开始结点a0和终端结点an-1的查找时间都是O（1），而表的操作常常是在表的首尾位置上进行。因此，实际情况是多采用尾指针表示单循环链表。带尾指针的单循环链表如图1-12所示。

注意：判断空链表的条件为last==last->next。

（4）循环链表的特点

循环链表的特点是无须增加存储量，循环链表的运算与单链表类似，但在涉及链头与链尾处理时稍有不同。在循环链表中检查指针current是否达到链表的链尾时，不是判断current→next==NULL，而是判断current→next==first。

例如，在实现循环链表的插入运算时，如果是在表的最前端插入，则必须改变链尾最后一个结点的指针域的值，这就需要沿链表搜索到最后一个结点。如果给出的存储指针不放在链头而放在链尾，实现插入和删除运算就会更方便，如图1-13所示。

【例1-2】在链表上实现将两个线性表（a0，a1，…，an-1）和（b0，b1，…，bm-1）连接成一个线性表（a0，…，an-1，b0，…，bm-1）的运算。

分析：若在单链表或头指针表示的单循环表上进行此连接操作，都需要遍历第一个链表，找到结点an，然后将结点b1链到an的后面，其执行时间是O（n）。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O（1）。相应的算法如下：

注意：循环链表中没有NULL指针。

涉及遍历操作时，其终止条件不再像非循环链表那样需判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。在单链表中，从一个已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其他结点。而在单循环链表中，从任意一个结点出发都可以访问到表中所有的结点，这一优点使某些运算在单循环链表上易于实现。

7.双链表

单链表要搜索一个指定结点的前驱结点十分不易，因为结点中只有一个指示直接后继的指针域，由此从某个结点出发只能顺指针往后查其他结点。若要寻找结点的直接前驱，则需从表头指针出发。如果在一个应用问题中，经常要求指针向前驱和后继方向移动，为保证移动的时间复杂度达到最小，就必须采用双向链表表示。双向链表中每个结点的结构如图1-14所示。

其中：

①在双向链表的每个结点中应有两个链接指针作为它的数据成员，prior指示它的前驱结点，next指示它的后继结点。

②双向链表的每个结点至少有3个域。双向链表是指在前驱和后继方向都能游历（遍历）的线性链表。

双向链表通常采用带表头结点的循环链表形式。

（1）双向链表的结点结构

双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还要增加一个指向其直接前驱的指针域prior，如图1-15所示。

注意：双向链表由头指针head唯一确定。带头结点的双链表使某些运算变得方便。将头结点和尾结点链接起来，为双（向）循环链表。

带头结点的双向链表如图1-16所示。

（2）双向链表的类型描述

双链表的形式描述如下：

（3）双向链表的插入和删除操作

在双向链表中，有些操作如LENGTH（L）、GET（L，i）、LOCATE（L，x）等仅需涉及一个方向的指针，它们的算法描述和线性链表的操作相同，但在插入、删除时则有很大的不同，即在双向链表中需要同时修改两个方向的指针，如图1-17所示（注意：图中×表示该指针关系不再存在。）。

注意：与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。这两个算法的时间复杂度均为O（1）。

（4）顺序表和链表的比较

顺序表和链表各有优劣，在实际应用中究竟选用哪一种存储结构要根据具体问题的要求和性质来决定。通常有两方面的考虑，如表1-2所示。

存储密度（Storage Density）是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即：存储密度=结点数据本身所占的存储量/结点结构所占的存储总量。

8.线性表的应用：约瑟夫问题

所谓约瑟夫（Josephus）问题指的是假设有n个人围坐一圈，现从某个位置start上的人开始报数，数到m的人出圈，然后从这个人的下一个人重新开始报数，再数到m的人又出圈，依次重复下去，直到所有的人都出圈为止，求出圈的人的次序。例如，当n=8，m=4，start=1时，出圈序列为4，8，5，2，1，3，7，6；又如，当n=8，m=4，start=4时，出圈序列为7，3，8，5，4，6，2，1。

由于这n个人围坐的位置号分别为1，2，3，…，n，因此可以采用顺序存储结构（顺序表）来存储这n个位置号，当有人要出圈时，则将这个人的位置号输出并从序列中删除，如此反复上述过程，则可以把所有人的位置号输出并从序列中删除。算法的实现如下：

此算法的执行时间主要花费在求出相应位置后，把其后未出圈的位置号前移，每次最多移动n-count+1个，因此，总的移动次数不超过（n-1）+（n-2）+…+2+1=n×（n-1）/2，因此，算法的时间复杂度为O（n2）。