C语言顺序表实现教程：结构体封装、动态扩容与插入删除详解

1. 顺序表到底在学什么，为什么绕不开它

先聊点实在的。顺序表这个名字听起来很“课程”，但它本质上就是“数组的封装”，或者更直白一点：用一块连续的内存空间，按顺序存储一组同类型的数据，并且能自由地增、删、改、查。初学者容易把它想复杂，其实你天天写的 int arr[100] 就是一个不带功能的顺序表，而课程里让你实现的顺序表，不过是在这个数组外面套了一层“管理逻辑”而已。

那为什么数据结构的入门课几乎都从顺序表开始？两个原因：第一，它最贴近计算机的内存模型，数组本身就是内存的线性映射，理解顺序表等于理解“程序怎么组织数据”，这比一上来就学链表、树要平滑得多；第二，它暴露了数据结构最重要的一对矛盾——操作简单和性能代价，插入一个元素要挪动一大堆数据，删除一个元素也要搬来搬去，这些细节能帮你建立“算法复杂度”的直觉，后面学什么都能往回联想。

这篇文章适合谁？当然是刚学到“线性表”这一章的在校生、准备考研408的自学者，还有那些想补数据结构短板的非科班开发者。我默认你已经有了一点点C语言基础，至少知道什么叫数组、什么叫函数、什么叫指针，不需要你是个C语言高手——顺序表刚好卡在“初学者能写、老手能优化”这个位置，我会把每一步的前因后果都写出来，尤其是那些上课不细讲、自己看书会踩坑的点。

顺序表的应用场景其实比你想象的多。操作系统内核的任务队列、编译器的符号表、内存分配器里的空闲块记录，很多底层组件都用类似顺序表的结构来管理连续数据。虽然真实工程里更多用动态扩容版本（也就是自动增长的顺序表），但原理和我们下面要写的这套一模一样。

2. 动手前，先把C语言这四样预备知识盘清楚

很多人写顺序表写得一塌糊涂，不是逻辑问题，而是C语言地基不稳。我见过太多同学把结构体指针传来传去传成一团浆糊，或者忘记给指针分配内存就直接 p->data[0] = 1 导致段错误。磨刀不误砍柴工，把这四样东西过一遍，后面写代码会顺很多。

2.1 结构体：顺序表的“容器”

顺序表需要同时管理两类信息：一是数据存在哪、能存多少，二是当前实际存了多少。这两个信息必须打包在一起，否则每次函数调用都要传两个参数三个参数，代码难看且容易漏。用结构体把事情封装起来，写代码传一个指针就够了，可维护性高一大截。

C语言里这么定义：

c复制typedef struct {
    int *data;      // 指向数据区首地址，以后用动态内存分配
    int capacity;   // 容量，这个数组最多能装多少个元素
    int size;       // 当前实际元素个数
} SeqList;

这里多提一句 typedef 的作用：它给结构体类型起了个别名叫 SeqList，这样以后声明变量写 SeqList list; 而不用写 struct SeqList list;。纯粹是省事的写法，但能减少很多麻烦，尤其当结构体名字比较长的时候。还有个小细节，data 可以定义为任意类型的指针，今天我用的例子是 int，但只要你愿意，改成 double *、char * 甚至另一个结构体指针都可以，顺序表存储的数据类型和它的实现逻辑是解耦的，这也是“数据结构”里“结构”和“数据”分离的雏形。

2.2 动态内存分配：让表能长能缩

很多教材会先用“定长数组”讲顺序表，也就是在结构体里直接写 int data[MAXSIZE];。这种写法简单直观，但有一个硬伤：MAXSIZE 到底定多少？定大了浪费内存，定小了存不下数据。工程上几乎都采用动态分配方案，运行时根据实际需要申请内存，不够用就再扩容。

动态分配主要就两个函数：malloc 和 free，配 realloc 扩容。

• malloc(n * sizeof(int)) 向系统申请一块能放下 n 个 int 的内存，返回 void*，所以通常要强转成 int*。
• realloc(ptr, newSize) 在原有 ptr 指向的内存块基础上，重新分配一块 newSize 大小的内存，返回新的首地址，原数据会自动拷贝过去。
• free 负责释放不再使用的内存，防止内存泄漏。

