顺序表是顺序存储方式，即逻辑上相邻的数据在计算机内的存储位置也是相邻的。在顺序存储方式中，元素存储是连续的，中间不允许有空，可以快速定位某个元素，所以插入、删除时需要移动大量元素。根据分配空间方法的不同，顺序表可以分为静态分配和动态分配两种。

在顺序表中，最简单的方法是使用一个定长数组data[]存储数据，最大空间为Maxsize，用length记录实际的元素个数，即顺序表的长度。这种用定长数组存储的方法被称为静态分配。

当采用静态分配的方法时，定长数组需要预先分配一段固定大小的连续空间，但是在运算过程中进行合并、插入等操作容易超过预分配的空间长度，并出现溢出。可以采用动态分配的方法解决溢出问题。

在程序运行过程中，根据需要动态分配一段连续的空间（大小为Maxsize），用elem记录该空间的基地址（首地址），用length记录实际的元素个数，即顺序表的长度。采用动态分配方法时，在运算过程中如果发生溢出，则可以另外开辟一块更大的存储空间，用来替换原来的存储空间，从而达到扩充存储空间的目的。

顺序表的动态分配结构体定义如下图所示。

1. 插入

在顺序表中的第 i 个位置之前插入一个元素 e ，需要从最后一个元素开始，后移一位……直到把第 i 个元素也后移一位，然后把 e 放入第 i 个位置，如下图所示。

算法步骤：

（1）判断插入位置 i 是否合法（1≤ i ≤ L .length+1），可以在第1个元素之前插入，也可以在第 L .length+1个元素之前插入。

（2）判断顺序表的存储空间是否已满。

（3）将第 L .length至第 i 个元素依次向后移动一个位置，空出第 i 个位置。

（4）将要插入的新元素 e 放入第 i 个位置。

（5）表长加1，插入成功后返回true。

完美图解： 例如，在顺序表中的第5个位置之前插入一个元素9。

（1）移动元素。从最后一个元素（下标为 L .length−1）开始后移一位，移动过程如下图所示。

（2）插入元素。此时第5个位置空出来，将要插入的元素9放入第5个位置，表长加1。

算法代码 ：

算法分析： 可以在第1个位置之前插入，也可以在第2个位置之前插入……在第 n 个位置之前插入或在第 n +1个位置之前插入，共有 n +1种情况，每种情况下移动元素的个数都是 n − i +1。把每种情况移动次数乘以其插入概率 p _i 并求和，即平均时间复杂度。如果插入概率均等，即每个位置的插入概率均为1/( n +1)，则平均时间复杂度如下：

因此，假设每个位置插入的概率均等，则顺序表中插入元素算法的平均时间复杂度为 O ( n )。

2. 删除

在顺序表中删除第 i 个元素时，需要把该元素暂存到变量 e 中，然后从第 i +1个元素开始前移……直到把第 n 个元素也前移一位，即可完成删除操作。

算法步骤：

（1）判断插入位置 i 是否合法（1≤ i ≤ L .length）。

（2）将欲删除的元素保留在 e 中。

（3）将第 i +1至第 n 个元素依次向前移动一个位置。

（4）表长减1，若删除成功则返回true。

完美图解： 例如，从顺序表中删除第5个元素，如下图所示。

（1）移动元素。首先将待删除元素2暂存到变量 e 中，以后可能有用，如果不暂存，则将被覆盖。然后从第6个元素开始前移一位，移动元素的过程如下图所示。

（2）表长减1，删除元素后的顺序表如下图所示。

算法代码 ：

算法分析： 在顺序表中删除元素共有 n 种情况，每种情况移动元素的个数都是 n − i 。把每种情况移动次数乘以其删除概率 p _i 并求和，即平均时间复杂度。假设删除每个元素的概率均等，即每个元素的删除概率均为1/ n ，则平均时间复杂度如下：

因此，假设每个元素删除的概率均等，则顺序表中删除元素算法的平均时间复杂度为 O ( n )。

● 顺序表的优点：操作简单，存储密度高，可以随机存取，只需 O (1)的时间就可以取出第 i 个元素。

● 顺序表的缺点：需要预先分配最大空间，最大空间数估计过大或过小都会造成空间浪费或溢出。进行插入和删除操作时需要移动大量元素。

在实际问题中，如果经常需要进行插入、删除操作，则采用顺序表的效率很低，这时可以采用链式存储。 kWURmHv++UrHBTvanMwK/52EpGN2hEw789+jNjdhxmBtfaISPdALdgUqKlstlJTy