顺序表的插入删除算法移动元素次数分析

设：L.elem[0..maxleng-1] 中有 legth 个元素，

在 L.elem[i-1] 之前插入 新元素 e ,1<=i<=length

例：i = 3，e = 6，length = 6

如上图，我们需要在第三个元素，也就是 "8" 之前插入 “6”，

因此需要将 “8”，“20“，”30”，“35” 这些元素统统后移一格

如下图：

--------------------------------------------------分---------------界---------------线------------------------------------------------------------

 也就是将，从第 i-1 个元素开始，统统向后移动一位，然后将元素 “x” 插入 第 "i-1" 个位置，即下图：

移动元素下标范围：i - 1 ~ n - 1 或 i - 1 ~ L.length - 1

元素移动方向为：是从 最后一个元素 an 开始，一直到 ai 处，依次向后移动一个位置，而非从 第 ai 开始。

基于此思想，进行一个动态表插入与静态表插入的对比：

算法①：静态分配线性表空间，用指针指向被操作的线性表（下图）

算法思想：
① 判断插入的位置是否合理即：if ( i<1 || i>L.length+1 ) return ERROR; 

i 这里指的是第几个元素，而非下标。

因此，i<1这里即插入位置不合理。（我们无法在 第0个 元素前插入，因为它不存在）

L.length + 1 ：我们为了插入元素顺利，因此让线性表占用存储空间为元素数量+1，

体现在这里就是 L.length + 1，i 超出这个值，则无法插入（没位置了，添加不进去）

② 判断表长是否达到分配空间的最大值，

if (L.length>=maxleng) return OVERFLOW

如果 线性表长度 大于等于 最大长度，这里是从线性表长度的角度表达规则。

③ 从线性表中的最后一个位置到插入位置的所有元素，依次往后移动一个元素的位置，这样给待插入元素留出一个空位置

即：L.elem[j+1] = L.elem[j]; //将原位置元素赋值给新位置

④ 线性表长度变量 + 1，L.length ++;

⑤ return ok，返回结果，表示插入成功。

关于 for 循环部分：

1. 从最后一个元素开始，依次向后移动一位

2. j = L.length - 1 // L.length 即线性表长度，L.length - 1 即线性表中 最后一位元素 的 下标

3. j >= i-1 为 for 循环的条件，当下标变成 i - 1 时停止 for 循环。在满足 j>=i-1 条件的情况下，才会进行for 循环，不满足这个条件，就停止 for 循环，同时 “；”是在 L.elem[j+1] = L.elem[j] 这个代码后，因此 for 循环在运行过程中，它的运行范围就止步于此。

4. L.elem[j+1] = L.elem[j] 将下标为 j 的元素，赋值到下标为 j+1 的位置。

--------------------------------------------------分---------------界---------------线------------------------------------------------------------

动态 分配线性表空间，用 引用参数 表示被操作的线性表

伪代码部分（如下图）

如果插入元素使得表长超过原来分配的空间大小时，这时候可以使用：

newbase = (ElemType *) realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));

寻找更大片的连续地址空间，但极端情况下可能发生扩容失败。

如果找到新的更大片的连续地址空间后，我们要将线性表的基地址改成一个新地址。

代码讲解：

L.length：当前数据元素的个数（即线性表的长度）

L.listsize：当前分配的存储容量

ElemType *newbase：定义一个Elemtype类型的指针变量

关于 realloc ：

L.elem = newbase：新基地址，

L.listsize += LISTINCREMENT：增加存储容量

for 循环代码块：从最后一个开始，到第 i 个元素，挨个往后挪

L.elem[i - 1] = e：将元素 "e" 赋值给被空出来的 原第 i-1 个元素 的存储位置

L.length++：线性表长度加一

--------------------------------------------------分---------------界---------------线------------------------------------------------------------

插入操作  移动元素次数  的分析

总之，在一个线性表中，往里面插入一个元素的时候，它移动元素的长度的数学期望值，是等于线性表长度的一半。

--------------------------------------------------分---------------界---------------线------------------------------------------------------------

在线性表中删除元素，同样也存在移动元素的过程，只是这个移动方向和插入元素时的移动方向是相反的。

比如对上边这个线性表中的元素 “ai” 进行删除时，需要把 ai+1 一直到 an ，依次向原 ai 位置移动一格。变成如下：

删除代码如下：

 代码中算法基本思想：

① 判断删除元素的下标是否存在。关于此处用 ->

② 用一个 for 循环来移动元素，移动元素下标范围为 i 到 length - 1

③ 修改表长为原表长减一

--------------------------------------------------分---------------界---------------线------------------------------------------------------------

删除操作及移动元素次数的分析：

删除元素的位置只有 n 中情形。

 --------------------------------------------------分---------------界---------------线------------------------------------------------------------

一个思考题：顺序存储结构的线性表插入一个元素算法的时间复杂度是平方数量及的吗？

原文：https://www.cnblogs.com/AronKeener/p/14639449.html