顺序表的插入运算

2.3.3　顺序表的插入运算

下面以一个例子来说明如何在顺序存储结构的线性表中插入一个新元素。

例2-4　如图2-6(a)所示为一个长度为8的线性表顺序存储在长度为10的存储空间中。现在要求在第2个元素(即18)之前插入一个新元素87。其插入过程如下：

首先从最后一个元素开始直到第2个元素，其次将其中的每一个元素均依次往后移动一个位置，然后将新元素87插入到第2个位置。

插入一个新元素后，线性表的长度变成了9。如图2-6(b)所示。

如果要在线性表的第9个元素之前插入一个新元素14，则采用类似的方法：将第9个元素往后移动一个位置，然后将新元素插入到第9个位置。插入后，线性表的长度变成了10，如图2-6(c)所示。

图2-6　线性表在顺序存储结构下的插入

现在，为线性表开辟的存储空间已经满了，不能再插入新的元素。如果再要插入，则会造成“上溢”的错误。

一般来说，设长度为n的线性表为（a₁，a₂，…，a_i ，…，a_n）。

现要在线性表的第i个元素a_i之前插入一个新元素b，插入后得到长度为n+l的线性表为（a_l，a₂，…，a_j，a_j+1，…，a_n，a_n+1）。

则插入前后的两线性表中的元素满足如下关系：

在一般情况下，要在第i（1≤i≤n）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1。

显然，在线性表采用顺序存储结构时，如果插入运算在线性表的末尾进行，即在第n个元素之后（可以认为是在第n+1个元素之前）插入新元素，则只要在表的末尾增加一个元素即可，不需要移动表中的元素；如果要在线性表的第1个元素之前插入一个新元素，则需要移动表中所有的元素。在一般情况下，如果插入运算在第i（1≤i≤n）个元素之前进行，则原来第i个元素之后（包括第i个元素）的所有元素都必须移动。在平均情况下，要在线性表中插入一个新元素，需要移动表中一半的元素。因此，在线性表顺序存储的情况下，要插入一个新元素，其效率是很低的，特别是在线性表比较大的情况下更为突出，由于数据元素的移动而消耗较多的处理时间。