第43章 动态数组

动态数组（Dynamic Array）是一种在程序运行时可以灵活调整大小的数组结构，它克服了静态数组编译时确定大小的限制，能够根据实际需求动态分配和释放内存。动态数组是处理不确定规模数据的重要工具，也是后续链表（第44章）、**高精度（第42章）**等五级考点的内存基础。

与 GESP 五级的关系：五级大纲虽未单列"动态数组"为独立知识块，但链表节点的创建（new）、高精度大数组的分配都依赖动态内存管理。掌握本章有助于理解指针、堆内存与扩容策略。

43.1 动态数组的基本概念

43.1.1 定义

动态数组是指在程序运行期间通过内存分配函数（如 C 的 malloc、realloc，C++ 的 new、delete[]）创建的数组，其大小可以在运行时根据需要进行调整（扩容或缩容），无需在编译时预先确定。

43.1.2 与静态数组的对比

示例静态数组：int arr[10]; 编译时固定长度 10； 示例动态数组：int* arr = new int[n]; $n$ 为运行时输入的变量。

43.1.3 核心优势

1. 灵活性：可根据数据量分配内存，无固定容量限制；
2. 可扩展：运行中数据增多时支持扩容；
3. 内存利用率：仅按需分配，减少内存闲置浪费。

43.2 C 语言中的动态数组操作

C 语言依靠 <stdlib.h> 提供 malloc、calloc、realloc、free 管理堆内存。

43.2.1 malloc 创建动态数组

malloc 分配未初始化内存空间：

#include <stdlib.h>
#include <stdio.h>
int main() {
    int n = 5;
    int* arr = (int*)malloc(n * sizeof(int));
    if (arr == NULL) { // 内存分配失败判断
        printf("内存分配失败\n");
        exit(1);
    }
    arr[0] = 10; // 下标正常访问
    free(arr);    // 使用完毕释放
    arr = NULL;
    return 0;
}

43.2.2 calloc 创建动态数组

calloc 分配内存并自动初始化为 0：

int n = 5;
int* arr = (int*)calloc(n, sizeof(int));
if (arr == NULL) {
    exit(1);
}
// 数组全部元素初始值为 0
free(arr);
arr = NULL;

43.2.3 realloc 扩容/缩容

int n = 5;
int* arr = (int*)malloc(n * sizeof(int));
int new_n = 10;
int* new_arr = (int*)realloc(arr, new_n * sizeof(int));
if (new_arr == NULL) {
    free(arr); // 分配失败原内存仍有效，必须释放
    exit(1);
}
arr = new_arr;
n = new_n;
free(arr);

注意：扩容新增内存无初始化；缩容会截断尾部数据。

43.2.4 free 释放内存

所有 malloc/calloc/realloc 分配的内存必须 free 释放，否则内存泄漏；释放后置空指针防止野指针：

free(arr);
arr = NULL;

43.3 C++ 动态数组操作

43.3.1 new / delete[] 原生动态数组

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int* arr = new int[n]; // 未初始化
    // 初始化版本 int* arr = new int[n]{};
    arr[1] = 20;
    delete[] arr; // 数组必须用 delete[]，不能 delete
    arr = nullptr;
    return 0;
}

补充：new(nothrow) 分配失败返回 nullptr，不抛出异常。

43.3.2 std::vector（推荐标准动态数组）

vector 封装动态内存，自动管理分配释放，无需手动管理内存。

#include <vector>
#include <iostream>
using namespace std;
int main() {
    vector<int> vec(5, 0); // 初始 5 个 0
    vec.push_back(12); // 尾部添加元素，自动扩容
    int a = vec[0]; // 下标访问（无越界检查）
    int b = vec.at(1); // 带越界抛出异常
    int s = vec.size(); // 当前元素个数
    int cap = vec.capacity(); // 当前分配容量
    vec.resize(8); // 修改元素数量
    vec.reserve(20); // 预分配容量，不改变元素
    vec.clear(); // 清空元素，内存不释放
    // 释放多余内存
    vector<int>(vec).swap(vec);
    return 0;
}

vector 核心优势：自动扩容、自动析构、内置丰富操作函数。

43.4 动态数组扩容策略

1. 固定步长扩容：每次增加固定数量，内存碎片少，但闲置空间多；
2. 倍数扩容（vector 默认 1.5/2 倍）：均摊插入复杂度 $O(1)$，平衡复制与内存开销。

43.5 常见坑点

1. 内存泄漏：分配后忘记 free/delete[]；
2. 野指针：释放后不置空，继续访问；
3. 数组越界：下标超过 size，程序崩溃；
4. 扩容后指针失效：必须更新指针变量；
5. 类型不匹配：C 中 malloc 返回 void* 需要强制转换。

43.6 多维动态数组

C 二维动态数组

#include <stdlib.h>
int main() {
    int rows = 3, cols = 4;
    int** mat = (int**)malloc(rows * sizeof(int*));
    for (int i = 0; i < rows; i++) {
        mat[i] = (int*)malloc(cols * sizeof(int));
    }
    mat[1][2] = 5;
    // 释放
    for (int i = 0; i < rows; i++) free(mat[i]);
    free(mat);
    mat = NULL;
    return 0;
}

C++ vector 二维数组

#include <vector>
using namespace std;
int main() {
    vector<vector<int>> mat(3, vector<int>(4, 0));
    mat[1][2] = 10;
    return 0;
}

43.7 选择题练习

1. 下列关于动态数组的说法，正确的是： A. 动态数组在编译时确定大小 B. 动态数组通常分配在栈区 C. 动态数组的大小可在运行时决定，存于堆区 D. vector 无法在运行时改变大小

   查看答案

   答案：C。动态数组大小运行时决定、存于堆区；vector 可运行时 push_back 改变大小。

2. 在 C++ 中申请了 int* p = new int[10];，释放时应使用： A. delete p; B. delete[] p; C. free(p); D. 无需释放

   查看答案

   答案：B。数组必须用 delete[] 配对 new[]；用 delete 或 free 会导致未定义行为或内存泄漏。

3. vector 采用倍数扩容（如 2 倍），每次 push_back 的均摊时间复杂度是： A. $O(n)$ B. $O(1)$ C. $O(\log n)$ D. $O(n^2)$

   查看答案

   答案：B。虽然偶尔扩容需要 $O(n)$ 拷贝，但拷贝代价被后续多次 $O(1)$ 插入摊薄，均摊为 $O(1)$。

4. 内存分配失败后，为避免野指针和泄漏，下列做法错误的是： A. malloc 返回 NULL 时停止并使用已分配内存 B. realloc 失败时先 free 原指针再退出 C. free 之后将指针置为 NULL D. 释放后继续访问该指针

   查看答案

   答案：D。释放后继续访问指针会产生野指针，行为未定义，是严重错误。

5. 已知 vector<int> v(3, 0);，执行 v.push_back(5); 后，v.size() 和 v[3] 分别是： A. 3, 0 B. 4, 5 C. 4, 0 D. 3, 5

   查看答案

   答案：B。push_back 后元素个数变为 4，新元素 5 位于下标 3，故 v[3] = 5。