第18章动态数组的实现

课程目录第18章动态数组的实现

18、动态数组的实现：用malloc实现动态数组、动态数组的扩容策略、动态二维数组

说实话，C语言的数组有个硬伤——长度必须在编译时就定死。你想想看，很多时候我们写程序，根本不知道用户会输入多少数据。比如一个日志系统，今天可能只记录10条，明天突然来了1000条。静态数组怎么搞？要么浪费空间，要么直接崩掉。

这时候就得靠动态数组了。说白了，就是用malloc在堆上申请内存，运行时想多大就多大。我当年刚入行时，第一次用动态数组解决了一个内存溢出的bug，那种感觉……嗯，就像手里突然多了一把万能钥匙。

18.1 用malloc实现动态数组

动态数组的核心就三步：申请、使用、释放。别小看第三步，我见过太多人只记得malloc，不记得free。结果程序跑几天，内存就爆了。

先看一个最简单的例子：

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    printf("请输入数组长度：");
    scanf("%d", &n);

    // 动态申请 n 个 int 的空间
    int *arr = (int *)malloc(n * sizeof(int));
    if (arr == NULL) {
        printf("内存申请失败！\n");
        return 1;
    }

    // 像普通数组一样使用
    for (int i = 0; i < n; i++) {
        arr[i] = i * 10;
    }

    // 打印
    for (int i = 0; i < n; i++) {
        printf("arr[%d] = %d\n", i, arr[i]);
    }

    // 千万别忘了释放
    free(arr);
    return 0;
}

关键点：

malloc返回的是void*，记得强制类型转换。虽然C语言允许隐式转换，但我个人习惯显式写出来，代码更清晰。
一定要检查返回值是否为NULL。内存申请失败不是开玩笑的，我曾经在嵌入式设备上遇到过堆空间不足，程序直接跑飞。
free之后，建议把指针置为NULL。防止出现野指针，这是很多隐蔽bug的根源。

18.2 动态数组的扩容策略

动态数组的好处是能长大。但怎么长大？直接realloc？没那么简单。扩容策略选不好，性能会惨不忍睹。

我给大家讲三种常见的扩容策略，每种我都踩过坑：

策略	描述	时间复杂度	适用场景
固定增量	每次扩容增加固定大小（如每次加10个元素）	O(n) 均摊	数据量小且可预测
倍数扩容	每次扩容为当前容量的2倍	O(1) 均摊	大多数通用场景
指数衰减	初始扩容倍数大，后续逐渐减小	O(1) 均摊	内存敏感型系统

我个人最推荐倍数扩容，尤其是2倍扩容。为什么？因为均摊下来，每次插入的时间复杂度是O(1)。你想想看，如果每次只加1个元素，那每次扩容都要把旧数据全部拷贝一遍，数据量一大就卡死了。

来看一个带扩容的动态数组实现：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;
    int size;      // 当前元素个数
    int capacity;  // 当前容量
} DynamicArray;

// 初始化
void initArray(DynamicArray *arr, int initCapacity) {
    arr->data = (int *)malloc(initCapacity * sizeof(int));
    arr->size = 0;
    arr->capacity = initCapacity;
}

// 扩容（2倍策略）
void expandArray(DynamicArray *arr) {
    int newCapacity = arr->capacity * 2;
    int *newData = (int *)realloc(arr->data, newCapacity * sizeof(int));
    if (newData == NULL) {
        printf("扩容失败！\n");
        return;
    }
    arr->data = newData;
    arr->capacity = newCapacity;
    printf("扩容：%d -> %d\n", arr->capacity / 2, arr->capacity);
}

// 插入元素
void pushBack(DynamicArray *arr, int value) {
    if (arr->size >= arr->capacity) {
        expandArray(arr);
    }
    arr->data[arr->size++] = value;
}

// 释放
void freeArray(DynamicArray *arr) {
    free(arr->data);
    arr->data = NULL;
    arr->size = 0;
    arr->capacity = 0;
}

int main() {
    DynamicArray arr;
    initArray(&arr, 4);

    for (int i = 0; i < 20; i++) {
        pushBack(&arr, i);
    }

    for (int i = 0; i < arr.size; i++) {
        printf("%d ", arr.data[i]);
    }
    printf("\n");

    freeArray(&arr);
    return 0;
}

避坑指南：

我曾经在项目中直接用realloc，没检查返回值。结果有一次内存不够，realloc返回NULL，原来的指针也丢了——内存泄漏加数据丢失，双重打击。记住：realloc失败时，原内存块不变，但返回NULL。所以一定要用临时变量接收返回值。

18.3 动态二维数组

二维数组的动态实现，说白了就是「数组的数组」。但实现方式有讲究，我见过两种主流做法：

方法一：用指针数组

int **matrix = (int **)malloc(rows * sizeof(int *));
for (int i = 0; i < rows; i++) {
    matrix[i] = (int *)malloc(cols * sizeof(int));
}

这种方法的优点是每行可以有不同的长度（锯齿数组）。缺点是内存不连续，访问时缓存命中率低。我在做图像处理时吃过这个亏——数据量大时，非连续内存的遍历速度能差好几倍。

方法二：用一维数组模拟二维

int *matrix = (int *)malloc(rows * cols * sizeof(int));
// 访问 matrix[i][j] 等价于 matrix[i * cols + j]

这种方法内存连续，访问效率高。我个人的习惯是：只要行列固定，就用一维模拟二维。代码稍微绕一点，但性能好很多。

来看一个完整的动态二维数组例子：

#include <stdio.h>
#include <stdlib.h>

int main() {
    int rows = 3, cols = 4;

    // 方法一：指针数组
    int **arr1 = (int **)malloc(rows * sizeof(int *));
    for (int i = 0; i < rows; i++) {
        arr1[i] = (int *)malloc(cols * sizeof(int));
    }

    // 赋值
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            arr1[i][j] = i * cols + j;
        }
    }

    // 释放（注意顺序：先释放行，再释放列指针）
    for (int i = 0; i < rows; i++) {
        free(arr1[i]);
    }
    free(arr1);

    // 方法二：一维模拟二维
    int *arr2 = (int *)malloc(rows * cols * sizeof(int));
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            arr2[i * cols + j] = i * cols + j;
        }
    }
    free(arr2);

    return 0;
}

注意：

释放二维数组时，顺序很重要。先释放每一行的内存，再释放行指针数组。反过来会怎么样？嗯，你试试就知道了——内存泄漏没跑了。

知识体系总览

下面这张图把本章的核心逻辑串起来了，建议你多看几遍：

动态数组这东西，说难不难，说简单也不简单。关键是要理解内存管理的本质——你向系统借了一块地，用完了得还回去。不还？系统会找你算账的（内存泄漏）。还错了？程序直接崩溃（野指针）。

我个人建议，刚开始学的时候，每写一个malloc，就立刻写对应的free。养成习惯后，你会发现动态数组其实比静态数组灵活得多，也强大得多。