2.2 顺序表

线性表的存储结构主要分为顺序存储结构和链式存储结构两类，前者简称为顺序表。本节主要介绍顺序表及其线性表基本运算在顺序表上实现的算法。

2.2.1 顺序表的定义

顺序表是线性表采用顺序存储结构在计算机内存中的存储方式，它由多个连续的存储单元构成，每个存储单元存放线性表的一个元素，逻辑上相邻的数据元素在内存中也是相邻的，不需要额外的内存空间来存放元素之间的逻辑关系。顺序表称为线性表的直接映射。

假定线性表的数据元素的类型为ElemType（在实际应用中，此类型应根据实际问题中的数据元素的特性具体定义，如为int、char类型等），在C/C++语言中，声明顺序表类型如下。

其中，数据域data是一个一维数组，线性表的第1，2，…，n个元素分别存放在此数组的第0，1，…，n—1个单元中；数据域length表示线性表当前的长度，顺序表的示意图如图2.4所示。常数MaxSize称为顺序表的容量，其值通常根据具体问题的需要取为线性表实际可能达到的最大长度。length～MaxSize—1下标为顺序表当前的空闲区（或称备用区）。

注意：在算法设计时，应遵守相应的语法规定。例如，L被声明为SqList类型的变量，即为一个顺序表，其表长应写为L.length。另外，线性表的元素ai（1≤i≤n）存放在data数组的data[i—1]中，也就是说，逻辑序号为i的元素在顺序表中对应的物理下标（或物理序号）为i—1。

由于顺序表采用数组存放元素，而数组具有随机存取特性，所以顺序表具有随机存取特性。

2.2.2 线性表基本运算在顺序表上的实现

所谓实现运算就是用C/C++语言给出完整的求解步骤即算法，因此运算实现必须以存储结构的类型定义为前提。上面已经给出了顺序表的类型定义，在此基础上可以进一步讨论线性表的基本运算在顺序表上的实现。

下面讨论顺序表中线性表基本运算算法的实现过程。

1．顺序表的基本运算算法

1）初始化线性表运算算法

将顺序表L的length域置为0，对应的算法如下。

本算法的时间复杂度为O（1）。

2）销毁线性表运算算法

这里顺序表L作为自动变量，其内存空间是由系统自动分配的，在不再需要时会由系统自动释放其空间，所以对应的函数不含任何语句。对应的算法如下。

      void DestroyList(SqList L)
      {    }

3）求线性表长度运算算法

返回顺序表L的length域值，对应的算法如下。

      int GetLength(SqList L)
      {
           return L.length;
      }

本算法的时间复杂度为O（1）。

4）求线性表中第i个元素运算算法

对于顺序表L，算法在逻辑序号i无效时返回特殊值0（假），有效时返回1（真），并用引用型形参e返回第i个元素的值。对应的算法如下。

本算法的时间复杂度为O（1）。

5）按值查找运算算法

在顺序表L中找第一个值为x的元素，找到后返回其逻辑序号，否则返回0（由于线性表的逻辑序号从1开始，这里用0表示没有找到值为x的元素）。对应的算法如下。

本算法的时间复杂度为O（n），其中，n为L中的元素个数。

6）插入元素运算算法

将新元素x插入到顺序表L中逻辑序号为i的位置（如果插入成功，元素x成为线性表的第i个元素）。当i无效时返回0（表示插入失败），i有效时将L.data[i—1..L.length—1]均后移一个位置，再在L.data[i—1]处插入x，顺序表长度增1，并返回1（表示插入成功），如图2.5所示（图中n表示顺序表L的长度）。对应的算法如下。

对于插入算法InsElem（）来说，在顺序表L中插入新元素共有n+1种情况，如图2.6所示。元素x插入到不同的位置，顺序表中元素移动的次数是不同的。当i=n+1时（插入尾元素），移动次数为0，呈现最好的情况；当i=1时（插入第一个元素），移动次数为n，呈现最坏的情况。

对于一般情况，在位置i插入新元素x，需要将ai～an的元素均后移一次，移动次数为n—i+1。假设pi是在第i个位置上插i入一个元素的概率，则在长度为n的线性表L中插入一个元素时，所需移动元素的平均次数为：

而插入算法的主要时间花费在元素移动上，所以算法InsElem（）的平均时间复杂度为O（n）。

