← CS50

CS50x 2025 · 听课笔记
Week 4 & Week 5

上一篇：Week 2 & 3  ·  下一篇：Week 6 & 7

🔑 关键词索引

关键词	一句话说明
⭐ 指针（Pointer）	存储另一个变量内存地址的变量。是 C 的灵魂——没有指针，就没有动态内存、链表、树，甚至没有 Python 的引用
&（取地址）	一元运算符，返回变量的内存地址。你在 scanf("%d", &x) 里已经用了三周，现在揭晓它到底在干什么
*（解引用）	一元运算符，沿着指针「走到」目标地址，读写那个地址上存的值。指针的「*」和乘法的「*」是同一个符号但完全不同的操作
⭐ malloc / free	C 的动态内存分配——malloc 向操作系统申请一块堆内存，free 归还。忘了 free = 内存泄漏。这是 Week 4 的重中之重
calloc / realloc	calloc = malloc + 清零初始化；realloc = 调整已分配内存的大小。和 malloc 组成动态内存三剑客
栈（Stack）vs 堆（Heap）	程序内存的两个主区域——栈管局部变量和函数调用（自动回收），堆管动态分配（你负责回收）
程序内存全景	从低地址到高地址：text（代码）→ data（全局变量）→ bss（未初始化）→ heap ↑ → ... → stack ↓。一图胜千言
valgrind	内存调试神器——检测内存泄漏、非法读写、未初始化值。Malan 说「当你折腾到凌晨三点找不到 bug 时，valgrind 是你的最后希望」
野指针 & 悬垂指针	未初始化的指针（野指针）指向随机地址；free 后还用的指针（悬垂指针）指向已归还的内存。两者都是段错误的元凶
缓冲区溢出	向数组写入超过其容量的数据，多余的数据覆盖了相邻内存——可能覆盖其他变量，甚至覆盖函数返回地址（被黑客利用跳转到恶意代码）
Segmentation Fault	操作系统给你的惩罚——访问了不属于你的内存。段错误 = 你的程序在未经允许的情况下碰了不该碰的内存地址
文件 I/O	fopen / fread / fwrite / fclose——读写磁盘文件。Week 4 的 Problem Set 是用 C 从磁盘镜像中恢复被删除的 JPEG
memcpy / memmove / memset	内存操作三剑客——拷贝、安全拷贝（处理重叠）、填充。比 strcpy 更底层，直接操作原始字节
⭐ 链表（Linked List）	最简单的动态数据结构——每个节点存一个值 + 一个指向下一个节点的指针。插入 O(1)，查找 O(n)。Malan 用真人 + 毛线演示
双向链表	每个节点多一个 prev 指针——可以向前向后走。删除节点不需要遍历找前驱，但多一个指针 = 多一份内存和维护成本
哈希表（Hash Table）	数组 + 链表的混血——哈希函数把键映射成数组索引，冲突时用链表处理。理想 O(1) 查找。索引卡片的比喻
负载因子（Load Factor）	哈希表已用槽位 / 总槽位。超过阈值（如 0.7）就需要扩容（rehash），否则性能从 O(1) 退化到 O(n)
二叉搜索树	每个节点最多两个子节点——左边小、右边大。查找 O(log n)（平衡时），O(n)（退化成链表时）
树的遍历	前序（根→左→右）、中序（左→根→右，刚好是升序！）、后序（左→右→根）。是递归在数据结构上最漂亮的展示
Trie（前缀树）	按「字符」组织——每个节点存一个字母，沿着路径走到头就是一个单词。查找时间是单词长度，与数据总量无关
队列 vs 栈	FIFO（先进先出，像排队）vs LIFO（后进先出，像一摞盘子）。所有复杂的软件架构最终都归结为这两种抽象
抽象数据类型（ADT）	把「做什么」（接口）和「怎么做」（实现）分开。链表、栈、队列都是 ADT——你可以用数组或指针来实现它们

Week 4 · Memory

这节课的定位——过了这关就是另一个世界

Week 4 是 CS50 公认的「试金石」。前 3 周你一直在用别人封装好的东西——string、get_int()、make。这一周全部掀开。你会看到 string 的骨骼（就是一个 char *）、你会理解为什么 scanf 要加 &、你会亲手申请内存然后亲手还回去。学生口碑里这一周的评语很统一：「上完 Week 4 之前，我写 C；上完 Week 4 之后，我理解 C。」

4-1：指针——C 语言的灵魂

Malan 的开场是一行看似无害的代码：「我们用了三周的 string，今天要看看它的真面目。」然后他在黑板上写：

string s = "HI!";
// 等价于
char *s = "HI!";    // 这才是真的——指针！string 是假名，char * 是真名

从这一刻起，你不能再假装「string 是一个基本类型」了。

内存地址——每个变量都有一个门牌号

Malan 用一栋公寓楼做比喻。内存就像一栋巨大的公寓楼——每户人家（每个字节）都有一个独一无二的门牌号（地址）。变量是你给住户起的外号，指针是你在纸上抄下来的门牌号。

int n = 50;
// n 存着整数 50，但 n 本身住在内存的某个地址

int *p = &n;   // p 存着的不是 50——是 n 的门牌号（地址）
// p 的类型是「指向 int 的指针」

printf("%p\n", p);    // 打印 n 的地址，如 0x7ffd5f3a2c14
printf("%i\n", *p);   // 沿着地址走过去，读出里面的值 → 50

& 和 *——指针世界的「来」和「回」

