编程抽象
这门课学什么
第二门编程课，用 C++ 讲抽象数据类型、递归与回溯、算法分析、排序、链表、树、哈希和图。作业包括 Boggle 拼字和寻路程序。
内容摘要
这门课是 CS106A 的后续课，用 C++ 讲数据结构和算法的基础。2008 年版共 27 讲。主线是先当容器的使用者，再当容器的实现者。讲师 Julie Zelenski 讲课条理清楚，经常现场写代码和调试。
第 1 阶段（第 1–7 讲）帮有 Java 基础的学生过渡到 C++：语法、字符串、流和文件。然后以使用者视角学 Vector、Grid、Stack、Queue、Map 和 Set。第 2 阶段（第 7–13 讲）讲递归：从简单递归到分形、排列和子集，再到回溯。之后讲指针和链表。
第 3 阶段（第 14–17 讲）讲算法分析和排序，包括大 O 记号、归并排序和快速排序。第 4 阶段（第 17–25 讲）转到实现者视角：写 C++ 类和模板，实现 Vector、Stack、Queue 和 Map。实现中依次用到链表、二叉搜索树、哈希表和字典树。图和图搜索也在这一阶段讲。第 26 讲总结设计权衡，第 27 讲是 C++ 进阶客座讲座。
课程有 7 个编程作业：Simple C++、ADT 使用、递归题组、Boggle 文字游戏、排序实验、优先队列 PQueue、地图寻路 Pathfinder。另有 9 次小组讨论课练习，以及期中和期末样卷。学完后，你能按时间和空间需求选择数据结构，并能用 C++ 自己实现它们。
为什么值得学
这门课把学生从会写程序带到会设计数据结构。Zelenski 的作业以打磨精细著称。
课程信息
- 学校
- 斯坦福（Stanford）
- 课程号
- CS106B
- 讲师
- Julie Zelenski
- 学期
- 2008 (SEE)
- 平台
- Stanford Engineering Everywhere
- 费用
- 免费
- 难度
- 入门
- 学时
- 27 讲
- 先修
- 需要 CS106A 程度的编程基础。
- 材料
- 视频、幻灯片、作业、考试、代码
- 许可证
- CC BY-NC-SA 4.0（SEE 站声明）
课程大纲 · 共 27 节
大纲依据：SEE 2008 版讲次列表（27 讲，按每讲 Topics 概括）（查看原始页面 ↗）
- 1课程导论与 C++ 初识Course Introduction and a First Look at C++
介绍 CS106 系列的定位、课程安排和学这门课的理由。初步展示 C++。
- 2面向 Java 程序员的 C++ 基础C++ Basics for Java Programmers
对比 C++ 与 Java 的语法、变量类型和控制结构。现场写一个含函数原型和 main 的完整程序。
- 3C++ 库与字符串C++ Libraries and Strings
介绍标准库和 CS106 库。讲 C++ string 的操作，并对比 C 字符串和 Java String。
- 4流、文件读写与类库Streams, File I/O and Class Libraries
讲控制台和文件的输入输出，以及流的引用传递。介绍 CS106 类库和面向对象的好处。
- 5容器类：Vector、Grid、Stack、QueueContainer Classes: Vector, Grid, Stack, Queue
以使用者视角讲模板容器的接口和用法。讨论类型安全和嵌套模板。
- 6Map 与 SetMap and Set
讲 Map 和 Set 的接口与用例。讲怎样遍历 Map，以及集合的高层运算。
- 7函数作为数据与递归入门Functions as Data; Introduction to Recursion
讲回调函数和存放自定义类型的 Set。开始讲递归分解。
- 8递归基础Recursion Basics
讲函数式递归和求幂的例子。分析递归调用的执行过程。
- 9递归思维：分形、汉诺塔与排列Thinking Recursively: Fractals, Hanoi, Permutations
用分形图和随机蒙德里安画讲过程式递归。讲汉诺塔和全排列，并画出递归调用树。
- 10子集、穷举递归与回溯Subsets, Exhaustive Recursion and Backtracking
讲子集生成和穷举递归。把排列改写成回溯，写出字谜（anagram）查找器。
- 11回溯实例与指针入门Backtracking Examples; Introduction to Pointers
用数独求解和字母算术讲回溯模板。开始讲指针的基本操作。
- 12指针、动态数组与链表Pointers, Dynamic Arrays and Linked Lists
讲指针操作、内存图和动态数组。引入递归数据结构，开始写链表。
- 13链表操作Linked List Operations
讲链表的打印、释放、头插和有序插入。比较数组和链表，并讲指针的引用传递。
- 14算法分析与大 O 记号Algorithm Analysis and Big-O
用语句计数分析程序性能。讲大 O、最好/最坏/平均情形，以及递归算法的分析。
- 15选择排序、插入排序与归并排序Selection, Insertion and Merge Sort
演示并分析 3 种排序。比较二次增长和 n log n 增长。
- 16快速排序Quicksort
讲分区（partition）和快速排序代码。演示最坏情形，并讨论选主元的策略。
- 17带回调的通用排序与类的编写Generic Sort with Callbacks; Writing Classes
用模板和回调写通用排序函数。讲 C++ 类的头文件、实现文件和成员函数。
- 18抽象数据类型：实现 VectorAbstract Data Types: Building a Vector
讲抽象墙（wall of abstraction）和 ADT 的意义。现场实现可动态增长的 Vector 类，并把它模板化。
- 19模板规则与实现 StackTemplate Rules and Implementing Stack
讲模板实现的规则和禁止逐成员复制。用 Vector 实现 Stack，并点评期中考试。
- 20Stack 与 Queue 的实现；编辑器缓冲区案例Stack and Queue Implementations; Editor Buffer Case Study
用链表实现 Stack 和 Queue，并分析运行时间。开始文本编辑器缓冲区案例。
- 21链表版编辑器缓冲区与 Map 的实现Editor Buffer with Linked Lists; Implementing Map
比较 Vector、Stack、单链表和双链表版的缓冲区。讨论时空权衡，并开始用 Vector 实现 Map。
- 22二叉搜索树Binary Search Trees
讲树的基本概念和遍历。用二叉搜索树实现 Map 的查找和插入。
- 23图与图搜索Graphs and Graph Search
演示 Pathfinder 作业。讲图的表示方法、深度优先搜索（DFS）和广度优先搜索（BFS）。
- 24哈希Hashing
讲哈希表、哈希函数和冲突。比较 Map 的几种实现，并用哈希实现 Set。
- 25词典案例：从有序数组到 DAWGLexicon Case Study: From Sorted Vector to DAWG
分别用有序 Vector、BST、哈希表和字典树（trie）实现词典。最后讲有向无环词图（DAWG）。
- 26设计权衡与课程总结Design Trade-offs and Course Wrap-up
从运行时间、内存和代码复杂度比较数据结构的选择。总结课程要点和后续课程。
- 27客座讲座：CS106 之外的 C++Guest Lecture: C++ Beyond CS106 (Keith Schwarz)
Keith Schwarz 讲 C++ 的历史和设计理念。介绍不依赖 CS106 库的写法和标准模板库（STL）。