C语言实现顺序表：从结构体设计到动态扩容全解析

想当年我学数据结构，第一关就是顺序表。当时只觉得这是最简单的线性结构，不就是个数组嘛，有什么好学的。后来才意识到，顺序表这套东西，表面是代码，实际是给你立规矩：存储空间怎么管理，下标怎么算，边界怎么卡，都是后面链表、栈、队列、乃至树和图的地基。地基没打牢，后面越学越虚。

这篇文章就从C语言实现的角度，把顺序表从头到尾拆一遍。适合刚碰数据结构、在数组和指针之间还晕头转向的同学，也适合期末复习赶到顺序表这章想快速理清思路的兄弟。看完你至少能独立写完一个能跑、能改、能查、不会崩的顺序表。

1. 为什么入门第一个数据结构是顺序表

1.1 顺序表和数组的关系：先破除一个误解

很多人觉得顺序表就是数组，这个说法对了一半。数组是编程语言提供的原生类型，它真的就是一块连续的内存，下标访问直接算地址，速度快得离谱。而顺序表是在数组之上封装出来的一种数据结构，它规定了逻辑上的元素关系是"一个挨着一个"，同时还要自己维护长度、容量、还有各种操作规则。

说得直白点：数组是原材料，顺序表是把原材料加工后的半成品。你直接拿数组写代码，得自己管数组多大、存了多少个、满了怎么办，这些散落在业务逻辑里，写着写着就乱套。顺序表把这堆事情统一收编，对外只暴露"插入""删除""查找"这些操作，内部怎么倒腾，调用者不用关心。

这个思路就是数据结构的精髓：逻辑结构和物理结构解耦。逻辑上元素有先后顺序，物理上它们在内存里连续存放，顺序表就是这两者统一的产物。

1.2 顺序表的逻辑定义和存储形态

从逻辑上讲，顺序表的元素之间是一对一的关系，除了第一个元素没有前驱、最后一个元素没有后继，其他每个元素都有一个直接前驱和一个直接后继。这个和其他线性表没有区别，真正区分它的是物理存储方式：所有元素在内存中占用一段连续的存储空间，像火车车厢一样一节挨一节。

这带来两个直接后果。第一个是随机访问能力强，知道下标就能用下标直接算出地址，O(1)时间访问任意元素。第二个是插入删除必须大量移动元素，你在中间塞一个元素，从那个位置往后的所有元素都得往后挪一格。这个代价是O(n)，数组越大，挪得越痛苦。

生活中最贴近的类比就是看电影排队。你往队伍中间插进去，后面所有人都得往后错一位；有人从中间走了，后面的人得往前补位。顺序表就是这条队伍，只不过它是一支不能断开的、站得笔直的队伍。

1.3 顺序表解决了什么问题

顺序表的存在，核心解决的是"有限空间里的有序管理"问题。原始数组给了你一整块空间，但空间的利用率、元素的动态变化、越界的保护，这些都需要你自己操心。顺序表把这些问题标准化了：

• 空间不够时自动扩容，你不用在业务代码里到处写realloc
• 插入删除时统一处理元素移动，不用每次手工算移动范围和方向
• 越界访问有统一的检查入口，虽然不保证能拦截所有错误，但至少给了你一个可控的边界

这些能力今天看起来不值钱，但它们是后面所有复杂数据结构的设计理念雏形。你学会了顺序表怎么管理连续空间，后面学哈希表时的开放寻址法、学堆时的数组存储，都会有似曾相识的感觉。

2. 动手写之前，先把结构体设计明白

2.1 静态数组方案的瓶颈在哪里

网上很多教程先用静态数组练手，声明一个ElemType data[MAXSIZE]，再配一个length记录当前元素个数。这种做法用来理解概念没问题，但一放到真实场景就难堪了：空间小了不够用，大了浪费内存，而且一旦数组满了，插入操作只能返回失败，没有任何补救余地。

我在初学的时候就被这种东西坑过。练习题目里数据量很小，静态数组够用，但后来自己写一个小项目想复用这套代码，数据量稍大就直接溢出。然后我被迫回到业务代码里改MAXSIZE，改完这边又担心别的场景太小，整个人在"调大空间"和"担心浪费"之间反复横跳。

所以这次直接采用动态数组方案。用malloc申请堆空间，容量不够就realloc扩展，这样表和数组解耦，容量跟着数据走，才算真正理解了顺序表作为"容器"的定位。

