【笔记】CS50x 2025 版 第 5 讲：数据结构

• 时长: 约 2 小时（标准 CS50 讲座时长）
• 授课: David J. Malan（哈佛大学）

TL;DR (内容摘要)

本讲是 C 语言部分的最后一课，主题为数据结构。从抽象数据类型（队列、栈）出发，复习数组的内存连续性与扩容代价，进而引入链表（malloc、realloc、指针、箭头运算）、二叉搜索树、哈希表与 Trie，分析了各结构的运行时间、内存开销与实现复杂度，并强调时间与空间之间的 trade-off。

1. 引言：C 语言巅峰 [01:17]

• 这是第 5 周，也是在 C 语言中的最后一周；本讲普遍被认为是最具挑战性的一周，相当于整个课程前期累积知识的高潮。
• 课程比喻：我们一直在爬坡，虽然每一步都费劲，但本周开始“进入高原”，能喘口气并应用前几周的知识。
• 核心区分：
  • 数据结构（data structures）：具体的实现，涉及变量、指针、函数等。
  • 抽象数据类型（abstract data types, ADT）：更宽泛的描述，只关心“能做什么”和“有什么性质”，不关心底层怎么实现。
• 理解：抽象让我们可以在高层描述问题（如“排队”），而在底层用不同方式实现（数组、链表等），这正是计算机科学中的分层思想。

2. 队列（Queue）与 ADT [03:03]

• 队列是抽象数据类型之一，现实世界中就是“排队”。
• 例子：电影院的队伍、打印机任务队列——先提交的先打印。
• 理论性质：FIFO（First In, First Out）——先进先出。
• 代码层面的基本操作：
  • enqueue：把元素加入队尾。
  • dequeue：把元素从队头移除。
• 用结构体实现队列时，需要两个字段：
  • capacity（容量）：固定值，如 50 人。
  • size（当前大小）：已有多少人。
• 易错点：如果没有记录 size，数组中未使用的部分会是垃圾值（garbage values），无法区分有效元素。
• 在 C 中可以用 typedef struct 定义队列，内部包含 person people[50] 和 int size。
• 理解：capacity 是“最多能装多少”，size 是“现在装了多少”，两者含义完全不同，缺一不可。

3. 栈（Stack）与 LIFO [07:43]

• 栈是另一种常见 ADT，特性是 LIFO（Last In, First Out）——后进先出。
• 现实例子：
  • 衣橱里叠放的毛衣：最后放上去的最先穿。
  • 食堂的餐盘架：人们总是取走最上面的盘子。
  • Gmail 收件箱：新邮件出现在顶部，你通常会回最新的邮件，而忽略旧邮件。
• 代码操作：
  • push：把元素压入栈顶。
  • pop：把元素从栈顶移除。
• 注意：操作只能在栈顶进行，不能从中间或底部取出。
• 与队列的代码结构几乎相同，只是删除/插入时操作的位置不同（队列从头取，栈从尾部取）。
• 思考：人的直觉是“公平”或 FIFO，但在很多系统里（如函数调用、撤销操作）LIFO 反而是最自然的。
• 考点：区分 FIFO（Queue）与 LIFO（Stack），并掌握 enqueue/dequeue 与 push/pop 这两套术语。

4. 动画短片：Jack学习队列与栈 [13:00]

• 教授播放了一段来自 Elon University 的短片，用生活化的方式强化概念：
  • Jack 把衣服都堆成一堆，每天取最上面的穿，洗完又放回上面——这就是栈（LIFO）。
  • 他的朋友 Blue 建议改用队列：每天从一端的末尾放衣服，从另一端的最前取衣服，这样每件衣服都会被轮流穿到。
• 短片传达的核心：栈是一种“不公平”的存取方式，而队列提供“公平”的轮转。

5. 数组的局限：连续内存与扩容问题 [15:00]

• 数组的关键特性：所有元素在内存中连续存放（contiguous）。
• 问题：创建数组时（如 int array[3]）必须预先确定大小，之后要想增加元素，可能“把自己画进墙角”。
  • 因为在数组右侧的内存可能已被其他数据（如字符串 "hello world"）占用。
