# 线性表、队列与栈：C++17 参考实现

版本：2026-09-11。对应“线性表 ADT 的实现与应用”的四个任务。

这是有明确契约和自测的教学参考，不是对尚未找回的原课程头文件、输入文件或线上评测规则的复原。现存练习关联的 `list_testcase.txt`、`radixSort1.txt`、P1886 与 P10473 提交版本未收录，不能据本附件宣称原评测通过。

## 文件

| 文件 | 用途 |
| --- | --- |
| array_list.hpp / singly_list.hpp / doubly_list.hpp | 固定槽位数组、单链表、双链表三种 List |
| array_dqueue.hpp / linked_dqueue.hpp | 循环数组与双链队列 |
| list_commands.hpp / list_demo.cpp | 安全逐行字符指令解析和可编译驱动 |
| applications.hpp | 窗口极值、非递归快排、股票跨度、两种基数排序 |
| expression.hpp | 带语法/数值错误结果的双栈表达式求值 |
| applications_demo.cpp | 四个任务中各应用的输入输出驱动 |
| tests.cpp / run_tests.py | 契约、边界、随机差分和驱动回归检查 |
| test-summary.json / manifest.json | 两种环境的真实测试摘要和文件 SHA256 |

## 契约摘要

- List 光标为元素的 0 基下标，空表为 -1。插入在当前之后并选中新值；删除后选后继，删除尾元素回到首元素；删空为 -1。
- `moveToNth(n)` 的 n 是移动后的 0 基下标。非法位置不改变表；这是修正原稿不一致行为后的参考约定，原下发规格待核。
- `find` 保留从当前光标向尾部查找的行为；失败停在尾部。空表读值是 `nullopt`。
- List 的 `init` 接受 0，但不接受负数。数组 capacity 是固定槽位数；链表 capacity 是实际结点数。limit 是独立的插入上限，已满插入返回 false。
- DQueue 容量必须大于 0。满队插入 false，空队读取/删除 nullopt；可区分合法 0、空字符串和“没有元素”。
- 所有表示禁止复制和移动。链式结构逐结点 delete，重复 init 和析构都清理。ArrayList 的 clear 是 O(1) 逻辑清空，固定槽位对象保留到 init/析构；ArrayDQueue 的 clear 会释放已占用槽位的元素。
- 元素需支持用到的复制/赋值/相等操作，ArrayList 还要求默认构造。未承诺用户自定义元素抛异常时的强异常保证，不把普通测试解释为任意类型/内存不足环境的证明。
- 窗口要求 1 <= k <= n；输出最小值与最大值两行。股票跨度找左侧最近的严格更大值，相等值弹出。
- QuickSort 是显式栈的随机轴快排，支持空序列，有 O(n^2) 最坏情况。默认 seed=20260911；并非用于不可信网络输入的排序服务。
- 整数基数排序范围是 uint64_t 的非负范围，负号和溢出在驱动中拒绝。位数由最大值控制，不能因为某一中间位都为 0 就提前停止。
- 字符串基数排序只接受恰好 8 个 ASCII 英文字母，先验证再读下标，按 ASCII 大写在小写前排序；短串、长串、非字母/Unicode 字节拒绝。
- 表达式支持十进制整数/小数、括号、+ - * / ^ 和一元正负号。幂右结合且优先于一元号：2^3^2=512，-2^2=-4，2^-3=0.125。科学计数法、隐式乘法不支持；除零、非实数幂、0 的非正次幂和非有限结果报错。
- 表达式错误结果含 0 基字节位置，驱动显示 1 基列号；输入最多 200000 字节，不使用递归解析。

## 编译与运行

在解压后的目录中执行，不需要安装第三方库：

```sh
g++ -std=c++17 -O1 -g -Wall -Wextra -Wpedantic -Werror tests.cpp -o tests
g++ -std=c++17 -O1 list_demo.cpp -o list_demo
g++ -std=c++17 -O1 applications_demo.cpp -o applications_demo
./tests
./list_demo single < list_testcase.txt > single-output.txt
./applications_demo radix-int < radixSort1.txt
```

两个输入文件由使用者提供，并非附件中不存在却假称随附的原始测试集。下方示例可以直接输入标准输入。

若已有 Python 3.9+ 和 GCC，可运行完整自测，输出目录必须是新的目录：

```sh
python3 run_tests.py --cxx /usr/bin/g++ --output ../check-local
python3 run_tests.py --cxx /usr/bin/g++ --output ../check-sanitized --sanitize
```

Windows 传入本机现有 `g++.exe` 的绝对路径。脚本将临时文件和编译产物写到显式指定的目录，并保存每个步骤的 stdout/stderr 与 results.json；不安装工具，不删除以前的测试证据。远端受限测试使用 --run-as nobody；普通用户在自己的环境不需要这个选项。

## 输入输出

- `list_demo [array|single|double]`：每行包含 +x、=x、-、#、*、>、<、~。两个带参命令允许空白分隔，但字符必须是非空白可打印 ASCII。整行语法失败不执行；合法行的失败操作不改变状态，其他操作继续。每个合法行输出状态。
- `applications_demo window`：先 n k，再 n 个 int。例 `8 3 / 1 3 -1 -3 5 3 6 7`（/表示换行）输出 `-1 -3 -3 -3 3 3` 和 `3 3 5 5 6 7` 两行。
- `applications_demo quick`：先 n，再 n 个 int；输出排序序列。
- `applications_demo stock`：先 n，再 n 个 int。例 `7 / 100 80 60 70 60 75 85` 输出 `1 1 1 2 1 4 6`。
- `applications_demo expr`：每行一个表达式，成功时输出 6 位小数，错误写入 stderr。
- `applications_demo radix-int`：直到 EOF 的非负十进制整数，以空白分隔；不是先给 n。
- `applications_demo radix-string`：直到 EOF 的 8 字母 ASCII 串，以空白分隔；不是先给 n。

计数模式要求 0 <= n <= 200000，window 还受合法 k 限制；整数 token 不支持前导 + 或科学计数法。缺值、多余值、非法数字和范围溢出均拒绝。退出码 0 表示成功，2 表示输入或操作错误。

## 复核边界

GCC 14.2.0 / Windows 与 GCC 13.3.0 / Ubuntu 均完成 35 项检查，包括 2913195 次单元断言、180000 次 List 随机操作、120000 次队列随机操作、3000 组算法差分、5000 棵表达式随机语法树及 10000 个混合字符串。随机种子固定为 20260911 至 20260914。

Ubuntu 以 nobody 用户执行 ASan/UBSan 和泄漏检测，35 项全部通过。随机测试不是对全部输入的证明；参阅 [GCC instrumentation 文档](https://gcc.gnu.org/onlinedocs/gcc/Instrumentation-Options.html) 了解检查范围，[C++ delete 语义](https://eel.is/c++draft/expr.delete)说明正确释放的要求。