这里有个新手特别容易犯的错：malloc之后没判断是否成功。内存申请可能失败，返回 NULL，如果直接拿着 NULL 去写数据，程序当场崩溃。所以规范写法是分配完立刻判空，失败就给用户一个明确提示。

2.3 指针与传参：函数该传值还是传地址

写顺序表时，你会频繁写这样的函数：

c复制void InitList(SeqList *list);
void InsertList(SeqList *list, int pos, int val);

为什么都要加 *？因为 C 语言默认是值传递。如果你写 void InitList(SeqList list)，那函数内部拿到的是结构体的一份拷贝，你在里面改了 list.size，外面的原变量纹丝不动——传了半天等于白干。所以凡是需要修改结构体内容的函数，一律传结构体指针。

这里我再提供一个实用建议：只读函数（比如查询长度、读取某个位置的元素）可以传结构体本身，或者更严谨地传 const SeqList *list，既能防止误改，又能省去拷贝结构体的开销。有些人觉得这是小题大做，但养成这个习惯，对你以后读别人源码、写更大项目很有帮助。

2.4 边界与约定：数组下标从0开始这件事

C语言的数组下标永远从0开始，顺序表的下标和这个保持一致，逻辑上更顺。但那“第几个元素”和“下标是多少”经常差1，写代码时容易搞混。我给自己定了一个规矩：接口上对外用“位置”描述，即0表示第一个元素，实现时直接用这个值当下标。这能避免很多 pos-1 这种来回换算带来的心智负担。

顺序表还有一个隐性约定：size 永远是“已占用元素个数”，同时等于“下一个空闲位置的下标”。比如 size 为3，说明data[0]、data[1]、data[2]放了东西，新元素应该插到data[3]。这个约定简单但极其重要，你不会可以推导出来，我见过有人分别用两个变量记录“已存数目”和“尾部位置”，两个值一不同步就乱了，完全没必要。

3. 初始化与扩容：所有操作的基石

这个阶段的目标是：把顺序表从“一片未使用的内存”变成“一个能正式使用的空表”，并且为后面的数据猛增做好准备。我见过很多初学者跳过这一步，直接用未初始化的结构体变量往里塞数据，然后得到一堆随机值，查半天不知道哪里错了——根因就是没做初始化。

3.1 初始化函数：别偷懒，每一个字段都要赋值

初始化函数要做的事很明确：给 data 分配初始内存、设置 capacity、把 size 清0。初始容量不用太大，常见做法是给个4或者8，因为大部分表一开始都是空的，给多了浪费，等真的不够了再扩容也不迟。

c复制#define INIT_CAPACITY 4

void InitList(SeqList *list) {
    list->data = (int *)malloc(INIT_CAPACITY * sizeof(int));
    if (list->data == NULL) {
        printf("内存分配失败\n");
        exit(1);  // 严重错误，直接退出程序
    }
    list->size = 0;
    list->capacity = INIT_CAPACITY;
}

注意这里我用 list->data 而不是 list.data，因为 list 本身是个指针，访问成员需要用箭头运算符。不少人在这儿栽跟头：定义了 SeqList *list; 然后写 list->data = ...，但别忘了这个 list 指针自己也得先有合法的地址空间。常见的两种做法：一是在 main 里声明 SeqList list; 再取地址 &list 传给初始化函数；二是用 malloc 动态分配一个 SeqList 结构体本身，再把这个指针传进去。两种都行，但第二种多了一层的释放（要 free(list) 两次：先释放 data，再释放结构体），初学者很容易搞漏，所以我的建议是先用第一种，变量在栈上，不依赖你手动释放。

函数里的 exit(1)，有些教材可能不讲，这里简单说明：它在 stdlib.h 里声明，用来终止整个程序。内存分配失败属于“无路可走”的情况——数据区都没了，后面的操作全没意义，所以直接终止比返回一个错误码更省事。日常工作中这种做法会比较粗暴，但在学习阶段可以让代码逻辑简单清晰。

3.2 双倍扩容：顺手推导一下为什么乘2

