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

要想将线性表在计算机上表示，必须先将其逻辑结构转化存储结构，存放在计算机中。线性表的存储结构主要有两种：顺序存储和链式存储。

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

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

2.2.2 顺序表的基本运算

顺序表的基本运算如下（以下算法的实现保存在文件“SeqList.h”中）。

（1）顺序表的初始化。

（2）判断顺序表是否为空。

（3）按序号查找操作。查找操作分为两种：按序号查找和按内容查找。按序号查找就是查找顺序表L中的第i个元素，如果找到将该元素值赋值给e。

（4）按内容查找操作。

（5）插入操作。插入操作就是在顺序表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，首先需将表中位置为n，n-1，…，i上的元素依次后移一个位置，将第i个位置空出，然后在该位置插入新元素e。当i=n+1时，是指在顺序表的末尾插入元素，无需移动元素，直接将e插入表的末尾即可。

例如，要在顺序表{3，15，49，20，23，44，18，36}的第5个元素之前插入一个元素22，需要为36，18，44，23依次向后移动一个位置，然后在第5号位置插入元素22，顺序表就变成了{3，15，49，20，22，23，44，18，36}，如图2.4所示。

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

注意： 插入元素之前要判断插入位置是否合法，另外还要判断顺序表的存储空间是否已满，在插入元素后要将表长增加1。

（6）删除操作。删除操作就是将顺序表L中第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。

例如，要删除顺序表{3，15，49，20，22，23，44，18，36}的第4个元素，需要将序号为5，6，7，8，9的元素依次向前移动一个位置，这样就删除了第4个元素，最后将表长减1。如图2.5所示。

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

注意： 在删除元素时，首先要判断顺序表中是否还有元素，另外，还需要判断删除的序号是否合法。删除成功后，将顺序表的长度减1。

（7）求顺序表的长度。

（8）清空顺序表。

2.2.3 基本操作算法分析

在以上顺序表的基本操作算法中，除了按内容查找运算、插入和删除操作外，算法的时间复杂度都为O（1）。

在按内容查找的算法中，如果要查找的元素在第一个位置，则需要比较一次；如果要查找的元素在最后一个位置，则需要比较n次（n为线性表的长度）。设p _i 为在第i个位置上找到与e相等元素的概率，假设在任何位置上找到元素的概率相等，即p _i =1/n。则查找过程中需要比较的平均次数为：

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

在顺序表的插入算法中，时间的耗费主要集中在移动元素上。如果要插入的元素在第一个位置，则需要移动元素的次数为n次；如果要插入的元素在最后一个位置，则需要移动元素的次数为1次；如果插入位置在最后一个元素之后，即第n+1个位置，则需要移动元素的次数为0次。设p _i 为在第i个位置上插入元素的概率，假设在任何位置上找到元素的概率相等，即p _i =1/（n+1）。则顺序表的插入操作需要移动元素的平均次数为：

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

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

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

2.2.4 顺序表应用举例

【例2.1】 利用线性表的基本运算，实现如果在线性表A中出现的元素，在线性表B中也出现，则将A中的该元素删除。

分析：这其实是求两个表的差集，即A-B。依次检查线性表B中的每一个元素，如果该元素在线性表A中也出现，则在A中删除该元素。

求A-B的差集算法如下：

测试程序如下：

程序运行结果如图2.6所示。

【例2.2】 编写一个算法，把一个顺序表分拆成两个部分，使顺序表中小于等于0的元素位于左端，大于0的元素位于右端。要求不占用额外的存储空间。例如，顺序表（-12，3，-6，-10，20，-7，9，-20）经过分拆调整后变为（-12，-20，-6，-10，-7，20，9，3）。

【分析】设置两个指示器i和j，分别扫描顺序表中的元素，i和j分别从顺序表的左端和右端开始扫描。如果i遇到小于等于0的元素，略过不处理，继续向前扫描；如果遇到大于0的元素，暂停扫描；如果j遇到大于0的元素，略过不处理，继续向前扫描；如果遇到小于等于0的元素，暂停扫描。如果i和j都停下来，则交换i和j指向的元素。重复执行直到i≥j为止。

算法描述如下：

测试程序如下：

程序运行结果如图2.7所示。