2.2 结构体的三个字段缺一不可

动态方案下，结构体需要三个字段：

c复制typedef struct {
    ElemType *data;      // 指向堆区数组的指针
    int length;          // 当前元素个数（已用长度）
    int capacity;        // 当前分配的总容量
} SeqList;

这三个字段各有分工，少了哪个都会出问题。data是数组的起始地址，所有元素都通过它来访问；length是逻辑长度，它决定了遍历的上界和插入的最终位置；capacity是物理容量，它决定了当前还能不能继续插入。

很多初学朋友只写data和length，把容量问题完全抛掉。等到插入的时候发现"长度已经等于数组大小"，只能自己找链表里申请大数组，没有任何统一的处理入口。加上capacity以后，扩容的判断逻辑就变成一句非常干净的比较：if (list->length == list->capacity)，一步到位。

注意：ElemType是元素类型的统一别名。写成int可以直接跑通，但为了后面复用，建议在头部用typedef int ElemType;定义，这样以后想把表改成存放结构体或浮点数，只需要改这一行。

2.3 谁负责管理内存，提前把责任划清

顺序表涉及堆内存，就一定要在头文件或代码注释里明确接口的"所有权"规则。这是工程里特别容易踩坑的地方：谁malloc了，谁就应该free；表传进函数，函数只负责操作，不负责释放。

从设计上讲，顺序表这个类型对外暴露以下接口就够了：

• InitList：初始化，申请初始容量空间
• DestroyList：销毁，释放所有堆内存
• ListInsert：在指定位置插入元素
• ListDelete：删除指定位置元素，拿回被删的值
• LocateElem：按值查找，返回下标
• ListPrint：遍历打印，方便调试

先在脑子里把这个接口清单列清楚，再动手写代码，就不会在实现过程中越写越乱，也不会出现"这个函数到底归谁管"的纠结。

3. 核心操作的代码实现与拆解

3.1 初始化：堆内存申请之后立刻判空

初始化的工作很朴素：申请一段初始容量的内存，把length设为0，capacity设为初始值。但这个函数虽然短，却有两个细节直接影响后面的稳定性。

c复制#define INIT_CAPACITY 8

