顺序表的删除运算

2.3.4　顺序表的删除运算

举一个例子来说明如何在顺序存储结构的线性表中删除一个元素。

例2-5　如图2-7(a)所示为一个长度为8的线性表顺序存储在长度为10的存储空间中。现在要求删除线性表中的第1个元素（即删除元素29）。其删除过程如下：

从第2个元素开始直到最后一个元素，将其中的每一个元素均依次往前移动一个位置。此时，线性表的长度变成了7。如图2-7(b)所示。

如果再要删除线性表中的第6个元素，则采用类似的方法：将第7个元素往前移动一个位置。此时，线性表的长度变成了6。如图2-7(c)所示。

图2-7　在顺序存储结构下线性表的删除

一般来说，设长度为n的线性表为

（a_l，a₂，…，a_i，…，a_n）

现在要删除第i个元素，删除后得到长度为n-1的线性表为

（a_l，a₂，…，a_j，…，a_n-1）

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

在一般情况下，要删除第i（1≤i≤n）个元素时，则要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。删除结束后，线性表的长度就减小了1。

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

由线性表在顺序存储结构下的插入与删除运算可以看出，线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单。但这种顺序存储的方式对于元素经常需要变动的大线性表就不太合适了，因为插入与删除的效率比较低。