• 解决方案：
  • 把原数组复制到一块更大的新内存中，再添加新元素——但复制需要 O(n) 时间，效率低。
  • 从一开始就分配多余空间（例如申请 5000 个 int）——浪费内存，且不优雅。
• 理解：这体现了经典的 trade-off——要么牺牲时间（每次复制），要么牺牲空间（预先分配）。
• 易错点：数组中可能存在“垃圾值”，它们只是“不再使用”的内存，可以被覆盖或重新利用，但你不能假设它们是有效数据。

6. 手动扩容：malloc、realloc 与内存泄漏 [17:00]

• 使用 malloc 手动分配数组，并实现扩容的完整代码示例（list.c）：
  1. int *list = malloc(3 * sizeof(int)) 分配 3 个 int。
  2. 初始化 list[0]=1, list[1]=2, list[2]=3。
  3. 需要第 4 个元素时，int *tmp = malloc(4 * sizeof(int))。
  4. 用循环把旧的 3 个元素复制到 tmp。
  5. tmp[3] = 4;
  6. free(list); list = tmp;
• 重要提醒：malloc 可能返回 NULL，必须检查；并且在第二次 malloc 失败时，如果直接 return 1，之前 malloc 出的内存就泄漏了。
• realloc 函数可以自动完成“在原始地址上扩容”或“复制到新地址”的工作，只需传入原指针和新的字节数。
• 但即使使用 realloc，代码仍然冗长，因此需要更聪明的结构——链表。

内存管理黄金法则：用 malloc/realloc 分配的内存，必须用 free 释放。即使发生错误提前退出，也要释放之前成功分配的内存，否则就是内存泄漏（memory leak）。操作系统最终会回收内存，但这不能成为不写 free 的借口。

7. 链表（Linked List）：概念与动机 [21:00]

• 链表解决的问题：不需要把所有数据都连续存放在内存中，可以充分利用碎片化的空闲内存。
• 基本思路：
  • 每个数据元素称为节点（node）。
  • 每个节点中除了存储数据本身，还存储一个指针，指向下一个节点。
  • 链表的开头用一个独立指针 list（head）指向第一个节点。
  • 最后一个节点的指针指向 NULL（0x0），表示链表结束。
• 代码结构：

  typedef struct node {
      int number;
      struct node *next;
  } node;
  

  • 易错点：在 C 中，由于编译器自上而下处理代码，你必须在结构体内部用 struct node *next 而不能直接用 node *next，除非预先 typedef struct node node;。
• 新语法：箭头运算符 ->，等价于 (*ptr).field。
• 链表的代价：每个节点多存一个指针，占用额外空间（通常 8 字节）。
• 理解：链表用“指向”替代“紧挨着”，换取了动态增长的灵活性，这是时间-空间权衡的另一体现。
• 考点：链表的节点定义、malloc 分配节点、初始化 next 为 NULL。

8. 构建链表：前插（prepend）与遍历 [22:00]

• 构造链表的典型循环（构建 3 个节点）：
  1. node *n = malloc(sizeof(node)) 创建一个新节点。
  2. 检查 n != NULL。
  3. 设置 n->number = get_int()。
  4. 设置 n->next = NULL。
  5. 把新节点插入到链表头部：

     n->next = list;
     list = n;
     

  6. 先让新节点指向原来的头节点，再更新 list 指向新节点。
• 错误示范：若直接写 list = n 而不更新 n->next，会导致第一个节点“孤儿化”，即没有任何指针指向它，造成内存泄漏。
• 遍历链表并打印所有值：

  for (node *ptr = list; ptr != NULL; ptr = ptr->next) {
      printf("%d\n", ptr->number);
  }
  

• 注意：如果使用前插法，最终链表的顺序与插入顺序相反（例如输入 1,2,3，链表实际为 3→2→1）。这也是 LIFO 的体现。
• 思考：前插法让插入操作变成 O(1)，但会反转顺序；这对栈是合适的，但对队列不合适。

