探索顺序表与动态数组的实现奥秘

小白向大厂看齐

522人浏览 · 2026-06-15 06:00:00

小白向大厂看齐 · 2026-06-15 06:00:00 发布

探索顺序表与动态数组的实现奥秘

1. 什么是顺序表？

顺序表是数据结构中最基础的线性结构之一，它通过连续的存储空间来存储数据元素。简单来说，顺序表就是用一段物理地址连续的存储单元依次存储数据元素的线性结构。

顺序表的核心特点

1. 连续存储

所有元素在内存中占据连续的存储空间
元素之间的逻辑关系通过物理位置来体现

2. 随机访问

由于内存连续，可以通过下标直接访问任意位置的元素
访问时间复杂度为 O(1)

3. 动态扩展

现代顺序表通常支持动态扩容
当空间不足时自动分配更大的存储空间

顺序表的三要素

成员	作用	为什么需要
`data`	指向动态分配的数组空间	数据总要有个地方存，而且空间大小要能动态变化
`size`	当前元素个数	我需要知道现在存了几个元素，才能确定在哪插入、删除
`capacity`	最大容量	我需要知道还剩多少空间，才能决定要不要扩容

2. 为什么需要顺序表？

学C语言的时候，数组用得很顺手。int arr[100]，存啥都快，按下标访问瞬间就到。

但有一个问题：如果我事先不知道要存多少数据呢？开100可能不够，开10000又浪费。更麻烦的是，我想在中间插入一个元素，后面的全部要手动往后挪；想删一个元素，后面的全部要往前挪。每次写这些重复代码，既繁琐又容易出错。

那些高级语言里的ArrayList、vector是怎么解决这些问题的？底层其实就是一个能自动扩容的动态数组——也就是顺序表。

这篇文章记录我从零实现一个顺序表的全过程。不光把代码写出来，更重要的是把每一步为什么这样设计讲清楚。

3. 数据结构设计：为什么需要这三个成员？

动手写代码之前，先问自己一个问题：管理一堆动态数据，最少需要哪些信息？

答案是三个：

转化成代码：

typedef struct _SeqList {
    DataType* data;   // 存储管理 —— 动态内存分配
    int size;         // 访问管理 —— 当前元素个数
    int capacity;     // 容量管理 —— 最大容量
} SeqList;

三个字段，各司其职。少任何一个，都会在某些操作上遇到麻烦：

没 size：不知道尾插该写哪，不知道遍历到哪结束
没 capacity：不知道什么时候该扩容，每次插入都要提心吊胆
没 data：数据根本没地方放

4. 错误处理设计：为什么不用 return -1？

C语言里最常见的错误处理是 return -1。但这有两个问题：

语义模糊：-1到底是什么意思？是参数错了、内存不够了、还是数据不存在？过两周再看代码，自己都忘了。
容易漏判：调用方可能忘记检查返回值，程序带着错误继续跑，最后在完全不相干的地方崩溃。

我的做法是用枚举把每个错误类型钉死：

typedef enum ErrorCode {
    SUCCESS = 0,            // 成功
    ERR_MALLOC = 1,         // 内存分配失败
    ERR_INVALID_PARAM = 2,  // 参数不合法
    ERR_INVALID_OPERATOR,   // 操作不合法
    ERR_DATA_NOT_EXISTS     // 数据不存在
} ErrorCode;

调用方看到ERR_MALLOC，立刻知道是内存分配出问题了，不用猜。

另外加一个调试宏：

