CS106B 编程抽象：C++ 实现与算法图解 · 开篇与课程概览
资料基础：斯坦福 CS106B 官方课程网站（2026 夏季学期，8 周压缩学期，共 28 讲）全部公开页面——课程主页、Syllabus、讲座页（含各讲文字讲义与公开附件）、作业页等。完整调研记录见同目录
00_research_inventory.md（及lecture_data_records.json数据记录）。 版权与用途声明：官方材料 © Stanford University，受保护、不得擅自传播。本文档是自学整理笔记：将 28 讲公开内容按主题重组成 17 章，讲解均为原创中文表述，未逐字转载任何官方讲义；全部代码为本笔记撰写的教学示例（现代 C++17、仅用标准库），并非课程作业提交物。 学习建议：每章先读“概述”，再看“核心概念与算法原理”里的图示/步骤分解，然后亲手把代码敲一遍并运行，最后用“思考题”自测。链表、二叉树、堆、图这几章强烈建议边读边在纸上画内存/结构图。
课程概览
这门课是什么？
CS106B（Programming Abstractions，编程抽象）是斯坦福入门编程序列的第二门课。先修 CS106A 用 Python 建立了编程方法论与问题求解基础；CS106B 在此基础上做三件大事：
- 学一门新语言：C++（类型系统、函数、字符串、类、指针与动态内存）；
- 掌握编程抽象：认识“抽象数据类型”(ADT)——把“用什么”与“怎么实现”分开，先会用（客户端视角），再自己实现（实现者视角）；
- 吃透经典数据结构与算法：线性表、栈、队列、集合/映射、树、堆、哈希表、图，以及递归、回溯、分治、贪心（Dijkstra、霍夫曼）、复杂度分析（大 O）。
官方 syllabus 给的主题推进顺序（“近似顺序”）正是本文档 17 章的骨架：
C++ 基础 → 数据抽象与经典 ADT → 递归与回溯 → 类与面向对象 → 指针与动态内存 → 链式数据结构 → 进阶算法
与 CS106A 的衔接
- CS106A 结业水平 = 能写多函数程序、会用循环/条件/列表/字典、理解基础测试。CS106B 不重复教编程入门，而是以“你会写程序”为前提，快速补 C++ 语法差异后直接进入抽象与算法。
- Python 经验迁移要点：列表→
std::vector、字典→std::map/std::unordered_map、集合→std::set/std::unordered_set、字符串 API 差异大（C++ 字符串可原地修改）、一切传参默认按值拷贝（要显式写&引用）。这些差异会在 Lecture 1–3 反复强调。
官方课程要点（摘自 syllabus，概括）
- 教学团队：讲师 Sean（Szumlanski）、Head TA Butch、14 名 section leaders；小班讨论每周一次、占 5%。
- 节奏与考核：8 周、28 讲（MTWTh 13:30–14:45，NVIDIA Auditorium）；作业 25% + 期中 27.5% + 期末 37.5% + 小班 5% + 讲座小测 4% + Quiz0 1%；期中 7/17、期末 8/14（纸笔）。
- 作业（8 个，约每周一个，10–20 小时/个）： | # | 名称 | 覆盖主题（对应章节） | |—|—|—| | 0 | Welcome to CS106B! | 环境与工具 | | 1 | Getting Your C++ Legs | C++ 基础、字符串（L1） | | 2 | Fun with Collections | 栈/队列/集合/映射等 ADT（L2–L3） | | 3 | Recursion Etudes | 递归（含分形）（L5） | | 4 | Recursive Backtracking | 回溯（L6） | | 5 | Tone Matrix | 类/数组/动态内存（L8–L9） | | 6 | Listy Things | 链表与树（L11–L12） | | 7 | Huffman Coding（选做🌱） | 霍夫曼编码（L13） |
- 工具：Qt Creator（编辑器+编译器）+ Stanford C++ Library（课程专用容器库，文档公开：web.stanford.edu/dept/cs_edu/resources/cslib_docs/）。本文档代码一律用标准库
std::容器（等价关系见文末速查表），保证你能在任何现代 C++ 环境编译运行。 - 教科书：Eric Roberts, Programming Abstractions in C++（第 5 版），ISBN 978-0133454840。
- 学习目标（概括）：乐于用编程解决现实问题；识别常见抽象；理解日常技术背后的程序化概念；能用递归/算法推理拆分复杂问题；能评估数据结构与算法的设计取舍。
学习路线：真实 28 讲 ↔ 本文 17 章
官方 2026 夏季学期 28 讲实际顺序如下。本文档按官方教学顺序把它重组成 17 章主题笔记（每章开头标注“对应真实讲座 Lxx–Lyy”），数字编号即学习顺序：
| 本文章 | 主题 | 对应官方讲座 |
|---|---|---|
| Lecture 1 | C++ 基础回顾与 STL 容器入门 | L01 Welcome! · L02 C++ Fundamentals · L03 C++ Strings · L04 Testing, Vectors, and Grids |
| Lecture 2 | 栈与队列 | L05 Stacks and Queues |
| Lecture 3 | 集合与映射（基于树的有序容器） | L06 Sets and Maps |
| Lecture 4 | 算法分析：大 O 记号 | L07 Big-O and Algorithmic Analysis |
| Lecture 5 | 递归：原理与递归策略 | L08 Introduction to Recursion · L09 More Recursion · L10 Recursive Problem Solving |
| Lecture 6 | 递归回溯与枚举 | L11 Recursive Backtracking and Enumeration · L12 More Recursive Backtracking |
| Lecture 7 | 排序算法 | L13 Sorting Algorithms |
| （L14 Problem Solving Day 为复习/答疑，并入相关章节练习） | ||
| Lecture 8 | 面向对象编程：类与封装 | L15 Object-Oriented Programming |
| Lecture 9 | 指针、数组与动态内存管理 | L16 Pointers and Arrays · L17 Dynamic Memory Management |
| Lecture 10 | 优先队列与二叉堆 | L18 Priority Queues and Binary Heaps |
| Lecture 11 | 链表 | L19 Introduction to Linked Lists · L20 More Linked Lists |
| Lecture 12 | 二叉树、二叉搜索树与遍历 | L21 Binary Trees, BSTs, and Tree Traversals · L22 More on Binary Trees |
| Lecture 13 | 霍夫曼编码 | L23 Huffman Coding |
| Lecture 14 | 散列与哈希表 | L24 Hashing |
| Lecture 15 | 图：表示、遍历与拓扑排序 | L25 Graphs |
| Lecture 16 | 最短路径：Dijkstra 与 A* | L26 Dijkstra and A* · L27 Graph Coding |
| Lecture 17 | 拓展专题：Trie 与并查集 | 延伸内容（官方未设独立讲座；L24 曾提及 trie 思路） |
（L28 Wrap 为期末回顾，无新主题。）
笔记约定
- 每章统一结构：概述 → 核心概念与算法原理 → 代码示例与实现详解（代码做什么 / 实现机制解说）→ 复杂度分析 → 关键要点 → 常见陷阱与注意事项 → 思考题（带答案）。
- ASCII 图一律放在
text代码块中；cpp代码块可直接复制编译。 - 术语采用“中文（English）”或“English（中文）”双语标注，方便对照原版材料。