这是你三周前就在用的 &（scanf("%d", &x)），现在 Malan 终于揭晓全貌：

运算符	方向	作用	比喻
&x	变量 → 地址	「x 住在哪里？」	查门牌号
*p	地址 → 变量	「这个门牌号里面住着谁？」	按门牌号敲门

Malan 的经典口诀：「& 给你地址。 * 沿着地址走。」他说完会停顿三秒，让这句话沉下去，因为后面所有内容都建立在这句话之上。

用指针交换两个变量的值——终于解开了「为什么需要第三个杯子」

Week 0 的杯子演示。Week 1 的 C 代码实现。但一直有个问题挥之不去——你在 C 里写的交换函数，为什么需要指针？

// ❌ 这样不行——C 的传参是「值传递」，函数收到的是副本
void swap_bad(int a, int b)
{
    int temp = a;
    a = b;
    b = temp;     // 只修改了副本！外部的 x 和 y 纹丝不动
}

// ✅ 传地址进去——函数顺着地址去改原版
void swap(int *a, int *b)
{
    int temp = *a;   // 去 a 的地址，把值拿出来
    *a = *b;         // 去 b 的地址，把值搬到 a 的地址
    *b = temp;       // 把暂存的值放到 b 的地址
}

// 调用时
int x = 1, y = 2;
swap(&x, &y);   // 传的是门牌号，不是值本身
// x=2, y=1 ✅ 终于换了！

Malan 在这里说出了 Week 1-3 一直藏着的话：「所以 scanf 为什么需要 &？因为它需要知道把你输入的值存到哪里去。 scanf 的签名是 scanf(format, 地址)——它通过地址去改你的变量，而不是通过值的副本。现在你明白了。」

4-2：动态内存分配——malloc 与 free

到现在为止，你声明的所有数组大小都是编译时确定的——int scores[100]。但你不知道用户有几个学生——10 个？1000 个？Malan 掏出了一个新武器：堆（Heap）。

栈 vs 堆——程序内存的两个世界

Malan 在黑板上画了一个长方形——程序运行时的整个内存空间。然后他在中间画了一条横线，上半部分标注「堆」，下半部分标注「栈」。

	栈（Stack）	堆（Heap）
谁管	编译器自动管理	你手动管理（malloc / free）
放了什么	局部变量、函数参数、返回地址	动态分配的数组、节点、字符串
回收时机	函数返回时自动收回	你调用 free 时才收回。忘了？永远占着
大小	相对较小（MB 级）	可以很大（GB 级）
增长方向	向下（往低地址）	向上（往高地址）
满了会怎样	栈溢出（Stack Overflow）	malloc 返回 NULL——优雅地失败

Malan 的比喻：「栈像自助餐厅的餐盘——你用完的盘子服务员自动收走。堆像你从仓库借出来的工具——你不还，它就永远占着仓库的位置。程序结束后操作系统会强制收回，但程序运行期间，你忘了 free 的那块内存就一直占着，像房间里堆满了你不用的箱子。」

程序内存全景——不只是栈和堆

Malan 在第 4 周后半段展开了完整的程序内存地图——从最低地址到最高地址，一共五个区域。这张图是整个 CS50 被截图次数最多的板书之一：

  高地址 (0xFFFFFFFF...)
  ┌──────────────────┐
  │   命令行参数 & 环境变量   │
  ├──────────────────┤
  │      栈 (Stack)        │ ← 向下生长 ↓  (局部变量、函数帧)
  │                        │
  │      ⬇ 未使用空间 ⬇      │
  │      ⬆ 未使用空间 ⬆      │
  │                        │
  │       堆 (Heap)         │ ← 向上生长 ↑  (malloc 从这里分配)
  ├──────────────────┤
  │    未初始化数据 (BSS)    │ ← 全局变量、static 变量（未初始化）
  ├──────────────────┤
  │    已初始化数据 (Data)   │ ← 全局变量、static 变量（已初始化）
  ├──────────────────┤
  │      代码 (Text)        │ ← 你的程序的机器码（只读）
  └──────────────────┘
  低地址 (0x00000000)

区域	放了什么	特点
Text	编译后的机器码（你的 main、swap、所有函数的指令）	只读。 你的代码不能修改自己。共享——多个进程运行同一程序时共用一份 Text
Data	已初始化的全局变量和 static 变量	可读写。程序启动时从可执行文件加载
BSS	未初始化的全局变量和 static 变量	可读写。程序启动时自动清零。BSS 段在可执行文件中不占空间——只记录「需要多少字节的全零」
Heap	malloc 分配的所有东西	往上长。你需要维护秩序（free 归还）
Stack	局部变量、函数参数、返回地址	往下长。自动管理。满了 = Stack Overflow

Malan 指着这张图说：「这就是你写 C 程序时脚下的整个大陆。接下来 4 周的每次段错误、每次内存泄漏、每次栈溢出，你都可以回到这张图来定位问题。」

malloc——向操作系统借一块内存

// 借一块能存 3 个 int 的内存（3 × 4 bytes = 12 bytes）
int *scores = malloc(3 * sizeof(int));

// 检查是否借到了（内存可能不够）
if (scores == NULL) {
    printf("内存不足！\n");
    return 1;
}

// 可以像普通数组一样用
scores[0] = 72;
scores[1] = 85;
scores[2] = 93;

// 用完必须还——忘了就泄漏
free(scores);
scores = NULL;  // 好习惯：释放后把指针置空，防止「悬垂指针」

