顺序表示

真题练习

关于顺序表，一般不会直接考察本节中介绍的这些操作，因为太简单了。更多的是考察基于顺序表（数组）的 算法设计，但是这些操作是更高级算法设计的基础。

顺序表定义

顺序表（Sequential List） 是一种常见的数据结构，用于存储一组元素，并按照它们在内存中的物理顺序来排列和访问这些元素。顺序表通常由一个 数组 或 列表 构成，其中每个元素都占据一个连续的内存位置，并且可以通过索引值来访问。

假设线性表 $A=(a_1,a_2,\ldots,a_n)$ 的起始地址为 $\operatorname{LOC}(A)$，每个元素占用 $L=\operatorname{sizeof}(\text{Elem})$ 字节。若数组下标从 0 开始，则第 $i$ 个逻辑元素 $a_i$（$1\le i\le n$）的存储地址为

这就是顺序表能够随机访问的原因：给定逻辑位置 $i$，只需一次地址计算即可定位元素。

• 顺序表 优点：
  • 随机访问性强：顺序表支持通过索引直接访问元素，访问速度快，时间复杂度为 $O(1)$。
  • 空间使用连续：顺序表中的元素存储在连续的内存块中，这有助于提高缓存的局部性，从而提高访问速度。
  • 操作简单：无需处理复杂的指针操作。
• 顺序表 缺点：
  • 固定大小或调整大小的开销：对于静态数组，大小是固定的，如果预分配的空间不足或过大，会导致内存浪费或数组溢出。动态数组可以重新分配大小，但这会增加时间和空间开销。
  • 插入和删除的时间开销：如果要在顺序表的中间插入或删除元素，可能需要移动大量的元素，时间复杂度为 $O(n)$。

常见操作复杂度

操作	前提或说明	时间复杂度
按逻辑位置访问	位置合法	$O(1)$
按值查找	无序顺序表需逐项比较	$O(n)$
在第 $i$ 个位置插入	最多移动 $n-i+1$ 个元素	$O(n)$
删除第 $i$ 个元素	最多移动 $n-i$ 个元素	$O(n)$

移动次数与边界检查

顺序表插入和删除的核心不是“写入或清除一个位置”，而是保持有效元素连续。长度为 (n) 时，在第 (pos) 个逻辑位置插入，需把原来的第 (pos) 至第 (n) 个元素后移，共移动 (n-pos+1) 个元素；删除第 (pos) 个元素后，原来的第 (pos+1) 至第 (n) 个元素前移，共移动 (n-pos) 个元素。因此首部操作最坏、尾部操作最省移动，但二者仍需要先检查位置是否合法。

实现时可把顺序表的不变量写成：0 <= length && length <= MAXSIZE，并且有效元素恰好位于 data[0] 到 data[length - 1]。插入必须从尾部向后复制，删除必须从当前位置向前复制；若方向反了，尚未复制的元素会被覆盖。返回元素值的指针也应在位置检查通过后再写入。

操作

数据结构定义

以下代码定义了一个顺序表 SeqList，它使用 固定大小的数组 data 来存储元素，length 记录当前表的长度。InitList 函数初始化顺序表，设置 长度为 0，表示空表。

#define MAXSIZE 100
typedef struct {
    ElementType data[MAXSIZE];
    int length;
} SeqList;

void InitList(SeqList *L) {
    L->length = 0;
}

插入

在第 pos 个逻辑位置（从 1 开始）插入新元素 e。首先检查 插入位置合法性 和 空间是否已满，然后从尾部向后移动元素，为插入留出位置，最后将元素插入并更新长度。合法范围是 $1\le pos\le n+1$。

bool Insert(SeqList *L, int pos, ElementType e) {
    if (L->length == MAXSIZE || pos < 1 || pos > L->length + 1) {
        return false;
    }
    for (int i = L->length; i >= pos; i--) {
        L->data[i] = L->data[i - 1];
    }
    L->data[pos - 1] = e;
    L->length++;
    return true;
}

删除

删除第 pos 个逻辑元素（从 1 开始），并通过指针返回删除的元素值。删除后将该位置后的所有元素 前移，最后更新长度。合法范围是 $1\le pos\le n$。

bool Delete(SeqList *L, int pos, ElementType *e) {
    if (pos < 1 || pos > L->length) {
        return false;
    }
    *e = L->data[pos - 1];
    for (int i = pos; i < L->length; i++) {
        L->data[i - 1] = L->data[i];
    }
    L->length--;
    return true;
}

查找操作

在线性表中 顺序查找 第一个值等于 e 的元素，返回其逻辑位置（从 1 开始）；若未找到，返回 0。

int LocateElem(SeqList L, ElementType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;
        }
    }
    return 0;
}

获取元素

获取顺序表中第 pos 个元素，返回值通过指针 *e 输出。若位置非法则返回 false。

bool GetElem(SeqList L, int pos, ElementType *e) {
    if (pos < 1 || pos > L.length) {
        return false;
    }
    *e = L.data[pos - 1];
    return true;
}

判空

判断顺序表是否为空，直接判断 length 是否为 0。

bool IsEmpty(SeqList L) {
    return L.length == 0;
}

清空

清空顺序表，只需将 length 置 0，无需实际删除元素，等价于逻辑上的清空。

void ClearList(SeqList *L) {
    L->length = 0;
}

长度

返回当前顺序表的长度，即有效元素个数。

int Length(SeqList L) {
    return L.length;
}