跳转至

UCB CS61b: Data Structures

课程简介

  • 先修要求：任何一门编程语言的熟练使用（推荐 C++ 或者 Python），以及离散数学
  • 参考材料：
    • UCB 的 CS61b 课程
    • 《算法导论》，作者：Thmos.H.Cormen, Charles E. Leiserson, etc.
    • Hello 算法，提供了多版本的代码实现，配图详实
    • OI-wiki，OI 人的 wiki 网站
  • 主要内容：
    • Java 编程基础
    • 大部分数据结构与部分算法内容
    • 非常有趣的 lab

个人心得

学习数据结构，既能锻炼自己的代码能力，又能为后续学习算法打下坚实基础。在我看来，学习数据结构的一个可能的姿势为：

  1. 跟随 CS61b 的课程学习一个新的数据结构，通过图形化的方式理解该数据结构的实现方法
  2. 完成 CS61b 的 homework 和 projects
  3. 关掉所有网站，打开你的编辑器/IDE，从零开始实现所学的数据结构。遇到卡顿的地方，尽可能地自己想出办法解决，然后上网查询是否有更优解；如果的确不能解决，再 Google 所遇到的问题（而不是整个实现方法）。为了检测自己的代码是否正确，应该编写一系列测试代码（在 CS61b 中有测试代码的相关讲解）
  4. 写完整个代码后，反思是否可以改进效率，是否可以简化代码过程，是否可以通过继承等方式减少代码量
  5. 在后续实现其它数据结构时，如果需要这次编写的代码，则直接使用之（同时可以测验代码正确性）

这样，等到你学完整门课程后，你就拥有了一个独属于自己的、代码量至少上千的数据结构库了！这不仅会给自己一种巨大的成就感，还会极大地提高自己的代码能力，最重要的是，经过这种锻炼后，你肯定深刻地理解并记住了若干数据结构的实现过程，而不是死记硬背了。

另外，《算法导论》这本书还介绍了一些高级的数据结构，如斐波那契堆、van Emde Boas 树等，可以作为补充读物。其数学推理非常精细，很适合用于学习分析时间复杂度的方法。

相关链接

  1. 课程网站：2018 spring，2024 spring
  2. 课程参考教材：https://cs61b-2.gitbook.io/cs61b-textbook
  3. Hello 算法：Github 上的 62k+star 项目，包含了基本的数据结构和算法教程，提供了不少的代码的可视化，可以帮助理解背后的逻辑；另外还提供了多种语言的数据结构实现。
  4. OI-wiki：一个 OI 竞赛向网站，里面囊括了若干进阶数据结构的教程，可作为课外扩展内容。
  5. Data Structure Visualizations：一个可视化数据结构的网站。