动态内存三剑客——malloc、calloc、realloc

Malan 介绍完 malloc 后，立刻引出了它的两个「兄弟」——它们仨一起构成 C 语言动态内存分配的完整武器库：

函数	参数	做什么	关键区别
malloc(n)	总字节数	向堆申请 n 个字节	不清零。 内存里是上任用户留下的随机值
calloc(count, size)	元素个数 + 每个的大小	申请 count×size 字节，全部初始化为 0	两个参数，不是乘积。而且清零——适合数组
realloc(ptr, new_size)	旧指针 + 新大小	调整已分配内存的大小——可以放大或缩小	可能搬走！返回的新地址可能与旧地址不同——旧指针会失效

// calloc 示例——直接拿到一个全零数组
int *scores = calloc(3, sizeof(int));  // 3 个 int，全为 0
// 等价于：
// int *scores = malloc(3 * sizeof(int));
// memset(scores, 0, 3 * sizeof(int));

// realloc 示例——数组从 3 个元素扩展到 5 个
int *tmp = realloc(scores, 5 * sizeof(int));
if (tmp == NULL) {
    free(scores);        // realloc 失败时原内存还在，记得释放！
    return 1;
}
scores = tmp;            // ← 关键！必须用返回值覆盖旧指针
// 前 3 个元素的值被保留了，后 2 个是未初始化的（realloc 不清零）

realloc 最常见的坑：直接写 scores = realloc(scores, ...)。如果 realloc 失败返回 NULL——你就失去了 scores 指向的原内存的引用。 内存泄漏 + 数据丢失双杀。正确做法：用一个临时变量接收 realloc 的返回值，确认非 NULL 后再赋值。

内存泄漏——房间里堆满你不再用的箱子

Malan 写了一个演示——在一个循环里不停地 malloc，但从不 free：

// 这个程序会慢慢吃掉你所有的内存！
int main(void)
{
    while (true)
    {
        int *leak = malloc(1000000);  // 每次借 1MB
        // 没有 free(leak)！← 内存泄漏
        sleep(1);
    }
}

运行这个程序，打开「活动监视器」——你会亲眼看到它的内存占用每秒增长 1MB。Malan 让学生打开终端跑这个，然后兴奋地指着监视器的曲线：「看，你的程序正在把自己吃成胖子。」

三个经典的内存错误（后面 valgrind 能全部检测出来）：① 忘了 free → 内存泄漏。② free 之后还继续用那个指针 → 悬垂指针（Use After Free）。③ free 同一个地址两次 → 双重释放（Double Free）。

野指针与悬垂指针——段错误的两个元凶

Malan 在第 4 周反复强调两种危险的指针状态，因为它们会导致最经典的 Segmentation Fault：

类型	怎么产生的	为什么危险	防御
野指针（Wild Pointer）	声明了指针但从未初始化—— int *p;（p 里面是随机值）	解引用它 → 访问一个随机的内存地址 → 段错误（或者更糟——碰巧撞上了别人的数据）	声明时立刻初始化：int *p = NULL;
悬垂指针（Dangling Pointer）	free(p) 之后还继续使用 p	那块内存已经归还给堆了——可能已经被别的 malloc 分配走了。你通过 p 去读写的，可能是别人的数据	free(p); p = NULL; ——释放后立刻置空，之后再解引用 NULL 至少会干净地段错误，而不是默默破坏数据

Malan 的警示：「野指针导致的 bug 是最难排查的——因为它是不确定的。同一个程序，今天在 0x7fff... 那个随机地址上碰巧有你自己的数据，所以 '好像没问题'；明天换个环境，随机地址不同了，段错误。这种'时灵时不灵'的 bug 最让人崩溃。」

4-3：valgrind——内存问题的终极侦探

Malan 把 valgrind 称作「你凌晨三点的最后希望」。它是一个命令行工具，运行你的程序并实时监视每一次内存操作——分配、读写、释放。然后生成一份详细报告：

valgrind ./myprogram
==12345== HEAP SUMMARY:
==12345==   definitely lost: 0 bytes in 0 blocks
==12345==   indirectly lost: 0 bytes in 0 blocks
==12345==   possibly lost:   0 bytes in 0 blocks
==12345==   still reachable: 0 bytes in 0 blocks
==12345== ERROR SUMMARY: 0 errors from 0 contexts

valgrind 能发现的	什么意思
内存泄漏（definitely lost）	有一块内存，你分配了但没有任何指针指向它——彻底弄丢了，永远没法释放了
非法读写（Invalid read/write）	你访问了不属于你的内存——比如 array[100] 越界，或者 free 之后还用了那个指针
未初始化值的使用	你声明了一个变量但没赋值就用了——它的值是内存里的随机垃圾。valgrind 会标黄（Conditional jump depends on uninitialised value）
双重释放	同一个地址被 free 两次——第二次 free 时那块内存可能已经被分配给别的东西了

4-4：指针运算——指针的算术

Malan 把指针的算术拆成最直观的图示。如果 int *p = &scores[0]，那么：

• p + 1 不是地址值 + 1——是地址值 + sizeof(int)（通常是 4）
• p + 2 是 +8 个字节
• 这就是为什么 scores[3] 和 *(scores + 3) 完全等价——数组索引只是指针运算的语法糖

int scores[] = {72, 85, 93};
int *p = scores;  // 等价于 &scores[0]

