顺序表

顺序表用数组实现，是最简单也最常用的存储方式。核心操作包括插入、删除、查找。

顺序表的插入

在第 i 个位置插入元素 x，需要将第 i 个到最后一个元素依次后移一位。

#define MaxSize 100
typedef struct {
    int data[MaxSize];
    int length;  // 当前长度
} SqList;

// 在第 i 个位置插入元素 x（i 从 1 开始）
bool ListInsert(SqList &L, int i, int x) {
    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.data[i - 1] = x;
    L.length++;
    return true;
}

顺序表的删除

删除第 i 个位置的元素，需要将第 i+1 个到最后一个元素依次前移一位。

// 删除第 i 个位置元素，用 e 返回
bool ListDelete(SqList &L, int i, int &e) {
    if (i < 1 || 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];  // 元素前移
    L.length--;
    return true;
}

复杂度推导

插入操作：最好情况（插在表尾）移动 0 个元素；最坏情况（插在表头）移动 n 个元素；平均移动 $\frac{n}{2}$ 个元素。因此：

$T_{insert}(n) = O(n)$

删除操作：同理，平均移动 $\frac{n-1}{2}$ 个元素，$T_{delete}(n) = O(n)$。

按位查找：通过下标直接访问，$T_{get}(n) = O(1)$。

习题

习题 1

在长度为 n 的顺序表中，在第 i（1≤i≤n+1）个位置插入一个元素，需要移动的元素个数为（ ）

A. n-i+1 B. n-i C. i D. i-1

习题 2

如何实现线性表的遍历？