UC Berkeley CS61B — 数据结构

简介

CS61B 是加州大学伯克利分校（UC Berkeley）的经典数据结构课程，由 Josh Hug 教授主讲。这门课以 Java 为教学语言，通过大量精心设计的实验（Lab）和项目（Project）让你亲手实现各种数据结构和算法。课程强调"做中学"，不是纸上谈兵，而是让你从零开始构建列表、树、图、哈希表、排序算法等。

CS61B 在 CS 自学社区中口碑极好，被誉为"最好的数据结构入门课之一"。它的实验设计非常出色 — 你会在实现一个 Deque（双端队列）的过程中同时理解数组和链表的权衡，在实现一个 Git 版本控制系统的过程中理解哈希和图遍历。

先修要求

• 编程基础：需要熟悉一门编程语言（Java 最好，但不是必须）。CS61A 或同等水平的编程经验
• 基本的面向对象概念：类、对象、继承、接口
• 不需要：算法或数据结构的前置知识

难度

🌟🌟🌟（中等）

课程前半部分（基础数据结构和 Java 语法）相对容易，后半部分（图算法、排序、并发）难度明显上升。项目 2B（构建一个 Git 原型）和项目 3（构建一个游戏引擎）是课程的高潮，需要投入大量时间。

学时

约 120-150 小时（含实验和项目）

• lecture：约 40 小时
• lab：约 20 小时
• project：约 50-80 小时
• 复习和考试准备：约 10-20 小时

课程资源

• 课程主页：sp21.datastructur.es
• 课程视频：YouTube 播放列表
• 课程代码和实验：GitHub
• 教材：Hug's Data Structures（免费在线）

自学建议

1. 一定要做实验和项目。 看视频只是热身，真正的学习发生在你亲手写代码的时候。CS61B 的实验设计得非常好，每个实验都围绕一个核心概念展开。

2. 不要跳过 Project 2（Deque）。 这个项目要求你用数组和链表分别实现一个双端队列，是理解"数据结构选择影响性能"的最佳练习。

3. Project 3（Ngordnet）是可选的但强烈推荐。 这个项目要求你构建一个基于 N-gram 的历史趋势查询工具，涉及图算法和数据处理，非常有趣。

4. 善用课程提供的 JUnit 测试。 CS61B 为每个实验和项目都提供了完整的测试框架。先跑测试，看哪些没过，再针对性调试。

5. 如果 Java 不熟，先花 1-2 周学 Java 基础。 课程假设你会 Java，如果语法不熟，前期会比较痛苦。

6. 推荐配合《算法（第4版）》阅读。 Sedgewick 的书和 CS61B 的内容高度互补，很多章节直接对应。