线性结构的基本特点是除第一个元素无直接前驱，最后一个元素无直接后继之外，其他每个数据元素都有一个前驱和后继。线性表是最基本且最常用的一种线性结构，同时也是其他数据结构的基础，尤其单链表，是贯穿整个数据结构课程的基本技术。本章将讨论线性表的逻辑结构、存储结构和相关运算，以及线性表的应用实例。本章所涉及的许多问题都具有一定的普遍性。因此，本章是整个课程的重点与核心内容，也是其他后续章节的重要基础。

2.1 线性表的定义和特点

在日常生活中，线性表的例子比比皆是。例如，26个英文字母的字母表： （A，B，C，…，Z） 是一个线性表，表中的数据元素是单个字母。在稍复杂的线性表中，一个数据元素可以包含若干个数据项。

由以上示例可以看出，它们的数据元素虽然不同，但同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序偶关系。

诸如此类由n（n≥0）个数据特性相同的元素构成的有限序列称为线性表。

线性表中元素的个数n（n≥0）定义为线性表的长度，n = 0时称为空表。

对于非空的线性表或线性结构，其特点是：

（1）存在唯一的一个被称作“第一个”的数据元素；
（2）存在唯一的一个被称作“最后一个”的数据元素；
（3）除第一个之外，结构中的每个数据元素均只有一个前驱；
（4）除最后一个之外，结构中的每个数据元素均只有一个后继。

2.2 案例引入

案例2.1：一元多项式的运算。

在数学上，一个一元多项式Pn(x)可按升幂写成：Pn(x) = p0 + p1x + p2x2 + … + pnxn

要求：实现两个一元多项式的相加、相减和相乘的运算。

实现两个多项式相关运算的前提是如何在计算机中有效地表示一元多项式，进而在此基础上设计相关运算的算法？这个问题看似很复杂，我们通过学习本章中线性表的表示及其相关运算便可以完成。

可以看出，一元多项式可由n + 1个系数唯一确定，因此，可以将一元多项式Pn(x)抽象为一个由n+1个元素组成的有序序列，可用一个线性表P来表示：

P = (p0,p1,p2,…,pn)

这时，每一项的指数i隐含在其系数pi的序号中。

假设Qm(x)是一元m次多项式，同样可用线性表Q来表示：

Q = (q0,q1,q2,…,qm)

不失一般性，设m ≤ n，则两个多项式相加的结果Rn(x) = Pn(x) + Qm(x)可用线性表R表示：

R = (p0 + q0,p1 + q1,p2 + q2,…,pm + qm,pm+1,…,pn)

在后面的叙述中将看到，对此类多项式的线性表只需要用数组表示的顺序存储结构便很容易实现上述运算。

然而，在通常的应用中，多项式的次数可能很高且变化很大，这种所谓的稀疏多项式如果采用上述表示方法，将使得线性表中出现很多零元素。下面给出稀疏多项式的例子。

案例2.2：稀疏多项式的运算。

例如，在处理形如S(x) = 1 + 3x10000 + 2x20000 的多项式时，就要用一个长度为20001的线性表来表示，而表中仅有3个非零元素，此时将会造成存储空间的很大浪费，这种对空间的浪费是应当避免的。由于线性表的元素可以包含多个数据项，由此可改变元素设定，对多项式的每一项，可用（系数，指数）唯一确定。

一般情况下的一元n次多项式可写成

Pn(x) = p1 + p2 + … + pm （2-1）

其中，pi是指数为ei的项的非零系数，且满足

0 ≤ e1 < e2 < … < em = n

若用一个长度为m且每个元素有两个数据项（系数项和指数项）的线性表

((p1, e1), (p2, e2),…,(pm, em)) （2-2）

便可唯一确定多项式Pn(x)。在最坏情况下，n + 1( = m)个系数都不为零，则比只存储每项系数的方案要多存储一倍的数据。但是，对于类似S(x)的稀疏多项式，这种表示将大大节省空间。

由上述讨论可以看出，如果多项式属于非稀疏多项式，且只对多项式进行“求值”等不改变多项式的系数和指数的运算，可采用数组表示的顺序存储结构。如果多项式属于稀疏多项式，虽然可以采用数组表示法，但这种顺序存储结构的存储空间分配不够灵活。因为事先无法确定多项式的非零项数，所以需要根据预期估计可能的最大值定义数组的大小，这种分配方式可能会带来两种问题：一种是实际非零项数比较小，浪费了大量存储空间；另一种是实际非零项式超过了最大值，存储空间不够。另外在实现多项式的相加运算时，还需要开辟一个新的数组保存结果多项式，导致算法的空间复杂度较高。改进方案是利用链式存储结构表示多项式的有序序列，这样灵活性更大些。

那么，如何利用链式存储结构表示由式（2-2）定义的多项式，并实现多项式的相关运算呢？本章2.8节将给出详细的介绍。

案例2.3：图书信息管理系统。

出版社有一些图书数据保存在一个文本文件book.txt中，为简单起见，在此假设每种图书只包括三部分信息：ISBN（书号）、书名和价格，文件中的部分数据如图2.1所示。现要求实现一个图书信息管理系统，包括以下6个具体功能。

（1）查找：根据指定的ISBN或书名查找相应图书的有关信息，并返回该图书在表中的位置序号。
（2）插入：插入一种新的图书信息。
（3）删除：删除一种图书信息。
（4）修改：根据指定的ISBN，修改该图书的价格。
（5）排序：将图书按照价格由低到高进行排序。
（6）计数：统计图书表中的图书数量。

要实现上述功能，与以上案例中的多项式一样，我们首先根据图书表的特点将其抽象成一个线性表，每本图书作为线性表中的一个元素，然后可以采用适当的存储结构来表示该线性表，在此基础上设计完成有关的功能算法。具体采取哪种存储结构，可以根据两种不同存储结构的优缺点，视实际情况而定。

