线性表之顺序表：从底层原理到工程实践

各位同学，今天我们来聊聊线性表中最基础、最常用的一种实现——顺序表。说白了，顺序表就是用一块连续的内存空间，把数据一个挨一个地存起来。你想想看，这就像一排编号的储物柜，每个柜子放一个元素，找起来特别快。

我在做嵌入式开发的头几年，几乎天天跟顺序表打交道。那时候内存资源紧张，用得好能省不少事，用不好嘛……嗯，后面我会讲到一些坑。

1. 顺序表的定义与初始化

先看定义。顺序表的核心数据结构通常长这样：

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];  // 静态数组存储元素
    int length;          // 当前元素个数
} SeqList;

这里我用了静态数组，好处是简单直接，坏处是大小固定。初始化时，把 length 置为 0 就行：

void InitList(SeqList *L) {
    L->length = 0;
    // 静态数组不需要额外分配内存
}

我个人习惯在初始化时把 data 数组全部清零，虽然 C 标准不要求，但能避免一些野值带来的调试困扰。有一次我在项目中排查一个 bug，查了两天才发现是未初始化的数组里残留了上一步的数据……从那以后，我初始化时都会顺手 memset 一下。

2. 插入与删除操作

插入和删除是顺序表的核心操作，也是容易出问题的地方。

插入操作

在位置 i 插入一个元素，需要把 i 及之后的所有元素往后挪一位。代码实现：

int InsertList(SeqList *L, int i, int e) {
    // 检查合法性
    if (i < 1 || i > L->length + 1) return -1;
    if (L->length >= MAX_SIZE) return -1;  // 表满

    // 从后往前挪
    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = e;
    L->length++;
    return 0;
}

注意这里是从后往前挪，如果从前往后挪，数据会被覆盖掉。我曾经见过一个新手同事写反了，结果插入后数据全乱了。

删除操作

删除位置 i 的元素，把后面的元素往前挪：

int DeleteList(SeqList *L, int i, int *e) {
    if (i < 1 || i > L->length) return -1;

    *e = L->data[i-1];
    for (int j = i; j < L->length; j++) {
        L->data[j-1] = L->data[j];
    }
    L->length--;
    return 0;
}

3. 查找与遍历

查找分两种：按位置查找和按值查找。

按位置查找很简单，直接下标访问：

int GetElem(SeqList *L, int i, int *e) {
    if (i < 1 || i > L->length) return -1;
    *e = L->data[i-1];
    return 0;
}

按值查找需要遍历：

int LocateElem(SeqList *L, int e) {
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] == e) return i + 1;  // 返回位序
    }
    return 0;  // 没找到
}

遍历就更直接了，一个 for 循环搞定。我在调试嵌入式设备时，经常写一个 PrintList 函数来打印所有元素，方便看数据对不对。

4. 动态数组的实现与扩容策略

静态数组大小固定，用起来不够灵活。实际项目中，我更喜欢用动态数组——说白了就是根据需要动态扩容。

动态顺序表的结构：

typedef struct {
    int *data;      // 指向动态分配的内存
    int length;     // 当前元素个数
    int capacity;   // 当前容量
} DynSeqList;

初始化时先分配一小块内存：

void InitDynList(DynSeqList *L, int initCap) {
    L->data = (int *)malloc(initCap * sizeof(int));
    L->length = 0;
    L->capacity = initCap;
}

插入时如果满了，就扩容：

int InsertDynList(DynSeqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) return -1;

    // 检查是否需要扩容
    if (L->length >= L->capacity) {
        int newCap = L->capacity * 2;  // 扩容策略：翻倍
        int *newData = (int *)realloc(L->data, newCap * sizeof(int));
        if (newData == NULL) return -1;  // 扩容失败
        L->data = newData;
        L->capacity = newCap;
    }

    // 挪位插入
    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = e;
    L->length++;
    return 0;
}

扩容策略很关键。我见过有人每次只扩一个元素，结果频繁 realloc，性能惨不忍睹。常用的策略有两种：

策略	说明	优点	缺点
翻倍扩容	每次容量翻倍（×2）	均摊时间复杂度 O(1)	可能浪费空间
固定增量	每次增加固定大小（如 10）	空间利用率高	频繁扩容时性能差

我个人更推荐翻倍扩容。虽然偶尔会多占点内存，但整体性能稳定。在嵌入式场景下，如果内存特别紧张，可以改成 1.5 倍扩容——这是 Java 的 ArrayList 用的策略，空间和时间比较均衡。

知识体系总览

下面这张图把顺序表的核心知识点串起来了，你可以对照着复习：

好了，顺序表的核心内容就这些。记住：它适合读多写少的场景，比如配置表、查找表。如果你要频繁插入删除，还是考虑链表吧。

---

公众号:蓝海资料掘金营，微信deep3321