---

动态数组

普通数组长度固定：

int arr[10];

但如果运行时才知道需要多少个元素，就可以使用动态数组。

核心就是：

data       → 数据
size       → 当前元素数量
capacity   → 当前容量

一、基本结构

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

例如：

capacity = 4
size = 3

[10][20][30][  ]

表示容量为 4，目前用了 3 个。

---

二、malloc：申请初始空间

创建动态数组：

DynArray arr;

arr.size = 0;
arr.capacity = 4;
arr.data = malloc(arr.capacity * sizeof(int));

得到：

malloc
  ↓
申请4个int
  ↓
[ ][ ][ ][ ]

malloc 的作用：

申请一块新的动态内存。

---

三、加入元素

void push(DynArray *arr, int value)
{
    if (arr->size >= arr->capacity)
    {
        arr->capacity *= 2;

        arr->data = realloc(
            arr->data,
            arr->capacity * sizeof(int)
        );
    }

    arr->data[arr->size++] = value;
}

例如：

capacity = 4
size = 4

[10][20][30][40]

继续：

push(&arr, 50);

发现满了：

4 → 8

扩容后：

[10][20][30][40][50][ ][ ][ ]

---

四、realloc：扩容

arr->data = realloc(
    arr->data,
    arr->capacity * sizeof(int)
);

realloc 用来：

调整已经申请的动态内存大小。

注意：

realloc 后地址可能改变

如果原地址后面没有足够连续空间，系统可能：

申请新空间
    ↓
复制旧数据
    ↓
释放旧空间

所以不要认为扩容后指针一定不变。

---

五、为什么容量通常翻倍？

不要每增加一个元素就扩容：

4 → 5 → 6 → 7 → 8

而是：

4 → 8 → 16 → 32 → 64

这样可以减少 realloc 次数，使 push 的均摊复杂度达到 O(1)。

---

六、最后释放

动态内存使用完必须释放：

free(arr.data);

arr.data = NULL;
arr.size = 0;
arr.capacity = 0;

完整生命周期：

malloc
  ↓
使用
  ↓
空间不足
  ↓
realloc 扩容
  ↓
继续使用
  ↓
free

---

七、嵌入式中的注意事项

动态数组虽然灵活，但 MCU 裸机和实时系统中通常谨慎使用：

malloc / realloc
      ↓
可能造成内存碎片
      ↓
分配失败
      ↓
执行时间不确定

因此嵌入式中经常直接：

#define MAX_SIZE 100

int data[MAX_SIZE];
int size = 0;

即：

预分配最大容量，用 size 记录当前使用数量。

---

八、最终记忆

动态数组
├── data       → 数据
├── size       → 当前数量
└── capacity   → 当前容量

malloc
└── 申请初始内存

realloc
└── 调整已有内存大小

free
└── 释放内存

核心思想：

动态数组 = 指针 + size + capacity + 动态内存管理。

本质上就是 C 语言自己实现一个类似 C++ vector 的可扩容数组。