7）删除元素运算算法

删除顺序表L中逻辑序号为i的元素。在i无效时返回0（表示删除失败），i有效时将L. data[i..L.length—1]均前移一个位置，顺序表长度减1，并返回1（表示删除成功），如图2.7所示（图中n表示顺序表L的长度）。对应的算法如下。

对于删除算法DelElem（）来说，在顺序表L中删除已存在的元素共有n种情况，如图2.8所示。删除元素的位置不同，顺序表中元素移动的次数是不同的。当i=n时（删除尾元素），移动次数为0；当i=1时（删除第一个元素），移动次数为n—1。

对于一般情况，删除位置i的元素ai，需要将ai+1～an的元素均前移一次，移动次数为n—（i+1）+1=n—i。假设pi是删除第i个位置上元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素的平均次数为：

而删除算法的主要时间花费在元素移动上，所以删除算法的平均时间复杂度为O（n）。

从以上分析看到，当线性表采用顺序表存储时，插入、删除算法的性能不太理想，主要是需要移动大量的元素。

8）输出元素值运算算法

从头到尾扫描（或者称为遍历）顺序表L，输出各元素值。对应的算法如下。

本算法的时间复杂度为O（n），其中，n为L中的元素个数。

提示：将顺序表类型声明及其基本运算函数存放在SqList.cpp文件中。

当顺序表的基本运算设计好后，给出以下主函数调用这些基本运算函数，读者可以对照程序执行结果进行分析，进一步体会顺序表各种操作的实现过程。

以上程序的执行结果如图2.9所示。

2．整体创建顺序表的算法

可以通过调用基本运算算法来创建顺序表，其过程是先初始化一个顺序表，然后向其中一个一个地插入元素。这里介绍的是快速创建整体顺序表的算法，也称为整体建表。假设给定一个含有n个元素的数组，由它来创建顺序表，对应的算法如下。

算法的时间复杂度为O（n）。

说明：尽管该算法只是简单地将a[0..n—1]的元素复制到L的data数组中，但可以体会到整体创建顺序表L的过程。实际上，可以通过修改插入元素的条件使得仅仅将满足条件的元素插入到L中。

2.2.3 顺序表的算法设计示例

1．基于顺序表基本操作的算法设计

这类算法设计中包括顺序表元素的查找、插入和删除等。

【例2.3】假设有一个顺序表L，其中元素为整数且所有元素值均不相同。设计一个算法将最大值元素与最小值元素交换。

解：用maxi和mini记录顺序表L中最大值元素和最小值元素的下标，初始时maxi= mini=0，i从1开始扫描L.data的所有元素：当L.data[i]＞L.data[maxi]时置maxi=i；否则若L.data[i]＜L.data[mini]时置mini=i。扫描完毕时，L.data[maxi]为最大值元素，L. data[mini]为最小值元素，将它们交换。对应的算法如下。

上述算法的时间复杂度为O（n）。

【例2.4】设计一个算法，从线性表中删除自第i个元素开始的k个元素，其中，线性表用顺序表L存储。

解：本题将线性表中ai～ai+k—1元素（对应L. data[i—1..i+k—2]的元素）删除，即将ai+k～an（对应L.data[i+k—1..n—1]）的所有元素依次前移k个位置，如图2.10所示（图中n表示顺序表L的长度）。对应的算法如下。

本算法的时间复杂度为O（n），其中，n为顺序表L中的元素个数。

【例2.5】假设有一个顺序表L，其中元素为整数且所有元素值均不相同。设计一个尽可能高效的算法将所有奇数移到所有偶数的前面。

解：采用前后元素交换的算法设计思路：置i=0，j=n—1，在顺序表L中从前向后找到偶数L.data[i]，从后向前找到奇数L.data[j]，将两者交换；循环这个过程直到i等于j为止。对应的算法如下。

本算法正好扫描了顺序表中每个元素一次，所以时间复杂度为O（n），算法中只定义了固定几个临时变量，所以算法的空间复杂度为O（1）。

2．基于整体建表的算法设计

这类算法设计中需要根据条件产生新的结果顺序表。

【例2.6】已知一个整数线性表采用顺序表L存储。设计一个尽可能高效的算法删除其中所有值为x的元素（假设L中值为x的元素可能有多个）。

