数据结构重学日记（五）顺序表的操作

2019-01-06 本文已影响1人南瓜方糖

插入操作

有 $a_1$ - $a_4$ 几个元素组成的顺序表，新增一个 $a_5$ ， $a_5$ 的位置在 $a_1$ 和 $a_2$ 之间，那么 $a_2$ - $a_4$ 就需要相应的后移。

算法流程：在顺序表 L 的第 i (1 <= i < L.length + 1) 个位置插入新元素 e，如果 i 插入不合法，则返回false，表示插入失败，否则将顺序表的第 i 个元素以及其后的所有元素右移一个位置，腾出一个空位插入新元素 e，顺序表长度 + 1，插入成功，返回 true。

示例代码

bool ListInsert(SqList &L, int i, ElemType e){
# SqList &L  为带插入顺序表
# i 插入位置
# e 待插入元素

    if(i < 1 || i > L.length+1) return false;
    if(L.length >= MaxSize) return false;

    for(int j = L.length; j >= i; j--)
        L.data[j] = L.data[j-1];
    # L 最后一个元素的位置为 L.length -1 

L.data[i -1] = e;
L.length ++;
return true;
}

最好情况：在表尾插入（即 i = n +1），元素后移语句将不执行，时间复杂度为O(1)。

最坏情况：在表头插入（即 i = 1），元素后移语句将执行 n 次，时间复杂度为 O(n)。

平均情况：假设每个位置插入的概率均等，可以在第一个位置之前插入，第二个位置之前插入……，最后一个位置之前，第 n + 1 个位置之前，一共有 n + 1 种情况，每种情况的概率为 $\frac{1}{n + 1}$ ，每种情况移动元素的个数是 n - i + 1 ，把所有情况加起来平均，平均时间复杂度为以下等差数列求和，抛去常数 2 后为 O(n)：

$\frac{1} {n + 1} \sum_{i=1}^{n + 1} (n - i +1)$ = $\frac{1} {n + 1}( n + (n - 1)) + …… + 1 + 0 )$ = $\frac{1} {n + 1}$ $\frac{n(n + 1)}{2}$ = $\frac{n}{2}$

删除操作

假设我们有 $a_1$ - $a_4$ 的顺序表， $a_2$ 要请假离队，那么我们要把它删除， $a_3$ 、 $a_4$ 要往前移动。

算法流程：删除顺序表 L 中第 i (1 <= i <= L.length)个位置的元素，成功则返回 true，并将被删除的元素用引用变量 e 返回，否则返回 false。

示例代码：


bool ListDelete(SqList &L, int i, ElemType &e){
    if(1 > i || i > L.length) return false;
    
    e = L.data[i - 1];
    for(int j = i; j < L.length; j ++)
        L.data[j - 1] = L.data[j];
    return true;
}

最好情况：删除表尾元素，（即 i = n），无需移动元素，时间复杂度为 O(1)。

最坏情况：删除表头元素，即（i = 1），需要移动除第一个元素外的所有元素，时间复杂度为 O(n)。

平均情况：假设删除每个元素的概率均等，一共有 n 种情况，每种情况的概率为 $\frac{1}{n}$ 。需要移动元素的个数是 n - i，把所有情况加起来平均，时间复杂度为 O(n)：