33_顺序表（待完善）

核心摘要本文使用C语言从零实现动态顺序表重点讲解内存分配策略、增删改查的核心算法以及边界条件处理解决“数组越界”和“扩容无效”两大常见问题。一、顺序表的基本概念与结构设计1. 逻辑结构与物理结构对比(1) 逻辑结构线性表元素之间具有一对一的前后关系。(2) 物理结构连续的内存地址与数组一致但支持动态扩展。2. 静态数组 vs 动态顺序表(1) 静态数组的致命缺陷容量固定编译时确定易溢出。(2) 动态顺序表的优势运行时扩容内存利用率高。3. 结构体定义C语言描述采用SeqList结构体封装三个必要属性typedefintSLDataType;// 方便后续修改数据类型如改为char或doubletypedefstructSeqList{SLDataType*a;// 指向动态开辟数组的指针intsize;// 有效数据个数当前长度intcapacity;// 当前最大容量总空间大小}SeqList;a. 为什么需要capacity—— 区分“已用空间”和“总空间”是扩容判断的依据。b. 为什么用typedef定义数据类型—— 提高代码复用性一行修改即可适配int/float/struct。二、核心操作的实现增删改查1. 初始化与销毁内存管理(1)初始化将指针置NULLsize和capacity置 0。voidSLInit(SeqList*psl);(2)销毁释放psl-a重新调用初始化防止野指针。voidSLDestroy(SeqList*psl);2. 扩容机制核心难点(1)触发条件size capacity。(2)扩容策略a. 小容量场景capacity为 0 时开辟 4 个元素大小。b. 大容量场景新容量 原容量 × 2指数增长减少 realloc 次数。(3)扩容函数实现voidSLCheckCapacity(SeqList*psl){if(psl-sizepsl-capacity){intnewCapacity(psl-capacity0?4:psl-capacity*2);SLDataType*tmp(SLDataType*)realloc(psl-a,newCapacity*sizeof(SLDataType));if(tmpNULL){perror(realloc fail);return;}psl-atmp;psl-capacitynewCapacity;}3. 增头插 / 尾插 / 任意位置插入(1)尾插先检查容量再在psl-a[psl-size]处赋值最后size。时间复杂度 O(1)。(2)头插从后往前移动元素for循环从size到1腾出[0]位置。时间复杂度 O(n)。(3)任意位置插入将[pos, size-1]全部后移一位再插入。必须判断pos合法性0 ≤ pos ≤ size。4. 删头删 / 尾删 / 任意位置删除(1)尾删直接size--注意不需要真正清除内存下次插入会覆盖。(2)头删从前往后移动元素for循环从1到size-1最后size--。(3)任意位置删除将[pos1, size-1]前移覆盖pos位置。⚠️ 删除操作的三重检查⓵ 断言psl不为空。⓶ 断言psl-size 0空表不能删。⓷ 检查pos范围0 ≤ pos size。5. 查与改(1)按值查找遍历数组返回第一个匹配的下标找不到返回 -1。(2)按位置修改直接赋值psl-a[pos] x前提是pos size。(3)按值修改先查找位置再修改查找逻辑复用。三、打印与调试辅助函数1. 打印顺序表遍历size次输出psl-a[i]格式统一为[1, 2, 3, 4]。2. 菜单交互示例用于控制台测试提供 0-7 的数字菜单⓵ 尾插 ⓶ 头插 ⓷ 尾删 ⓸ 头删⓹ 任意插入 ⓺ 任意删除 ⓻ 查找 ⓼ 打印 ⓿ 退出四、常见错误与避坑指南实用性重点1. 扩容时的野指针问题(1)错误写法直接用realloc(psl-a, newSize)且不判断返回值。(2)正确写法用临时指针tmp接收realloc返回值成功后再赋值给psl-a。原因realloc失败返回NULL直接赋值会丢失原有内存地址导致内存泄漏且无法恢复。2. 删除/插入时的越界访问(1) 头插移动元素时必须从后往前移动for (i size; i pos; i--)。(2) 头删移动元素时必须从前往后移动for (i pos; i size-1; i)。口诀插入向后挪删除向前盖反向操作必越界。3. 结构体传值 vs 传址(1)错误函数参数写void func(SeqList sl)修改的是临时副本。(2)正确一律传指针void func(SeqList* psl)用-访问成员。4. 缩容的误区不建议在删除元素时立即缩容频繁缩容会导致性能抖动。业界通用做法只扩不缩或仅在剩余空间占比极低时如size capacity/4考虑缩容。五、完整代码文件结构项目组织1. 分文件编写工业级规范(1)SeqList.h—— 头文件结构体定义、函数声明、宏定义。(2)SeqList.c—— 源文件所有函数的具体实现。(3)test.c—— 测试文件main函数和菜单交互。2. 头文件中的防重复包含#ifndef_SEQLIST_H_#define_SEQLIST_H_// 所有声明放在这里#endif3. 编译命令示例gccgcc-otestSeqList.c test.c-stdc99-Wall六、顺序表的性能总结与适用场景1. 时间复杂度汇总操作时间复杂度备注尾插 / 尾删O(1)平均情况考虑扩容均摊后仍为 O(1)头插 / 头删 / 任意位置插入删除O(n)需要移动大量元素按位置访问O(1)随机访问是顺序表的最大优势按值查找O(n)无序情况下必须遍历2. 适用场景什么时候用顺序表⓵ 需要频繁随机访问如通过下标取第 i 个元素。⓶ 插入/删除操作只在尾部进行栈结构。⓷ 元素个数可预估或对内存连续有硬性要求如 DMA 传输。3. 不适用场景什么时候该换链表⓵ 频繁在头部或中间插入/删除。⓶ 元素个数极其不稳定且单个元素体积很大扩容拷贝成本高。