printf("%i\n", *p);        // 72 → scores[0]
printf("%i\n", *(p + 1));  // 85 → scores[1]
printf("%i\n", *(p + 2));  // 93 → scores[2]

// 这两个写法完全等价：
scores[i]  ⇔  *(scores + i)  // C 就是这么实现数组的！

Malan 的解密时刻：「这就是为什么 Week 2 我说数组名就是指向第一个元素的指针。整个 C 语言的数组操作——从 scores[5] 到 strlen(s)——底层全部是指针运算。你以为是数组，其实你一直在用指针。」

指向指针的指针——指针的「元」操作

在链表等数据结构中，你经常需要「修改指针本身的值」。这时就需要一个指向指针的指针：

int x = 42;
int *p = &x;        // p 指向 int
int **pp = &p;      // pp 指向「指向 int 的指针」

printf("%i\n", **pp);  // 解引用两次：pp → p → x → 42

// 实战场景：在链表头部插入新节点，函数需要修改「头指针」的值
void insert_head(node **list, int value)
{
    node *n = malloc(sizeof(node));
    n->number = value;
    n->next = *list;    // *list 是真实的头指针，不是副本
    *list = n;          // 修改真实的头指针
}

Malan 解释：「当你需要让一个函数修改指针本身——而不是指针指向的内容——你就往上再加一个 *。一层 * 能改值，两层 * 能改指针，三层能改指针的指针……但说实话，到第三层就该想想是不是设计出了问题。」

内存操作三剑客——memcpy / memmove / memset

和 strcpy 不同，这三个函数不关心数据「是什么」——它们直接操作原始字节。Malan 在 Week 4 末尾引入它们，为 JPEG 恢复作业做铺垫：

#include <string.h>

// memset：把一块内存全部填成某个值
char buffer[512];
memset(buffer, 0, 512);  // 把 buffer 的 512 字节全设为 0

// memcpy：从源地址拷贝 n 个字节到目标地址
int src[5] = {1, 2, 3, 4, 5};
int dest[5];
memcpy(dest, src, 5 * sizeof(int));  // 拷贝 5 个 int = 20 字节

// memmove：和 memcpy 一样，但能处理源和目标的内存重叠
char str[] = "abcdef";
memmove(str + 2, str, 4);  // str → "ababcd"（安全✅）
// 如果用 memcpy 做同样的事 → 未定义行为（可能正确，可能崩溃，取决于实现）

函数	作用	区别
memset(ptr, value, n)	把 ptr 开头的 n 个字节全填成 value	value 是 unsigned char，虽然参数是 int。常见用法：清零
memcpy(dest, src, n)	把 src 的 n 个字节拷贝到 dest	不检查 dest 和 src 是否重叠。重叠时行为未定义——用 memmove
memmove(dest, src, n)	把 src 的 n 个字节「移动」到 dest	能正确处理重叠。 内部先判断方向，再从安全的端开始拷贝。比 memcpy 略慢一点

4-5：缓冲区溢出——黑客的入口

Malan 恢复了严肃的表情。他在黑板上画了一个字符数组 char buffer[4]，然后写了一个向它写入 8 个字符的程序。多余的 4 个字符不会消失——它们会覆盖 buffer 之后的内存。 在典型的程序内存布局中，buffer 后面紧挨着的是……函数的返回地址。

这就是历史上最经典的攻击手段——缓冲区溢出攻击：精心构造一个超长输入，让它覆盖函数返回地址，把这个地址改写成你提前植入的恶意代码的位置。函数执行完准备返回时，跳到了黑客指定的地方。Malan 说：「这不是科幻小说——这是过去 40 年里一切重大操作系统漏洞的核心机制。」

4-6：文件 I/O——用 C 读写文件

Malan 说这是 Week 4 的「甜点」——相比指针和内存，文件操作意外地简单：

// 打开文件
FILE *file = fopen("phonebook.txt", "r");  // "r"=读, "w"=写, "a"=追加
if (file == NULL) {
    printf("打不开文件！\n");
    return 1;
}

// 逐行读取
char buffer[256];
while (fgets(buffer, sizeof(buffer), file) != NULL) {
    printf("%s", buffer);  // 打印这一行
}

// 关闭文件
fclose(file);

四个基本操作——fopen、fread（或 fgets）、fwrite（或 fprintf）、fclose——构成了 C 语言与磁盘世界的全部接口。

文件读写模式和常见的文件操作函数：

fopen 模式	含义	文件不存在时
"r"	只读	返回 NULL
"w"	只写（会清空已有内容！）	创建新文件
"a"	追加（在末尾写，不清空）	创建新文件
"rb" / "wb"	二进制读写（JPEG 恢复作业必须用这个！）	同上

关键区分——文本模式（"r"）vs 二进制模式（"rb"）：在 Windows 上，文本模式会自动把 \n 转换为 \r\n（行尾符），会损坏 JPEG 等二进制文件。Mac/Linux 上两者行为相同，但为跨平台安全，读二进制永远用 "rb"。

4-7：JPEG 恢复——Week 4 的 Problem Set

这是 CS50 最被人津津乐道的作业之一。给你一个叫 card.raw 的文件——这是一张数码相机存储卡的完整磁盘镜像（dd 命令做的）。你把照片删了？没关系——删除只是把文件系统的目录条目标记为「空」了，照片的原始数据还在存储卡上。 你的任务：写一个 C 程序，在这个镜像里扫描 JPEG 文件头（0xff 0xd8 0xff 这三个魔数开头），找到所有照片并恢复出来。

