好的，我们来详细讲解 C/C++ 数据结构中的动态数组（Dynamic Array），这是数据结构中非常重要的一部分，尤其在对内存管理和性能有要求的 C/C++ 开发中。

📚 目录

  1. 什么是动态数组？
  2. 静态数组 vs 动态数组
  3. C 语言中的动态数组实现
  4. C++ 中的 vector 封装
  5. 实现原理：扩容与缩容机制
  6. 动态数组操作（增、删、改、查）
  7. 手动实现一个简易动态数组（C代码）
  8. 动态数组的使用场景与注意事项
  9. 参考资料

1. 什么是动态数组？

动态数组是一种可以在运行时改变其大小的数组结构。

  • 在 静态数组 中，我们必须在编译时指定数组大小。
  • 动态数组 可以随着元素的添加或删除自动调整容量。

2. 静态数组 vs 动态数组

特性静态数组动态数组
内存分配方式编译时运行时（heap）
数组大小是否固定是否，可扩容/缩容
灵活性差高
控制权程序员无法更改大小程序员控制 realloc

3. C语言中动态数组的实现（使用 malloc/realloc）

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

int main() {
    int *arr = NULL;
    int capacity = 2;
    int size = 0;

    arr = (int*) malloc(capacity * sizeof(int));
    if (!arr) {
        perror("malloc failed");
        return 1;
    }

    // 添加元素
    for (int i = 0; i < 10; ++i) {
        if (size >= capacity) {
            capacity *= 2;
            arr = (int*) realloc(arr, capacity * sizeof(int));
            if (!arr) {
                perror("realloc failed");
                return 1;
            }
        }
        arr[size++] = i * 10;
    }

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

    free(arr);
    return 0;
}

4. C++ 中的动态数组封装：std::vector

C++ 提供了更安全、更强大的封装 —— std::vector

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;

    // 添加元素
    for (int i = 0; i < 10; ++i)
        v.push_back(i * 10);

    // 访问
    for (int i = 0; i < v.size(); ++i)
        cout << v[i] << " ";

    return 0;
}

🔹 自动管理内存
🔹 支持迭代器
🔹 支持动态扩容和缩容

5. 动态数组的扩容与缩容机制

动作实现方式
扩容capacity *= 2
缩容capacity /= 2（可选）
realloc重新分配更大/更小的内存空间，拷贝数据到新空间

6. 动态数组的常见操作

操作方法描述
增加元素push_back / insert在末尾添加
删除元素pop_back / erase删除末尾或指定位置
查找元素[] / at()访问下标元素
修改元素arr[i] = newVal;修改值

7. 手动实现一个简易动态数组结构（C语言封装版）

typedef struct {
    int *data;
    int size;
    int capacity;
} DynamicArray;

void init(DynamicArray *a, int initCap) {
    a->data = (int*) malloc(initCap * sizeof(int));
    a->size = 0;
    a->capacity = initCap;
}

void push_back(DynamicArray *a, int value) {
    if (a->size >= a->capacity) {
        a->capacity *= 2;
        a->data = (int*) realloc(a->data, a->capacity * sizeof(int));
    }
    a->data[a->size++] = value;
}

void freeArray(DynamicArray *a) {
    free(a->data);
    a->size = a->capacity = 0;
}

8. 动态数组的使用场景与注意事项

✅ 适用场景：

  • 不确定元素数量时（用户输入、读取文件等）
  • 想要按需动态扩容的数据结构
  • 性能敏感场景（避免链表频繁分配）

⚠️ 注意事项：

  • realloc 后必须检查指针是否为 NULL
  • 内存泄漏风险（记得 free）
  • 多线程场景下需加锁保护

🔗 参考资料（出站链接）