2.2.2　线性表的顺序表示与实现

1．线性表的顺序存储结构

线性表的顺序存储指的是将线性表中的各个元素依次存放在一组地址连续的存储单元中。

假设线性表的每个元素需占用m个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个元素的存储位置LOC（a_i+1）和第i个元素的存储位置LOC（a_i）之间满足关系LOC（a_i+1）=LOC（a_i）+m。

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

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

其中，第一个元素的位置LOC（a₁）称为起始地址或基地址。线性表的顺序存储如图2-1所示。

线性表的这种机内表示称为线性表的顺序存储结构或顺序映像（sequential mapping），通常将这种方法存储的线性表称为顺序表。顺序表逻辑上相邻的元素在物理上也是相邻的。只要确定了第一个元素的起始位置，线性表中的任一元素都可以随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构。

由于C语言的数组具有随机存取的特点，因此可采用数组来描述顺序表。根据内存分配的方式，顺序表的类型定义可以分为静态分配和动态分配两种方式。对于静态分配，在定义顺序表变量时，其存储空间随之分配；对于动态分配，在定义了顺序表L之后，还需要为L动态分配内存空间。静态分配与动态分配的比较如表2-1所示。

2．顺序表的基本运算

在顺序存储结构中，线性表的基本运算如下：

①初始化线性表。

②判断线性表是否为空。

③按序号查找。先判断序号是否合法，如果合法，则把对应位置的元素赋给e，并返回1表示查找成功，否则返回-1表示查找失败。

④按内容查找。从线性表中的第一个元素开始，依次与e比较，如果相等，则返回该序号表示成功，否则返回0表示查找失败。

若要查找的是第一个元素，则仅需要进行一次比较；若要查找的是最后一个元素，则需要比较n次才能找到该元素（设线性表的长度为n）。设P_i表示在第i个位置上找到与e相等的元素的概率，若在任何位置上找到元素的概率相等，即P_i=1/n，则查找元素的平均比较次数为：

因此，按内容查找的平均时间复杂度为O（n）。

⑤插入操作。插入操作就是在线性表L中的第i个位置插入新元素e，使线性表｛a₁，a₂，…，a_i-1，a_i，…，a_n｝变为｛a₁，a₂，…，a_i-1，e，a_i，…，a_n｝，线性表的长度也由n变成n+1。

要在顺序表中的第i个位置上插入元素e，首先将第i个位置以后的元素依次向后移动1个位置，然后把元素e插入第i个位置。移动元素时，要从后往前移动元素，先移动最后1个元素，再移动倒数第2个元素，以此类推。

例如，在线性表｛9，12，6，15，20，10，4，22｝中，要在第5个元素之前插入1个元素28，需要将序号为8、7、6、5的元素依次向后移动1个位置，然后在第5号位置插入元素28，这样，线性表就变成了｛9，12，6，15，28，20，10，4，22｝，如图2-2所示。

插入元素之前，要判断插入的位置是否合法，顺序表是否已满；在插入元素后，要将表长增加1。插入元素的算法实现如下：

插入元素的位置i的合法范围应该是1≤i≤L->length+1。当i=1时，插入位置是在第一个元素之前，对应C语言数组中的第0个元素；当i=L->length+1时，插入位置是最后一个元素之后，对应C语言数组中的最后一个元素之后的位置。当插入位置是i=L->length+1时，不需要移动元素；当插入位置是i=0时，则需要移动所有元素。

顺序表的插入操作时间主要耗费在元素的移动上。设P_i表示在第i个位置上插入元素的概率，假设在任何位置上找到元素的概率相等，即P_i=1/（n+1）。则在顺序表的第i个位置插入元素时，需要移动元素的平均次数为：

因此，插入操作的平均时间复杂度为O（n）。

⑥删除第i个元素。删除第i个元素之后，线性表｛a₁，a₂，…，a_i-1，a_i，a_i+1，…，a_n｝变为｛a₁，a₂，…，a_i-1，a_i+1，…，a_n｝，线性表的长度由n变成n-1。

为了删除第i个元素，需要将第i+1后面的元素依次向前移动一个位置，将前面的元素覆盖。移动元素时，先将第i+1个元素移动到第i个位置，再将第i+2个元素移动到第i+1个位置，以此类推，直至最后一个元素移动到倒数第二个位置。最后将顺序表的长度减1。

例如，要删除线性表｛9，12，6，15，28，20，10，4，22｝的第4个元素，需要依次将序号为5、6、7、8、9的元素向前移动一个位置，并将表长减1，如图2-3所示。

在进行删除操作时，先判断顺序表是否为空，若不空，则接着判断序号是否合法；若不为空且合法，则将要删除的元素赋给e，并把该元素删除，将表长减1。删除第i个元素的算法实现如下：

删除元素的位置i的合法范围应该是1≤i≤L->length。当i=1时，表示要删除第一个元素，对应C语言数组中的第0个元素；当i=L->length时，要删除的是最后一个元素。

在顺序表的删除算法中，时间主要耗费仍在元素的移动上。若要删除的是第一个元素，则需要移动元素次数为n-1次；若要删除的是最后一个元素，则需要移动0次。设P_i表示删除第i个位置上的元素的概率，假设在任何位置上找到元素的概率相等，即P_i=1/n，则在顺序表中删除第i个元素时，需要移动元素的平均次数为。

因此，删除操作的平均时间复杂度为O（n）。

⑦求线性表的长度。

⑧清空顺序表。