顺序表有一项隐藏能力：插入元素前判断容量，不够就扩容。扩容策略是成倍增长，而不是每次多申请几个。为什么是2倍？这是“均摊复杂度”的典型场景：虽然扩容那一次 O(n) 地搬数据很贵，但翻倍之后又要 n 次插入才会再次扩容，平摊下来每次插入的代价接近 O(1)。如果每次只多申请1个空间，总会遇到“插1个数据就搬一次家”，插入的均摊复杂度就退化成了 O(n)。

c复制void ExpandCapacity(SeqList *list) {
    if (list->size < list->capacity) return;   // 容量还有富余，不扩容
    int newCap = list->capacity * 2;
    int *newData = (int *)realloc(list->data, newCap * sizeof(int));
    if (newData == NULL) {
        printf("扩容失败\n");
        exit(1);
    }
    list->data = newData;
    list->capacity = newCap;
}

这里有个极易踩的坑：realloc 可能返回新的内存地址，也可能返回和原来一样的地址。它还有可能在失败时返回 NULL——注意，此时原来的内存块并没有被释放，如果你直接写 list->data = realloc(...)，一旦返回值是 NULL，你就把原来的指针覆盖丢了，这块内存也就再也释放不了了。所以务必先用临时指针 newData 接住返回值，判空确认无误后再赋值给 list->data。这个细节在底层开发里是“教科书级陷阱”，我当年面试就遇到过类似的问题，直接决定了能不能过。

扩容是翻倍还是1.5倍？这其实是个工程权衡。翻倍实现简单，均摊下来也是常数级；1.5倍的内存利用率稍高一点，但多一次乘法运算。学习阶段用2倍，思路越清晰越好。

4. 插入与删除：顺序表的核心操作全拆解

插入和删除是线性表最核心的两个操作，也是考试和面试的重点。它们的共同点在于：都要移动数据，区别只是方向不同。这一个部分我打算写细一点，因为里面全是细节，任何一步差1，程序要么越界要么漏数据。

4.1 插入操作：先把位置合法性讲透

要在顺序表的 pos 位置插入一个元素 val。位置合法必须同时满足两个条件：pos >= 0 且 pos <= size。注意，pos == size 是允许的，相当于在表尾部追加一个新元素；而 pos > size 是非法的，比如表里只有5个元素，你非要插到第8个位置，那中间就会出现“空洞”，这就破坏了顺序表“连续存放”的定义。

插入了怎么办？核心就一句话：从尾部开始，把元素逐个往后挪，给新元素腾出一个空位，再写入。

c复制void InsertList(SeqList *list, int pos, int val) {
    if (list == NULL || pos < 0 || pos > list->size) {
        printf("插入位置非法\n");
        return;
    }
    ExpandCapacity(list);
    
    for (int i = list->size; i > pos; i--) {
        list->data[i] = list->data[i - 1];
    }
    
    list->data[pos] = val;
    list->size++;
}

这段代码里有三个地方值得反复强调：

• 为什么从尾部往前挪，而不是从前往后？ 如果从 pos 位置开始把前面的元素往后覆盖，那就会把相邻的后面元素覆盖掉，数据就损坏了。从尾部开始挪，每个元素只往相邻的后一个位置移动，不会覆盖还没搬走的元素。你可以拿手边的纸片模拟一下，一下就懂了。
• 移动前是否需要担心容量问题？ 不用担心，我在移动之前先调用了 ExpandCapacity，如果容量不够会先扩容，确保 data 数组至少有 size + 1 个空位。这个顺序很重要：先确保有空间，再移动数据。
• list->size 什么时候更新？ 数据移动完、新元素写完，最后再 size++。如果先自增 size，循环的终止条件就变了，容易越界。

插入操作的时间复杂度：最好情况是插在表尾，循环一次不执行，O(1)；最坏情况是插在表头，所有元素都挪一遍，O(n)；平均下来也是 O(n)。这个结论很重要，考试常考，工程选型也靠它——如果频繁在头部插入，顺序表就不是合适的数据结构了，应该考虑链表。

4.2 删除操作：反向思维，从前往后覆盖

删除位置 pos 的元素，要让这个元素“消失”，同时保持连续性。简单粗暴的方式是直接“左移覆盖”：从 pos 的下一个位置开始，把每个元素往前搬运一位，最后一个位置空出来，再把 size 减1。

