视频元信息
- 时长：约1小时（推断）
内容摘要（TL;DR）
本讲是C语言部分的最后一课，聚焦数据结构。介绍抽象数据类型（队列、栈、字典），深入讲解数组动态扩容（malloc/realloc）、链表、二叉搜索树、哈希表和Trie，分析各种结构的运行时间与空间权衡，并通过实际案例说明数据结构在真实世界中的应用，为下周Python和问题集5（拼写检查器）做铺垫。
一、引言：本周主题与过渡
[47.3s] 这是CS50第五周，主题是数据结构。本周是C语言的最后一周，下周将转向Python——一种高级编程语言，能让我们更快地解决问题，但代码运行速度可能不如C。
- 核心主题：权衡（trade-offs）。在接下来的课程中，我们会反复看到“用空间换时间”或“用时间换空间”的取舍。
- 理解：Python等高级语言隐藏了底层细节，但底层仍然在解决同样的问题，只是由语言设计者替我们做了。
二、抽象数据类型：队列（Queue）与栈（Stack）
[99.0s] 通过动画（Jack和Blue的故事）引入队列和栈的概念。
队列（Queue）
[242.6s] 队列是现实世界常见的“排队”结构，具有FIFO（先进先出） 属性：先来的人先服务。
- 两个基本操作：
- enqueue（入队）：进入队列末尾。
- dequeue（出队）：从队列头部离开。
- 实现示例：在C中，可以用结构体包含一个固定大小的数组（如容量50）和当前大小（size）。
- 易错点：固定容量限制。如果第51个人到达，无法存储。修改容量需要重新编译，且存在“分配过多浪费内存”或“分配不足”的风险。
- 思考：理想的队列应能动态增长和收缩，就像向操作系统请求更多内存一样，但静态数组做不到。
- 附加难点：需要跟踪队头位置，因为出队后要更新队头。
栈（Stack）
[446.2s] 栈具有LIFO（后进先出） 属性，就像一叠盘子，总是取最上面的。
- 两个基本操作：
- push（压栈）：把元素放到栈顶。
- pop（弹栈）：从栈顶移除元素。
- 现实例子：食堂的餐盘堆、Gmail收件箱默认新邮件在顶部（因此容易忽略旧邮件）。
- 实现：与队列类似，可以用数组+大小实现，但栈更容易——始终在数组末尾插入/删除，第一个元素永远在位置0。
- 同样存在固定容量限制，但栈和队列是抽象类型，可以通过动态内存管理改进。
考点：FIFO vs LIFO——队列先进先出，栈后进先出。务必区分两者操作名称：enqueue/dequeue vs push/pop。
三、字典（Dictionary）：键值对
[644.1s] 字典是另一种抽象数据类型，本质是键值对（key-value pairs） 集合。
- 现实世界：英语词典（单词→定义）、电话簿（名字→号码）。
- 计算机科学中，左侧叫键（key），右侧叫值（value）。
- 实现方式多种多样：可以用数组（固定大小、可能慢），也可以用更动态的结构（如哈希表）。
- 理解：手机通讯录如果只允许50个联系人会很不合理，所以实际应用一定采用了更动态的实现。
四、数组与动态内存管理
[746.1s] 回顾数组：连续内存块，值一个接一个。数组的优点是访问速度快（支持二分查找），缺点是大小需预先确定。
静态分配的问题
[856.1s] 如果数组大小不够，想增加一个元素，不能直接“放在旁边”，因为相邻内存可能已被其他数据占用（例如字符串"hello, world"恰好就在旁边）。
- 解决方案：申请一块更大的新内存，把旧数据复制过去，然后释放旧内存。
- 这需要用到
malloc和free。
动态分配示例：list.c
[970.1s] 使用 malloc 分配3个整数的空间，并利用指针与数组的等价性：
int *list = malloc(3 * sizeof(int));
list[0] = 1;
list[1] = 2;
list[2] = 3;
- 易错点：内存泄漏。如果直接
list = malloc(4 * sizeof(int))，会丢失原内存地址，无法释放，导致内存泄漏（可用Valgrind检测）。 - 正确做法：使用临时变量
tmp保存新内存地址，复制旧数据，释放旧内存，最后更新list。 - 必须检查
malloc返回值是否为NULL，否则可能发生段错误。
使用 realloc 简化
[1170.1s] realloc 可以智能地扩展内存块：如果原位置后面有空间，直接原地扩展；否则分配新内存并自动复制旧数据。
int *tmp = realloc(list, 4 * sizeof(int));
if (tmp == NULL) {
free(list);
return 1;
}
list = tmp;
list[3] = 4;
- 易错点：仍然要检查NULL，且要使用临时变量，避免
realloc失败后丢失原指针。 - 理解：
realloc知道要复制多少数据，因为标准库内部记录了之前分配的大小。 - 思考：在Python中，这些问题由语言自动处理，所以我们不需要写这么多行代码。
五、链表（Linked List）
[1290.1s] 链表是数组的替代品，通过指针把分散在内存各处的节点“串”起来，从而避免连续内存的限制。
节点定义
typedef struct node {
int number;
struct node *next;
} node;
- 注意：结构体内部必须写
struct node *next，因为typedef名要到结尾才生效，编译器需要先看到struct node。 - 每个节点包含数据（int）和指向下一个节点的指针。
构建链表
[1460.1s] 初始链表为空：node *list = NULL;
每次插入新节点：
node *n = malloc(sizeof(node));- 检查
n != NULL - 设置
n->number = 用户输入 - 设置
n->next = NULL - 前插（prepend）：
n->next = list; list = n;
- 箭头运算符
->是(*n).number的简写，相当于“解引用指针并访问字段”。 - 理解：前插操作是常数时间 O(1)，因为不需要遍历列表。
- 易错点：顺序很重要。如果先执行
list = n再执行n->next = list，就会丢失原链表，造成内存泄漏。
遍历链表
[1800.1s] 打印链表所有值：
for (node *ptr = list; ptr != NULL; ptr = ptr->next) {
printf("%i\n", ptr->number);
}
- 或者用 while 循环：
node *ptr = list; while (ptr != NULL) { ... ptr = ptr->next; }
运行时间分析
- 插入（前插）：O(1)
- 搜索：O(n)（最坏情况在末尾）
- 删除：O(n)（需要先找到节点）
-
遍历：O(n)
-
思考：链表牺牲了二分查找的能力，因为无法直接跳到中间，必须从头遍历。
有序插入的复杂性
[1930.1s] 如果希望链表始终有序，插入时需要判断四种情况：
- 列表为空 → 直接插入
- 新节点应插到开头 → 前插
- 新节点应插到末尾 → 遍历到末尾后追加
- 新节点应插到中间 → 需要两个指针，仔细调整链接
- 易错点：中间插入时指针操作顺序错误会导致节点“孤儿化”，即丢失部分链表。
- 释放链表时也必须逐个节点
free，不能只free(list)，因为free不知道链表结构。
考点：链表 vs 数组——链表支持动态增长，但搜索/删除为O(n)；数组支持二分查找O(log n)，但扩容代价高。实际使用需根据场景权衡。
六、二叉搜索树（Binary Search Tree）
[2210.1s] 二叉搜索树（BST）是链表和数组的“混合体”，每个节点有两个指针（左孩子、右孩子），形成二维结构。
性质
- 每个节点的值 大于其左子树的所有值，小于其右子树的所有值。
- 该性质是递归的：每个子树也满足BST性质。
搜索运行时间
[2340.1s] 从根开始，每次比较后丢弃一半子树，类似二分查找，因此搜索、插入、删除均为 O(log n)，前提是树保持平衡。
- 示例：在包含7个元素的树中查找5，只需2步。
- 代价：每个节点需要存储两个指针，内存使用约为数组的3倍。
搜索代码（递归）
bool search(int number, node *tree) {
if (tree == NULL) {
return false;
}
else if (number < tree->number) {
return search(number, tree->left);
}
else if (number > tree->number) {
return search(number, tree->right);
}
else {
return true;
}
}
- 理解：递归完美匹配BST的递归结构——左子树和右子树本身就是更小的树。
退化问题
[2500.1s] 如果插入顺序不当（例如1,2,3,4...），BST会退化为一个“长条”链表，运行时间退化为O(n)。
- 解决方案：平衡树（如AVL树、红黑树），在插入/删除后重新调整结构，但会增加额外时间。
- 思考：这就是权衡——为了保持O(log n)，必须付出额外维护成本。
七、哈希表（Hash Table）
[2650.1s] 哈希表是“数组+链表”的混合体，通过哈希函数将键映射到数组的某个“桶”，每个桶是一个链表，用于解决碰撞。
哈希函数
- 把无限（或很大）的输入域映射到有限的输出范围（如0~25对应A~Z）。
- 示例：根据名字首字母返回索引：
toupper(name[0]) - 'A'，返回0~25。 - 改进：使用
const和unsigned int增强安全性，防止误修改和负数索引。
哈希表结构
node *hash_table[26]; // 26个桶，每个桶是一个链表的头指针
- 插入：计算哈希值 → 到对应桶 → 在链表中插入（前插）。
- 查找：计算哈希值 → 到对应桶 → 在链表中线性搜索。
碰撞与运行时间
[2800.1s] 碰撞无法避免（多个名字首字母相同）。如果每个桶的链表平均长度为 n/26，则查找时间为 O(n/26) = O(n)（渐进意义下仍是线性，但实际快26倍）。
- 改进哈希函数：使用名字前3个字母（如"lin"），减少碰撞，但需要更大数组，浪费更多内存。
- 权衡：哈希函数越复杂，碰撞越少，但空间开销越大。
考点：哈希表本质是“数组+链表”，通过哈希函数定位桶，桶内用链表解决碰撞。理想情况下接近O(1)，但最坏仍为O(n)。
八、Trie：常数时间查找
[2950.1s] Trie（检索树）是一种树形结构，每个节点是一个大小为26的数组（对应26个字母），用于存储字符串，可以实现真正的 O(1) 查找（与数据量无关）。
工作原理
- 从根节点开始，根据单词的第一个字母选择对应的指针，走到下一个节点。
- 每个节点代表单词的一个字符，节点中的数组存储指向下一个字符的指针。
- 用布尔标记（或存储电话号码）表示一个单词在此结束。
- 示例：存储 "towed" 需要 t→o→w→e→d 五个节点，每个节点中对应字母的指针非空。
优点
- 查找时间固定为单词长度（通常有上限，如20个字符），因此视为常数时间 O(1)。
- 支持前缀匹配、自动补全。
缺点
- 极其浪费空间：每个节点有26个指针，但大多数为空。
- 理解：这是“用空间换时间”的极致——为了常数时间，必须牺牲大量内存。
九、现实世界应用与总结
[3300.1s] 数据结构无处不在：
- Sweetgreen餐厅：用哈希表按名字首字母分区存放外卖沙拉（A-E, F-J, K-N, O-Z），但也会出现“桶溢出”的问题，所以他们调整了桶的大小和数量。
- 问题集5：实现拼写检查器，加载10万+英文单词，要求高效且省内存，可对比不同数据结构的性能。
总结
- 数组：连续、快、支持二分查找，但扩容困难。
- 链表：动态、易插入/删除，但搜索慢。
- 二叉搜索树：平衡时O(log n)，但可能退化且占用更多空间。
- 哈希表：平均接近O(1)，但碰撞和空间开销需权衡。
-
Trie：常数时间，但空间浪费极大。
-
核心：没有完美的数据结构，只有最适合特定场景的结构。程序员需要在时间、空间、实现复杂度之间做出选择。
关键标签/关键词
数据结构 队列 栈 FIFO LIFO 字典 键值对 数组 malloc realloc 内存泄漏 链表 二叉搜索树 哈希表 哈希函数 Trie 运行时间 大O记号 权衡 CS50
生成时间：2026-09-02 16:16:01 生成平台：VideoNote