可以看出，在工作和生活中的许多实际应用问题都会涉及图书信息管理中用到的这些基本操作。这些问题中都包含由n个数据特性相同的元素，即可以表示为线性表。不同的问题所涉元素的数据类型不尽相同，可以为简单数据类型（如案例2.1所示的一元多项式表示），也可以为复杂数据类型（如案例2.2所示的稀疏多项式表示和案例2.3中的图书数据），但这些问题所涉的基本操作都具有很大的相似性，如果为每个具体应用都编一个程序显然不是一种很好的方法。解决这类问题的最好方法就是从具体应用中抽象出共性的逻辑结构和基本操作（即抽象数据类型），然后采用程序设计语言实现相应的存储结构和基本操作。 本章后续章节将依次给出线性表的抽象数据类型定义、线性表的顺序和链式存储结构的表示及实现、线性表应用实例的实现。 在学完本章后，案例2.3的基本操作读者很容易就能实现。

2.3 线性表的类型定义

线性表是一个相当灵活的数据结构，其长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，而且可以进行插入和删除等操作。为不失一般性。下面给出线性表的抽象数据类型定义：

ADT List{

数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}

数据关系：R={|ai-1,ai∈D,i=2,…,n}

基本操作：

InitList(&L)
操作结果：构造一个空的线性表L。

DestroyList(&L)

初始条件：线性表L已存在。

操作结果：销毁线性表L。

ClearList(&L)

初始条件：线性表L已存在。

操作结果：将L重置为空表。

ListEmpty(L)

初始条件：线性表L已存在。

操作结果：若L为空表，则返回true，否则返回false。

ListLength(L)

初始条件：线性表L已存在。

操作结果：返回L中数据元素个数。

GetElem(L,i,&e)

初始条件：线性表L已存在，且1≤i≤ListLength(L)。

操作结果：用e返回L中第i个数据元素的值。

LocateElem(L,e)

初始条件：线性表L已存在。

操作结果：返回L中第1个值与e相同的元素在L中的位置。若这样的数据元素不存在，则返回值为0。

PriorElem(L,cur_e,&pre_e)

初始条件：线性表L已存在。

操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回其前驱，否则操作失败，pre_e无定义。

NextElem(L,cur_e,&next_e)

初始条件：线性表L已存在。

操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无定义。

ListInsert(&L,i,e)

初始条件：线性表L已存在，且1≤i≤ListLength(L)+1。

操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。

ListDelete(&L,i)

初始条件：线性表L已存在且非空，且l≤i≤ListLength(L)。

操作结果：删除L的第i个数据元素，L的长度减1。

TraverseList(L)

初始条件：线性表L已存在。

操作结果：对线性表L进行遍历，在遍历过程中对L的每个结点访问一次。

}ADT List

2.4 线性表的顺序表示和实现

2.4.1　线性表的顺序存储表示

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表（Sequential List）。其特点是，逻辑上相邻的数据元素，其物理次序也是相邻的。

假设线性表的每个元素需占用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的存储位置，通常称作线性表的起始位置或基地址，表中相邻的元素ai和ai + 1的存储位置LOC(ai)和LOC(a i+ 1)是相邻的。每一个数据元素的存储位置都和线性表的起始位置相差一个常数，这个常数和数据元素在线性表中的位序成正比（见图）。

由此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。 由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。在此，由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在C语言中可用动态分配的一维数组表示线性表。

2.4.2 顺序表中基本操作的实现

可以看出，当线性表以上述定义的顺序表表示时，某些操作很容易实现。因为表的长度是顺序表的一个“属性”，所以可以通过返回length的值实现求表长的操作，通过判断length的值是否为0判断表是否为空，这些操作算法的时间复杂度都是O(1)。下面讨论顺序表其他几个主要操作的实现。

1．初始化

顺序表的初始化操作就是构造一个空的顺序表。

算法2.1　顺序表的初始化 【算法步骤】

① 为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。
② 将表的当前长度设为0。

【算法描述】

Status InitList(SqList &L)
{//构造一个空的顺序表L
L.elem=new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
if(!L.elem) exit(OVERFLOW); //存储分配失败退出
L.length=0; //空表长度为0
return OK;
}

动态分配线性表的存储区域可以更有效地利用系统的资源，当不需要该线性表时，可以使用销毁操作及时释放占用的存储空间。

2．取值

取值操作是根据指定的位置序号i，获取顺序表中第i个数据元素的值。

由于顺序存储结构具有随机存取的特点，可以直接通过数组下标定位得到，elem[i-1]单元存储第i个数据元素。

算法2.2　顺序表的取值

【算法步骤】

① 判断指定的位置序号i值是否合理（1≤i≤L.length），若不合理，则返回ERROR。
② 若i值合理，则将第i个数据元素L.elem[i-1]赋给参数e，通过e返回第i个数据元素的传值。

【算法描述】

