C-Journey

主题

正常

阶段 3 Lab：查找进化史 ​

实验目标 ​

「查找」这件事贯穿了阶段 3 的一半章节：链表按值查找是 O(n)、排序后二分是 O(log n)、BST 平均 O(log n)、哈希表平均 O(1)。这个 Lab 把这条进化线完整走一遍——你在同一个「找数」问题上，亲手把复杂度从线性一路压到常数，每一步都真跑、第 5 步还要用 clock() 计时实锤「量级的差距」。走完你会对「为什么选对数据结构值几个数量级」有肌肉记忆，这正好是第 12 章大 O 收口要交的货。

所有实验在 /tmp 下独立目录做。每步有验收标准；卡住先回题面每步标注的章节链接读教材，再不行看实验参考。凡是 malloc 过的程序，交卷前用 -fsanitize=address,undefined 跑一遍。

步骤 1（L1）：O(n) 的起点——线性查找数比较次数 ​

目标：在乱序数组里线性查找，数清楚「找到」和「找不到」各要比较多少次。

  1. 写 linear_search(const int* a, int n, int key, int* compares)：从头扫到尾，每比一次 (*compares)++，命中返回下标、扫完返回 -1。
  2. 在 {8, 3, 9, 1, 5} 里找 9（在表里）和 7（不在表里），打印下标和比较次数。

验收标准：贴出输出；一句话说清「最坏情况比较 n 次」意味着 O(n) 里的 n 是什么。

实验参考 →

步骤 2（L2）：先排序，再二分 ​

目标：体会「排序换速度」——先花 O(n²) 排一次，之后每次查找只要 O(log n)。

  1. 用带 swapped 标志的冒泡排序把 {29, 10, 14, 37, 13, 25} 排成升序并打印。
  2. 写迭代版二分查找（闭区间、mid=lo+hi−lo2），在排好的数组里查 25（应在）和 30（应不在）。

验收标准：贴出排序结果和两次查找的下标；说清二分为什么必须先排序。

实验参考 →

步骤 3（L3）：BST——把「有序」嵌进树形 ​

目标：用 BST 把查找压到平均 O(log n)，并亲手复现「有序插入退化」。

  1. 插入 {50, 30, 70, 20, 40, 60, 80}：中序打印、search(60)/search(90)、用递归 height 打印树高。
  2. 再建一棵升序插入 1..7 的 BST，打印中序和树高——对比两棵树的高度差距。

验收标准：贴出两组输出；说清「树高」和查找代价的关系，以及升序插入为什么是灾难。

实验参考 →

步骤 4（L3）：哈希表——冲突与 rehash ​

目标：亲手造一场哈希冲突，再看 rehash 怎么把负载因子压下来。

  1. 链地址哈希表（桶数 7，key % 7），插入 {3, 10, 17, 24, 31, 38, 45, 52}——这 8 个数 % 7 全是 3，逼出 rehash。
  2. 负载因子超 0.75 就 rehash 到 17 桶（复用节点、不重新 malloc），打印 rehash 事件、最终负载因子、桶分布，search(38)/search(99) 验证。

验收标准：贴出全部输出；说清为什么「只把桶数组变大、不重新哈希」会让查找失效。

实验参考 →

步骤 5（L4）：大审判——clock() 计时四结构 ​

目标：把前四步攒下的四种查找拉到同一块数据上计时，亲眼见证 O(n)/O(log n)/O(1) 的差距。

  1. 造一个 0..99999 的有序数组；线性查找、二分查找各重复 100 次查最末元素 99999，用 clock() 计时。
  2. 用「中位优先插入」造一棵平衡 BST（值 0..99999，每个值插一次，search 查 99999 重复 100 次计时）；链地址哈希表（桶数 100003）装 0..99999，查 99999 重复 100 次计时。
  3. 打印四种耗时和各自相对线性的倍数；用 -fsanitize=address,undefined 复核整段无泄漏。

验收标准：贴出计时表；说明为什么二分和 BST 的耗时量级相同、哈希还要再低一档。

实验参考 →

附加挑战（L5）：双引擎随机交叉验证 ​

目标：两个独立实现（BST 与哈希集合）驱动同一份随机操作序列，互相作对方的「考官」——这是竞赛和工程里最硬核的验证手法（教材外补充：随机压力测试的做法，数据结构与算法均为教材内容）。

  1. 实现 BST（第 7 章，含三种删除）和哈希集合（第 8 章链地址 + 第 1 章「记前驱」删除），都维护「0..99 范围内的一批数」的集合语义。
  2. srand(42) 固定种子，跑 2000 次随机操作：rand()%3 决定插入（两引擎同步）、查询（两引擎结果必须一致，不一致立即报错退出）、删除（两引擎同步）。
  3. 每 100 次操作做一次自检：BST 中序遍历严格升序 + 两引擎节点数相等；全程用 -fsanitize=address,undefined 构建，退出码 0。

验收标准：贴出全部 20 次自检输出和最终统计；说清「两个独立实现交叉验证」为什么比「只看一个实现跑得对不对」强得多。

实验参考 →

提交物清单 ​

一个目录装下全部源码、每步终端记录（stepN.log）、以及 200 字以内的小结——用你自己的话说清「O(n) 到 O(1) 这条进化线」上，哪一步的差距最让你吃惊。