SCHOOL
1a5ef9063c
新增功能： - q_addpro 任意位置插入，含位置合法性检查（0 <= num <= end） - q_reducepro 任意位置删除，含位置合法性检查（0 <= num <= end-1） - q_reduce 出队，一行复用 q_reducepro(q, 0, x) 修复： - q_add 的扩容判断改用 end。原先用未初始化的 length， 导致 "length == max" 永远不成立，扩容代码从未执行过，是潜在的堆越界 结构调整： - 去掉 length 字段 —— 它与 end 表示同一件事，并存必然产生不一致 - 1.c 改名为 seqlist.c（顺序表 sequential list） 调试记录.md 改名为 seqlist-debug-notes.md 验收： - gcc -Wall -Wextra 零 warning 零 error - 18 个用例全绿（含 0 号位 / 末尾 / 末尾+1 / 负数 / 空表 / 自动扩容） 详见 seqlist-debug-notes.md 中记录的 8 个坑及沉淀的原则。
267 lines
11 KiB
Markdown
267 lines
11 KiB
Markdown
# seqlist —— 顺序表开发记录
|
||
|
||
用 C 手写顺序表（顺序存储的线性表）：动态数组 + 任意位置插入/删除。
|
||
|
||
---
|
||
|
||
## 状态
|
||
|
||
| | |
|
||
|---|---|
|
||
| 源文件 | `seqlist.c` |
|
||
| 编译 | `gcc -Wall -Wextra seqlist.c -o seqlist.exe` —— **零 warning 零 error** |
|
||
| 进度 | 增、删、查全部完成 ✅ |
|
||
|
||
## 接口一览
|
||
|
||
| 函数 | 作用 | 返回值 |
|
||
|---|---|---|
|
||
| `q_init(q, len)` | 建表，容量 len | 0 |
|
||
| `q_add(q, x)` | 尾部追加（容量不够自动扩容） | 0 |
|
||
| `q_addpro(q, num, x)` | 在 num 号位插入 x | 0 成功 / −1 位置非法 |
|
||
| `q_reducepro(q, num, &x)` | 取走 num 号位的元素，值写给 x | 0 成功 / −1 位置非法 |
|
||
| `q_reduce(q, &x)` | 取走队头元素 | 同 `q_reducepro` |
|
||
| `printall(q)` | 打印全表 | 0 |
|
||
|
||
## 结构体
|
||
|
||
```c
|
||
typedef struct {
|
||
int max; // 容量
|
||
int *start; // 内存起始地址
|
||
int front; // 预留（循环队列要用）
|
||
int end; // 元素个数，同时也是"下一个空位"的下标
|
||
} queue;
|
||
```
|
||
|
||
**决定：不要 `length` 字段。** 曾经有过一个 `length`，和 `end` 表示同一件事。
|
||
两个变量记同一件事，就必然有"两个数不一样"的那天。现在统一用 `end`。
|
||
|
||
## 约定
|
||
|
||
- **`end` 是"下一个空位"的下标**，数值上等于元素个数。
|
||
- 合法下标范围：`0 .. end-1`
|
||
- 合法**插入**位置：`0 <= num <= end`（可以插在末尾，等于追加）
|
||
- 合法**删除**位置：`0 <= num <= end-1`（不能删"末尾之后"，那儿没东西）
|
||
|
||
---
|
||
|
||
# 踩过的坑
|
||
|
||
按发现顺序排列。每条都记下"当时是怎么识别出来的"——这个比结论更值钱。
|
||
|
||
## 1. `realloc` 尺寸算错 → 堆越界
|
||
|
||
```c
|
||
q->start = realloc(q->start, sizeof(q->max)); // ❌
|
||
q->start = realloc(q->start, q->max * sizeof(int)); // ✅
|
||
```
|
||
|
||
`sizeof(q->max)` 是"一个 int 占几字节"(4)，不是"总共要几字节"。
|
||
|
||
**现象**：打印出来一串每次都不同的随机数（`490`→`467`、`1494745424`→`-960036528`）。
|
||
|
||
> 💡 **识别技巧：数据每次运行都不一样 → 读到的不是自己的数据，是别人的内存。**
|
||
|
||
因为 realloc 只申请了 4 字节，后面的格子被堆的管理数据占用了。
|
||
|
||
## 2. 忘了把 `x` 真正写进去
|
||
|
||
平移做完了，但没执行 `q->start[num] = x;`，参数 `x` 从头到尾没被用过。
|
||
|
||
> 💡 编译器的 warning 里点了名：`unused parameter 'x'`。
|
||
> **编译器说某个参数"没被用过"，八成是漏写了什么。**
|
||
|
||
## 3. 平移循环：起点、方向、类型，三个错
|
||
|
||
```c
|
||
for (size_t i = q->end; i < num-1; i--) // ❌ 三个错全占了
|
||
for (int i = q->end - 1; i >= num; i--) // ✅
|
||
```
|
||
|
||
| 错 | 表现 | 原因 |
|
||
|---|---|---|
|
||
| **起点** `end` | 多搬一次"空气"，垃圾值混进表 | `end` 是空位，真数据只到 `end-1` |
|
||
| **方向** `i--` 配 `i <` | 条件第一秒就为假，**循环一次都不跑** | 往上数的条件配了往下数的循环 |
|
||
| **类型** `size_t` | 往下数会"翻车" | 无符号类型减到 0 以下会变成天文数字 |
|
||
|
||
**方向为什么必须从后往前**：如果从前往后搬，`start[1] = start[0]` 会先把 1 号位
|
||
原来等着被搬的东西**踩掉**。从后往前，每一格的目标位都是刚刚腾出来的。
|
||
|
||
> 💡 **识别技巧：在循环里插一行 `printf("i=%d\n", i)`。**
|
||
> 空的就是一次没跑 → 怀疑条件；有值但值不对 → 怀疑起点。一次插桩把问题一劈两半。
|
||
|
||
> 💡 **写循环之前先在注释里填三个空：起点、停手线、方向。**
|
||
> 填不完，说明还没想清楚，先别写。
|
||
|
||
## 4. `size_t` 到底是什么
|
||
|
||
**无符号整数**，标准库用来表示"大小/个数"。`sizeof`、`malloc`、`strlen` 都用它。
|
||
本机是 8 字节，最大 18446744073709551615。
|
||
|
||
**为什么危险**：拿一个"可能为负"的数和它比较时，**负数会被转成天文数字**。
|
||
|
||
```c
|
||
int num = 0;
|
||
size_t i = 5;
|
||
i > num - 1 // 心里想的是 5 > -1 → 成立
|
||
// 实际: -1 被转成 18446744073709551615
|
||
// 5 > 18446744073709551615 → 不成立！
|
||
```
|
||
|
||
**口诀：`size_t` 是"往上数"的类型；要往下数，用 `int`。**
|
||
|
||
> 📌 别盲信编辑器补全。`for (size_t i = 0; i < n; i++)` 是最标准的"往上数"写法，
|
||
> 但它不知道你的循环是倒着走的。**循环头必须自己想清楚再按 Tab。**
|
||
|
||
## 5. `end + 1` 这个 off-by-one
|
||
|
||
```c
|
||
for (int i = num; i < q->end+1; i++) // ❌ 删多了一次
|
||
for (int i = num; i < q->end-1; i++) // ✅
|
||
```
|
||
|
||
`+1` 让 `i` 跑到了 `end`，把"空位"当成了"数据"，读写了数据之外的内存。
|
||
|
||
> 📌 **规律：`end` 是空位、不是数据。凡是循环想碰"最后一个元素"，上界就得是 `end-1`。**
|
||
|
||
## 6. 没有参数校验 → 静默堆越界
|
||
|
||
`q_addpro(&q, 11, x)` 在表长只有 5 时被接受，数据写到了下标 11。
|
||
程序不报错、不崩溃、静默跑完。
|
||
|
||
**教训**：
|
||
- **越界 ≠ 崩溃。** Windows 上页是按 4KB 给的，多写几个字节可能还在同一页里。
|
||
最危险的就是这种"静默写坏"。
|
||
- **容量不够可以扩；位置不存在，只能拒绝。** 用扩容去接非法位置，
|
||
只会在表中间造出"洞"，那就不是顺序表了。
|
||
- **做"安全检查"的人也要防**：如果非法位置能触发任意大的 `realloc`，
|
||
别人传个 `num = 100000000` 就能把你的程序搞垮。
|
||
|
||
## 7. `q->length` 从未初始化 → 扩容逻辑变成死代码
|
||
|
||
`q_init` 设了 `max`、`front`、`end`，唯独没设 `length`。
|
||
而 `q_add` 的扩容判断是 `if (q->length == q->max)` —— 拿一个**栈上的随机数**做判断。
|
||
|
||
实测：重新初始化后 `length` 还留着上一次的 151，于是 `151 == 3` 永远不成立，
|
||
**扩容那段代码一次都没跑过**。往容量 3 的表里放 6 个数，后 3 个直接写到缓冲区外面。
|
||
|
||
> 📌 **`malloc` 出来的是"别人用过的"，栈上的变量是"上个人留下的"。**
|
||
> **任何没被你亲自赋过值的字段，都是在读别人的垃圾。**
|
||
> **初始化时，结构体的每个字段都应该是确定的。**
|
||
|
||
## 8. 删 `length` 字段时，多留了一行 `q->end++`
|
||
|
||
把 `q->length++;` 换成 `q->end++;` —— 但 `q->end++` 那行本来就在上面：
|
||
|
||
```c
|
||
q->start[q->end] = num;
|
||
q->end++; // 本来就有
|
||
q->end++; // 新加的 ← 每加一个数，end 往前走两格
|
||
```
|
||
|
||
**现象**：加了 `1 2 3`，得到 `end=6`、表 `[1 0 2 0 3 0]`（元素之间夹着洞）。
|
||
|
||
**注意：编译器一条 warning 都没报。** 两句 `q->end++;` 完全合法 ——
|
||
语法没错、类型没错，**它错在"意图"上，而编译器读不懂意图**。
|
||
|
||
> 📌 **教训一：改代码不是"找一行相似的替换掉"。**
|
||
> 替换之前先问："**我要换掉的那个东西，是不是真的在这儿？**"
|
||
> （和之前那个复制粘贴没改的 `if (num>q->max)` 是同一类毛病：
|
||
> 靠"形状相似"改代码，而不是靠"理解这块地方在干什么"。）
|
||
|
||
> 📌 **教训二：`零 warning` ≠ `正确`。**
|
||
> 编译器能挡住语法错、类型错、明显笔误，**挡不住逻辑错**。
|
||
> 这半边的责任只能靠测试来扛。
|
||
>
|
||
> | 手段 | 抓什么 | 抓不到什么 |
|
||
> |---|---|---|
|
||
> | `gcc -Wall -Wextra` | 语法错、类型错、可疑写法 | **逻辑错** |
|
||
> | **跑测试** | 逻辑错 | 编译期问题 |
|
||
|
||
---
|
||
|
||
# 沉淀下来的原则
|
||
|
||
1. **初始化要把所有字段都设上。** 没设的字段 = 别人的垃圾。
|
||
2. **校验放在最前面。** 碰内存的动作，一个都不能在校验之前发生。
|
||
3. **改原因，不要在下游拦症状。** 用 `if` 挡住错的循环，循环还是错的。
|
||
4. **能用一个路径解决的，别开两个。** 两个分支 = 两份要维护的逻辑。
|
||
5. **错误要一路传上去，不能半路被吞。** `return q_reducepro(q,0,x);` 就是全部。
|
||
6. **越界有两种**：逻辑越界（读自己的垃圾）不崩；物理越界（写别人的内存）危险。
|
||
7. **先看函数签名要什么类型**（编译器会念 `expected ...`），再检查手上的变量。
|
||
`&q` 在 `q` 已是指针时多加一层；`*x` 在 `x` 已是指针时剥掉一层。
|
||
8. **边界测试**：测"0 号位""末尾""末尾+1""负数""空表"。
|
||
**只测"正常情况"等于没测。**
|
||
9. **先写期望，再跑。** 不然"看起来对"会骗你。
|
||
（曾经看到 `666` 出现在 0 号位就以为插入对了，其实原来的 `1` 被覆盖了。）
|
||
10. **检查返回值**，也要检查**表本身有没有被动过**。报错了但数据被改坏，等于白报。
|
||
|
||
---
|
||
|
||
# 测试清单（当前全绿）
|
||
|
||
**插入**（表 `1 2 3 4 5`）
|
||
|
||
| 调用 | 期望 |
|
||
|---|---|
|
||
| `addpro(0, 666)` | `666 1 2 3 4 5` |
|
||
| `addpro(2, 666)` | `1 2 666 3 4 5` |
|
||
| `addpro(end, 666)` | `1 2 3 4 5 666` |
|
||
| `addpro(end+1, 666)` | −1，表不动 |
|
||
| `addpro(-1, 666)` | −1，表不动 |
|
||
|
||
**删除**（表 `1 2 3 4 5`）
|
||
|
||
| 调用 | 期望 |
|
||
|---|---|
|
||
| `reducepro(0)` | x=1，表变 `2 3 4 5` |
|
||
| `reducepro(2)` | x=3，表变 `1 2 4 5` |
|
||
| `reducepro(end-1)` | x=5，表变 `1 2 3 4` |
|
||
| `reducepro(end)` | −1，表不动 |
|
||
| `reducepro(-1)` | −1，表不动 |
|
||
| `reducepro(0)`（空表） | −1，表不动 |
|
||
|
||
**队头出队**
|
||
|
||
| 调用 | 期望 |
|
||
|---|---|
|
||
| 连续 `q_reduce` 五次 | 依次拿到 1 2 3 4 5，表变空 |
|
||
| 空表再 `q_reduce` | −1 |
|
||
|
||
**扩容**
|
||
|
||
- [x] 往容量 3 的表里加 6 个 → `max` 涨到 8，表 `[1 2 3 4 5 6]` ✅
|
||
|
||
---
|
||
|
||
# 环境与工具
|
||
|
||
- **编码**：源文件是 GBK，PowerShell 里中文正常显示。
|
||
**不要**加 `-fexec-charset=GBK`（会转两次，反而乱码）。
|
||
- **编译**：`gcc -Wall -Wextra seqlist.c -o seqlist.exe`
|
||
- **检查警告要用完整编译**：`-fsyntax-only` 会漏掉 `-Wreturn-type` 这类后阶段警告。
|
||
- **本机没装 ASan**（AddressSanitizer）。想抓堆越界可以自己埋"地雷"：
|
||
多申请一格、放一个哨兵值、事后检查它有没有被动过。
|
||
（ASan 的原理就是这个，只是自动化的：在每块内存前后埋一圈"红区"并标记为禁止访问。）
|
||
- **VSCode**：`.`vscode/tasks.json` 里配了构建任务，`Ctrl+Shift+B` 编译，
|
||
结果进「问题」面板。**但记住：编辑器的波浪线是参考，编译器才是判决。**
|
||
- **看循环变量**：`gdb` 可用 `watch` 命令给内存地址下监视点，值一变就中断。
|
||
|
||
---
|
||
|
||
# 下一步：循环队列
|
||
|
||
顺序表做队列用时，暴露一个痛点：
|
||
|
||
> **`q_reduce` 每次从队头取元素，都要把后面所有元素往前搬一遍。表越长越慢。**
|
||
|
||
`q_reduce(q, &x)` 内部调的是 `q_reducepro(q, 0, x)` —— 删 0 号位，
|
||
意味着 `end-1` 个元素全都要挪窝。取 N 次就是 O(N²)。
|
||
|
||
**循环队列要解决的就是这个**：不搬数据，改成让"队头"和"队尾"两个下标
|
||
在数组里**绕圈走**，走到末尾就回到开头。
|
||
|
||
预告：到时候会遇到一个新问题 —— **队空和队满，怎么区分？**
|
||
（`front == rear` 既可能是空、也可能是满。）
|