这就是为什么 Week 4 要花一大半时间讲指针和文件 I/O——因为你马上要用了。这个作业模拟的是真实的数字取证工作。而且你会发现，用 C 做这个事的代码不超过 100 行。Malan：「这就是 C 的魔力——它让你直接面对字节。没有 Python 的 PIL.Image.open()，没有 Java 的 BufferedImage。你和你需要恢复的数据之间只有 fread 和 malloc。」

作业的核心挑战：

• 找到 JPEG 文件头——前三个字节是 0xff 0xd8 0xff，第四个字节 0xe0 到 0xef
• 管理多个输出文件——每遇到一个新 JPEG，就要 fclose 上一个文件、fopen 一个新文件（001.jpg, 002.jpg...）
• 用 fread 按块读取——存储卡以 512 字节为块（block）。你需要用 fread(buffer, 512, 1, file) 逐块读取
• 用 malloc 分配缓冲区——你需要一个 512 字节的缓冲区来逐块读取镜像文件
• 理解 FAT 文件系统的块对齐——JPEG 文件恰好从块的边界开始（这是作业的简化假设）

做完这个作业的学生，发朋友圈的标题通常是：「用 90 行 C 代码做了一次 FBI 的工作。」

Week 5 · Data Structures

这节课的格局

到 Week 4 结束时，你有了两个超级技能——指针（能「指向」任何东西）和动态内存（能在运行时申请任意大小的空间）。把它们拼在一起，你就获得了第三个能力：创造不存在于硬盘和教科书里的数据结构。 Week 5 全程在讲这件事——Malan 会用毛线、纸杯、乐高和至少 30 个学生志愿者，把抽象的数据结构变成物理世界的实物。

5-1：链表（Linked List）——为什么数组不够用了

Malan 以一个「痛点」开场——数组的插入。如果你有一个容量为 100 的数组，前 50 个位置存了数据，你想在第 3 个位置插入一个新数据——你必须把第 3 到第 50 个元素全部向右移一位。 这是 O(n) 的操作。删除同理。

链表的回答：每个节点不需要紧挨着。每个节点有一个指针，指向「下一个在哪里」。 插入一个新节点只需要「拆开」两个旧节点的连接，各自指向新节点就行——O(1)。

链表的结构——节点（Node）

// 链表的一个节点：存一个值 + 存一个「指向下一个」的指针
typedef struct node
{
    int number;           // 值
    struct node *next;    // 指向下一个节点的指针
}
node;

// 创建第一个节点
node *list = NULL;  // 空链表

// 在头部插入新节点（O(1)）
node *n = malloc(sizeof(node));
n->number = 42;
n->next = list;   // 新节点「接上」旧的头
list = n;         // 新节点成为新的头

注意 n->number 这个语法——它是 (*n).number 的简写。箭头「穿」过指针访问成员。Malan 说：「记住 -> 吧，从今以后你天天用它。」

链表的完整操作——遍历、搜索、销毁

Malan 把链表「活」起来需要的不只是插入——你需要会走、会找、会收尾：

// ① 遍历——打印整个链表
void print_list(node *list)
{
    for (node *cursor = list; cursor != NULL; cursor = cursor->next)
        printf("%i → ", cursor->number);
    printf("NULL\n");
}

// ② 搜索——找某个值是否存在
bool search(node *list, int target)
{
    for (node *cursor = list; cursor != NULL; cursor = cursor->next)
        if (cursor->number == target)
            return true;
    return false;
}

// ③ 销毁——释放整条链表（必须按顺序！）
void destroy(node *list)
{
    while (list != NULL)
    {
        node *next = list->next;  // 先记住下一个在哪
        free(list);               // 释放当前节点
        list = next;              // 移到下一个
    }
}
// ⚠️ 不能先 free(list) 再 list = list->next！
// 因为 free 之后那块内存已经不属于你了——读 list->next 是未定义行为

销毁链表的代码是 CS50 面试题的常客——必须先记住 next，再 free。 它的重要性不在于代码多长，在于它浓缩了指针操作的核心纪律：永远不要访问已经 free 了的内存。

尾部插入——永远走到最后再加

头部插入是 O(1)，因为你知道头在哪。尾部插入呢？你必须从头走到尾——O(n)。但如果你的程序经常在尾部插入，可以额外维护一个 tail 指针：

node *head = NULL;
node *tail = NULL;  // 始终指向最后一个节点

// 在尾部插入（O(1)——前提是你维护了 tail）
node *n = malloc(sizeof(node));
n->number = 99;
n->next = NULL;   // 新节点是新的尾，所以 next = NULL

if (head == NULL)      // 空链表
    head = tail = n;   // 头尾都是它
else
{
    tail->next = n;    // 旧尾接上新节点
    tail = n;          // 新节点成为尾
}

双向链表——可以往回走了

Malan 在讲完单向链表后提了一句：「如果你受够了单向链表'删除时需要从头开始找前驱'的痛苦——加一个 prev。」

typedef struct dnode
{
    int number;
    struct dnode *prev;  // 指向上一个节点
    struct dnode *next;  // 指向下一个节点
}
dnode;

// 双向链表删除节点——不需要遍历找前驱了！
void delete(dnode *n)
{
    if (n->prev != NULL)
        n->prev->next = n->next;  // 跳过 n
    if (n->next != NULL)
        n->next->prev = n->prev;  // 倒着也跳过 n
    free(n);
}

	单向链表	双向链表
