以下是一个C语言结构体用于实现一个动态数组（列表）的代码：

typedef struct {
    int *arr;        // 数组（存储列表元素）
    int capacity;    // 列表容量
    int size;        // 列表大小
    int extendRatio; // 列表每次扩容的倍数
} MyList;

结构体成员说明：

1. arr（数组指针）

• 指向动态分配的整型数组，用于实际存储列表元素。
• 初始时指向一块预分配的内存，随着元素增加可能被重新分配。

2. capacity（容量）

• 表示当前数组的最大可容纳元素数量。
• 初始化时设定（如默认值 10），扩容时按 extendRatio 倍数增长（如容量不足时从 10 扩容到 20）。

3. size（当前大小）

• 记录列表中实际存储的元素数量，总满足 size ≤ capacity。
• 插入元素时 size 递增，删除时递减。

4. extendRatio（扩容倍数）

• 当 size 达到 capacity 时，触发扩容，新容量为 capacity * extendRatio（如默认 2 倍）。
• 确保扩容策略平衡内存使用与性能（避免频繁扩容）。

代码实现

1. 初始化列表initList

// 初始化动态数组
void initList(MyList *list, int initialCapacity, int ratio) {
    list->capacity = initialCapacity;   // 初始容量
    list->size = 0;                     // 初始元素数量为0
    list->extendRatio = ratio;          // 扩容倍数（例如2）
    list->arr = (int*)malloc(sizeof(int) * list->capacity); // 分配初始内存
    
    if (list->arr == NULL) {            // 内存分配失败处理
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
}

关键点：

• 需要用户指定 initialCapacity（初始容量）和 ratio（扩容倍数）。
• 检查 malloc 是否成功，失败时直接退出程序（实际项目中可改为错误码返回）。

2. 销毁列表destroyList

// 销毁动态数组，释放内存
void destroyList(MyList *list) {
    if (list->arr != NULL) {            // 确保指针有效
        free(list->arr);                // 释放数组内存
        list->arr = NULL;               // 避免野指针
        list->capacity = 0;
        list->size = 0;
    }
}

关键点：

• 释放动态分配的 arr 内存，并将指针置为 NULL 防止误用。
• 重置 capacity 和 size 为 0。

3. 扩容函数resize

// 扩容数组（私有函数，不直接暴露给用户）
void resize(MyList *list) {
    int newCapacity = list->capacity * list->extendRatio;  // 计算新容量
    int *newArr = (int*)malloc(sizeof(int) * newCapacity); // 分配新内存
    
    if (newArr == NULL) {               // 内存分配失败处理
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    
    // 将旧数据复制到新数组
    for (int i = 0; i < list->size; i++) {
        newArr[i] = list->arr[i];
    }
    
    free(list->arr);                    // 释放旧内存
    list->arr = newArr;                 // 更新数组指针
    list->capacity = newCapacity;       // 更新容量
}

关键点：

• 使用 extendRatio 计算新容量，例如容量从 10 扩容到 20。
• 复制旧数据到新数组后，必须释放旧内存避免泄漏。
• 时间复杂度为 O(n)（复制数据）。

4. 添加元素add

// 在列表末尾添加元素
void add(MyList *list, int val) {
    if (list->size == list->capacity) { // 容量不足时触发扩容
        resize(list);
    }
    list->arr[list->size] = val;        // 插入元素到末尾
    list->size++;                       // 更新元素数量
}

关键点：

• 当 size == capacity 时自动扩容。
• 插入元素时间复杂度为均摊 O(1)（扩容操作均摊到多次插入）。

5. 删除末尾元素removeLast

// 删除列表末尾元素
void removeLast(MyList *list) {
    if (list->size == 0) {              // 列表为空时直接返回
        fprintf(stderr, "List is empty\n");
        return;
    }
    list->size--;                       // 只需减少 size，无需实际删除数据
    
    // （可选）缩容：当 size 远小于 capacity 时可释放多余内存
    // 例如：if (list->size < list->capacity / 4) shrink();
}

关键点：

• 仅减少 size，不会实际删除内存中的数据（类似栈的 pop 操作）。
• 时间复杂度 O(1)。
• 缩容是可选的优化操作（注释中给出示例）。

6. 在指定索引插入元素insert

// 在指定索引位置插入元素
void insert(MyList *list, int index, int val) {
    // 1. 检查索引合法性
    if (index < 0 || index > list->size) {
        fprintf(stderr, "错误：索引 %d 超出范围 [0, %d]\n", index, list->size);
        exit(EXIT_FAILURE); // 终止程序（实际项目可改为返回错误码）
    }

    // 2. 检查是否需要扩容
    if (list->size == list->capacity) {
        resize(list); // 触发扩容
    }

    // 3. 移动元素：将索引后的元素后移一位（使用 memmove 高效处理内存块）
    memmove(
        &list->arr[index + 1],    // 目标起始位置
        &list->arr[index],        // 源起始位置
        (list->size - index) * sizeof(int) // 需移动的字节数
    );

    // 4. 插入新元素并更新大小
    list->arr[index] = val;
    list->size++;
}

关键点：

1. 索引越界：必须严格检查 index 范围，否则可能导致内存访问错误。
2. 内存管理：确保扩容后释放旧内存，避免泄漏。
3. 性能优化：使用 memmove 替代手动循环提升效率，尤其在处理大数据时。

• 平均时间复杂度：O(n)（需移动 n - index 个元素）。
• 最坏情况：在头部插入（index = 0），需移动所有元素。
• 最优情况：在尾部插入（index = size），无需移动元素，时间复杂度 O(1)。

完整代码整合

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

typedef struct {
    int *arr;
    int capacity;
    int size;
    int extendRatio;
} MyList;

void initList(MyList *list, int initialCapacity, int ratio) { /* 同上 */ }
void destroyList(MyList *list) { /* 同上 */ }
void resize(MyList *list) { /* 同上 */ }
void add(MyList *list, int val) { /* 同上 */ }
void removeLast(MyList *list) { /* 同上 */ }
void insert(MyList *list, int index, int val) {/* 同上 */}

使用示例

int main() {
    MyList list;
    initList(&list, 2, 2);  // 初始容量2，扩容倍数2
    
    add(&list, 10);         // 容量足够，直接插入
    add(&list, 20);         // 容量足够，直接插入
    add(&list, 30);         // 容量不足，触发扩容到4
  
    insert(&list, 1, 40);  // 在索引 1 插入 40 
    
    printf("Capacity: %d, Size: %d\n", list.capacity, list.size);  
    
    removeLast(&list);      // 删除末尾元素30
    printf("Size after removal: %d\n", list.size);        
    
    destroyList(&list);     // 释放内存
    return 0;
}

设计思考与优化

1. 缩容策略（可选）：

• 当 size 小于 capacity / extendRatio 时，可以缩容以减少内存占用。
• 实现类似 resize，但新容量为 capacity / extendRatio。

2. 错误处理：

• 在 add 和 removeLast 中可返回错误码（如 bool 类型）替代直接退出。
• 实际项目中建议使用更健壮的错误处理机制。

3. 时间复杂度权衡：

• 访问元素：直接通过索引 O(1)。
• 插入/删除末尾：均摊 O(1)（因扩容分摊成本）。
• 中间插入/删除：需要移动元素 O(n)。

4. 内存对齐：

• 在 resize 中可使用 realloc 替代 malloc + memcpy，但需注意 realloc 可能直接扩展原内存块，避免不必要的复制。

关键注意事项：

• 内存管理：确保每次扩容后释放旧数组，避免内存泄漏。
• 时间复杂度：
• 访问元素：O(1)（直接通过索引）。
• 插入/删除末尾元素：均摊 O(1)（扩容操作均摊到多次插入）。
• 中间插入/删除：O(n)（需移动元素）。
• 扩展倍数选择：
• 倍数过小（如 1.5）减少内存浪费，但可能增加扩容频率。
• 倍数过大（如 2）减少扩容次数，但可能浪费内存。

通过合理管理 arr、capacity 和 size，该结构体实现了高效的元素存储与动态扩容，适合需要频繁增删元素的场景。