#define LOG(fmt, ...) \
    printf("[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)

程序跑到LOG("插入位置无效")时，自动打印出是哪个文件的哪一行出了问题。比满屏printf找bug效率高太多。

5. 初始化与销毁：为什么 free 后还要置 NULL？

#define SEQLIST_INIT_CAPACITY 100  // 初始容量：不大不小，减少频繁扩容

ErrorCode SeqListInit(SeqList* pList) {
    assert(pList != NULL);  // 传个空指针进来？直接崩，别让错误扩散
    pList->data = malloc(SEQLIST_INIT_CAPACITY * sizeof(DataType));
    if (NULL == pList->data) {
        LOG("申请空间失败");
        return ERR_MALLOC;  // 明确告诉调用方：内存不够了
    }
    pList->size = 0;
    pList->capacity = SEQLIST_INIT_CAPACITY;
    return SUCCESS;
}

void SeqListDestory(SeqList* pList) {
    assert(NULL != pList);
    free(pList->data);
    pList->data = NULL;   // 关键！防止悬空指针
    pList->size = 0;
    pList->capacity = 0;
}

销毁时把三个成员全部归零，不是啰嗦，是防御。

free之后，data还指着一个已经被回收的地址。如果不置NULL，后续代码有可能误用这个指针——这是C语言里最臭名昭著的bug：悬空指针。运气好直接崩溃，运气不好悄无声息地破坏其他数据，调试到怀疑人生。

6. 插入操作：为什么用 memmove 而不是 memcpy？

顺序表插入的核心动作是：把插入位置及之后的元素全部往后挪一位，腾出空位，填入新值。

ErrorCode SeqListInsert(SeqList* pList, int pos, DataType val) {
    assert(NULL != pList);
    if (pos < 0 || pos > pList->size) {
        LOG("插入数据时，插入位置无效");
        return ERR_INVALID_PARAM;
    }
    if (pList->capacity == pList->size) {
        printf("顺序表容量不足，需要扩容\n");
        return ERR_MALLOC;
    }

    // 核心：把 pos 开始到末尾的元素整体后移一位
    memmove(pList->data + pos + 1, pList->data + pos,
            sizeof(DataType) * (pList->size - pos));

    pList->data[pos] = val;
    pList->size++;
    return SUCCESS;
}

为什么用 memmove 而不是 memcpy？

这是最容易踩的一个坑。我们挪动的是同一块数组内相邻的元素，比如把下标2_{5的元素搬到3}6。源地址和目标地址有重叠！

memcpy的设计前提是源和目标不重叠，遇到重叠的情况结果是未定义的。memmove内部处理了重叠逻辑，保证结果正确。数组里自己挪自己，必须用memmove。

为什么 pos 可以等于 size？

如果pos == size，memmove的第三个参数(size - pos)等于0，什么都不挪，直接在数组末尾写入新值。这恰好就是尾插的语义。

于是尾插和头插可以直接复用Insert，各一行代码：

ErrorCode SeqListPushBack(SeqList* pList, DataType val) {
    return SeqListInsert(pList, pList->size, val);  // 在末尾插入
}

ErrorCode SeqListPushFront(SeqList* pList, DataType val) {
    return SeqListInsert(pList, 0, val);  // 在开头插入
}

这就是复用的思想：基础操作写一次，复合操作调基础操作。后面的删除系列完全同理。

7. 删除操作：插入的镜像

删除是插入的逆过程：把删除位置之后的元素整体往前挪一位，覆盖掉要删的元素。

ErrorCode SeqListErase(SeqList* pList, int pos) {
    assert(NULL != pList);
    if (pos < 0 || pos >= pList->size) {
        LOG("删除数据时，删除位置无效:%d，当前数据量:%d", pos, pList->size);
        return ERR_INVALID_PARAM;
    }

    memmove(pList->data + pos, pList->data + pos + 1,
            sizeof(DataType) * (pList->size - pos - 1));

    pList->size--;
    return SUCCESS;
}

头删尾删各一行，和插入系列的设计完全对称：

ErrorCode SeqListPopBack(SeqList* pList) {
    return SeqListErase(pList, pList->size - 1);  // 删最后一个
}

ErrorCode SeqListPopFront(SeqList* pList) {
    return SeqListErase(pList, 0);  // 删第一个
}

8. 删除所有指定值：为什么不用循环 Find + Erase？

最直观的想法：先Find找到目标值的位置，再调Erase删掉，反复做直到找不到为止。但这个做法的时间复杂度是O(N²)——每删一个就要把后面的元素整体挪一次。

我用双指针法一趟遍历搞定：

int SeqListRemoveAll(SeqList* pList, DataType val) {
    assert(NULL != pList);
    if (pList->size == 0) return 0;

    int count = 0;         // 统计删了多少个
    int writeIndex = 0;    // "写指针"：下一个要写入的位置

    for (int i = 0; i < pList->size; i++) {
        if (pList->data[i] != val) {
            pList->data[writeIndex++] = pList->data[i];  // 保留
        } else {
            count++;  // 跳过
        }
    }
    pList->size = writeIndex;  // 更新有效元素数
    return count;
}

思路：想象两个指针，i是"读指针"，从左往右扫描每个元素。writeIndex是"写指针"，指向"下一个要保留的位置"。遇到不等于目标值的元素就搬到writeIndex位置，遇到目标值就跳过。遍历完，writeIndex就是新的size。

一趟遍历，时间O(N)，空间O(1)。

9. 扩容机制：为什么是二倍扩容？

ErrorCode SeqListEnsureEnoughSpace(SeqList* pList) {
    assert(NULL != pList);

    if (SeqListIsFull(pList)) {
        // 先接到临时变量，防止 realloc 失败导致原指针丢失
        DataType* p = realloc(pList->data,
                              2 * pList->capacity * sizeof(DataType));
        if (p != NULL) {
            LOG("扩容成功！新容量 = %d", pList->capacity * 2);
            pList->data = p;
            pList->capacity *= 2;
            return SUCCESS;
        } else {
            LOG("扩容失败！扩容空间不足");
            return ERR_MALLOC;
        }
    }
    return SUCCESS;
}

为什么用临时变量接 realloc 的返回值？

realloc失败时返回NULL。如果直接写pList->data = realloc(...)，一旦失败，pList->data被赋成NULL，原来的空间地址就丢了——内存泄漏。先用临时变量p判断，成功再赋值，这是必须养成的习惯。

为什么每次扩 2 倍，而不是扩一个固定值（比如 +10）？

这关系到性能。假设初始容量100，我要插入1000个元素：

每次扩 +10：需要扩容90次，每次扩容都要把旧数据拷贝到新空间。第1次拷100个，第2次拷110个……总拷贝量约O(N²)，巨慢。
每次扩 2 倍：100 → 200 → 400 → 800 → 1600。只需扩容4次。总拷贝量约100+200+400+800=1500个元素，是O(N)级别。

二倍扩容让每次插入的均摊时间降到O(1)，这就是所有动态数组底层都采用倍增策略的原因。

10. 测试验证

#include "SeqList.h"

void showInt(DataType val) {
    printf("%d ", val);
}

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

    // 尾插 5 个元素
    for (int i = 1; i <= 5; i++) SeqListPushBack(&list, i * 10);
    printf("尾插："); SeqListPrint(&list, showInt);

    // 头插 99
    SeqListPushFront(&list, 99);
    printf("头插："); SeqListPrint(&list, showInt);

    // 位置 2 插入 55
    SeqListInsert(&list, 2, 55);
    printf("插入："); SeqListPrint(&list, showInt);

    // 查找
    printf("查找55：位置%d\n", SeqListFind(&list, 55));
    printf("查找999：位置%d\n", SeqListFind(&list, 999));

    // 获取首尾
    DataType val;
    SeqListGetFront(&list, &val);
    printf("头部：%d\n", val);
    SeqListGetBack(&list, &val);
    printf("尾部：%d\n", val);

    // 删除位置2、头删、尾删
    SeqListErase(&list, 2);
    SeqListPopFront(&list);
    SeqListPopBack(&list);
    printf("删除后："); SeqListPrint(&list, showInt);

    // RemoveAll
    SeqListClear(&list);
    int d[] = {10, 20, 30, 20, 40, 20, 50};
    for (int i = 0; i < 7; i++) SeqListPushBack(&list, d[i]);
    SeqListRemoveAll(&list, 20);
    printf("RemoveAll："); SeqListPrint(&list, showInt);

    // 扩容
    SeqListClear(&list);
    for (int i = 0; i < 150; i++) {
        SeqListEnsureEnoughSpace(&list);
        SeqListPushBack(&list, i);
    }
    printf("扩容后：size=%d, capacity=%d\n",
           (int)SeqListGetSize(&list), (int)SeqListGetCapacity(&list));

    SeqListDestory(&list);
    return 0;
}

