2.1 线性表与顺序表

线性表的逻辑定义与基本操作，顺序存储的实现、插入删除的移动规律与复杂度分析。

线性表的定义

• $a_1$ 是唯一的”第一个”元素，称为表头元素；$a_n$ 是唯一的”最后一个”元素，称为表尾元素。
• 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。
• $i$ 称为元素 $a_i$ 在线性表中的位序——注意位序从 1 开始，而 C 数组下标从 0 开始。

线性表的特点：元素个数有限；元素具有逻辑上的顺序性；每个元素都是单个数据元素；数据类型都相同（每个元素占用相同大小的存储空间）；表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

基本操作

InitList(&L);            // 初始化表，构造一个空的线性表
Length(L);               // 求表长
LocateElem(L, e);        // 按值查找
GetElem(L, i);           // 按位查找：获取第 i 个位置的元素
ListInsert(&L, i, e);    // 插入：在第 i 个位置插入元素 e
ListDelete(&L, i, &e);   // 删除：删除第 i 个位置的元素，并用 e 返回
PrintList(L);  Empty(L);  DestroyList(&L);

顺序表：线性表的顺序存储

用一组地址连续的存储单元依次存储线性表中的数据元素，使逻辑上相邻的两个元素在物理位置上也相邻，就得到了顺序表。

设每个元素占 $\ell$ 个存储单元，第一个元素的地址为 $\mathrm{LOC}(A)$，则

因此顺序表最主要的特点是随机访问：通过首地址和元素序号可在 $O(1)$ 时间内找到指定元素。

类型定义

// 静态分配：数组大小在编译时确定
#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];  // 顺序表的元素
    int length;              // 当前长度
} SqList;

// 动态分配：存储空间在运行时由 malloc 申请
#define InitSize 100
typedef struct {
    ElemType *data;          // 指示动态分配数组的指针
    int MaxSize, length;
} SeqList;
// 初始化：L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);

基本操作的实现

下面的动画演示了三种核心操作。试着在不同位置插入、删除，观察需要移动的元素个数如何随位置变化：

1bool ListInsert(SqList &L, int i, ElemType e) {
2    if (i < 1 || i > L.length + 1)  // 判断 i 是否合法
3        return false;
4    if (L.length >= MaxSize)        // 存储空间已满
5        return false;
6    for (int j = L.length; j >= i; j--)
7        L.data[j] = L.data[j - 1];  // 后移
8    L.data[i - 1] = e;              // 放入 e
9    L.length++;
10    return true;
11}

插入：从后往前，依次后移

在第 $i$ 个位置插入元素 e，需要把第 $i$ 个到第 $n$ 个元素依次后移一位，空出位置 $i$ 再放入 e。注意必须从表尾开始移动，否则会覆盖尚未移动的元素。

• 合法的插入位置为 $1 \le i \le n + 1$（可以插在表尾之后）。
• 最好情况：在表尾插入（$i = n + 1$），不移动元素，$O(1)$。
• 最坏情况：在表头插入（$i = 1$），移动 $n$ 个元素，$O(n)$。
• 平均情况：设在每个位置插入的概率相同，$p_i = \frac{1}{n+1}$，则平均移动次数为

删除：从前往后，依次前移

删除第 $i$ 个元素，需要把第 $i+1$ 到第 $n$ 个元素依次前移一位。

• 合法的删除位置为 $1 \le i \le n$。
• 最好 $O(1)$（删表尾），最坏 $O(n)$（删表头）。
• 平均移动次数：$\displaystyle\sum_{i=1}^{n} \frac{1}{n}(n - i) = \frac{n-1}{2}$。

查找

• 按位查找 GetElem(L, i)：直接返回 L.data[i-1]，时间复杂度 $O(1)$。
• 按值查找 LocateElem(L, e)：顺序比较，平均比较次数 $\frac{n+1}{2}$，时间复杂度 $O(n)$。

顺序表的优缺点

算法设计题精讲

408 的算法题通常要求：①给出基本设计思想；②用 C/C++ 写出算法；③说明时间与空间复杂度。下面两道是顺序表的经典题型。

void Reverse(int R[], int from, int to) {
    for (int i = 0; i < (to - from + 1) / 2; i++) {
        int temp = R[from + i];
        R[from + i] = R[to - i];
        R[to - i] = temp;
    }
}
void Converse(int R[], int n, int p) {
    Reverse(R, 0, p - 1);
    Reverse(R, p, n - 1);
    Reverse(R, 0, n - 1);
}

void DeleteX(SqList &L, ElemType x) {
    int k = 0;
    for (int i = 0; i < L.length; i++)
        if (L.data[i] != x)
            L.data[k++] = L.data[i];
    L.length = k;
}

即时练习