C语言入门（顺序表）

目录引言代码结构概览三、头文件ST.h深度解析关键解析四、源文件ST.c核心函数实现前置定义解决 VS 编译器警告1. 顺序表初始化SeqListInit2. 顺序表销毁SeqListDestroy3. 顺序表打印SeqListPrint4. 容量检查与扩容cheakfull5. 尾插SeqListPushBack6. 头插SeqListPushFront7. 头删SeqListPopFront8. 尾删SeqListPopBack9. 元素查找SeqListFind10. 指定位置插入SeqListInsert11. 指定位置删除SeqListErase五、完整测试用例测试结果六、关键注意事项与避坑指南1. 内存越界最常见错误2. 空指针访问3. 扩容错误4. 插入 / 删除时的循环方向5. 结构体参数传递6. 内存泄漏七、总结与扩展核心总结扩展方向引言顺序表是基于动态数组实现的线性表相比静态数组它的核心优势是容量可动态扩容能灵活适应数据量的变化。在实际开发中顺序表常用于需要频繁随机访问、少量插入删除的场景如配置列表、简单数据缓存。本文实现的顺序表包含完整的增删查改功能初始化、销毁、头插 / 尾插、头删 / 尾删、指定位置插入 / 删除、元素查找等代码遵循 C 语言工程化规范兼顾可读性与健壮性。代码结构概览顺序表的代码分为两部分符合 C 语言 “声明与实现分离” 的工程化思想头文件ST.h定义数据结构、函数声明对外暴露接口源文件ST.c实现头文件声明的函数封装具体逻辑。这种结构的优势降低耦合修改实现逻辑无需改动头文件便于复用头文件可被多个源文件包含实现代码复用接口清晰头文件直观展示顺序表的可用操作。三、头文件ST.h深度解析头文件是顺序表的 “接口定义层”决定了外部如何使用顺序表核心包含数据类型定义、结构体定义、函数声明三部分。#pragma once // 防止头文件重复包含替代传统的#ifndef...#define...#endif #include stdio.h // 标准输入输出打印函数用 #include assert.h // 断言防御性编程检查非法参数 #include stdlib.h // 内存分配malloc/realloc/free // 1. 数据类型别名统一管理元素类型便于扩展 typedef int SLDateType; // 2. 顺序表核心结构体 typedef struct SeqList { SLDateType* a; // 动态数组指针存储元素的内存起始地址 int size; // 有效元素个数当前已存储的元素数量 int capacity; // 容量当前分配的内存可容纳的最大元素数 } SeqList; // 3. 顺序表操作函数声明接口 // 基础操作初始化/销毁/打印 void SeqListInit(SeqList* ps); void SeqListDestroy(SeqList* ps); void SeqListPrint(SeqList* ps); // 插入/删除头/尾操作常用简化版 void SeqListPushBack(SeqList* ps, SLDateType x); // 尾插 void SeqListPushFront(SeqList* ps, SLDateType x); // 头插 void SeqListPopFront(SeqList* ps); // 头删 void SeqListPopBack(SeqList* ps); // 尾删 // 通用操作查找/指定位置插入/删除 int SeqListFind(SeqList* ps, SLDateType x); // 查找元素返回索引失败返回-1 void SeqListInsert(SeqList* ps, int pos, SLDateType x); // 指定位置插入 void SeqListErase(SeqList* ps, int pos); // 指定位置删除关键解析SLDateType 类型别名将int重命名为SLDateType若需存储char/float等类型仅需修改这一行如typedef float SLDateType;无需改动所有函数体现 “开闭原则”。SeqList 结构体三要素a动态数组指针顺序表的核心存储区通过malloc/realloc动态分配size有效元素数仅size范围内的元素是合法的超出部分为未初始化内存capacity容量capacity - size是剩余可用空间size capacity时需扩容。函数声明设计参数统一使用SeqList* ps指针避免结构体拷贝提升效率且能修改结构体成员功能分层基础操作初始化 / 销毁→ 常用操作头 / 尾插删→ 通用操作指定位置操作符合使用习惯。四、源文件ST.c核心函数实现源文件是顺序表的 “逻辑实现层”需严格遵循头文件的接口定义同时处理内存分配、边界检查、数据移动等核心逻辑。前置定义解决 VS 编译器警告#define _CRT_SECURE_NO_WARNINGS // 关闭VS对scanf/strcpy等函数的安全警告 #include ST.h // 包含头文件关联结构体和函数声明1. 顺序表初始化SeqListInitvoid SeqListInit(SeqList* ps) { assert(ps); // 断言确保传入的指针非空开发阶段快速定位空指针错误 // 初始容量设为4分配4个SLDateType大小的内存 ps-a (SLDateType*)malloc(sizeof(SLDateType) * 4); if (ps-a NULL) // 检查内存分配是否成功关键避免空指针访问 { perror(malloc fail); // 打印错误原因如内存不足 return; } ps-size 0; // 初始无有效元素 ps-capacity 4; // 初始容量为4 }关键注意原代码中malloc(sizeof(SLDateType))是错误的仅分配 1 个元素空间却设置capacity4已修正为malloc(sizeof(SLDateType)*4)否则会导致扩容前就内存越界assert(ps)仅在 Debug 模式生效Release 模式会被忽略生产环境可补充if (ps NULL) return;增强健壮性。2. 顺序表销毁SeqListDestroyvoid SeqListDestroy(SeqList* ps) { assert(ps); free(ps-a); // 释放动态数组内存防止内存泄漏 ps-a NULL; // 置空指针避免悬空指针野指针 ps-size 0; // 重置有效元素数 ps-capacity 0; // 重置容量 // ps NULL; // 无效参数是值传递修改的是副本外部指针不受影响 }关键注意销毁的核心是free(ps-a)ps-a NULLfree仅释放内存不会改变指针值置空可避免后续误操作无需free(ps)ps是外部传入的结构体指针顺序表仅负责管理内部的a指针不负责管理结构体本身的内存。3. 顺序表打印SeqListPrintvoid SeqListPrint(SeqList* ps) { assert(ps); // 仅遍历有效元素size范围内 for (int i 0; i ps-size; i) { printf(%d , ps-a[i]); } printf(\n); // 换行提升可读性 }核心逻辑遍历范围是[0, size-1]而非capacity避免打印未初始化的内存数据。4. 容量检查与扩容cheakfull// 静态函数仅在当前源文件可见对外隐藏扩容细节 static void cheakfull(SeqList* ps) { assert(ps); // 有效元素数 容量 → 已满需要扩容 if (ps-size ps-capacity) { // 扩容为原来的2倍行业通用策略平衡扩容次数和内存浪费 SLDateType* tmp (SLDateType*)realloc(ps-a, ps-capacity * 2 * sizeof(SLDateType)); if (tmp NULL) // 检查扩容是否成功 { perror(realloc fail); return; } ps-a tmp; // 指向新的内存空间 ps-capacity * 2; // 更新容量 printf(扩容成功新容量%d\n, ps-capacity); } }关键解析原代码中realloc的类型转换错误(SeqList*)已修正为(SLDateType*)否则会导致内存访问异常使用static修饰将函数作用域限定在当前源文件避免外部误调用符合 “封装” 思想扩容策略每次扩 2 倍避免频繁扩容若每次扩 1 个插入 n 个元素需 n 次扩容时间复杂度 O (n²)。5. 尾插SeqListPushBackvoid SeqListPushBack(SeqList* ps, SLDateType x) { assert(ps); cheakfull(ps); // 先检查容量满则扩容 ps-a[ps-size] x; // 尾插有效元素的下一个位置size索引 ps-size; // 有效元素数1 }核心逻辑尾插无需移动元素直接在size位置赋值时间复杂度 O (1)扩容时为 O (n)但平均仍为 O (1)。6. 头插SeqListPushFrontvoid SeqListPushFront(SeqList* ps, SLDateType x) { assert(ps); cheakfull(ps); // 先扩容 // 从后往前移动元素避免覆盖数据 // 遍历范围[size, 1]将a[i-1]赋值给a[i] for (int i ps-size; i 0; i--) { ps-a[i] ps-a[i - 1]; } ps-a[0] x; // 头位置赋值 ps-size; // 有效元素数1 }关键注意循环必须从后往前i size → 1若从前往后i0 → size-1会导致前面的元素覆盖后面的元素数据丢失时间复杂度 O (n)头插需要移动所有元素这是顺序表的缺点。7. 头删SeqListPopFrontvoid SeqListPopFront(SeqList* ps) { assert(ps); assert(ps-size 0); // 断言顺序表非空避免删除空表 // 从前往后移动元素覆盖头元素 // 遍历范围[0, size-2]将a[i1]赋值给a[i] for (int i 0; i ps-size - 1; i) { ps-a[i] ps-a[i 1]; } ps-size--; // 有效元素数-1逻辑删除无需修改最后一个元素 }核心逻辑头删本质是 “覆盖”将索引 1 到 size-1 的元素依次前移最后size--逻辑上删除头元素无需释放内存仅修改size剩余空间可复用后续插入时直接覆盖。8. 尾删SeqListPopBackvoid SeqListPopBack(SeqList* ps) { assert(ps); assert(ps-size 0); // 空表不能删 ps-size--; // 逻辑删除仅减少有效元素数无需修改数组值 }关键解析尾删是顺序表最高效的删除操作时间复杂度 O (1)仅需修改size。9. 元素查找SeqListFindint SeqListFind(SeqList* ps, SLDateType x) { assert(ps); // assert(ps-size 0); // 注释空表返回-1更友好无需断言 if (ps-size 0) { printf(顺序表为空查找失败\n); return -1; } // 遍历有效元素查找目标值 for (int i 0; i ps-size; i) { if (ps-a[i] x) { return i; // 找到返回索引 } } return -1; // 未找到返回-1约定俗成的失败标识 }优化点原代码的assert(ps-size0)会导致空表直接崩溃改为if判断并返回 - 1更友好返回值设计找到返回索引未找到返回 - 1符合 C 语言函数的返回值习惯如strchr返回指针失败返回 NULL。10. 指定位置插入SeqListInsertvoid SeqListInsert(SeqList* ps, int pos, SLDateType x) { assert(ps); // 检查pos合法性[0, size]possize等价于尾插 assert(pos 0 pos ps-size); cheakfull(ps); // 扩容检查 // 从后往前移动元素[size, pos1] for (int i ps-size; i pos; i--) { ps-a[i] ps-a[i - 1]; } ps-a[pos] x; // 插入到指定位置 ps-size; // 有效元素数1 }关键解析pos 的合法范围是[0, size]pos0是头插possize是尾插覆盖所有插入场景原代码assert(ps-size pos)未限制pos0已补充pos0避免负索引越界。11. 指定位置删除SeqListErasevoid SeqListErase(SeqList* ps, int pos) { assert(ps); // 检查pos合法性[0, size-1]必须是有效元素的索引 assert(pos 0 pos ps-size); // 从前往后移动元素覆盖pos位置 for (int i pos; i ps-size - 1; i) { ps-a[i] ps-a[i 1]; } ps-size--; // 逻辑删除 }核心逻辑pos 的合法范围是[0, size-1]只能删除有效元素不能删除超出范围的位置时间复杂度 O (n)需要移动 pos 后的所有元素。五、完整测试用例为验证顺序表的所有功能编写测试代码main 函数int main() { SeqList sl; // 1. 初始化 SeqListInit(sl); // 2. 尾插 SeqListPushBack(sl, 1); SeqListPushBack(sl, 2); SeqListPushBack(sl, 3); SeqListPushBack(sl, 4); printf(尾插4个元素); SeqListPrint(sl); // 输出1 2 3 4 // 3. 尾插第5个元素触发扩容 SeqListPushBack(sl, 5); printf(尾插第5个元素扩容后); SeqListPrint(sl); // 输出1 2 3 4 5 // 4. 头插 SeqListPushFront(sl, 0); printf(头插0后); SeqListPrint(sl); // 输出0 1 2 3 4 5 // 5. 头删 SeqListPopFront(sl); printf(头删后); SeqListPrint(sl); // 输出1 2 3 4 5 // 6. 尾删 SeqListPopBack(sl); printf(尾删后); SeqListPrint(sl); // 输出1 2 3 4 // 7. 查找元素 int pos SeqListFind(sl, 3); if (pos ! -1) { printf(找到元素3索引%d\n, pos); // 输出2 } // 8. 指定位置插入 SeqListInsert(sl, 2, 99); printf(在索引2插入99后); SeqListPrint(sl); // 输出1 2 99 3 4 // 9. 指定位置删除 SeqListErase(sl, 2); printf(删除索引2的元素后); SeqListPrint(sl); // 输出1 2 3 4 // 10. 销毁 SeqListDestroy(sl); return 0; }测试结果尾插4个元素1 2 3 4 扩容成功新容量8 尾插第5个元素扩容后1 2 3 4 5 头插0后0 1 2 3 4 5 头删后1 2 3 4 5 尾删后1 2 3 4 找到元素3索引2 在索引2插入99后1 2 99 3 4 删除索引2的元素后1 2 3 4六、关键注意事项与避坑指南1. 内存越界最常见错误错误场景访问a[size]或a[capacity]避坑方法所有数组访问限定在[0, size-1]插入前先扩容删除前检查size0。2. 空指针访问错误场景未初始化a指针就访问或malloc/realloc失败后使用a避坑方法每次malloc/realloc后检查返回值是否为NULL用assert(ps)检查结构体指针生产环境补充if (ps NULL)。3. 扩容错误错误场景realloc的大小计算错误如忘记乘sizeof(SLDateType)避坑方法扩容公式统一为capacity * 2 * sizeof(SLDateType)避免硬编码。4. 插入 / 删除时的循环方向插入必须从后往前移动元素否则覆盖数据删除必须从前往后移动元素否则遗漏数据。5. 结构体参数传递错误场景传SeqList结构体值传递而非指针避坑方法所有操作函数的参数都用SeqList* ps避免拷贝且能修改成员。6. 内存泄漏错误场景使用完顺序表后未调用SeqListDestroy避坑方法遵循 “谁初始化谁销毁” 原则顺序表使用完毕必须调用destroy。七、总结与扩展核心总结顺序表基于动态数组实现核心是size有效元素和capacity容量的管理优势随机访问效率高O (1)尾插 / 尾删效率高劣势头插 / 头删、指定位置插入 / 删除效率低O (n)扩容有内存开销核心避坑点内存越界、空指针、扩容错误、循环方向错误、内存泄漏。扩展方向缩容当size远小于capacity如size capacity/4时缩小容量减少内存浪费批量操作实现SeqListInsertBatch批量插入、SeqListRemoveAll删除所有指定元素排序 / 去重结合快速排序、哈希表实现顺序表的排序和去重泛型支持通过void*指针实现支持任意类型的顺序表进阶。顺序表是 C 语言数据结构的基础掌握其实现原理能为后续学习链表、栈、队列等数据结构打下坚实基础。核心是理解 “动态内存管理” 和 “线性表的顺序存储” 思想同时注重代码的健壮性和工程化规范。