动态数组 (Dynamic Array)
基于
malloc/realloc实现的可自动扩容数组。连续内存存储，支持 O(1) 随机访问。
结构定义
typedef struct {
int *data; /* 元素指针 */
size_t size; /* 当前元素个数 */
size_t capacity; /* 已分配容量 */
} DArray;函数签名
| 函数 | 复杂度 | 说明 |
|---|---|---|
void da_init(DArray *a, size_t cap) | O(1) | 初始化，分配初始容量 |
void da_push_back(DArray *a, int val) | 均摊 O(1) | 尾部追加，容量不足时 realloc 倍增 |
int da_pop_back(DArray *a) | O(1) | 弹出尾部元素，size 减 1 |
int da_get(DArray *a, size_t i) | O(1) | 按下标获取元素（不做越界检查） |
void da_resize(DArray *a, size_t new_cap) | O(n) | 扩容/缩容，可能触发数据搬迁 |
void da_free(DArray *a) | O(1) | 释放 data 并清零 |
扩容策略
/* 典型倍增策略 */
if (a->size >= a->capacity) {
a->capacity = a->capacity == 0 ? 4 : a->capacity * 2;
a->data = realloc(a->data, a->capacity * sizeof(int));
}倍增策略使 push_back 的均摊复杂度为 O(1)：n 次插入总搬迁次数不超过 2n。
使用模式
DArray a;
da_init(&a, 4);
da_push_back(&a, 10);
da_push_back(&a, 20);
printf("%d\n", da_get(&a, 0)); /* 10 */
da_pop_back(&a);
da_free(&a);注意事项
realloc失败时返回 NULL，原内存保持有效 — 不要直接ptr = realloc(ptr, size)，应使用临时变量- 动态数组为手动内存管理，必须配对调用
da_free size_t为无符号类型，size--在 size=0 时会产生下溢