9. 链表的运行时间分析 [27:00]

• 搜索：O(n)——必须从头遍历到尾部，无法二分查找。
• 插入（头插）：O(1)——总是通过 list 指针即可完成，与链表长度无关。
• 优势：灵活利用零散内存，动态增长。
• 劣势：额外指针空间开销；无法像数组一样通过下标随机访问；不能二分查找（因为内存不连续，无法直接跳到中间）。
• 易错点：链表“搜索”与“插入”的运行时间要分开记忆。头插是 O(1)，尾插则是 O(n)（除非另外维护 tail 指针）。

10. 后插（append）与释放链表 [31:00]

• 若要保持插入顺序（类似队列），需要把新节点追加到链表尾部。
• 实现方法：
  • 先判断链表是否为空：如果 list == NULL，直接 list = n。
  • 否则用循环从 list 出发，找到最后一个节点（ptr->next == NULL），然后设置 ptr->next = n。
• 这种尾插操作的开销是 O(n)，因为每次都要遍历一遍链表。
• 释放整个链表：

  node *ptr = list;
  while (ptr != NULL) {
      node *next = ptr->next;
      free(ptr);
      ptr = next;
  }
  

  • 必须先暂存 ptr->next，再 free(ptr)，否则 free 之后访问 ptr->next 是未定义行为（use-after-free）。
• 考点：释放链表时指针更新的顺序；不能 free 后又读取该指针。

free 并不会自动释放整个链表，它只释放一次 malloc 得到的那块内存。你必须自己遍历并逐个释放所有节点。释放后不能再次访问已释放的内存，否则是未定义行为。

11. 有序插入（Sorted Insertion）的复杂度 [36:00]

• 如果想让链表始终有序（从小到大），需要处理多种情况：
  • 链表为空（直接插入）。
  • 新节点的值最小（前插）。
  • 新节点的值最大（后插）。
  • 新节点位于中间（需要找到合适位置并修改两个指针）。
• 伪代码如下：

  if (list == NULL) { list = n; }
  else if (n->number < list->number) { n->next = list; list = n; }
  else {
      for (node *ptr = list; ptr != NULL; ptr = ptr->next) {
          if (ptr->next == NULL) {           // 到达末尾
              ptr->next = n;
              break;
          }
          else if (n->number < ptr->next->number) {  // 插入到 ptr 和 ptr->next 之间
              n->next = ptr->next;
              ptr->next = n;
              break;
          }
      }
  }
  

• 这种复杂性与大量边界条件让 C 语言写“精致的结构”变得痛苦，也是之后转向 Python 的原因之一。
• 思考：有序插入可以在 O(n) 内完成，与搜索同为 O(n)。这说明链表的灵活性并不免费，逻辑越复杂的实现越容易出错。

12. 二叉搜索树（Binary Search Tree, BST） [40:00]

• 数组有连续性和二分查找优势，但扩容成本高；链表灵活但无法二分查找。BST 试图结合二者优点。
• 结构：
  • 树根（root）在最上面，包含一个值和两个指针：left（左孩子）和 right（右孩子）。
  • 性质（递归定义）：
    • 每个节点的左子树所有值都小于该节点的值。
    • 每个节点的右子树所有值都大于该节点的值。
• 在 BST 中搜索的效率为 O(log n)，与二分查找相同。
• 递归搜索代码：

  bool search(node *tree, int number) {
      if (tree == NULL)
          return false;
      else if (number < tree->number)
          return search(tree->left, number);
      else if (number > tree->number)
          return search(tree->right, number);
      else
          return true;
  }
  

• 易错点：BST 的搜索时间高度依赖树是否平衡。如果按递增顺序插入，二叉树会退化成一条“歪斜的链表”，搜索退化为 O(n)。
• 理解：平衡的 BST 高度约为 log₂(n)，但如果数据近乎有序，就退化为链式结构。保持平衡需要额外操作（如旋转），这属于更高级算法的范畴。
• 考点：BST 节点定义、递归搜索、最好／最坏运行时间。

