Skip to main content

第43章 动态数组

动态数组(Dynamic Array)是一种在程序运行时可以灵活调整大小的数组结构，它克服了静态数组编译时确定大小)的局限性，能够根据实际需求动态分配和释放内存。动态数组是处理不确定规模数据的重要工具。

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.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_n;
n = new_n;
free(arr);

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

43.4 free 释放内存​

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

free(arr);
arr = NULL;

43.3 C++ 动态数组操作​

43.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.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)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;
}