void InitList(SeqList *list) {
    list->data = (ElemType *)malloc(sizeof(ElemType) * INIT_CAPACITY);
    if (list->data == NULL) {
        printf("内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    list->length = 0;
    list->capacity = INIT_CAPACITY;
}

第一个细节是malloc返回后用if判断。堆分配不保证一定成功，内存吃紧的时候会返回NULL，这时候你对NULL进行写入，就是典型的空指针解引用，程序直接崩。初学者最容易忽略这一点，总觉得自己的机器内存大得离谱，不可能分配失败。但代码是要给别人用的，你自己的机器没事，不代表别人的环境没事。

第二个细节是初始容量的选择。我用8，纯粹是经验值。太小的话，插入几个元素就要频繁扩容，性能白白浪费在realloc上面；太大则一上来就占着几十上百个ElemType的堆空间，对于只需要存三五个元素的场景来说太奢侈。8到16之间都是合理的选择，这个和C++标准库vector的初始策略也差不多。

3.2 插入操作：先移动还是先检查，顺序不能错

插入是顺序表里最讲究的操作。要在第i个位置插入新元素，从最后一个元素开始，到第i个元素为止，所有元素都往后挪一个位置，然后再把新元素放进去，length加1。

写这个函数的顺序，我的建议是：先做所有检查，再移动元素，最后执行插入。

c复制bool ListInsert(SeqList *list, int pos, ElemType elem) {
    // 1. 检查表是否合法、位置是否越界
    if (list == NULL || pos < 0 || pos > list->length) {
        return false;
    }

    // 2. 满了就扩容
    if (list->length == list->capacity) {
        if (!ExpandCapacity(list)) {
            return false;
        }
    }

    // 3. 从后往前移动元素
    for (int i = list->length; i > pos; i--) {
        list->data[i] = list->data[i - 1];
    }

    // 4. 写入新元素
    list->data[pos] = elem;
    list->length++;

    return true;
}

这里的关键点在第三个步骤的移动方向：必须从后往前挪。假设在位置0插入一个元素，所有元素都要后移。如果你从前往后挪，第一个元素被覆盖掉了，后面的数据就全乱了套。从后往前挪，每一步覆盖的都是"已经挪完的、不再需要的旧位置"，安全性有保证。

至于允许插入的位置范围，pos = list->length是合法的，代表尾插；pos = 0也是合法的，代表头插，只是头插要移动所有元素，代价很大。中间位置则是常见操作，移动的元素个数是length - pos个，这个值也是后面分析时间复杂度的依据。

提示：bool类型需要包含<stdbool.h>。如果你用的编译器不支持，可以用int和0/1代替，但可读性会差一些。

3.3 删除操作：覆盖比释放更重要

删除的逻辑和插入正好反向：把第i个位置后面的所有元素往前移动一位，覆盖掉要删除的元素，然后length减1。如果需要保留被删元素的值，就在移动之前先用一个临时变量接住。

c复制bool ListDelete(SeqList *list, int pos, ElemType *deleted) {
    if (list == NULL || pos < 0 || pos >= list->length) {
        return false;
    }

    if (deleted != NULL) {
        *deleted = list->data[pos];
    }

    for (int i = pos; i < list->length - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->length--;

    return true;
}

这个循环的写法是i = pos; i < length - 1; i++，每次把data[i + 1]赋给data[i]，也就是"后面的往前补"。循环结束时，length位置上的那个旧数据其实还在内存里，但因为length已经减1了，逻辑上看不到它，下次插入的时候会被直接覆盖，不需要显式清理。

一个常见的错误是删除最后一个元素：如果pos = length - 1，循环条件i < length - 1一开始就不成立，循环体不执行，只是长度减1，这样反而是对的，因为最后一个元素"删除"本身就只是向前沿缩小。但如果你把循环写成i <= pos或者i <= length - 1，就会越界访问，访问到不属于当前表的地址。

3.4 查找和扩容：一个靠遍历，一个靠realloc

按值查找的思路很直接，从头到尾扫一遍，找到第一个匹配的元素，返回它的下标。扫描不到就返回-1。

c复制int LocateElem(SeqList *list, ElemType elem) {
    for (int i = 0; i < list->length; i++) {
        if (list->data[i] == elem) {
            return i;
        }
    }
    return -1;
}

这个函数有两个习惯要养成。一是返回-1表示"没找到"，因为下标是非负的，-1成了一个天然的哨兵。二是这个函数只支持整型和指针这类可以直接用==比较的类型，如果你把ElemType换成结构体，就得改成逐字段比较或者单独写回调函数。

扩容函数是动态方案的心脏：

c复制bool ExpandCapacity(SeqList *list) {
    int newCapacity = list->capacity * 2;
    ElemType *newData = (ElemType *)realloc(list->data, sizeof(ElemType) * newCapacity);
    if (newData == NULL) {
        return false;
    }
    list->data = newData;
    list->capacity = newCapacity;
    return true;
}

扩容倍数我定为2倍。这个"翻倍"不是随手写的，背后是均摊分析：如果每次增加固定的几个元素，比如每次+1，那么连续插入n个元素的总移动次数是O(n^2)；如果每次容量翻倍，插入n个元素需要扩容O(log n)次，平摊下来每次插入的代价是O(1)。这就是为什么所有主流动态数组都选择倍增而不是等差数列增长。

realloc可能有两种行为：原地扩大，或者搬家到新地址。无论哪种，原来内存中的数据都会被原封不动地搬运过去，所以你不需要手动释放旧内存，也不要再持有旧的data指针。用中间变量newData接住realloc返回值，是一个保险的做法：万一扩展失败，旧的next内存被保留，你还可以继续用旧表，而不是直接变成NULL。

3.5 销毁和打印：收尾和debug的习惯

销毁顺序表就一行：free(list->data)，然后把指针置NULL，长度和容量归零。强调一点，free之后必须置NULL。释放后的指针是悬空指针，你虽然不能再解引用它，但它本身还保存着那块地址，如果不手动置NULL，后面要是不小心又调一次DestroyList，就会对同一块内存重复free，这是未定义行为，轻则崩溃重则堆损坏，排查的时候极其痛苦。

c复制void DestroyList(SeqList *list) {
    if (list->data != NULL) {
        free(list->data);
        list->data = NULL;
    }
    list->length = 0;
    list->capacity = 0;
}

打印函数反而是调试阶段利用率最高的。每次操作之后打印一遍全表，你能立刻看见数据长什么样。遍历时要用length而不是capacity，否则会把没存入数据的空位也打出来，一堆乱值干扰判断。

4. 完整代码与运行验证

4.1 完整代码的组织结构

把前面这些函数组装成一个可以跑起来的完整程序，注意每个函数的位置和依赖关系，方便你直接拿去看、去改。

c复制#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int ElemType;

typedef struct {
    ElemType *data;
    int length;
    int capacity;
} SeqList;

#define INIT_CAPACITY 8

void InitList(SeqList *list);
void DestroyList(SeqList *list);
bool ExpandCapacity(SeqList *list);
bool ListInsert(SeqList *list, int pos, ElemType elem);
bool ListDelete(SeqList *list, int pos, ElemType *deleted);
int LocateElem(SeqList *list, ElemType elem);
void ListPrint(SeqList *list);

int main() {
    SeqList list;
    InitList(&list);

    ListInsert(&list, 0, 10);
    ListInsert(&list, 1, 20);
    ListInsert(&list, 2, 30);
    ListInsert(&list, 1, 15);   // 在位置1插入15
    ListPrint(&list);           // 期望输出: 10 15 20 30

    int deleted;
    ListDelete(&list, 2, &deleted);
    printf("删除了 %d\n", deleted);
    ListPrint(&list);           // 期望输出: 10 15 30

    int idx = LocateElem(&list, 30);
    printf("30 的位置: %d\n", idx);  // 期望输出: 2

    DestroyList(&list);
    return 0;
}

void InitList(SeqList *list) {
    list->data = (ElemType *)malloc(sizeof(ElemType) * INIT_CAPACITY);
    if (list->data == NULL) {
        printf("内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    list->length = 0;
    list->capacity = INIT_CAPACITY;
}

void DestroyList(SeqList *list) {
    if (list->data != NULL) {
        free(list->data);
        list->data = NULL;
    }
    list->length = 0;
    list->capacity = 0;
}

bool ExpandCapacity(SeqList *list) {
    int newCapacity = list->capacity * 2;
    ElemType *newData = (ElemType *)realloc(list->data, sizeof(ElemType) * newCapacity);
    if (newData == NULL) {
        return false;
    }
    list->data = newData;
    list->capacity = newCapacity;
    return true;
}

bool ListInsert(SeqList *list, int pos, ElemType elem) {
    if (list == NULL || pos < 0 || pos > list->length) {
        return false;
    }
    if (list->length == list->capacity) {
        if (!ExpandCapacity(list)) {
            return false;
        }
    }
    for (int i = list->length; i > pos; i--) {
        list->data[i] = list->data[i - 1];
    }
    list->data[pos] = elem;
    list->length++;
    return true;
}

bool ListDelete(SeqList *list, int pos, ElemType *deleted) {
    if (list == NULL || pos < 0 || pos >= list->length) {
        return false;
    }
    if (deleted != NULL) {
        *deleted = list->data[pos];
    }
    for (int i = pos; i < list->length - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->length--;
    return true;
}

int LocateElem(SeqList *list, ElemType elem) {
    for (int i = 0; i < list->length; i++) {
        if (list->data[i] == elem) {
            return i;
        }
    }
    return -1;
}

void ListPrint(SeqList *list) {
    for (int i = 0; i < list->length; i++) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

整个代码的逻辑流是这样的：main里先InitList拿到一张空表，然后连续插入若干元素，再测试删除、查找的功能，最后DestroyList释放所有资源。你可以照着这个结构扩展自己的测试用例。

4.2 一次典型运行过程的现场分析

我把上面的代码跑了一遍，输出是这样的：

code复制10 15 20 30 
删除了 20
10 15 30 
30 的位置: 2

这段运行结果看着简单，但每一步背后都有值得推敲的点。

先看插入。ListInsert(&list, 0, 10)是尾插，因为此刻length = 0，所以pos = 0和pos = length是重合的，循环不执行，直接写入。ListInsert(&list, 1, 15)这个操作值得注意，此时表里有10、20、30三个元素，要在位置1插入15。循环从i = 3开始，把data[2]的30挪到data[3]，把data[1]的20挪到data[2]，然后data[1]写入15。最终的结果是10 15 20 30，20和30被推后了一位，15补进了空出来的位置。这就是中间插入时元素移位的全过程。

再看删除。ListDelete(&list, 2, &deleted)删位置2的元素，此时表里是10 15 20 30，位置2是20。先把20存入deleted，然后循环把data[3]的30覆盖到data[2]，长度从4变成3。打印出来就是10 15 30。注意，data[3]里还残留着30的旧值，但因为length = 3，遍历永远不会碰到它，它就成了"逻辑上不存在、物理上残留"的幽灵数据。

4.3 边界情况测试：空表、满表、越界

真正检验代码质量的不是正常流程，而是边界情况。我把这些情况都测了一遍，你可以直接照着在你自己代码里跑：

这里有一点要特别强调：插入时的pos = length是合法的，删除时的pos = length - 1是最后一个元素的位置，删除pos = length就是错的。很多同学把这两个边界搞混，写插的时候能对，到删的时候就把pos >= length写成pos > length，这样删除最后一个元素时就会越界访问到data[length]这个不属于表的元素，取值是随机的，结果不可预测。

5. 常见问题与排查技巧实录

5.1 初始化之后忘记检查指针是不是NULL

这是我在帮某个同学调试时遇到的最典型问题。他的代码跑了没几步就崩溃，我一看InitList里malloc完直接赋值，压根没判空。后来确实在构造大表时内存分配失败，指针成了NULL，后面所有写入都打在空地址上，程序直接段错误。

排查这种问题有个笨办法，但很有效：在InitList和ExpandCapacity里都加上分配失败的打印，把errno和当前尝试分配的字节数打出来。如果失败，你能明确看到是哪一次分配出的问题，而不是面对一个莫名其妙的崩溃无从下手。

5.2 为什么我的插入操作数据总是丢

最经典的错误是把移动方向搞反了。你想在位置pos插入，往前挪的应该是pos到length - 1这段，也就是从后往前覆盖。如果写反成从前往后，你先把data[0]的值赋给data[1]，data[0]的值被覆盖之前，data[1]的老值就已经丢了，所有数据整体错乱，像是"丢了两三个元素又多了两个重复值"。

另一个丢数据的原因是pos判断写错。比如pos >= list->length的判断误把length当作合法位置，结果插入到了data[length]，但此时下一轮插入又从这个位置开始，数据就被覆盖了。建议每次插入后用ListPrint验证，别急着写下一个功能。

5.3 查找返回-1的逻辑陷阱

LocateElem返回-1表示没找到，这个约定本身没问题，但调用方容易踩坑。如果你把返回值直接当作下标用，比如list->data[LocateElem(...)] = xxx，那么查不到的时候就变成list->data[-1]，这是访问数组首地址的前一个单元，在大多数环境下是未定义行为，不崩是你运气好，崩了就是血泪教训。

正确的使用方式是先拿返回值做判断，再决定是否访问：

c复制int idx = LocateElem(&list, 30);
if (idx != -1) {
    // 找到才操作
}

5.4 扩容之后原数据不见了怎么办

先不要慌，想一想realloc的行为。realloc能做的是尽量原地扩展；原地空间不够，它会在新地址分配一块更大的空间，把旧数据整体拷过去，然后释放旧内存。从使用者的角度看，逻辑上数据没丢，data指针指向新地址，length保持不变，只有capacity变了。

如果你看到扩容后数据丢了，多半是代码里把realloc的返回值直接用给了list->data，而realloc失败时返回NULL，把NULL覆盖给了list->data，原来的指针也丢了，既没数据也释放不了内存。我以前踩过一次，内存泄漏是小事，数据全没了得重新跑一遍流程才要命。

5.5 关于命名和代码习惯的几点心得

顺序表代码本身不难，但代码习惯会影响后面学链表。我个人的习惯是：函数名统一用List前缀，一眼就知道是这张表的操作；位置参数统一叫pos而不是index或idx，因为后面学树和图时会用到index的场合更多，提前区分能减少语义混淆；表指针统一用list，不要用l这种难认的单字符变量名，代码维护起来舒服得多。

调试的时候，我强烈建议在每个操作后都打印一遍表。这虽然让输出变得有点啰嗦，但你能直接看到每一步变换是否符合预期。所有debug技巧里，最土但最有效的就是"打印中间状态"。真到了顺序表都跑不通的阶段，指望调试器单步跟踪反而容易把自己绕进去，因为你原本就还没完全掌握逻辑。

顺序表这个问题，我后来在好几个场景里都用到了它的思想。做一个小型内存池时，空闲块的管理就是顺序表；写一个日志缓存区时，追加写入加定期清理也是顺序表的变形。数据结构这个东西，学的时候觉得抽象，但用的时候到处都是它的影子。你把这套C语言的实现练扎实了，后面的路会顺很多。