线性表之顺序表：从定义到实战

大家好，我是你们的嵌入式工程师老朋友。今天咱们来聊聊数据结构里最基础、也最常用的一种结构——顺序表。

说实话，我刚开始学数据结构时，觉得顺序表不就是个数组嘛，有啥好讲的？后来在项目中吃过亏才明白，会用数组和真正理解顺序表，是两码事。今天我就把这些年踩过的坑、总结的经验，一次性说清楚。

一、顺序表的定义

先看定义。顺序表，英文叫 Sequential List，本质上是数组的升级版。我习惯这样定义它的结构体：

#define MAX_SIZE 100  // 最大容量

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

这里有两个关键点：

• data：实际存数据的地方，连续内存
• length：当前有多少个有效元素

你可能会问：为什么不直接用数组？嗯，因为数组本身不记录长度，你得自己维护一个变量。顺序表把这个变量封装进去了，用起来更安全。

二、顺序表的初始化

初始化很简单，就是把表清空。我见过不少新手忘了初始化就直接用，结果读到一堆垃圾值。

void InitList(SeqList *L) {
    L->length = 0;  // 长度置0
    // data数组不用清零，因为length控制了有效范围
}

为什么不用清data数组？因为length=0意味着没有有效元素，你读data[0]也是未定义行为。省掉这个操作，能提升一点性能——虽然微乎其微，但嵌入式开发里，这种细节积累起来就很可观。

三、顺序表的插入与删除

插入和删除是顺序表的核心操作。咱们先看插入。

3.1 插入操作

插入的核心逻辑：把插入位置后面的元素全部后移，腾出空位。

int Insert(SeqList *L, int pos, int elem) {
    // 1. 检查合法性
    if (pos < 1 || pos > L->length + 1) {
        return -1;  // 位置非法
    }
    if (L->length >= MAX_SIZE) {
        return -1;  // 表已满
    }
    
    // 2. 从后往前移动元素
    for (int i = L->length; i >= pos; i--) {
        L->data[i] = L->data[i-1];
    }
    
    // 3. 插入新元素
    L->data[pos-1] = elem;
    L->length++;
    
    return 0;
}

这里有个细节：为什么从后往前移动？你想想看，如果从前往后移，后面的元素会被覆盖掉。从后往前移，每个元素先挪到后面，前面的位置就空出来了。

3.2 删除操作

删除和插入是镜像操作：把删除位置后面的元素全部前移。

int Delete(SeqList *L, int pos, int *elem) {
    if (pos < 1 || pos > L->length) {
        return -1;
    }
    
    *elem = L->data[pos-1];  // 保存被删元素
    
    // 从前往后移动元素
    for (int i = pos; i < L->length; i++) {
        L->data[i-1] = L->data[i];
    }
    
    L->length--;
    return 0;
}

注意这里是从前往后移，和插入正好相反。我刚开始写时总搞混，后来记住一句话：插入从后往前，删除从前往后。

四、顺序表的查找与修改

4.1 按值查找

查找就是遍历，找到返回位置，找不到返回-1。

int LocateElem(SeqList *L, int elem) {
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] == elem) {
            return i + 1;  // 返回逻辑位置（从1开始）
        }
    }
    return -1;
}

这里有个约定：返回的位置是从1开始的逻辑位置，而不是数组下标。这样做的好处是，用户不用关心底层是数组实现，直接说"第3个元素"就行。

4.2 按位查找与修改

按位查找就简单了，直接通过下标访问——这是顺序表最大的优势：随机存取。

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

int UpdateElem(SeqList *L, int pos, int newElem) {
    if (pos < 1 || pos > L->length) {
        return -1;
    }
    L->data[pos-1] = newElem;
    return 0;
}

修改和查找的时间复杂度都是O(1)，这是链表比不了的。我在做嵌入式数据采集系统时，经常需要快速修改某个传感器的数据，用顺序表就特别合适。

五、知识体系总览

下面这张图，是我梳理的顺序表知识结构，帮你快速建立整体认知：

六、避坑指南与实战经验

最后，分享几个我这些年踩过的坑：

• 边界检查不能省：我曾经在插入时忘了检查表是否已满，结果数据把内存写穿了，整个系统崩溃。从那以后，我写任何操作都会先做边界检查。
• 位置从1开始还是从0开始？我建议对外接口统一从1开始，内部实现用0。这样用户更直观，代码也更清晰。
• 动态扩容要谨慎：如果使用动态数组，扩容时建议每次翻倍（比如从100扩到200），而不是只加1。否则频繁扩容会严重影响性能。

好了，顺序表的内容就讲到这里。记住一句话：顺序表是数组的封装，但比数组更安全、更好用。下一节咱们聊链表，那又是另一番天地了。

---