13. 字典（Dictionary）与哈希的动机 [44:00]

• 字典是抽象数据类型：存储键（key）与值（value）的映射关系。
• 例：电话簿 = 名字（key）→ 号码（value）；英文字典 = 单词 → 定义。
• 我们希望字典访问速度极快，目标是 O(1) 常数时间。
• 方法：使用哈希函数（hash function） 将任意输入（如名字）映射到一个有限范围内的整数，决定数据存放在哪里。
• 直观启发：把 52 张扑克牌分到 4 个花色桶，比在一堆里找快得多。

14. 哈希表（Hash Table） [45:00]

• 哈希表 = 数组 + 链表 的“混血结构”，按某种哈希函数把数据放入桶中。
• 常见实现：大小为 26 的数组，每个位置对应字母 A–Z，以名字首字母作为哈希值。
• 例子：Mario → 首字母 M 放入下标 12；Luigi → 下标 11；Peach → 下标 15。
• 问题：冲突（collision）——不同名字可能哈希到同一位置。
  • 解决办法：在每个数组元素处挂一个链表（链地址法）。
  • 因此哈希表实际上是一个“数组的链表”。
• 生日悖论：即使数据分布均匀，碰撞概率也会比直觉更高。
• 哈希函数的改进：不只取首字母，还可以取前两三个字母，从而把桶数从 26 增加到 17,576，大幅降低碰撞。
• 代码示例（简单哈希）：

  unsigned int hash(const char *word) {
      return toupper(word[0]) - 'A';
  }
  

• 权衡：桶数越多，冲突概率越低，但未使用的桶浪费内存。
• 理论运行时间：最坏 O(n)（所有数据进同一个桶）；实际平均时间 O(n/k)，k 为桶数，若 k 很大且哈希函数好，则非常接近 O(1)。
• 易错点：不要误以为哈希表是严格的 O(1)。它只是“概率上近乎 O(1)”，最坏情况仍会退化为 O(n)。

哈希表概念辨析：字典是 ADT（有键值对概念），哈希表是实现字典的一种具体数据结构。实现字典也可以用数组、链表或树。哈希表的值是“近乎常数时间”的，但前提是哈希函数足够好且桶数合理。

15. Trie（前缀树 / 检索树） [51:00]

• Trie（发音 /triː/，来自 retrieval）是一种专门用于字符串检索的数据结构。
• 结构：每个节点是一个包含 26 个指针的数组（对应 a–z），后续字母通过指针逐层延伸。
• 查找/插入的时间取决于字符串长度，而不是树中已有字符串的数量。
• 因此，Trie 的搜索、插入、删除均为 O(1)（因为名字长度有上界）。
• 节点定义示例：

  typedef struct node {
      struct node *children[26];
      char *number;
  } node;
  

• 缺点：空间开销巨大——每组字母都要预分配 26 个指针，即使大部分为空。
• 总结：Trie 用“多到离谱的内存”换取“真正的常数时间”，是极端的空间换时间策略。

16. 总结与生活类比 [54:00]

• 本周学会了用指针和 struct 在内存中“拼接”各种数据结构：队列、栈、链表、树、哈希表、Trie。
• 现实中的例子：Sweetgreen 沙拉店按首字母分格存放外卖 (A–E, F–J, K–N, O–Z)，这就是一个简化版的哈希表（数组的数组）。
• 核心信息：
  • 没有“银弹”——每个数据结构都有时间和空间的 trade-off。
  • 理论运行时间（Big-O）与实践中的墙钟时间并不总是相同，聪明的哈希函数可以让哈希表“感觉像” O(1)。
• 下一讲将进入 Python，届时很多底层内存管理细节会被自动抽象掉。

关键标签 / 关键词

CS50 Data Structures Abstract Data Types Queue FIFO Stack LIFO Linked List malloc realloc free Memory Leak Arrow Operator Binary Search Tree Recursion Dictionary Hash Table Hash Function Collision Trie Big-O Runtime Trade-off C Programming

生成时间：2026-09-10 16:29:11 生成平台：VideoNote www.xygy.top