2.2.1 线性表的顺序存储

线性表的顺序存储指的是将线性表中的各个元素依次存放在一组地址连续的存储单元中。线性表的这种机内表示称为线性表的顺序映像或线性表的顺序存储结构，用这种方法存储的线性表称为顺序表。顺序表具有以下特征：逻辑上相邻的元素，在物理上也是相邻的。

假设线性表有n个元素，每个元素占用m个存储单元，如果第一个元素的存储位置为LOC（a₁），第i个元素的存储位置为LOC（a_i），第i+1个元素的存储位置为LOC（a_i+1）。则线性表的第i+1个元素的存储位置与第i个元素的存储位置满足以下关系：

LOC（a_i+1）=LOC（a_i）+m

线性表的第i个元素的存储位置与第一个元素a₁的存储位置满足以下关系：

LOC（a_i）=LOC（a₁）+（i-1）*m

其中，第一个元素的位置LOC（a₁）称为起始地址或基地址。

线性表的顺序存储结构是一种随机存取的存储结构。只要知道其中一个元素的存储地址，就可以得到线性表中任何一个元素的存储地址。线性表的顺序存储结构如图2.3所示。

由于在C语言中，数组具有随机存取的特点，且数组中的元素依次存放在连续的存储空间中，因此，可以采用数组来描述顺序表。顺序表的存储结构描述如下。

图2.3 线性表顺序存储结构

其中，SeqList是结构体类型名，list用于存储顺序表中的数据元素，length表示顺序表当前的数据元素个数。