Skip to content

Berkeley CS61B

Basic Information

来源：UC Berkeley

课程名称：CS61B, Data Structures (Spring 2021)

主题：Java 语言基础，数据结构与算法

主要内容：40 个 Lecture, 10 个 Lab, 4 个 Project

课程网站：https://sp21.datastructur.es

个人实现：21Sp-CS61B-Berkeley （Private 仓库，依要求不公开）

起止时间：2023.12 - 2024.02

Content

Lectures

课程的主要内容是 Java 语言基础和数据结构与算法，同时包含了一部分软件工程的内容。

Part 1

第一部分主要是 Java 语言基础，主要包含以下内容：

  • Defining and Using Classes

  • JUnit Test & Test Driven Development

  • References

  • Interface Inheritance, Implementation Inheritance

  • Static type, Dynamic type, Casting

  • Comparators, Comparable, Iterators, Iterable, etc.

  • Generics

  • Serializable

Part 2

第二部分主要是数据结构与算法，主要包含以下内容：

  • 算法分析初步：如各种渐进 \(O(n)\ ,\ \Theta(n)\ ,\ \Omega(n)\)

  • Linked List (SLList, DLList) & Array List ，即链表与带自动伸缩的数组

  • Disjoint Set 并查集：树重优化与路径压缩

  • Abstract Data Type : Set, Map, etc.

  • 二叉搜索树及其改进：B 树，左偏红黑树

  • Hashing : 哈希函数与哈希表

  • Heaps & Priority Queue 堆与优先队列

  • 树与图的遍历：DFS, BFS, 拓扑排序

  • 最短路径算法：Bellman-Ford, Dijkstra, \(A^*\), DAG SPT

  • 最小生成树算法：Cut property, Prim, Kruskal

  • 多维空间里的 range searching : Quad Tree, K-D Tree

  • 与字符串相关的操作：Trie

  • 排序算法：基数排序、插入排序、归并排序、快速排序、Quick select、桶排序、堆排序

  • 排序算法的理论上限：通过比较的排序最低时间复杂度是 \(\Omega(n\log n)\)

其中，一个重要的观点是，各种搜索算法与 Set, Map 的常见实现之间的一种对应关系。例如，BST 与归并排序、插入排序、选择排序都基于可比较性，Trie 与基数排序都基于字符串的特性，无法比较的对象也可以通过计算哈希值来实现桶排序，等等。

Labs

该课程的 lab 主要围绕课程内容展开，有些也是 project 的前置练习。例如实现 BSTMap, HashMap ，练习 Serialization 等。在完成过程中，主要遇到了以下问题：

Problem 1

Still not finished:

Lab 7 Optional:

How to iterate through a BSTMap without using ArrayList or sth. ?

Or, how to construct a iterator?

Project 0

第一个 project 的内容是实现一个 2048 游戏，主要练习 OOP 与结构化的编程思想，强调通过写优秀的注释与合理分割对象（例如，将棋盘与 Tile 分别作为对象）来降低编写大型程序的难度。

Project 1

第二个 project 的内容是实现一个 ADT : Deque ，完成这个 ADT 的 Array 和 LinkedList 两种实现，并且通过一个统一的接口对外实现一致的功能。

具体实现中，需要关注以下部分：

  • ArrayDeque: 何时 resize, 如何 resize

  • LinkedListDeque: 如何通过同时位于首尾的 sentinel 节点减少边界判断

Project 2

第三个 project 的内容是实现一个简化的 git ，包括 add, commit, rm, branch, find, status, checkout, merge 等功能。 其中，源文件并没有给出代码框架，需要自行设计架构。笔者的最终实现大致有一千行代码，这也是笔者第一次完成千行量级的项目 (doge) 。由于 CS61B 仍然在使用该 project ，这里不再给出具体的代码，只介绍笔者的大致的设计思路。

Gitlet 中，最基本的数据单元是 Blob 和 Commit ，可以通过 Serialization 将它们分别存储到 .gitlet 目录下的 blob 和 commit 文件夹，并通过 SHA-1 值快速索引。更高一级的数据单元是 Branch ，可以通过 Serialization 将其存储到 branch 文件夹。其中，每个 branch 负责跟踪 HEAD ，并且笔者通过实现其 iterator 来实现对于 branch 的 for-each loop ，从而便于在后期 merge 等操作时遍历 branch 。最高级的数据单元是 Repository ，通过维护 staging area 的暂存区文件、 removed file 列表、当前 branch 等操作来记录目前 Repository 的状态，并可以被存储到 .gitlet 目录下的 repo 文件中。通过以上的数据结构与一些工具方法 （在 Tools.java 里实现）就可以维护当前 Repository 。

Project 3

第四个 project 的内容是实现一个类似二维 Minecraft 的游戏。主要包含地图生成器（地图由随机种子决定）、操作逻辑、Serialization 等几个部分。其中比较难实现的是地图生成器，具体来说，该 project 中要求地图生成器能够生成一系列借助走廊连通的矩形房间。笔者的大致设计思路如下：

首先在由墙壁填充的地形中随机生成一些矩形房间，其中通过要求新生成的矩形房间不与已生成的房间重叠太多来限制房间位置。之后，随机选取两个房间内的点来构建走廊，期间将所有非墙的点放到并查集中，动态改变它们之间的连接状态。像这样持续随机生成走廊，直到所有非墙点连通为止。最后，在保证连通性的前提下，随机将一些非墙点改为墙，来提高游戏的难度。这样即可完成地图生成。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 协议之条款下提供，附加条款亦可能应用