顺序表实现代码解析与学习笔记
一、顺序表基础概念
顺序表是线性表的一种顺序存储结构，它使用一段连续的内存空间（数组）存储数据元素，通过下标直接访问元素，具有随机访问的特性。其核心特点是：元素在内存中连续存放，逻辑顺序与物理顺序一致。
二、代码结构说明
本次实现包含 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）
初始化顺序表：创建容量为 3 的顺序表
测试插入功能：插入 5 个数据（10、20、30、40、50）
插入前 3 个数据时，容量为 3（未扩容）
插入第 4 个数据时，表满触发扩容（容量变为 6）
遍历输出：打印当前顺序表的所有元素（头插法下，元素顺序为 50、40、30、20、10）
测试删除功能：依次删除 30、10、50、12（12 不存在）
销毁顺序表：释放所有分配的内存
六、学习笔记总结
顺序表优缺点
优点：随机访问（通过下标直接访问，时间复杂度 O (1)）
缺点：插入 / 删除中间元素时需要移动大量元素（时间复杂度 O (n)）；容量固定（需手动扩容）
头插法特点
新元素始终插入到表头，插入顺序与元素存储顺序相反（如插入 10→20→30，存储为 30、20、10）
每次插入都需移动所有现有元素，适合元素数量少的场景
扩容策略思考
2 倍扩容：减少扩容次数，但可能浪费内存
1.5 倍扩容：平衡扩容次数和内存浪费，更适合实际应用
扩容时使用
realloc，可能触发内存拷贝（原有内存不足时）
内存管理要点
动态内存分配后必须检查是否成功（
NULL判断）释放内存时需先释放内部资源（如
data数组），再释放外部结构体释放后指针置空，避免悬挂指针导致的野指针操作
通过以上代码实现，可以清晰理解顺序表的基本操作原理及内存管理细节，为学习更复杂的数据结构奠定基础。