c复制void DeleteList(SeqList *list, int pos) {
    if (list == NULL || pos < 0 || pos >= list->size) {
        printf("删除位置非法\n");
        return;
    }
    
    for (int i = pos; i < list->size - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    
    list->size--;
    // 可选：把被“抛掉”的那个位置清零，方便调试
    list->data[list->size] = 0;
}

删除位置的合法条件和插入不一样：pos < size，但绝不等于 size。因为 size 是最后一个元素的下一个位置，那里本就没有元素，谈不上删除。很多人会把插入和删除的边界条件记混，干脆和我一样，每次写之前都问自己一句：“这个位置有没有元素？”有就合法，没有就非法。

最后那句 list->data[list->size] = 0 是可选的。不写也不影响逻辑，因为 size 变小之后这个位置就被“逻辑上无视了”，但我们写代码总爱留点调试后路——把这个位置清零，之后你打印整个数组的时候，被删掉的数据不会残留成随机数干扰你判断。这也引出一个观点：释放或删除数据，一定要把自己能控制的位置恢复到可知状态，这是安全编程的好习惯。

删除的时间复杂度也是 O(n)，平均同样 O(n)。从应用场景看，顺序表适合“读多写少尾部操作多”的场景，比如日志缓冲区的追加记录，就是一个标准的尾部插入场景。

4.3 修改与按位查找：最快的两个操作

按位置查找和修改，是顺序表效率最高的操作，因为数组是连续内存，可以直接“跳到指定位置”。时间复杂度 O(1)，不需要遍历。这也是顺序表对比链表最大的优势，链表得从头一个节点一个节点走过去。

c复制int GetElement(SeqList *list, int pos) {
    if (list == NULL || pos < 0 || pos >= list->size) {
        printf("位置越界\n");
        return -1;   // 用 -1 表示失败，但注意 -1 可能是一个合法元素，更好的是返回布尔值
    }
    return list->data[pos];
}

void SetElement(SeqList *list, int pos, int val) {
    if (list == NULL || pos < 0 || pos >= list->size) {
        printf("位置越界\n");
        return;
    }
    list->data[pos] = val;
}

你可能注意到 GetElement 返回 -1 表示出错这种方法有风险：如果表里恰好存的就是 -1 这个数，调用者怎么知道是查到了还是出错了？更严谨的写法是用指针带出结果，函数本身返回成败状态，比如 int GetElement(SeqList *list, int pos, int *out)。学习阶段用 -1 简化问题也能理解，但我建议你有空把这个“错误处理”的思维升级一下——写工程代码时，“返回特殊值”和“状态码独立返回”是两种经典设计，前者简单但有歧义，后者更稳健。无论选哪种，都要意识到边界条件不是小事，而是程序正确性的生命线。

5. 查找、遍历与一些“开窍”的扩展操作

核心操作写完，剩下的就是一些辅助功能。别觉得这部分不重要，去哪查找、怎么遍历，都会反复用到。我单独拿出来说，是因为很多时候程序调试不出结果，就是遍历打印的代码出了毛病——打印的范围错了，你看到的结果永远对不上号。

5.1 按值查找：第一次接触“线性扫描”思想

按值查找就是给你一个数，你在表里从头到尾找第一个相等的元素，返回它的下标；找不到返回 -1。这就是最朴素的“线性扫描”，时间复杂度 O(n)。

c复制int FindElement(SeqList *list, int val) {
    for (int i = 0; i < list->size; i++) {
        if (list->data[i] == val) {
            return i;
        }
    }
    return -1;
}

这个操作没有太多花活，关键是返回值的语义：返回“下标”而不是“第几个元素”或“是否成功”。我遇到过一些人把返回下标和返回布尔值混着用，调用端一会儿判断 if (FindElement(...) != -1)，一会儿又当布尔值 if (FindElement(...))，代码就乱了。建议从写函数的第一天起就明确注释：返回值是什么含义、失败时返回什么。

按值查找有一种优化变体：如果数据本身有序，可以二分查找，复杂度降到 O(log n)。但二分查找要求表必须有序，而且顺序表一旦频繁插入删除，维护有序性的代价不低，所以实际工程里用什么手段查找，取决于“读”和“写”的频率比。这个思路也是数据结构的魅力——没有银弹，只有取舍。

5.2 遍历与打印：调试的正道

写数据结构的小项目时，最常用的调试手段就是“把所有元素按顺序打出来”。遍历本身很简单，但它的作用被我严重低估了很久——早年间我写了半天代码，一运行段错误，根本不知道在哪挂的，后来学乖了：在每个关键函数里加打印，一步步定位问题。现在写复杂数据结构，我甚至会把遍历函数放在最前面写，之后每实现一个函数，都立刻调用遍历验证结果。

c复制void PrintList(SeqList *list) {
    if (list->size == 0) {
        printf("空表\n");
        return;
    }
    for (int i = 0; i < list->size; i++) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

如果你的元素类型不是 int，而是结构体，打印函数就要相应改成结构体成员的打印，逻辑一模一样。另一个小技巧：遍历时打印 size 和 capacity 两个元信息，能帮你快速发现“是不是 size 更新错了”的经典bug——比如 size 忘了加1，元素明明写进数组了，但你只看到了一部分元素。

5.3 去重与倒置：两道经典考研题

顺序表的扩展操作里，去重和倒置是两个高频练习，也是考试常客。去重就是删除重复元素，保留第一次出现的那个；倒置就是把表倒过来。这两种题目都要求“原地”完成，空间复杂度 O(1)，大部分初学者第一反应会新建一个数组来辅助，但这是没有必要的。

去重的实现思路：用两层循环，外层 i 遍历每个位置，内层 j 扫描 i 之前的所有元素，如果发现相同的值就把 i 位置的元素删除。但因为删除操作本身会移动元素，循环的细节要特别注意——删掉当前元素后，后面的元素会前移，外层的 i 要不要回退，这是分歧点。我的做法是换一种思路：维护一个 newSize，把不重复的元素依次往前放，一遍遍历搞定。

c复制void RemoveDuplicates(SeqList *list) {
    if (list->size <= 1) return;
    int newSize = 1;  // 第一个元素一定保留
    for (int i = 1; i < list->size; i++) {
        int j = 0;
        for (; j < newSize; j++) {
            if (list->data[i] == list->data[j]) {
                break;   // 发现重复
            }
        }
        if (j == newSize) {   // 没有重复
            list->data[newSize] = list->data[i];
            newSize++;
        }
    }
    list->size = newSize;
}

这个版本把“删除重复元素”变成了“把不重复元素搬到前面”，思路清晰，而且只需要一次遍历外层循环。时间复杂度 O(n^2)，空间 O(1)，作为练手完全合格。如果你后面学了哈希表，能用 O(n) 解决去重，但那属于另一个话题了，现在重点是理解“覆盖迁移”的思想。

倒置的经典做法是双指针：一个指头，一个指尾，两两交换，向中间靠拢。

c复制void ReverseList(SeqList *list) {
    int left = 0, right = list->size - 1;
    while (left < right) {
        int temp = list->data[left];
        list->data[left] = list->data[right];
        list->data[right] = temp;
        left++;
        right--;
    }
}

记住一个边界：while (left < right) 而不是 <=，因为相等时交换自己没意义，还会白跑一趟。倒置的时间复杂度 O(n)，空间 O(1)，代码量虽短，但考察的就是对下标边界的敏感性，值得反复默写几遍。

6. 写在代码之外：调试、测试与几个过来人的建议

代码写完了，不代表万事大吉。顺序表虽小，坑可不少。我把这些年带新人时最常见的问题整理一下，以及我自己的测试心法，这部分内容教科书上通常不写，但绝对是实战中能救命的。

6.1 高频Bug清单与排查思路

下面这份表格我建议你收藏，写的时候对照自查。很多问题一眼看去是“运行崩溃”，实际根因各不相同，排查思路也不一样。

还有一个非常隐蔽的坑：如果你在多个地方写了函数的声明和定义，但一个函数忘记加 *，你能通过编译却在运行时发现所有结构体字段都没有变化。这时候别急着怀疑算法，先检查函数参数是不是传值而不是传指针。我见过有人调了俩小时才发现 DeleteList(SeqList list, int pos) 少了个星号，非常折磨。所以一开始就养成习惯：需要修改结构体就在参数里加 *，不需要修改就加 const，既明确了意图，又能让编译器帮你抓错误。

6.2 怎么测试顺序表才叫“测全了”

很多人写完代码就在 main 里插入一两个元素，打印一眼觉得“差不多”，就算写完了。但顺序表的边界条件远比你以为的多。我总结了一套“最小测试清单”，建议每次都跑一遍：

1. 创建空表，打印 size，应该为 0；
2. 往尾部连续插入5个元素，再打印，size 应该为 5；
3. 在头部插入元素，检查所有元素是否后移且正确；
4. 在中间位置插入、删除元素，打印验证顺序；
5. 删除尾部元素，size 减1，越界访问不崩溃；
6. 连续插入远超初始容量的元素（比如10个以上），验证扩容逻辑没崩；
7. 删除所有元素到空表，再尝试删除，应该提示位置非法；
8. 使用 free 释放整个表，再运行程序，确认没有内存泄漏（可以用工具检测，比如 Valgrind，或者最简单的是观察程序多次运行后占用内存是否稳定）。

这套清单基本覆盖了正常路径和绝大部分异常路径。你自己动手写完顺序表，如果这8项全部通过，我可以负责任地说：这块你已经入门了。

6.3 动态内存的释放：“用完记得归还”

整个顺序表涉及两块动态内存：结构体内部的 data 指向的数组，以及如果你用 malloc 分配了 SeqList 结构体本身，那个结构体内存的释放。如果只free了结构体而没free data，就内存泄漏；反过来free了 data 但结构体指针丢掉了，也会漏。正确的释放函数长这样：

c复制void DestroyList(SeqList *list) {
    if (list == NULL) return;
    free(list->data);
    list->data = NULL;   // 防止悬空指针
    list->size = 0;
    list->capacity = 0;
}

注意释放之后一定要把 data 置为 NULL，这个习惯特别重要。如果不置空，list 结构体自己还活着，但里面存的地址已经是野指针了，下次不小心调用别的方法可能会操作一块已经释放的内存，这是最难排查的崩溃原因之一。置空后，哪怕真有人误用了 list->data，至少报“空指针”错误，一眼就能看出问题。这一步叫“防御性编程”，在写系统级代码时是基本功。

7. 最后分享三个小技巧，帮你彻底把顺序表吃透

我想分享几个自己在实战中验证过的、能让顺序表学习效果翻倍的小技巧。

技巧一：动手画内存图。 我说真的，每次插入和删除之后，拿出纸笔把数组、size、capacity 三个东西画一遍，模拟三五个元素的操作。尤其是插入和删除的那两个循环，你亲手画一遍数据搬移的过程，比看十遍书都管用。大多数人觉得数据结构抽象，抽象就抽象在指针和下标的关系上，而纸笔恰好能把这个关系可视化。

技巧二：给代码“找茬”。 写完一个函数后，专门往最坏情况想：如果 size 是 0 会发生什么？如果 pos 正好等于 size 会怎样？如果 capacity 刚好满呢？带着这些问题重构你的代码，你会发现原先你写了很多“看似正确但经不起推敲”的语句。这个过程就是训练边界思维的过程，考试题里的“陷阱”百分之八十都是边界情况。

技巧三：学会“物理删除”和“逻辑删除”的取舍。 有些场景下，删除元素实际上不是真的搬动数据，而是打个标记跳过它，这叫逻辑删除，好处是 O(1) 时间删除，坏处是数组里有“废墟”，偶尔要清理。顺序表里传统的物理删除是保持紧凑，这适合大多数场景。但你现在知道还有“逻辑删除”这种方案，以后遇到大文件中间删除一条记录的场景，就知道怎么选型了——这就是数据结构给你的思维肌肉。

顺序表写完之后，建议你立刻去做两个事：一是把它改成存字符串的版本，相当于重新实现一遍但数据类型变了；二是手写一遍双指针倒置，确保不看任何参考代码也能写出来。这两个练完，你的顺序表就算是真的“嚼碎了咽下去”了。数据结构这条路很长，但顺序表是第一个台阶，踏踏实实踩稳，后面爬链表、栈、队列、二叉树的时候，你会发现很多套路都是相似的——管理好连续空间，处理好边界条件，剩下的就只是时间问题了。