Status GetElem(SqList L,int i,ElemType &e) { if (iL.length) return ERROR; //判断i值是否合理，若不合理，返回ERROR e=L.elem[i-1]; //elem[i-1]单元存储第i个数据元素 return OK; }

3．查找

查找操作是根据指定的元素值e，查找顺序表中第1个与e相等的元素。若查找成功，则返回该元素在表中的位置序号；若查找失败，则返回0。

算法2.3　顺序表的查找

【算法步骤】

① 从第一个元素起，依次和e相比较，若找到与e相等的元素L.elem[i]，则查找成功，返回该元素的序号i+1。
② 若查遍整个顺序表都没有找到，则查找失败，返回0。

【算法描述】

int LocateElem(SqList L,ElemType e)

{//在顺序表L中查找值为e的数据元素，返回其序号

for(i=0;i< L.length;i++)

if(L.elem[i]==e) return i+1; //查找成功，返回序号i+1

return 0; //查找失败，返回0

}

4．插入

线性表的插入操作是指在表的第i个位置插入一个新的数据元素e，使长度为n的线性表

(a1,…,ai − 1,ai,…,an)

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

(a1,…,ai − 1,e,ai,…,an)

数据元素ai − 1和ai之间的逻辑关系发生了变化。在线性表的顺序存储结构中，由于逻辑上相邻的数据元素在物理位置上也是相邻的，因此，除非i = n + 1，否则必须移动元素才能反映这个逻辑关系的变化。

算法2.4　顺序表的插入

【算法步骤】

① 判断插入位置i是否合法（i值的合法范围是1≤i≤n + 1），若不合法则返回ERROR。
② 判断顺序表的存储空间是否已满，若满则返回ERROR。
③ 将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置（i = n + 1时无需移动）。
④ 将要插入的新元素e放入第i个位置。
⑤ 表长加1。

【算法描述】

Status ListInsert(SqList &L,int i ,ElemType e)
{//在顺序表L中第i个位置之前插入新的元素e，i值的合法范围是1≤i≤L.length+1
if((iL.length+1)) return ERROR; //i值不合法
if(L.length==MAXSIZE) return ERROR; //当前存储空间已满
for(j=L.length-1;j>=i-1;j--)
L.elem[j+1]=L.elem[j]; //插入位置及之后的元素后移
L.elem[i-1]=e; //将新元素e放入第i个位置
++L.length; //表长加1
return OK;
}

上述算法没有处理表的动态扩充，因此当表长已经达到预设的最大空间时，则不能再插入元素。

5．删除

线性表的删除操作是指将表的第i个元素删去，将长度为n的线性表

(a1,…,ai − 1,ai，ai + 1,…,an)

变成长度为n − 1的线性表

(a1,…,ai − 1,ai + 1,…,an)

数据元素ai−1、ai和ai+1之间的逻辑关系发生了变化，为了在存储结构上反映这个变化，同样需要移动元素。如图所示，为了删除第4个数据元素，必须将第5个至第8个元素都依次向前移动一个位置。

一般情况下，删除第i（1≤i≤n）个元素时需将第i + 1个至第n个元素（共n−i个元素）依次向前移动一个位置（i = n 时无需移动）。

算法2.5　顺序表的删除

【算法步骤】　

① 判断删除位置i是否合法（合法值为1≤i≤n），若不合法则返回ERROR。
② 将第i + 1个至第n个的元素依次向前移动一个位置（i = n 时无需移动）。
③ 表长减1。

【算法描述】

Status ListDelete(SqList &L,int i)
{//在顺序表L中删除第i个元素，i值的合法范围是1≤i≤L.length
if((iL.length)) return ERROR; //i值不合法
for(j=i;j<=L.length-1;j++)
L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移
--L.length; //表长减1
return OK;
}

顺序表可以随机存取表中任一元素，其存储位置可用一个简单、直观的公式来表示。然而，从另一方面来看，这个特点也造成了这种存储结构的缺点：在做插入或删除操作时，需移动大量元素。另外由于数组有长度相对固定的静态特性，当表中数据元素个数较多且变化较大时，操作过程相对复杂，必然导致存储空间的浪费。所有这些问题，都可以通过线性表的另一种表示方法—链式存储结构来解决。

2.5 线性表的链式表示和实现

2.5.1　单链表的定义和表示

线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素ai与其直接后继数据元素ai + 1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素ai的存储映像，称为结点（node）。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。n个结点（ai（1≤i≤n）的存储映像）链结成一个链表，即为线性表(a1, a2,…, an) 的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。

根据链表结点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等。其中单链表、循环链表和双向链表用于实现线性表的链式存储结构，其他形式多用于实现树和图等非线性结构。 本节先讨论单链表，例如，图所示为线性表的单链表存储结构，整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点（即第一个数据元素的存储映像，也称首元结点）的存储位置。同时，由于最后一个数据元素没有直接后继，则单链表中最后一个结点的指针为空（NULL）。

用单链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。换句话说，指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，由此，这种存储结构为非顺序映像或链式映像。

通常将链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针。上图所示的单链表可画成下图所示的形式，这是因为在使用链表时，关心的只是它所表示的线性表中数据元素之间的逻辑顺序，而不是每个数据元素在存储器中的实际位置。

由上述可见，单链表可由头指针唯一确定，在C语言中可用“结构指针”来描述：

//- - - - - 单链表的存储结构- - - - -
typedef struct LNode
{
ElemType data; //结点的数据域
struct LNode next; //结点的指针域
}LNode,LinkList; //LinkList为指向结构体LNode的指针类型

一般情况下，为了处理方便，在单链表的第一个结点之前附设一个结点，称之为头结点。单链表增加头结点后如图。

链表增加头结点的作用如下。

（1）便于首元结点的处理。增加了头结点后，首元结点的地址保存在头结点(即其“前驱”结点)的指针域中，则对链表的第一个数据元素的操作与其他数据元素相同，无需进行特殊处理。
（2）便于空表和非空表的统一处理。当链表不设头结点时，假设L为单链表的头指针，它应该指向首元结点，则当单链表为长度n为0的空表时， L指针为空（判定空表的条件可记为：L = = NULL）。

增加头结点后，无论链表是否为空，头指针都是指向头结点的非空指针。

在顺序表中，由于逻辑上相邻的两个元素在物理位置上紧邻，则每个元素的存储位置都可从线性表的起始位置计算得到。而在单链表中，各个元素的存储位置都是随意的。然而，每个元素的存储位置都包含在其直接前驱结点的信息之中。假设p是指向单链表中第i个数据元素（结点ai，即数据域为ai的结点）的指针，则p −>next是指向第i + 1个数据元素（结点ai + 1）的指针。换句话说，若p −>data = ai，则p −>next−>data = ai+1。由此，单链表是非随机存取的存储结构，要取得第i个数据元素必须从头指针出发顺链进行寻找，也称为顺序存取的存取结构。因此，其基本操作的实现不同于顺序表。

2.5.2　单链表基本操作的实现

1．初始化

单链表的初始化操作就是构造一个如图2.10（b）所示的空表。

算法2.6　单链表的初始化

【算法步骤】

① 生成新结点作为头结点，用头指针L指向头结点。
② 头结点的指针域置空。

【算法描述】

Status InitList(LinkList &L)
{//构造一个空的单链表L
L=new LNode; //生成新结点作为头结点，用头指针L指向头结点
L->next=NULL;　　　　　　　　　 //头结点的指针域置空
return OK;
}

2．取值

和顺序表不同，链表中逻辑相邻的结点并没有存储在物理相邻的单元中，这样，根据给定的结点位置序号i，在链表中获取该结点的值不能像顺序表那样随机访问，而只能从链表的首元结点出发，顺着链域next逐个结点向下访问。

算法2.7　单链表的取值

【算法步骤】

① 用指针p指向首元结点，用j做计数器初值赋为1。
② 从首元结点开始依次顺着链域next向下访问，只要指向当前结点的指针p不为空（NULL），并且没有到达序号为i的结点，则循环执行以下操作：

• p指向下一个结点；

• 计数器j相应加1。 ③ 退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i值不合法（i大于表长n或i小于等于0），取值失败返回ERROR；否则取值成功，此时j = i时，p所指的结点就是要找的第i个结点，用参数e保存当前结点的数据域，返回OK。

【算法描述】

Status GetElem(LinkList L,int i,ElemType &e)

{/ /在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值

p=L->next;j=1; / /初始化，p指向首元结点，计数器j初值赋为1

while(p&&j<i) / /顺链域向后扫描，直到p为空或p指向第i个元素

{

p=p->next; //p指向下一个结点

++j; //计数器j相应加1
}

if(!p||j>i)return ERROR; / /i值不合法i＞n或i≤0
e=p->data; //取第i个结点的数据域

return OK;
}

3．查找

链表中按值查找的过程和顺序表类似，从链表的首元结点出发，依次将结点值和给定值e进行比较，返回查找结果。

算法2.8　单链表的按值查找

【算法步骤】

① 用指针p指向首元结点。
② 从首元结点开始依次顺着链域next向下查找，只要指向当前结点的指针p不为空，并且p所指结点的数据域不等于给定值e，则循环执行以下操作：p指向下一个结点。
③ 返回p。若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL。

【算法描述】

LNode *LocateElem(LinkList L，ElemType e)
{//在带头结点的单链表L中查找值为e的元素
p=L->next; //初始化，p指向首元结点
while(p && p->data!=e) //顺链域向后扫描，直到p为空或p所指结点的数据域等于e
p=p->next; //p指向下一个结点
return p; //查找成功返回值为e的结点地址p，查找失败p为NULL
}

【算法分析】 该算法的执行时间与待查找的值e相关，其平均时间复杂度分析类似于算法2.7，也为O(n)。

4．插入

假设要在单链表的两个数据元素a和b之间插入一个数据元素x，已知p为其单链表存储结构中指向结点a的指针，如图2.11（a）所示。

为插入数据元素x，首先要生成一个数据域为x的结点，然后插入到单链表中。根据插入操作的逻辑定义，还需要修改结点a中的指针域，令其指向结点x，而结点x中的指针域应指向结点b，从而实现3个元素a、b和x之间逻辑关系的变化。假设s为指向结点x的指针，则上述指针修改用语句描述即为

s->next = p->next; p->next = s;

算法2.9　单链表的插入

【算法步骤】

将值为e的新结点插入到表的第i个结点的位置上，即插入到结点ai-1与ai之间，具体插入过程如图2.12所示，图中对应的5个步骤说明如下。

① 查找结点ai − 1并由指针p指向该结点。

② 生成一个新结点*s。

③ 将新结点*s的数据域置为e。

④ 将新结点*s的指针域指向结点ai。

⑤ 将结点p的指针域指向新结点s。

【算法描述】

Status ListInsert(LinkList &L,int i,ElemType e)

{//在带头结点的单链表L中第i个位置插入值为e的新结点

p=L;j=0;

while(p && (j<i−1))

{p=p->next;++j;} //查找第i−1个结点，p指向该结点

if(!p||j>i−1) return ERROR; //i＞n+1或者i＜1

s=new LNode; //生成新结点*s

s->data=e; //将结点*s的数据域置为e

s->next=p->next; //将结点*s的指针域指向结点ai

p->next=s; //将结点p的指针域指向结点s

return OK;

}

单链表的插入操作虽然不需要像顺序表的插入操作那样需要移动元素，但平均时间复杂度仍为O(n)。这是因为，为了在第i个结点之前插入一个新结点，必须首先找到第i − 1个结点，其时间复杂度与算法2.7相同，为O(n)。

5．删除

要删除单链表中指定位置的元素，同插入元素一样，首先应该找到该位置的前驱结点。如图所示，在单链表中删除元素b时，应该首先找到其前驱结点a。为了在单链表中实现元素a、b和c之间逻辑关系的变化，仅需修改结点a中的指针域即可。假设p为指向结点a的指针，则修改指针的语句为

p->next = p->next->next;

但在删除结点b时，除了修改结点a的指针域外，还要释放结点b所占的空间，所以在修改指针前，应该引入另一指针q，临时保存结点b的地址以备释放。

算法2.10　单链表的删除

【算法步骤】

删除单链表的第i个结点ai的具体过程如图2.14所示，图中的对应的4个步骤说明如下。

① 查找结点ai − 1并由指针p指向该结点。
② 临时保存待删除结点ai的地址在q中，以备释放。
③ 将结点*p的指针域指向ai的直接后继结点。
④ 释放结点ai的空间。

【算法描述】

Status ListDelete(LinkList &L,int i)
{//在带头结点的单链表L中，删除第i个元素
p=L;j=0;
while((p->next) && (j<i-1)) //查找第i−1个结点，p指向该结点

{p=p->next; ++j;}
if(!(p->next)||(j>i-1)) return ERROR; //当i>n或inext; //临时保存被删结点的地址以备释放
p->next=q->next; //改变删除结点前驱结点的指针域
delete q; //释放删除结点的空间
return OK;
}

删除算法中的循环条件(p->next&&j<i-1)和插入算法中的循环条件(p&&(j<i−1))是有所区别的。因为插入操作中合法的插入位置有n+1个，而删除操作中合法的删除位置只有n个，如果使用与插入操作相同的循环条件，则会出现引用空指针的情况，使删除操作失败。

类似于插入算法，删除算法时间复杂度亦为O(n)。

6．创建单链表

算法2.6的初始化操作是创建一个只有一个头结点的空链表，而上面链表的其他算法都是假定链表已经存在多个结点。那么，如何建立一个包括若干个结点的链表呢？链表和顺序表不同，它是一种动态结构。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是由系统按需即时生成。因此，建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从空表的初始状态起，依次建立各元素结点，并逐个插入链表。

根据结点插入位置的不同，链表的创建方法可分为前插法和后插法。

（1）前插法
前插法是通过将新结点逐个插入链表的头部（头结点之后）来创建链表，每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后。

算法2.11　前插法创建单链表

【算法步骤】

① 创建一个只有头结点的空链表。
② 根据待创建链表包括的元素个数n，循环n次执行以下操作：

• 生成一个新结点*p；

• 输入元素值赋给新结点*p的数据域；

• 将新结点*p插入到头结点之后。

图所示为线性表（a,b,c,d,e）前插法的创建过程，因为每次插入在链表的头部，所以应该逆位序输入数据，依次输入e、d、c、b、a，输入顺序和线性表中的逻辑顺序是相反的。

【算法描述】

void CreateList_H(LinkList &L,int n)
{//逆位序输入n个元素的值，建立带表头结点的单链表L
L=new LNode;
L->next=NULL; //先建立一个带头结点的空链表
for(i=0;i>p->data; //输入元素值赋给新结点p的数据域
p->next=L->next;L->next=p; //将新结点p插入到头结点之后
}
}

显然，算法2.11的时间复杂度为O(n)。

（2）后插法
后插法是通过将新结点逐个插入到链表的尾部来创建链表。同前插法一样，每次申请一个新结点，读入相应的数据元素值。不同的是，为了使新结点能够插入到表尾，需要增加一个尾指针r指向链表的尾结点。

算法2.12　后插法创建单链表

【算法步骤】

① 创建一个只有头结点的空链表。

② 尾指针r初始化，指向头结点。

③ 根据创建链表包括的元素个数n，循环n次执行以下操作：

• 生成一个新结点*p；
• 输入元素值赋给新结点*p的数据域；
• 将新结点p插入到尾结点r之后；
• 尾指针r指向新的尾结点*p。

图所示为线性表（a,b,c,d,e）后插法的创建过程，读入数据的顺序和线性表中的逻辑顺序是相同的。

【算法描述】

void CreateList_R(LinkList &L,int n)
{//正位序输入n个元素的值，建立带表头结点的单链表L
L=new LNode;
L->next=NULL; //先建立一个带头结点的空链表
r=L; //尾指针r指向头结点
for(i=0;i>p->data; //输入元素值赋给新结点p的数据域
p->next=NULL; r->next=p; //将新结点p插入尾结点r之后
r=p; //r指向新的尾结点p
}
}

算法2.12的时间复杂度亦为O(n)。

2.5.3　循环链表

循环链表（Circular Linked List）是另一种形式的链式存储结构。其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点，图所示为单链的循环链表。类似地，还可以有多重链的循环链表。

循环单链表的操作和单链表基本一致，差别仅在于：当链表遍历时，判别当前指针p是否指向表尾结点的终止条件不同。在单链表中，判别条件为p!=NULL或p->next!=NULL，而循环单链表的判别条件为p!=L或p->next!=L。

在某些情况下，若在循环链表中设立尾指针而不设头指针，可使一些操作简化。例如，将两个线性表合并成一个表时，仅需将第一个表的尾指针指向第二个表的第一个结点，第二个表的尾指针指向第一个表的头结点，然后释放第二个表的头结点。当线性表循环链表作存储结构时，这个操作仅需改变两个指针值即可，主要语句段如下：

p = B->next->next;

B->next = A->next;

A->next = p;

上述操作的时间复杂度为O(1)，合并后的表如图所示。

2.5.4　双向链表

以上讨论的链式存储结构的结点中只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针向后寻查其他结点。若要寻查结点的直接前驱，则必须从表头指针出发。换句话说，在单链表中，查找直接后继结点的执行时间为O(1)，而查找直接前驱的执行时间为O(n)。为克服单链表这种单向性的缺点，可利用双向链表（Double Linked List）。

顾名思义，在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱，结点结构如图2.19（a）所示，在C语言中可描述如下：

//- - - - - 双向链表的存储结构- - - - -
typedef struct DuLNode
{
ElemType data; //数据域
struct DuLNode *prior; //直接前驱

struct DuLNode next; //直接后继
}DuLNode,DuLinkList;

和单链的循环表类似，双向链表也可以有循环表，链表中存有两个环，只有一个表头结点的空表。

在双向链表中，若d为指向表中某一结点的指针（即d为DuLinkList型变量），则显然有

d->next->prior = d->prior->next = d

这个表示方式恰当地反映了这种结构的特性。

在双向链表中，有些操作（如ListLength、GetElem和LocateElem等）仅需涉及一个方向的指针，则它们的算法描述和线性链表的操作相同，但在插入、删除时有很大的不同，在双向链表中需同时修改两个方向上的指针，下图分别显示了插入和删除结点时指针修改的情况。在插入结点时需要修改四个指针，在删除结点时需要修改两个指针。它们的实现分别如算法2.13和算法2.14所示，两者的时间复杂度均为O(n)。

算法2.13　双向链表的插入

【算法描述】

Status ListInsert_DuL(DuLinkList &L,int i,ElemType e)
{//在带头结点的双向链表L中第i个位置之前插入元素e
if(!(p=GetElem_DuL(L,i))) //在L中确定第i个元素的位置指针p
return ERROR; //p为NULL时，第i个元素不存在
s=new DuLNode; //生成新结点s
s->data=e; //将结点s数据域置为e
s->prior=p->prior; //将结点*s插入L中，此步对应图2.20①
p->prior->next=s; //对应图2.20②
s->next=p; //对应图2.20③
p->prior=s; //对应图2.20④
return OK;
}

算法2.14　双向链表的删除

【算法描述】

Status ListDelete_DuL(DuLinkList &L,int i)
{//删除带头结点的双向链表L中的第i个元素
if(!(p=GetElem_DuL(L,i))) //在L中确定第i个元素的位置指针p
return ERROR; //p为NULL时，第i个元素不存在
p->prior->next=p->next; //修改被删结点的前驱结点的后继指针，对应图2.21①
p->next->prior=p->prior; //修改被删结点的后继结点的前驱指针，对应图2.21②
delete p; //释放被删结点的空间
return OK;
}

2.6 顺序表和链表的比较

前面两节介绍了线性表的两种存储结构：顺序表和链表。在实际应用中，不能笼统地说哪种存储结构更好，由于它们各有优缺点，选用哪种存储结构，则应根据具体问题作具体分析，通常从空间性能和时间性能两个方面作比较分析。

2.6.1　空间性能的比较

（1）存储空间的分配
顺序表的存储空间必须预先分配，元素个数扩充受一定限制，易造成存储空间浪费或空间溢出现象；而链表不需要为其预先分配空间，只要内存空间允许，链表中的元素个数就没有限制。
基于此，当线性表的长度变化较大，难以预估存储规模时，宜采用链表作为存储结构。

（2）存储密度的大小
链表的每个结点除了设置数据域用来存储数据元素外，还要额外设置指针域，用来存储指示元素之间逻辑关系的指针，从存储密度上来讲，这是不经济的。所谓存储密度是指数据元素本身所占用的存储量和整个结点结构所占用的存储量之比，即

存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1，而链表的存储密度小于1。如果每个元素数据域占据的空间较小，则指针的结构性开销就占用了整个结点的大部分空间，这样存储密度较小。例如，若单链表的结点数据均为整数，指针所占用的空间和整型量相同，则单链表的存储密度为0.5。因此，如果不考虑顺序表中的空闲区，则顺序表的存储空间利用率为100%，而单链表的存储空间利用率仅为50%。

基于此，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。

2.6.2　时间性能的比较

（1）存取元素的效率
顺序表是由数组实现的，它是一种随机存取结构，指定任意一个位置序号i，都可以在O(1)时间内直接存取该位置上的元素，即取值操作的效率高；而链表是一种顺序存取结构，按位置访问链表中第i个元素时，只能从表头开始依次向后遍历链表，直到找到第i个位置上的元素，时间复杂度为O(n)，即取值操作的效率低。
基于此，若线性表的主要操作是和元素位置紧密相关的这类取值操作，很少做插入或删除时，宜采用顺序表作为存储结构。

（2）插入和删除操作的效率
对于链表，在确定插入或删除的位置后，插入或删除操作无需移动数据，只需要修改指针，时间复杂度为O(1)。而对于顺序表，进行插入或删除时，平均要移动表中近一半的结点，时间复杂度为O(n)。尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。

基于此，对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构。

2.7 线性表的应用

2.7.1　线性表的合并

1．顺序有序表的合并

算法2.16　顺序有序表的合并

【算法步骤】

① 创建一个表长为m+n的空表LC。
② 指针pc初始化，指向LC的第一个元素。
③ 指针pa和pb初始化，分别指向LA和LB的第一个元素。
④ 当指针pa和pb均未到达相应表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中“摘取”元素值较小的结点插入到LC的最后。
⑤ 如果pb已到达LB的表尾，依次将LA的剩余元素插入LC的最后。
⑥ 如果pa已到达LA的表尾，依次将LB的剩余元素插入LC的最后。

【算法描述】

void MergeList_Sq(SqList LA,SqList LB,SqList &LC)
{//已知顺序有序表LA和LB的元素按值非递减排列
//归并LA和LB得到新的顺序有序表LC，LC的元素也按值非递减排列
LC.length=LA.length+LB.length; //新表长度为待合并两表的长度之和
LC.elem=new ElemType[LC.length]; //为合并后的新表分配一个数组空间
pc=LC.elem; //指针pc指向新表的第一个元素
pa=LA.elem; pb=LB.elem; //指针pa和pb的初值分别指向两个表的第一个元素
pa_last=LA.elem+LA.length-1; //指针pa_last指向LA的最后一个元素
pb_last=LB.elem+LB.length-1; //指针pb_last指向LB的最后一个元素
while((pa<=pa_last)&&(pb<=pb_last)) //LA和LB均未到达表尾
{
if(pa<=pb) pc++=pa++; //依次“摘取”两表中值较小的结点插入到LC的最后
else pc++=pb++;
}
while(pa<=pa_last) pc++=pa++; //LB已到达表尾，依次将LA的剩余元素插入LC的最后
while(pb<=pb_last) pc++=pb++; //LA已到达表尾，依次将LB的剩余元素插入LC的最后
}

若对算法2.16中第一个循环语句的循环体做如下修改：分出元素比较的第三种情况，当pa ==pb时，只将两者中之一插入LC，则该算法完成的操作和算法2.15相同，但时间复杂度却不同。在算法2.16中，由于LA和LB中元素依值非递减，则对LB中的每个元素，不需要在LA中从表头至表尾进行全程搜索。如果两个表长分别记为m和n，则算法2.16循环最多执行的总次数为m + n。所以算法的时间复杂度为O(m + n)。 此算法在归并时，需要开辟新的辅助空间，所以空间复杂度也为O(m + n)，空间复杂度较高。利用链表来实现上述归并时，不需要开辟新的存储空间，可以使空间复杂度达到最低。

2．链式有序表的合并

假设头指针为LA和LB的单链表分别为线性表LA和LB的存储结构，现要归并LA和LB得到单链表LC。因为链表结点之间的关系是通过指针指向建立起来的，所以用链表进行合并不需要另外开辟存储空间，可以直接利用原来两个表的存储空间，合并过程中只需把LA和LB两个表中的结点重新进行链接即可。

算法2.17　链式有序表的合并

【算法步骤】

① 指针pa和pb初始化，分别指向LA和LB的第一个结点。
② LC的结点取值为LA的头结点。
③ 指针pc初始化，指向LC的头结点。
④ 当指针pa和pb均未到达相应表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中“摘取”元素值较小的结点插入到LC的最后。
⑤ 将非空表的剩余段插入到pc所指结点之后。
⑥ 释放LB的头结点。

【算法描述】

void MergeList_L(LinkList &LA,LinkList &LB,LinkList &LC)
{//已知单链表LA和LB的元素按值非递减排列
//归并LA和LB得到新的单链表LC，LC的元素也按值非递减排列
pa=LA->next;pb=LB->next; //pa和pb的初值分别指向两个表的第一个结点
LC=LA; //用LA的头结点作为LC的头结点
pc=LC; //pc的初值指向LC的头结点
while(pa&&pb)
{//LA和LB均未到达表尾，依次“摘取”两表中值较小的结点插入到LC的最后
if(pa->data<=pb->data) //“摘取”pa所指结点
{
pc->next=pa; //将pa所指结点链接到pc所指结点之后
pc=pa; //pc指向pa
pa=pa->next; //pa指向下一结点
}
else //“摘取”pb所指结点
{
pc->next=pb; //将pb所指结点链接到pc所指结点之后
pc=pb; //pc指向pb
pb=pb->next; //pb指向下一结点
}
} //while
pc->next=pa?pa:pb; //将非空表的剩余段插入到pc所指结点之后
delete LB; //释放LB的头结点
}

可以看出，算法2.17的时间复杂度和算法2.16相同，但空间复杂度不同。在归并两个链表为一个链表时，不需要另建新表的结点空间，而只需将原来两个链表中结点之间的关系解除，重新按元素值非递减的关系将所有结点链接成一个链表即可，所以空间复杂度为O(1)。

2.8 案例分析与实现

案例2.1：一元多项式的运算。

【案例分析】

由2.2节的讨论我们已知，一元多项式可以抽象成一个线性表。在计算机中，我们可以采用数组来表示一元多项式的线性表。 利用数组p表示：数组中每个分量p[i]表示多项式每项的系数pi，数组分量的下标i即对应每项的指数。数组中非零的分量个数即为多项式的项数。

例如，多项式P(x) = 10 + 5x − 4x2 + 3x3 + 2x4 可以用表2.1所示的数组表示。

指数（下标i）	0	1	2	3	4
系数p[i]	10	5	-4	3	2

显然，利用上述方法表示一元多项式，多项式相加的算法很容易实现，只要把两个数组对应的分量项相加就可以了。

案例2.2：稀疏多项式的运算。

【案例分析】

由2.2节的讨论我们已知，稀疏多项式也可以抽象成一个线性表。结合2.7节介绍的两个有序表的归并方法，可以看出，稀疏多项式的相加过程和归并两个有序表的过程极其类似，不同之处仅在于，后者在比较数据元素时只出现两种情况（小于等于、大于），而多项式的相加过程在比较两个多项式指数时要考虑三种情况（等于、小于、大于）。因此，多项式相加的过程可以根据算法2.16和算法2.17改进而成。

和顺序存储结构相比，利用链式存储结构更加灵活，更适合表示一般的多项式，合并过程的空间复杂度为O(1)，所以较为常用。本节将给出如何利用单链表的基本操作来实现多项式的相加运算。

例如，图所示两个链表分别表示多项式A(x) = 7 + 3x + 9x8 + 5x17和多项式B(x) = 8x + 22x7 − 9x8。从图中可见，每个结点表示多项式中的一项。

如何实现用这种单链表表示的多项式的加法运算呢？

根据多项式相加的运算规则：对于两个多项式中所有指数相同的项，对应系数相加，若其和不为零，则作为“和多项式”中的一项插入到“和多项式”链表中去；对于两个多项式中指数不相同的项，则将指数值较小的项插入到“和多项式”链表中去。“和多项式”链表中的结点无需生成，而应该从两个多项式的链表中摘取。

【案例实现】

用链表表示多项式时，每个链表结点存储多项式中的一个非零项，包括系数（coef）和指数（expn）两个数据域以及一个指针域（next）。对应的数据结构定义为：

typedef struct PNode
{
float coef; //系数
int expn; //指数
struct PNode next; //指针域
}PNode,Polynomial;

一个多项式可以表示成由这些结点链接起来的单链表，要实现多项式的相加运算，首先需要创建多项式链表。

1．多项式的创建

多项式的创建方法类似于链表的创建方法，区别在于多项式链表是一个有序表，每项的位置要经过比较才能确定。首先初始化一个空链表用来表示多项式，然后逐个输入各项，通过比较，找到第一个大于该输入项指数的项，将输入项插到此项的前面，这样即可保证多项式链表的有序性。

算法2.18　多项式的创建

【算法步骤】

① 创建一个只有头结点的空链表。
② 根据多项式的项的个数n，循环n次执行以下操作：

• 生成一个新结点*s；
• 输入多项式当前项的系数和指数赋给新结点*s的数据域；
• 设置一前驱指针pre，用于指向待找到的第一个大于输入项指数的结点的前驱，pre初值指向头结点；
• 指针q初始化，指向首元结点；
• 循链向下逐个比较链表中当前结点与输入项指数，找到第一个大于输入项指数的结点*q；
• 将输入项结点s插入到结点q之前。

【算法描述】

void CreatePolyn(Polynomial &P,int n)
{//输入m项的系数和指数，建立表示多项式的有序链表P
P=new PNode;
P->next=NULL; //先建立一个带头结点的单链表
for(i=1;i<=n;++i) //依次输入n个非零项
{
s=new PNode; //生成新结点
cin>>s->coef>>s->expn; //输入系数和指数
pre=P; //pre用于保存q的前驱，初值为头结点
q=P->next; //q初始化，指向首元结点
while(q&&q->expn< s->expn) //通过比较指数找到第一个大于输入项指数的项*q
{
pre=q;
q=q->next;
} //while
s->next=q; //将输入项s插入到q和其前驱结点pre之间
pre->next=s;
} //for
}

【算法分析】

创建一个项数为n的有序多项式链表，需要执行n次循环逐个输入各项，而每次循环又都需要从前向后比较输入项与各项的指数。在最坏情况下，第n次循环需要作n次比较，因此，时间复杂度为O(n2)。

2．多项式的相加

创建两个多项式链表后，便可以进行多项式的加法运算了。假设头指针为Pa和Pb的单链表分别为多项式A和B的存储结构，指针p1和p2分别指向A和B中当前进行比较的某个结点，则逐一比较两个结点中的指数项，对于指数相同的项，对应系数相加，若其和不为零，则将插入到“和多项式”链表中去；对于指数不相同的项，则通过比较将指数值较小的项插入到“和多项式”链表中去。

算法2.19　多项式的相加

【算法步骤】

① 指针p1和p2初始化，分别指向Pa和Pb的首元结点。
② p3指向和多项式的当前结点，初值为Pa的头结点。
③ 当指针p1和p2均未到达相应表尾时，则循环比较p1和p2所指结点对应的指数值（p1->expn与p2->expn），有下列3种情况：

• 当p1->expn等于p2->expn时，则将两个结点中的系数相加，若和不为零，则修改p1所指结点的系数值，同时删除p2所指结点，若和为零，则删除p1和p2所指结点；
• 当p1->expn小于p2->expn时，则应摘取p1所指结点插入到“和多项式”链表中去；
• 当p1->expn大于p2->expn时，则应摘取p2所指结点插入到“和多项式”链表中去。

④ 将非空多项式的剩余段插入到p3所指结点之后。
⑤ 释放Pb的头结点。

【算法描述】

void AddPolyn(Polynomial &Pa,Polynomial &Pb)
{//多项式加法：Pa=Pa+Pb，利用两个多项式的结点构成“和多项式”
p1=Pa->next; p2=Pb->next; //p1和p2初值分别指向Pa和Pb的首元结点
p3=Pa; //p3指向和多项式的当前结点，初值为Pa
while(p1&&p2) //p1和p2均非空
{
if(p1->expn==p2->expn) //指数相等
{
sum=p1->coef+p2->coef; //sum保存两项的系数和
if(sum!=0) //系数和不为0
{
p1->coef=sum; //修改Pa当前结点的系数值为两项系数的和
p3->next=p1; p3=p1; //将修改后的Pa当前结点链在p3之后，p3指向p1
p1=p1->next; //p1指向后一项
r=p2; p2=p2->next; delete r; //删除Pb当前结点，p2指向后一项
}
else //系数和为0
{
r=p1; p1=p1->next; delete r; //删除Pa当前结点，p1指向后一项
r=p2; p2=p2->next; delete r; //删除Pb当前结点，p2指向后一项
}
}
else if(p1->expnexpn) //Pa当前结点的指数值小
{
p3->next=p1; //将p1链在p3之后
p3=p1; //p3指向p1
p1=p1->next; //p1指向后一项
}
else //Pb当前结点的指数值小
{
p3->next=p2; //将p2链在p3之后
p3=p2; //p3指向p2
p2=p2->next; //p2指向后一项
}
} //while
p3->next=p1?p1:p2; //插入非空多项式的剩余段
delete Pb; //释放Pb的头结点
}

【算法分析】

假设两个多项式的项数分别为m和n，则同算法2.17一样，该算法的时间复杂度为O(m + n)，空间复杂度为O(1)。

对于两个一元多项式减法和乘法的运算，都可以利用多项式加法的算法来实现。减法运算比较简单，只需要先对要减的多项式的每项系数进行取反，然后再调用加法运算AddPolyn即可。多项式的乘法运算可以分解为一系列的加法运算。

其中，每一项都是一个一元多项式。

多项式相加的例子说明，对于一些有规律的数学运算，借助链表实现是一种解决问题的途径。

案例2.3：图书信息管理系统。

【案例分析】

把图书表抽象成一个线性表，每本图书（包括ISBN、书名、定价）作为线性表中的一个元素。在图书信息管理系统中要求实现查找、插入、删除、修改、排序和计数总计6个功能，具体分析如下。

（1）对于查找、插入、删除这3个功能的算法，本章已分别给出了线性表利用顺序存储结构和链式存储结构表示时相应的算法描述。
（2）对于修改功能，可以通过调用查找算法，找到满足条件的图书进行修改即可。
（3）对于排序功能，如果在没有时间复杂度限制的情况下，可以采用读者熟悉的冒泡排序来完成；如果图书数目较多，对排序算法的时间效率要求较高，在学完第8章的内部排序算法后，可以选取一种较高效的排序算法来实现，例如，快速排序。
（4）对于计数功能，如果采取顺序存储结构，线性表的长度是它的属性，可以直接通过返回length的值实现图书个数的统计功能，时间复杂度是O(1)；如果采取链式存储结构，则需要通过从首元结点开始，附设一个计数器进行计数，一直“数”到最后一个结点，时间复杂度是O(n)。

在实现图书信息管理系统时，具体采取哪种存储结构，可以根据实际情况而定。如果图书数据较多，需要频繁地进行插入和删除操作，则宜采取链表表示；反之，如果图书数据个数变化不大，很少进行插入和删除操作，则宜采取顺序表表示。 此案例中所涉及的算法比较基础，但非常重要，读者可以分别采用顺序表和链表实现此案例的相应功能，作为本章内容的实验题目来完成。

2.9 小结

线性表是整个数据结构课程的重要基础，本章主要内容如下。

（1）线性表的逻辑结构特性是指数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链表）。
（2）对于顺序表，元素存储的相邻位置反映出其逻辑上的线性关系，可借助数组来表示。给定数组的下标，便可以存取相应的元素，可称为随机存取结构。而对于链表，是依靠指针来反映其线性逻辑关系的，链表结点的存取都要从头指针开始，顺链而行，所以不属于随机存取结构，可称之为顺序存取结构。不同的特点使得顺序表和链表有不同的适用情况，表中分别从空间、时间和适用情况3方面对二者进行了比较。

（3）对于链表，除了常用的单链表外，在本章还讨论了两种不同形式的链表，即循环链表和双向链表，它们有不同的应用场合。下表对三者的几项有差别的基本操作进行了比较。

学习完本章后，应熟练掌握顺序表和链表的查找、插入和删除算法、链表的创建算法，并能够设计出线性表应用的常用算法，比如线性表的合并等。要求能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合，明确它们各自的优缺点。