C语言实现一个动态数组

大家好，欢迎来到IT知识分享网。

以下是一个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 
  
    #include 
   
     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，该结构体实现了高效的元素存储与动态扩容，适合需要频繁增删元素的场景。