每个节点的额外内存	1 个指针（next）	2 个指针（prev + next）
删除已知节点	O(n)——需要找前驱	O(1)——直接通过 prev 找到前驱
遍历方向	只能向前	向前、向后都行
代码复杂度	低	插入/删除时要处理 4 根指针（前->后、后->前），容易出错

Malan 的毛线链表——真人演示

这是 CS50 最著名的场景之一。Malan 叫了约 10 个学生上台，每人手里拿一个数字——但关键道具是一卷毛线。 第一人牵着毛线的一端，另一端递给第二人。第二人再牵一根给第三人……一条物理的链表在讲台上成型了。

然后 Malan 演示插入——让一个新学生拿着数字「99」走到第 2 和第 3 人之间。旧毛线剪断，两条新毛线接上。O(1)。台下鼓掌。

然后演示删除——他剪断连向第 4 个人的毛线，把第 3 和第 5 接上。第 4 人拿着数字尴尬地站在台中央——「你现在被 free 了。」

链表的代价——查找 O(n)

毛线很直观，但 Malan 很快指出代价：你永远只能顺着毛线往下摸。要找第 50 个节点？你必须从第 1 个开始数。不能像数组那样 list[49] 直接跳过去。

这是数据结构的核心权衡：你不可能同时获得 O(1) 插入、O(1) 删除和 O(1) 随机访问。 数组给你 O(1) 随机访问但 O(n) 插入删除。链表给你 O(1) 插入删除但 O(n) 随机访问。选择一个数据结构，就是选择一组取舍。

5-2：哈希表（Hash Table）——鱼与熊掌的调和

Malan 问了一个很实用的问题：「如果我要同时获得快速的查找和插入呢？」他拿起了……一叠索引卡片。

「假设我有 26 张卡片——每张代表字母表的一个字母。我把所有以 A 开头的人名写在 A 卡片上，B 的写在 B 卡片上……现在我要找 'Malan'——我翻到 M 那张卡片，然后只需要搜那一张卡片上的人名。」

这就是哈希表：一个数组（26 张卡片），每个槽位挂着一个链表（卡片上的人名列表）。

// 哈希表 = 一个「装链表的数组」
node *table[26];   // 26 个链表头

// 哈希函数——把人名变成 0-25 的索引
int hash(string name) {
    return toupper(name[0]) - 'A';   // 'A'→0, 'B'→1, ...
}

// 查找——去对应的卡片上翻
int index = hash("Malan");
for (node *cursor = table[index]; cursor != NULL; cursor = cursor->next)
{
    if (strcmp(cursor->name, "Malan") == 0)
        return cursor->number;   // 找到了！
}
return -1;  // 没找到

理论上 O(1) 查找——但如果所有人都叫 Alice，全部挤在 A 那张卡片上，就退化成了 O(n)。所以哈希表的核心挑战是设计一个分布均匀的哈希函数。

负载因子与重哈希——哈希表不坍缩的秘诀

Malan 在讲到哈希表退化时引入了两个关键概念：

负载因子（Load Factor）= 已存储元素数 / 槽位数。 当负载因子超过某个阈值（通常 0.7），冲突概率急剧上升，性能从 O(1) 滑向 O(n)。这时候你需要——重哈希（Rehash）：

1. 创建一个更大的数组（通常是原来的 2 倍）
2. 把旧表里每一个节点重新计算哈希值，插入新表
3. 释放旧表

这就是 Python 的 dict 底层——每次扩容背后都有一套重哈希在跑。Malan：「你永远不需要手动重哈希——Python 帮你在幕后做了。但如果你不知道幕后有这么一台机器在运转，你会对 'dict 怎么这么快' 这个词产生一种接近迷信的信任。」

开放寻址——另一种冲突处理

Malan 顺便提了一句：链表解决冲突（链地址法）不是唯一的选择。另一种叫 开放寻址（Open Addressing）——槽位满了？按一个固定的规则往后找下一个空位（线性探测、二次探测、双重哈希）。

	链地址法	开放寻址
冲突时	往槽位的链表里加一个节点	往后找下一个空槽位
内存	每个节点额外有一个 next 指针	不需要额外指针——但需要预留空槽
删除	简单——从链表中移除节点即可	麻烦——不能直接清空槽位，需要「墓碑」标记（否则后续查找会中断）
CS50 用哪个	链地址法（因为学生已经会链表了）	仅介绍概念

5-3：二叉搜索树（Binary Search Tree）

Malan 换道具了——这次是彩色乒乓球。他拿起一个乒乓球写上「50」，放在白板正中央：「这是根（root）。」然后拿起一个写「30」的球：「30 比 50 小，放左边。」「70」放右边。然后「25」——30 比 50 小（放左），25 比 30 小（放左）。球在树上层层排开。

typedef struct node
{
    int number;
    struct node *left;   // 比它小的在左边
    struct node *right;  // 比它大的在右边
}
node;

// 查找——沿着树往下走，每次砍掉一半候选
bool search(node *root, int target)
{
    if (root == NULL)
        return false;
    if (root->number == target)
        return true;
    else if (target < root->number)
        return search(root->left, target);   // 走左边
    else
        return search(root->right, target);  // 走右边
}

查找 O(log n)——如果树是平衡的。 但如果你按 1-2-3-4-5 的顺序插入，树会退化成一根面条——退化成了链表，O(n)。

BST 的插入——递归的又一次漂亮展示

查找只会「问路」，插入要「铺路」——找到合适的位置后，创建一个新节点挂上去：

