[README] 更新项目概述、算法史故事、新手破冰指南、避坑锦囊等核心内容
学生：梁伟杰 (202521093001) 选题编号：A15 所属分队：红队 指导教师：朱宗晓
本项目源自《计算机程序设计艺术》（TAOCP）算法库的知识的系统化工程落地。
1960年，Edward Fredkin发明了Trie树以实现 O(L) 的快速字符串检索。但在内存昂贵的年代，大量的单分支节点造成了严重的内存浪费。美国空军研究实验室的 Morrison 于1968年提出了 PATRICIA 树，消除了所有单分支节点，使树节点数严格等于键数。
1968年，登月计划前夕，美国空军研究实验室的 Morrison 发明了 PATRICIA。当时的计算机内存比黄金还要昂贵。一个无脑的 Trie 树会耗尽整个系统的物理内存，导致设备死机。
PATRICIA 的伟大之处在于，它通过极致的数学与指针技巧，把树的节点数严格压缩到了等于键的数量。
在今天，我们虽然有了几十 GB 的内存，但在工业控制、航天探测、IoT 边缘网关等安全关键环境（Safety-Critical）中，内存依然极其受限。每一字节的浪费，都可能转化为网络拥塞和设备发热；而对数据结构的极致压榨，正是工程师面对有限物理资源时，所能展现出的最高级别的职业尊严与浪漫。
为自动化边缘网关设计轻量级路由表。首先实现标准的 Trie 树，处理简单的设备字符名精确查找。接着将其重构为紧缩的 PATRICIA 二叉树结构，处理变长二进制 IP 字符串的高效前缀匹配与无重复键插入。
理解在内存受限嵌入式环境下的空间优化哲学，培养对每一字节都精益求精的代码工匠精神。
在向标准 Trie 树和 PATRICIA 树中同时插入 10 万条相同的工业路由器 IP 前缀规则后，调用 memory_stats() 函数，打出两者的内存消耗对比图表，体会空间折叠魔法带来的极致浪漫。
如果把网络通信比作全球邮政系统：
简而言之：算法库提供的是”字符串检索理论”，而A15项目要求你完成”时间与空间的极限工程博弈”。
你的现状：只会用 strcmp() 在数组里循环比对字符串。
你要做的：用空间换取绝对的时间。
定义一个 26 叉树（假设先处理纯小写字母的设备名）。每个节点包含一个 is_end 标志和一个大小为 26 的指针数组 struct Node* children[26];。
插入 “cat”：在根节点找到下标 ‘c’-‘a’ 的指针，往下走；再找 ‘a’，再找 ‘t’，把最后的节点标记为 is_end = true。
体会速度：找 “cat” 只需要 3 次指针跳转，与词典里有 10 个词还是 100 万个词毫无关系！这就是 O(L) 的魔法。
你的现状：觉得 Trie 树很完美，天下无敌。
你要做的：计算它的物理代价。
把刚才的 Trie 打印出内存占用情况。如果你插入了长字符串 “industrialrouter”，中间这 16 个字符，每个节点都开辟了 26 个指针（64位系统下是 26*8 = 208 字节），但其中 25 个指针全是 NULL！
这种只有一个有效子节点的节点被称为”单分支节点”。在 IP 地址（32位二进制，只有 0 和 1 两个分支）匹配中，如果你插入了 11000000.10101000…，整棵树将变成一根极其冗长且浪费空间的”竹子”。
你要做的：理解 PATRICIA 的核心哲学——“只有出现分叉的地方，才值得被记录”。
重新定义节点。扔掉庞大的指针数组，改为只记录一个数字：check_bit（检测位索引），以及 left 和 right 两个指针。
跳跃机制：如果插入 “1000” 和 “1010”，它们在第 2 位（从 0 开始）才出现分叉。所以根节点的 check_bit 直接设为 2。查询时，直接提取目标字符串的第 2 位，是 0 走左，是 1 走右。第 0 和第 1 位被完美地”折叠”跳过了。
回边（Back Edge）的终极魔法：PATRICIA 树没有空指针，叶子节点的指针会”指回”树上更浅的节点，甚至是自己！
你要做的：解决 PATRICIA 树的”盲目自信”。
因为查询时跳过了很多位，PATRICIA 树走到最后（遇到回边时），找到的可能是一个”长得很像”的错误答案。
强制全量比对：在寻路结束时，必须拿找到的 key 和查询的 key 进行一次完整的 strcmp。只有这一次比对成功，才算是真正的路由命中。
在实现这套”内存压缩系统”时，初学者极易踩中以下三个雷区：
在普通的树中，遍历终止条件是 node == NULL。但在 PATRICIA 树中，没有 NULL！
你必须依靠检测位来判断是否到了尽头：while (next_node->check_bit > current_node->check_bit)。一旦发现下一个节点的检测位竟然变小了或者相等了，说明你踩到了”回边”，这才是循环结束的标志。
IP 路由不是精确匹配。如果路由表里有 192.168.1.*，你查 192.168.1.100 应该命中。
在设计节点时，你需要仔细区分”普通节点”和”路由终止节点”。在向下搜索的过程中，需要用一个变量时刻记录”沿途最后一次遇到的合法路由规则”，当走到尽头发现不匹配时，返回沿途记录的那个最长前缀。
IP 地址的处理不是字符数组，而是真正的 Bit 位。
写一个健壮的 get_bit(ip_string, bit_index) 函数是整个项目成败的关键。要注意网络字节序（大端序）与主机字节序（小端序）的差异，或者为了简化教学，直接先用仅包含 ‘0’ 和 ‘1’ 的 char 数组来模拟二进制。
. ├── README.md # 本文件（项目总览） ├── Makefile # GCC编译脚本 ├── .gitignore # Git忽略规则 ├── src/ # 源代码目录 │ ├── main.c # 主程序入口 │ ├── algorithm_a.c # 算法A实现 │ ├── algorithm_b.c # 算法B实现 │ ├── utils.c # 工具函数 │ └── include/ # 头文件目录 │ ├── algorithm_a.h │ ├── algorithm_b.h │ └── utils.h ├── docs/ # 文档目录 │ ├── 01-需求分析.md │ ├── 02-算法史故事.md │ ├── 03-功能框图.png │ ├── 04-详细设计.md │ └── 05-测试报告.md ├── report/ # 课程设计报告 │ └── 设计报告模板.md └── test/ # 测试代码 ├── unit_test.c # 单元测试 └── test_data/ # 测试数据集
make # 编译主程序 make test # 编译测试 make clean # 清理
./main ./unit_test
[A-模块] 具体修改内容 示例： [A-Trie树] 实现标准多叉Trie树的插入与精确查找 [A-PATRICIA] 实现单分支节点压缩与检测位记录 [A-前缀匹配] 实现最长前缀匹配算法 [A-内存统计] 实现节点数与内存占用统计
源自《计算机程序设计艺术》的新故事 —— 这本书的作者栏，写着你的名字。
A15 工业路由器IP前缀加速检索引擎 — 梁伟杰(202521093001) 课程设计仓库。组合算法：Trie树 + Radix树。TAOCP出处：卷3 §6.3 + 6.3S。
版权所有：中国计算机学会技术支持：开源发展技术委员会 京ICP备13000930号-9 京公网安备 11010802032778号
A15 工业路由器IP前缀高速检索与内存压缩系统
学生：梁伟杰 (202521093001) 选题编号：A15 所属分队：红队 指导教师：朱宗晓
项目概述
本项目源自《计算机程序设计艺术》（TAOCP）算法库的知识的系统化工程落地。
算法史故事
1960年，Edward Fredkin发明了Trie树以实现 O(L) 的快速字符串检索。但在内存昂贵的年代，大量的单分支节点造成了严重的内存浪费。美国空军研究实验室的 Morrison 于1968年提出了 PATRICIA 树，消除了所有单分支节点，使树节点数严格等于键数。
1968年，登月计划前夕，美国空军研究实验室的 Morrison 发明了 PATRICIA。当时的计算机内存比黄金还要昂贵。一个无脑的 Trie 树会耗尽整个系统的物理内存，导致设备死机。
PATRICIA 的伟大之处在于，它通过极致的数学与指针技巧，把树的节点数严格压缩到了等于键的数量。
在今天，我们虽然有了几十 GB 的内存，但在工业控制、航天探测、IoT 边缘网关等安全关键环境（Safety-Critical）中，内存依然极其受限。每一字节的浪费，都可能转化为网络拥塞和设备发热；而对数据结构的极致压榨，正是工程师面对有限物理资源时，所能展现出的最高级别的职业尊严与浪漫。
课程任务
为自动化边缘网关设计轻量级路由表。首先实现标准的 Trie 树，处理简单的设备字符名精确查找。接着将其重构为紧缩的 PATRICIA 二叉树结构，处理变长二进制 IP 字符串的高效前缀匹配与无重复键插入。
核心要求
工程哲学：可控可观（Controllability-Observability）
工程伦理
理解在内存受限嵌入式环境下的空间优化哲学，培养对每一字节都精益求精的代码工匠精神。
在向标准 Trie 树和 PATRICIA 树中同时插入 10 万条相同的工业路由器 IP 前缀规则后，调用 memory_stats() 函数，打出两者的内存消耗对比图表，体会空间折叠魔法带来的极致浪漫。
新手破冰指南：C语言视角的四步上手路径
如果把网络通信比作全球邮政系统：
简而言之：算法库提供的是”字符串检索理论”，而A15项目要求你完成”时间与空间的极限工程博弈”。
第一步：打破字符串比较的黑盒（建立 Standard Trie）
你的现状：只会用 strcmp() 在数组里循环比对字符串。
你要做的：用空间换取绝对的时间。
定义一个 26 叉树（假设先处理纯小写字母的设备名）。每个节点包含一个 is_end 标志和一个大小为 26 的指针数组 struct Node* children[26];。
插入 “cat”：在根节点找到下标 ‘c’-‘a’ 的指针，往下走；再找 ‘a’，再找 ‘t’，把最后的节点标记为 is_end = true。
体会速度：找 “cat” 只需要 3 次指针跳转，与词典里有 10 个词还是 100 万个词毫无关系！这就是 O(L) 的魔法。
第二步：直面内存灾难（可观性数据的震撼）
你的现状：觉得 Trie 树很完美，天下无敌。
你要做的：计算它的物理代价。
把刚才的 Trie 打印出内存占用情况。如果你插入了长字符串 “industrialrouter”，中间这 16 个字符，每个节点都开辟了 26 个指针（64位系统下是 26*8 = 208 字节），但其中 25 个指针全是 NULL！
这种只有一个有效子节点的节点被称为”单分支节点”。在 IP 地址（32位二进制，只有 0 和 1 两个分支）匹配中，如果你插入了 11000000.10101000…，整棵树将变成一根极其冗长且浪费空间的”竹子”。
第三步：折叠空间，跳过废话（实现 PATRICIA 树）
你要做的：理解 PATRICIA 的核心哲学——“只有出现分叉的地方，才值得被记录”。
重新定义节点。扔掉庞大的指针数组，改为只记录一个数字：check_bit（检测位索引），以及 left 和 right 两个指针。
跳跃机制：如果插入 “1000” 和 “1010”，它们在第 2 位（从 0 开始）才出现分叉。所以根节点的 check_bit 直接设为 2。查询时，直接提取目标字符串的第 2 位，是 0 走左，是 1 走右。第 0 和第 1 位被完美地”折叠”跳过了。
回边（Back Edge）的终极魔法：PATRICIA 树没有空指针，叶子节点的指针会”指回”树上更浅的节点，甚至是自己！
第四步：兜底验证（闭环）
你要做的：解决 PATRICIA 树的”盲目自信”。
因为查询时跳过了很多位，PATRICIA 树走到最后（遇到回边时），找到的可能是一个”长得很像”的错误答案。
强制全量比对：在寻路结束时，必须拿找到的 key 和查询的 key 进行一次完整的 strcmp。只有这一次比对成功，才算是真正的路由命中。
给新手的避坑锦囊
在实现这套”内存压缩系统”时，初学者极易踩中以下三个雷区：
1. 无限死循环的深渊（遍历陷阱）
在普通的树中，遍历终止条件是 node == NULL。但在 PATRICIA 树中，没有 NULL！
你必须依靠检测位来判断是否到了尽头：while (next_node->check_bit > current_node->check_bit)。一旦发现下一个节点的检测位竟然变小了或者相等了，说明你踩到了”回边”，这才是循环结束的标志。
2. 最长前缀匹配（LPM）的语义误区
IP 路由不是精确匹配。如果路由表里有 192.168.1.*，你查 192.168.1.100 应该命中。
在设计节点时，你需要仔细区分”普通节点”和”路由终止节点”。在向下搜索的过程中，需要用一个变量时刻记录”沿途最后一次遇到的合法路由规则”，当走到尽头发现不匹配时，返回沿途记录的那个最长前缀。
3. 指针偏移的灾难（C语言位操作）
IP 地址的处理不是字符数组，而是真正的 Bit 位。
写一个健壮的 get_bit(ip_string, bit_index) 函数是整个项目成败的关键。要注意网络字节序（大端序）与主机字节序（小端序）的差异，或者为了简化教学，直接先用仅包含 ‘0’ 和 ‘1’ 的 char 数组来模拟二进制。
目录结构
快速开始
编译
运行
里程碑
Git提交规范