C语言：顺序表详解

C语言顺序表详解SeqList · 连续内存里的线性表 · 从结构定义到动态扩容一次讲透一、什么是顺序表线性表是n个相同类型元素的有序序列。顺序表是线性表最朴素的实现——用一段连续的内存依次存放元素。数组就是最简单的顺序表。但顺序表通常指带容量管理的动态数组能自动扩容、能插入删除。▶ 顺序表三要素连续内存、相同类型、逻辑顺序物理顺序。二、结构定义静态 vs 动态2.1 静态顺序表#define MAX_SIZE 100typedef struct {int data[MAX_SIZE]; //定长数组int size; //当前元素个数} SeqListStatic;缺点容量写死。存满了要么拒绝要么溢出——毫无弹性。2.2 动态顺序表推荐typedef struct {int* data; //指向堆上的连续内存int size; //当前元素个数int capacity; //容量最多能存多少个} SeqList;▶ 动态顺序表的核心思想容量不够就 realloc 扩容元素内存由 malloc 管着。三、初始化与销毁void seqlist_init(SeqList* sl, int init_cap) {sl-data (int*)malloc(init_cap * sizeof(int));sl-size 0;sl-capacity init_cap;}void seqlist_destroy(SeqList* sl) {free(sl-data);sl-data NULL;sl-size sl-capacity 0;}▶ 每次 malloc 都有对应的 free。初始化时分配销毁时归还成对出现。四、尾插与尾删最常用的操作void seqlist_push_back(SeqList* sl, int val) {if (sl-size sl-capacity) {seqlist_grow(sl); //扩容}sl-data[sl-size] val;}void seqlist_pop_back(SeqList* sl) {if (sl-size 0) sl-size--;}尾插的时间复杂度 O(1)均摊尾删 O(1)——这是顺序表最擅长的操作。五、动态扩容核心中的核心void seqlist_grow(SeqList* sl) {int new_cap sl-capacity 0 ? 4 : sl-capacity * 2;int* tmp (int*)realloc(sl-data, new_cap * sizeof(int));if (tmp NULL) {perror(realloc failed);exit(1);}sl-data tmp;sl-capacity new_cap;}扩容策略容量×2均摊后每次插入 O(1)最经典的策略固定N每次插入均摊 O(N)性能差realloc 返回值要用临时变量接失败时原指针不丢▶ 扩容量×2 的原因均摊分析。N次插入的总 realloc 成本 O(N)平均每次 O(1)。六、任意位置插入与删除6.1 指定位置插入pos ∈ [0, size]int seqlist_insert(SeqList* sl, int pos, int val) {if (pos 0 || pos sl-size) return 0;if (sl-size sl-capacity) seqlist_grow(sl);//从后往前搬移元素给pos腾位置for (int i sl-size; i pos; i--)sl-data[i] sl-data[i - 1];sl-data[pos] val;sl-size;return 1;}6.2 指定位置删除int seqlist_erase(SeqList* sl, int pos) {if (pos 0 || pos sl-size) return 0;//从前往后搬移覆盖被删位置for (int i pos; i sl-size - 1; i)sl-data[i] sl-data[i 1];sl-size--;return 1;}▶ 插入/删除的平均时间复杂度 O(N)——这是顺序表最贵的操作。频繁中间插入请考虑链表。七、查找与修改int seqlist_find(SeqList* sl, int val) {for (int i 0; i sl-size; i)if (sl-data[i] val) return i;return -1;}//按下标访问O(1)随机访问顺序表的杀手锏int seqlist_at(SeqList* sl, int idx, int* out) {if (idx 0 || idx sl-size) return 0;*out sl-data[idx];return 1;}▶ 按下标访问 O(1) 是顺序表相对链表的绝对优势——数据在内存里连续存放地址直接可算data[i] data i*sizeof(int)。八、顺序表 vs 链表┌──────────┬───────────────┬───────────────┐│ │ 顺序表 │ 链表 │├──────────┼───────────────┼───────────────┤│ 随机访问 │ O(1) ★ │ O(n) ││ 尾插尾删 │ O(1) ★ │ O(1) ││ 中间插入 │ O(n) │ O(1) ★ ││ 缓存友好 │ ★ 好 │ 差 ││ 空间 │ 连续可能浪费│ 分散有指针开销││ 扩容 │ realloc │ 无需动态节点│└──────────┴───────────────┴───────────────┘▶ 结论频繁按下标访问 → 顺序表频繁中间插入删除 → 链表。工程里两者结合才是常态。九、八条常见错误① 忘了检查 pos 越界——插入/删除前不验证下标静默写坏内存② size 和 capacity 混淆——size是元素个数capacity是容量③ 扩容后忘了更新 capacity——下次插入直接溢出④ realloc 返回值直接赋给原指针——失败时空指针丢失原数据⑤ 插入从前往后搬移——应该从后往前否则覆盖还没搬的元素⑥ 删除从后往前搬移——应该从前往后⑦ 销毁后不置 NULL——野指针⑧ 结构体按值传参——复制整个结构修改无效要传指针十、总结▶ 顺序表 连续内存 容量管理。数组是它的静态形态动态数组是它的完全体。▶ 三个状态量size有多少、capacity能存多少、data存在哪。▶ 扩容×2 realloc 临时变量接收是顺序表的两条铁律。▶ 随机访问 O(1) 是它的王牌中间插入 O(n) 是它的软肋。▶ 凡是按下标存取、尾部增删的场合顺序表永远是最优解。The first rule of Fight Club is: you do not talk about Fight Club.—— Tyler Durden, Fight Club—— 顺序表的第一条规则是下标永远从0开始。第二条规则永远不要越界。— END —