解：由于删除所有x元素后得到的结果顺序表可以与原L共享存储空间，求解问题转化为新建结果顺序表。采用整体创建顺序表的算法思路，将插入元素的条件设置为“不等于x”，即仅将不等于x的元素插入到L中。用k记录结果顺序表中元素个数（初始值为0），扫描L，将L中所有不为x的元素重新插入到L中，每插入一个元素k增加1，最后置L的长度为k。对应的算法如下。

上述算法的时间复杂度为O（n），空间复杂度为O（1），属于高效的算法。如果另外创建一个临时顺序表L1，将L中所有不为x的元素插入到L1中，再将L1复制回L，对应算法的空间复杂度为O（n）。如果在扫描L时对每个等于x的元素都采用移动方式实现删除操作，对应算法的时间复杂度为O（n2）。这两个算法都不是高效的算法。

【例2.7】已知一个整数线性表采用顺序表L存储。设计一个尽可能高效的算法删除其中所有值为负整数的元素（假设L中值为负整数的元素可能有多个）。

解：采用例2.6的思路，仅将插入元素的条件设置为“元素值≥0”即可。对应的算法如下。

3．有序顺序表的二路归并算法

有序表是指按元素值递增或者递减排列的线性表，有序顺序表是有序表的顺序存储结构。对于有序表，可以利用其元素的有序性提高相关算法的效率，二路归并就是有序表的一种经典算法。

【例2.8】有两个按元素值递增有序的顺序表A和B，设计一个算法将顺序表A和B的全部元素归并到一个按元素递增有序的顺序表C中。并分析算法的空间复杂度和时间复杂度。

解：算法设计思路是：用i扫描顺序表A，用j扫描顺序表B。当A和B都未扫描完时，比较两者的当前元素，总是将较小者复制到C中。最后将尚未扫描完的顺序表的余下元素均复制到顺序表C中。这一过程称为二路归并，如图2.11所示。

对应的算法如下。

本算法的空间复杂度为O（1），时间复杂度为O（n+m），其中，n和m分别为顺序表A和B的长度。

说明：上述算法是新建有序顺序表C，它是采用整体建表实现的。插入到C中的元素是按二路归并即比较后得到的较小的元素。

【例2.9】有两个递增有序顺序表A和B，设计一个算法由顺序表A和B的所有公共元素产生一个顺序表C。并分析该算法的空间复杂度和时间复杂度。

解：本算法仍采用二路归并的思路，用i、j分别扫描有序顺序表A、B，跳过不相等的元素，将两者相等的元素（即公共元素）放置到顺序表C中。对应的算法如下。

本算法的空间复杂度为O（1），时间复杂度为O（m+n），其中，m和n分别为顺序表A和B的长度。和例2.2算法相比，它们的功能相同，但例2.2算法的时间复杂度为O（m×n），所以本例算法更优，这是因为本例中顺序表的元素是有序的。

【例2.10】有两个递增有序顺序表A和B，分别含有n和m个整数元素（最大的元素不超过32 767），假设这n+m个元素均不相同。设计一个尽可能高效的算法求这n+m个元素中第k小的元素。如果参数k错误，算法返回0；否则算法返回1，并且用参数e表示求出的第k小的元素。

解：本算法仍采用二路归并的思路。若k <1或者k >A.length+B.length，表示参数k错误，返回0。否则，用i、j分别扫描有序顺序表A、B，当两个顺序表均没有扫描完时，比较它们的当前元素，每比较一次k减1，当k=0时，较小的元素就是最终结果e，找到这样的e后返回1。如果没有找到e，若顺序表A没有扫描完，e就是A.data[i+k—1]，若顺序表B没有扫描完，e就是B.data[j+k—1]。对应的算法如下。

上述算法需要考虑三种情况：A、B均没有扫描完，A没有扫描完和B没有扫描完。由于A、B均没有扫描完时总是比较找最小元素，并且最大元素值为INF（32767），可以这样简化判断：x表示当前A的元素，当A扫描完时取x为INF，y表示当前B的元素，当B扫描完时取y为INF，从而简化为总是进行x、y的元素比较。对应的简化算法如下。

说明：本题仅求第k小的元素，没有必要将A、B中所有元素二路归并到临时表C中，再在C中求出e=C.data[k—1]，这样做算法的空间复杂度为O（n+m），从空间角度看，不如Topk1和Topk2算法高效。