// 插入一个值到 BST 中——返回（可能更新后的）根节点
node *insert(node *root, int value)
{
    if (root == NULL)
    {
        // 走到空位了——在这里创建新节点
        node *n = malloc(sizeof(node));
        n->number = value;
        n->left = n->right = NULL;
        return n;  // 新节点成为子树的新根
    }

    if (value < root->number)
        root->left = insert(root->left, value);    // 去左边找位置
    else if (value > root->number)
        root->right = insert(root->right, value);  // 去右边找位置
    // 如果 value == root->number，不做任何事（不允许重复值）

    return root;  // 返回自己——给上层递归「接回去」
}

// 使用
node *root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 70);
// 对，每次都要 root = insert(root, x) —— 因为传入空树时 root 会被更新

二叉树的三种遍历——递归在树上的最美展示

Malan 在第 5 周画了一棵小树，然后演示了三种走法——它们之间的区别只在于处理「根」的时机：

// 以这棵小树为例：
//     2
//    / \
//   1   3

// 前序（Pre-order）：根 → 左 → 右    输出：2 1 3
void preorder(node *root) {
    if (root == NULL) return;
    printf("%i ", root->number);  // ← 先处理根
    preorder(root->left);
    preorder(root->right);
}

// 中序（In-order）：左 → 根 → 右    输出：1 2 3 ← 刚好升序！
void inorder(node *root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%i ", root->number);  // ← 中间处理根
    inorder(root->right);
}

// 后序（Post-order）：左 → 右 → 根  输出：1 3 2
void postorder(node *root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%i ", root->number);  // ← 最后处理根
}

遍历	顺序	用途
前序	根→左→右	「复制一棵树」——先建根节点，再递归建子树。也用于文件系统的序列化
中序	左→根→右	输出 BST 中所有值的升序排列。这是 BST 独有的超能力——中序遍历 = 排序
后序	左→右→根	「删除一棵树」——先删除子树，再删除根。因为释放根之后就无法访问子树了

Malan 对这三种遍历的评价：「中序遍历是 BST 给你最大的礼物。你建好一棵树，中序遍历走一遍，所有值从小到大列出来——你不需要写任何排序算法。 建树本身就是排序。」

BST 的删除——最复杂的操作

Malan 承认这是 BST 最棘手的部分——因为删除一个节点后，必须保持 BST 的性质（左边小、右边大）。分三种情况：

情况	怎么删	难度
① 叶子节点（左右都 NULL）	直接 free，父节点的对应指针设为 NULL	⭐ 简单
② 只有一个子节点	让父节点「跳过」当前节点，直接接上那个唯一的子节点。然后 free 当前节点	⭐⭐ 中等
③ 有两个子节点	找到右子树的最小值（或左子树的最大值），用它替换当前节点的值，然后递归删除那个替身节点。这个替身一定是类型 ① 或 ②	⭐⭐⭐ 最难

情况 ③ 的「替身法」是整个 CS50 数据结构部分最优雅的技巧之一：你不在原地「硬删」——你找一个替身（后继节点），把它的值复制过来，然后去删那个替身。替身一定只有 0 或 1 个子节点，所以就退化成了情况 ① 或 ②。

5-4：Trie（前缀树）——拿空间换时间的极致

Malan 展示了最后一种结构——Trie（发音同 try）。一个节点不是一个值，而是一个字母。沿着路径往下走，走到头就是一个单词。

// 存 "cat", "car", "dog" 的 Trie：
//    root
//   /    \
//  c      d
//  |      |
//  a      o
// / \     |
// t  r    g
// (有词语) (有词语) (有词语)

Trie 的一个节点有 26 个子指针（每个字母一个）。存了 10 万个单词，查找 "zebra" 只需要 5 步（z-e-b-r-a）——跟字典里有多少个单词完全没有关系。 代价？内存。每个节点有 26 个指针，大部分是 NULL。Malan：「空间和时间永远是宿敌。你选一个。」

Trie 的代码实现

Malan 在黑板上逐步搭建的 Trie 节点结构与插入/搜索逻辑：

// Trie 节点——不是存一个值，而是存 26 个「子字母」的指针
typedef struct trie_node
{
    bool is_word;                          // 这个节点是一个完整单词的结尾吗？
    struct trie_node *children[26];        // 26 个子字母（a-z）
}
trie_node;

// 插入单词——沿着字母路径走，走到头打上标记
void insert(trie_node *root, string word)
{
    trie_node *cursor = root;
    for (int i = 0, n = strlen(word); i < n; i++)
    {
        int index = word[i] - 'a';   // 'a'→0, 'b'→1, ..., 'z'→25
        if (cursor->children[index] == NULL)
        {
            // 这个字母还没出现过——创建一个新节点
            cursor->children[index] = calloc(1, sizeof(trie_node));
        }
        cursor = cursor->children[index];  // 往下走一层
    }
    cursor->is_word = true;  // 路径的终点打上「这里有个词」的标记
}

// 查找——完全一样的走法，只是走到 NULL 就说明没有
bool search(trie_node *root, string word)
{
    trie_node *cursor = root;
    for (int i = 0, n = strlen(word); i < n; i++)
    {
        int index = word[i] - 'a';
        if (cursor->children[index] == NULL)
            return false;        // 这条路不通！
        cursor = cursor->children[index];
    }
    return cursor->is_word;      // 走到头了——这里是完整单词吗？
}
// 注意！不能用 cursor->is_word 替代最后的返回判断。
// 你可能是沿着 "ca" 走到了 'a' 节点——它存在（因为 "cat" 和 "car" 都经过它），
// 但 "ca" 本身不是一个完整的单词。is_word 专门区分这一点。

