一、什么是线性表？

线性表是一种最常用且最简单的数据结构，它是由零个或多个数据元素构成的有限序列。线性表中所存储元素的具体含义，在不同的情况下可以不同，它可以是一个数，也可以是字符串，甚至是更复杂的信息。

例如，七大星系

｛海王星，天王星，土星，……，水星｝

是一个线性表，表中的数据元素是字符串。又如，七大星系距地球的估算距离也可以用顺序表的形式给出（单位：光年）

｛4496，2870，1427，……，57.9｝

表中的数据元素是实数。

线性表也可以存储比较复杂的数据元素，一个数据元素可以由若干个数据项构成，在这种情况下，数据元素被称为记录。

例如，图书馆的书目信息就是一个顺序表，表中的元素就是一条记录。记录由索引号、图书名称、作者、出版社等数据项构成。

表 1-2图书馆书目信息表

线性表逻辑结构

前面的三个例子都是n个数据元素的有限序列（a1，a2，…，an），也称为线性表，它们具有共同的特点：

（1）每个线性表的数据元素类型可以不同，但同一线性表的元素必定具有相同数据类型；

（2）元素之间是相邻关系，即第i-1个元素领先于第i个元素，第i个元素领先于第i+1个元素；

（3）第i-1个元素称为第i个元素的直接前驱元素，第i+1个元素称为第i个元素的直接后继元素；

（4）元素的个数为线性表的长度，没有元素的线性表为空表。

图1描述了线性表的逻辑结构。

图 1线性表逻辑结构

线性表顺序存储结构

在计算机内，可以用不同的方式来存储线性表，其中较为简单和常用的方式是用一组地址连续的存储单元依次存储线性表中的数据元素。

假设表中一个数据元素占k个存储单元，长度为n，表第一个元素的地址为LOC（a），则第二个元素的地址为LOC（a+k），第i个元素的地址为LOC（a+(i-1)*k）。LOC（）函数为取表中元素地址的运算。存储结构如图2所示。

图 2线性表顺序存储结构

线性表用一组地址连续的存储单元来存储表中元素的结构称为顺序存储结构，也称为顺序表。它以元素在计算机内物理位置上的紧邻来表示线性表中数据元素之间相邻的逻辑关系。因为每一个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数，因此可以根据元素的序号和表首地址得到该元素的存储地址，所以线性表的顺序结构是一种随机存取的存储结构。

线性表的运算是指线性表的访问、插入、删除等运算操作。另外，线性表的长度也是不固定的，随着数据元素个数的变化而变化。

线性表链式存储结构

线性表也可以采用链式存储结构来存储线性表元素，链式存储结构不要求逻辑上相邻的两个元素在物理位置上也相邻，因此在插入或删除线性表元素时，不需要移动大量元素。由于线性表各元素的存储单元不再是连续的存储空间，无法在物理位置上表示元素间的逻辑关系，因此需要在线性表元素中增加额外的信息来存储元素间的逻辑关系。

线性表元素除了存储元素本身的信息之外，还需要存储一个指向其后继元素的信息，通过该信息可以获取其后继元素的存储位置。这两部分信息构成了线性表数据元素的存储映象，称为节点。它包括两个域，一个是存储元素本身信息的域称作数据域名；一个是存储直接后继元素存储位置的域称作指针域，指针域中存储的信息称作指针域（见图3）。n个节点链接成一个链表，称为线性链表（简称为链表），当节点只包含一个指针域时，称为线性链表，也称为单链表。

图 3链表元素节点数据结构

图 4 单链表

图4给出了单链表结构，整个链表的存取必须从头指针开始，头指针指示链表中第一个节点的存储位置。由于最后一个数据元素没有直接后继，因此线性单链表中最后一个结点的指针为空（NULL）。

例如，使用单链表存储下面的线性表。

｛北京，济南，成都，西安，上海，昆明｝

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

图 5单链表存储示例

图5给出了单链表元素和存储地址的关系，单链表的HEAD指针为21，指向“北京”节点数据，“北京”节点数据的指针域为26，指向“济南”节点数据，……，“昆明”节点数据的指针域为NULL，NULL表示该节点为最后一个元素。

用图示的方法表示单链表时，一般将链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针。如图1-8的线性链表可画成如图1-9所示的形式。

图 6单链表的逻辑状态

二、线性表在多项式计算的应用

在数学上，一个一元n次多项式可以按照升幂写成

Pn（x）= p0 + p1x + p2x2 + …… + p(n)x^n

其中

p0，p1，……，pn

为多项式的系数，n为多项式的最高次数，没有未知数的项为常数项。

分析多项式结构，多项式由n+1个系数唯一确定，使用线性表存储多项的系数就可以表示一个多项式。

（p0，p1，p2，……，pn）

多项式的每一项的指数隐含在线性表的序号里。例如多项式：

3+2x+8x2+6x3

可以使用下面的单链表表示：

链表第一个节点存储多项式第1项的系数3，第1个节点的序号为0，因此该项的指数为0，该项为常数项；链表第二个节点存储多项式第2项的系数2，第2个节点的序号为1，因此该项的指数为1，以此类推……

两个多项式的加法运算可以在两个线性表的基础上进行，例如下面的两个多项式P和Q：

P = （p0，p1，p2，……，pn）

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

若m<n，则：

P+Q = Pn（x）+ Qm（x）

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

在线性表中两个多项式相加，可以将它们对应的系数分别相加，生成一个新的线性表，该线性表即为两个多项式相加的计算结果。不过采用这种数据结构来表示多项式，有一个很大的问题，当多项式次数很高且变化很大时，很难确定线性表的长度，只能以多项式的最高次数作为线性表的长度，即使该多项式只有几个单项，例如在处理类似下面的多项式时

T（x）= 12x2 + 2x12000+3x30000

虽然多项式只有3个单项式，但用上面线性表的节点数据结构存储该多项式，需要一个长度为30000的线性表，这样的数据结构设计会浪费很大的内存空间。可以考虑线性表的节点数据在存储多项式每项系数的同时，也存储每项的指数，这样就可以只存储多项式的非零项了（如图7所示）。

图 7多项式节点数据结构

例如多项式

P（x）= 12 + 2x3+8x5+11x6

线性表的表示为

P = （（12，0）（2，3），（8，5），（11，6））

单链表存储结构为

图 8多项式单链表存储结构

两个一元n次多项式P和Q相加结果为L，其计算规则非常简单：将P和Q指数相同项的系数相加，若相加的结果不为零，则该项作为L的一项，P和Q所有指数不同的项按指数大小都复制到L中。