1. 动态数组的扩容与缩容实现

动态数组的核心矛盾

静态数组在创建时容量固定，插入元素一旦超出容量就必须整体搬迁。动态数组的思路是：内部维护一个容量为 capacity 的底层数组，同时用 size 记录当前有效元素个数。当 size == capacity 时触发扩容，当元素大量删除、size 远小于 capacity 时触发缩容。关键不在于“能自动变长”，而在于扩容/缩容的触发时机与容量增长策略，这直接决定了均摊时间复杂度。

实现要点

下面给出一个完整的动态数组实现，包含扩容、缩容、插入、删除和容量查询。核心逻辑集中在 ensureCapacity 和 shrink 两个方法中。

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

typedef struct {
    int *data;
    int size;       // 当前元素个数
    int capacity;   // 当前底层数组容量
} DynArray;

DynArray* da_create(int initCap) {
    DynArray *da = (DynArray*)malloc(sizeof(DynArray));
    da->data = (int*)malloc(sizeof(int) * initCap);
    da->size = 0;
    da->capacity = initCap;
    return da;
}

// 扩容：容量翻倍
static void da_resize(DynArray *da, int newCap) {
    int *newData = (int*)malloc(sizeof(int) * newCap);
    memcpy(newData, da->data, sizeof(int) * da->size);
    free(da->data);
    da->data = newData;
    da->capacity = newCap;
}

// 确保容量足够，不够则翻倍
static void da_ensureCapacity(DynArray *da) {
    if (da->size >= da->capacity) {
        da_resize(da, da->capacity * 2);
    }
}

// 缩容：当 size <= capacity/4 且 capacity > 初始容量时，容量减半
static void da_shrink(DynArray *da, int minCap) {
    if (da->capacity > minCap && da->size <= da->capacity / 4) {
        int newCap = da->capacity / 2;
        if (newCap < minCap) newCap = minCap;
        da_resize(da, newCap);
    }
}

void da_push(DynArray *da, int val) {
    da_ensureCapacity(da);
    da->data[da->size++] = val;
}

int da_pop(DynArray *da, int minCap) {
    if (da->size == 0) return -1; // 空数组
    int val = da->data[--da->size];
    da_shrink(da, minCap);
    return val;
}

int da_get(DynArray *da, int idx) {
    if (idx < 0 || idx >= da->size) return -1;
    return da->data[idx];
}

void da_free(DynArray *da) {
    free(da->data);
    free(da);
}

验证容量变化与性能

用一段测试代码观察扩容和缩容的实际触发点。初始容量设为 2，连续插入 10 个元素，再连续弹出 8 个元素，打印每次操作后的 size 和 capacity。

int main() {
    DynArray *da = da_create(2);
    printf("初始: size=%d cap=%d\n", da->size, da->capacity);

    for (int i = 1; i <= 10; i++) {
        da_push(da, i * 10);
        printf("push %2d -> size=%2d cap=%2d\n", i * 10, da->size, da->capacity);
    }

    for (int i = 0; i < 8; i++) {
        int v = da_pop(da, 2);
        printf("pop  %2d -> size=%2d cap=%2d\n", v, da->size, da->capacity);
    }

    da_free(da);
    return 0;
}

均摊复杂度验证

扩容的代价是 O(n) 的复制，但每两次扩容之间至少插入 n/2 个元素，因此把复制代价分摊到每次插入上，均摊为 O(1)。缩容同理。可以用计数方式验证：统计 n 次插入中总复制次数，观察其与 n 的比值是否趋近于常数。