这段代码里最微妙的设计是 is_word 布尔值。「这个节点被很多单词经过」和「这个节点本身就是一个单词的终点」是完全不同的概念。没有 is_word，你无法区分 "ca"（不是词）和已经插入的 "cat"（是词）——因为 "ca" 的路径也存在。

5-5：队列（Queue）与栈（Stack）——最基础的结构抽象

Malan 把最后 10 分钟留给两个最简单的抽象——队列和栈。它们不是新的数据结构，它们是你对已有数据结构的一种使用限制：

	队列（FIFO）	栈（LIFO）
规则	先进先出——排队的第一个人先被服务	后进先出——最后放上去的盘子最先被拿走
插入叫	入队（enqueue）——加到尾部	压栈（push）——放在顶部
删除叫	出队（dequeue）——从头部拿走	弹栈（pop）——从顶部拿走
实现方式	数组（尾部加，头部取）或链表（头尾各一个指针）	数组（只操作末尾）或链表（只操作头部）
你会遇到的地方	打印队列、消息队列、BFS（广度优先搜索）	函数调用栈、撤销操作（Undo）、DFS（深度优先搜索）、括号匹配

抽象数据类型（ADT）——把「做什么」和「怎么做」分开

Malan 在 Week 5 结束前引入了 CS50 的最后一个元概念——抽象数据类型（Abstract Data Type）。这不是新的数据结构，而是一种思维方式：

「你已经用两周时间手动实现了链表、栈、队列、BST。但下周开始——Python 周——你再也不会 malloc(sizeof(node)) 了。你会用 list.append()、dict['key']、set.add()。这些是 Python 的 ADT——它们有清晰的接口（做什么），但隐藏了实现（怎么做）。你的 list.append 背后是动态数组 + realloc。你的 dict 背后是哈希表 + 负载因子 + 重哈希——你不需要知道这些也能用。但当你知道了，你就能理解为什么 list.insert(0, x) 比 list.append(x) 慢那么多。」

ADT	接口（你能做的操作）	可能的底层实现
列表（List）	append、insert、remove、索引	动态数组（Python）或链表（Lisp）
字典（Dict / Map）	按键取值、插入、删除、遍历	哈希表（Python/Java）或平衡二叉树（C++ std::map）
栈（Stack）	push、pop、peek	数组或链表
队列（Queue）	enqueue、dequeue	链表（头尾指针）或环形数组

Malan 的收束：「这就是两门课的微妙关系——C 教你车轮是怎么造出来的。Python 教你开车。你不需要亲手造轮子才能开车，但只有造过轮子的人，才知道车在哪里会坏。」

Week 5 的 Problem Set：拼写检查器（Speller）

这是 CS50 标志性的终极作业——给你一本英文词典 + 一份待检查的文本，找出文本中所有不在词典里的单词。但要求是：你必须同时用链表实现一个版本，再用哈希表实现一个版本，最后用 Trie 实现一个版本。 然后比较三者的速度。

做完这道题的学生，对 O(n)、O(1)、O(log n) 的理解不是「背下来的」——是用秒表亲自测出来的。

Speller 作业的典型输出——你跑完三个版本后会在终端看到这样的对比：

WORDS MISSPELLED:     955
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        19190
TIME IN load:         0.04   （哈希表加载词典）
TIME IN check:        0.01   （哈希表检查拼写）
TIME IN size:         0.00
TIME IN unload:       0.02
TOTAL:                0.07

// 同样用链表实现时：TOTAL 可能是 2.45 秒
// Trie：TOTAL 大概 0.15 秒
// 你亲手制造了一个 35 倍的速度差异

核心公式速查——Week 4-5 的数据结构对决

数据结构	查找	插入	删除	空间	关键取舍
数组	O(1)（索引） O(n)（搜索）	O(n)	O(n)	紧凑	快速随机访问 + 固定大小（或用动态数组承担扩容成本）
链表	O(n)	O(1)（头部）	O(1)（头部）	每个节点多一个指针	快速插入删除，代价是丢失随机访问
哈希表	O(1) 平均 O(n) 最坏	O(1) 平均	O(1) 平均	比数组多一个指针数组 + 链表节点	近乎完美的平衡——除非哈希函数太烂导致全挤在一个槽
二叉搜索树	O(log n) 平衡 O(n) 退化	O(log n) 平衡	O(log n) 平衡	每个节点两个指针	中序遍历 = 自动排序。但平衡是代价
Trie	O(k)←单词长度	O(k)	O(k)	极大！每个节点 26 个指针	查找时间与数据总量无关——拿空间换时间的极致

CS50 C 语言期总结——Week 1-5 学到的能力栈

周	核心能力	能造什么了
Week 1	编译、变量、条件、循环	猜数字游戏
Week 2	数组、字符串、命令行参数	凯撒加密
Week 3	搜索、排序、大 O、递归	归并排序、递归画图
Week 4	指针、动态内存、文件 I/O	恢复删除的照片（JPEG 取证）
Week 5	链表、哈希表、树、Trie	拼写检查器（三版本对比竞速）
↓ Week 6 起切换到 Python——你用来造工具的语言，变成你用来调 API 的语言

---

2026.5.29 | 星尘整理