线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储又叫作顺序表。

（1）线性表的顺序存储基本概念

线性表的顺序存储结构具备以下两个基本特征：

1）线性表中的所有元素所占的存储空间是连续的。

2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

假设线性表的每个元素需要占用k个存储单元，并且所占的存储位置ADR(ai+1)和第i个数据元素的存储位置ADR(ai)之间满足下列关系：

ADR(ai+1)=ADR(ai)+k

线性表第i个元素ai的存储位置为：

ADR(ai)=ADR(a1)+(i-1)×k

公式中ADR(a1)是线性表的第一个数据元素的存储位置，通常称为线性表的起始位置或基址。

在C语言中，通常定义一个一维数组来表示线性表的顺序存储空间，如图1-1所示。
a[0] a[1] a[2] a[3] a[4]
图1-1  顺序存储

在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。

在线性表的顺序存储结构下，可以对线性表做以下运算：

1）在线性表的指定位置处加入一个新的元素（即线性表的插入）。

2）在线性表中删除指定的元素（即线性表的删除）。

3）在线性表中查找某个（或某些）特定的元素（即线性表的查找）。

4）对线性表中的元素进行排序（即线性表的排序）。

5）将一个线性表分解成多个线性表（即线性表的分解）。

6）将多个线性表合并成一个线性表（即线性表的合并）。

7）复制一个线性表（即线性表的复制）。

8）逆转一个线性表（即线性表的逆转）。

（2）顺序表的基本操作

顺序表的基本操作包括插入运算和删除运算。

1）顺序表的插入运算：线性表的插入运算是指在表的第i（1≤i≤n+l）个位置上，插入一个新节点x，使长度为n的线性表（a1,…,ai-1,ai,…,an）变成长度为n+1的线性表（a1,…,ai-1,x,ai,…,an+1）。

现在分析算法的复杂度。设它的值为n。该算法的时间主要花费在循环节点后移语句上，该语句的执行次数（即移动节点的次数）是n-i+1。由此可看出，所需移动节点的次数不仅依赖于表的长度，而且还与插入位置有关。

当i=n+1时，由于循环变量的终值大于初值，节点后移语句将不执行。这是最好的情况，其时间复杂度为O(1)。

当i=1时，节点后移语句将循环执行n次，需移动表中所有节点。这是最坏的情况，其时间复杂度为O(n)。

综合以上的情况，得出算法的平均时间复杂度为O(n)。

2）顺序表的删除运算：线性表的删除运算是指将表的第i（1≤i≤n）个节点删除，使长度为n的线性表（a1,…,ai-1,ai,ai+1,…,an）变成长度为n-l的线性表（a1,…,ai-1,ai+1,…,an-1）。

该算法的时间分析与插入算法相似，节点的移动次数也是由表长n和位置i决定的。

若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动节点。

若i=1，则前移语句将循环执行n-1次，需移动表中除开始节点外的所有节点。这两种情况下算法的时间复杂度分别为O(1)和O(n)。

综合以上的情况得出，在顺序表上做删除运算，平均要移动表中约一半的节点，平均时间复杂度也是O(n)。