顺序表实现代码解析与学习笔记

一、顺序表基础概念

顺序表是线性表的一种顺序存储结构，它使用一段连续的内存空间（数组）存储数据元素，通过下标直接访问元素，具有随机访问的特性。其核心特点是：元素在内存中连续存放，逻辑顺序与物理顺序一致。

二、代码结构说明

本次实现包含 3 个文件，分工如下：

• arraylist.h：定义顺序表结构体及相关操作函数的声明

• arraylist.c：实现顺序表的核心操作函数

• main.c：测试顺序表的各项功能

三、核心结构体解析

在arraylist.h中定义了顺序表的结构体：

typedef struct{​int capacity;    // 顺序表的容量（最大可存储元素数）​int last;        // 最后一个元素的下标（-1表示空表）​int \*data;       // 指向存储元素的数组（堆内存）​} ArrayList;

• capacity：记录当前顺序表的最大容量（数组长度）

• last：通过下标管理实际元素数量（元素个数 = last + 1）

• data：动态数组指针，实际存储元素的内存空间

四、核心函数实现解析

1. 初始化函数 init_list

 ArrayList \*init\_list(int cap) {​if (cap <= 0) return NULL;  // 容量必须为正数​ArrayList \*list = malloc(sizeof(ArrayList));​if (list) {​list->data = calloc(cap, sizeof(int));  // 分配数组内存并初始化为0​if (list->data == NULL) {​free(list);  // 数组内存分配失败时，释放结构体​return NULL;​}​list->capacity = cap;​list->last = -1;  // 初始化为空表​return list;​}​return NULL;​}

• 功能：创建并初始化顺序表，分配结构体和数组内存

• 关键：参数校验（容量 > 0）、内存分配失败的容错处理

2. 插入函数 insert（头插法）

 bool insert(ArrayList \*list, int data) {​if (list == NULL) return false;​// 满表时扩容（2倍扩容）​if (is\_full(list) && !expand\_list(list)) return false;​// 元素后移（从最后一个元素开始）​for (int i = list->last; i >= 0; i--) {​list->data\[i+1] = list->data\[i];​}​// 插入新元素到表头（下标0）​list->data\[0] = data;​list->last++;  // 更新最后元素下标​return true;​}

• 特点：采用头插法（新元素插入到表头位置）

• 扩容逻辑：当表满时调用expand_list扩容为原容量的 2 倍

• 时间复杂度：O (n)（需要移动所有现有元素）

3. 扩容函数 expand_list（静态辅助函数）

 static bool expand\_list(ArrayList \*list) {​if (list == NULL) return false;​int new\_cap = list->capacity \* 2;  // 2倍扩容策略​int \*new\_data = realloc(list->data, sizeof(int) \* new\_cap);​if (new\_data == NULL) return false;​list->data = new\_data;​list->capacity = new\_cap;​// 初始化新增内存（可选操作）​for (int i = list->last + 1; i < new\_cap; i++) {​list->data\[i] = 0;​}​return true;​}

• 关键：使用realloc重新分配内存，避免内存泄漏

• 扩容策略：简单采用 2 倍扩容（实际应用中可根据需求优化，如 1.5 倍扩容减少内存浪费）

4. 删除函数 remove_data

 bool remove\_data(ArrayList \*list, int data) {​if (!list || is\_empty(list)) return false;​// 查找第一个匹配元素的位置​int pos = -1;​for (int i = 0; i <= list->last; i++) {​if (list->data\[i] == data) {​pos = i;​break;​}​}​if (pos == -1) return false;  // 未找到元素​// 元素前移（覆盖被删除元素）​for (int i = pos; i < list->last; i++) {​list->data\[i] = list->data\[i+1];​}​list->last--;  // 更新最后元素下标​return true;​}

• 功能：删除第一个匹配的元素

• 步骤：查找位置 → 元素前移 → 更新下标

• 时间复杂度：O (n)（最坏情况需要移动 n-1 个元素）

5. 销毁函数 destroy

 void destroy(ArrayList \*list) {​if (list == NULL) return;​if (list->data != NULL) {​free(list->data);  // 先释放数组内存​list->data = NULL;  // 避免悬挂指针​}​free(list);  // 再释放结构体内存​list = NULL;​}

• 关键：先释放内部动态数组，再释放结构体，避免内存泄漏

• 注意：置空指针（list->data = NULL）防止后续误操作

五、测试流程解析（main.c）

1. 初始化顺序表：创建容量为 3 的顺序表

2. 测试插入功能：插入 5 个数据（10、20、30、40、50）

• 插入前 3 个数据时，容量为 3（未扩容）

• 插入第 4 个数据时，表满触发扩容（容量变为 6）

1. 遍历输出：打印当前顺序表的所有元素（头插法下，元素顺序为 50、40、30、20、10）

2. 测试删除功能：依次删除 30、10、50、12（12 不存在）

3. 销毁顺序表：释放所有分配的内存

六、学习笔记总结

1. 顺序表优缺点

• 优点：随机访问（通过下标直接访问，时间复杂度 O (1)）

• 缺点：插入 / 删除中间元素时需要移动大量元素（时间复杂度 O (n)）；容量固定（需手动扩容）

1. 头插法特点

• 新元素始终插入到表头，插入顺序与元素存储顺序相反（如插入 10→20→30，存储为 30、20、10）

• 每次插入都需移动所有现有元素，适合元素数量少的场景

1. 扩容策略思考

• 2 倍扩容：减少扩容次数，但可能浪费内存

• 1.5 倍扩容：平衡扩容次数和内存浪费，更适合实际应用

• 扩容时使用realloc，可能触发内存拷贝（原有内存不足时）

1. 内存管理要点

• 动态内存分配后必须检查是否成功（NULL判断）

• 释放内存时需先释放内部资源（如data数组），再释放外部结构体

• 释放后指针置空，避免悬挂指针导致的野指针操作

通过以上代码实现，可以清晰理解顺序表的基本操作原理及内存管理细节，为学习更复杂的数据结构奠定基础。