2.1.1　线性表的存储结构

1. 线性表的顺序存储

线性表顺序存储方式下，是用一组地址连续的存储单元依次存储线性表的数据元素。在这种顺序存储结构中，逻辑上相邻的两个元素在物理位置上也相邻，亦即线性表的逻辑关系无须额外增加存储空间来表达。

线性表第i个元素a_i的存储位置如下：

Loc(a_i)＝Loc(a₁)十(i-1)·L

其中：Loc(a₁)为线性表的起始位置 (即第一个元素的位置)；L为每个元素所占空间的大小。由此可知，线性表中的任一个元素都可以随机存取。

线性表的顺序存储表示如下:

2. 线性表的链式存储

线性表的链式存储可用连续或不连续的存储单元来存储线性表中的元素，但元素之间的逻辑关系需要用“指针”来指示，而这种指针是要占用额外存储空间的。链式存储方式失去了随机存取数据元素的功能，但换来了存储空间操作的方便性，进行插入或删除时无须移动大量元素。具体的链式存储结构又分为以下几种形式：

(1) 单向链表。每个结点除数据域外还包含一个指针域，用来指向直接后继结点。这种链表只能在一个方向上遍历其后继结点。

(2) 双向链表。每个结点除数据域外还包含两个指针，用来指向其直接前驱和直接后继结点。双向链表可以在两个方向上遍历其后继或前驱结点。

(3) 循环链表。链表中最后一个结点的指针又指向链表的首结点。循环链表可以在任何位置上遍历整个链表。几种常用的链式存储结构见表2.1。

表2.1 几种常用的链式存储结构

线性表链式存储的类型描述如下:

3. 静态链表

有些高级语言中，没有“指针”数据类型，要想发挥链表结构的长处，可用一个一维数组空间来模拟链表结构，即称之为静态链表。

静态链表的构造方法是用一维数组的一个分量表示一个结点，结点中的数据域(data)仍用于存储数据元素本身的信息，同时设一个下标域(cursor)来取代表中的指针域(next)，该下标域存放直接后继结点在数组中的位置序号。数组的第0个分量可看成固定的头结点，其下标域指示静态链表中的第一个数据结点位置：最后一个结点的下标域标0，标记该结点的尾结点。静态链表的示意图如图2-1所示。

4. 顺序存储结构和链式存储结构的特点

顺序存储结构的主要特点如下：

(1) 结点中只有自身的信息域，没有关联的信息域。因此，顺序存储结构的存储密度大、存储空间利用率高。

(2) 可以通过计算直接访问任何数据元素，即可以随机存取。

(3) 插入、删除操作会引起大量元素的移动。

图2-1 静态链表示意图

链式存储结构的主要特点如下：

(1) 结点中除自身信息域外，还有表示关联信息的指针域。因此，链式存储结构比顺序存储结构的存储密度小，存储空间的利用率低。

(2) 逻辑上相邻的结点在物理上不必相邻。

(3) 插入、删除操作方便、灵活，不必移动结点，只需修改结点中的指针即可。