运行结果

在这里插入图片描述

结果解读

操作	预期结果	实际输出	验证
尾插	10 20 30 40 50	10 20 30 40 50	✅
头插 99	99 10 20 30 40 50	99 10 20 30 40 50	✅
位置 2 插入 55	99 10 55 20 30 40 50	一致	✅
查找 55	位置 2	位置2	✅
查找 999	-1	位置-1	✅
删除位置2 + 头删 + 尾删	20 30 40	20 30 40	✅
RemoveAll 20	10 30 40 50	10 30 40 50	✅
扩容到 150 个	size=150, cap=200	size=150, capacity=200	✅

11. 设计决策速查

设计决策	为什么这样选
用结构体而不是裸数组	数据和元信息（size/capacity）绑定，避免外部管理分散
用枚举错误码而不是 -1	语义明确，调用方一目了然
用 memmove 而不是 memcpy	自己挪自己，地址重叠，memcpy不可靠
尾插/头插复用 Insert	基础操作写一次，复合操作调基础操作，减少重复
RemoveAll 用双指针法	一趟遍历O(N)，避免反复删除的O(N²)
销毁后 data 置 NULL	防悬空指针，是C语言的基本防御习惯
realloc 先用临时变量接	防 realloc 失败导致原指针丢失，内存泄漏
二倍扩容而不是固定增量	均摊O(1)插入，避免频繁扩容的O(N²)开销