cs61b学习记录

准备工作

在开始 cs61b 的学习之前，我在网上收集了一些资料。主要是 61b 的经验贴：

https://www.1point3acres.com/bbs/thread-908806-1-1.html
https://zhuanlan.zhihu.com/p/434144861

我选的是 21 sp 的课程，需要注意的是课程主界面给的 GradeScope 课程代码是私有的，Josh Hug 后来给了一个新的 Public Code: MB7ZPY，这个的作业是全的。

其他的配置按照 61b 的说明进行就可以了。

Week 1

proj0

week 1 主要是介绍 Java 的语法和面向对象的特性。看完 Reading，完成 Lab 之后就来到了第一个重头戏 Proj0。我在大一的时候就是在这里被劝退了，因为全英的项目说明和一大堆陌生代码实在是让人找不到头绪。正确的上手方法是反复阅读项目的说明文档。61b 提供了高质量的说明文档，堪称手把手的教学，把整个实现逻辑掰开了揉碎了喂给你，还有专门的 Google 表单来测试你对项目的理解（里面的示例函数真的帮了我大忙）。然后自己一点一点试着写出大概的代码框架，之后就是漫长的 DEBUG-REVISE 循环。然后你会发现自己的代码又臭又长，看了一段就忘了另一段在干嘛，于是又开始重构自己的代码，把代码解耦成一个个小的函数。这中间我前前后后大概花了 8+ 小时，最后还是没能通过全部测试。我跟 Gemini 反复确认自己的代码逻辑，实在是找不出来问题了，按理来说就应该全部通过。于是我想要修改一下测试函数，看看能不能让这个测试通过。吊诡的是，这个修改过后，我的代码就一下子没问题了，全部测试都能通过了，现在我也没有明白是为什么…

到这里你实际上还没有完成 proj0，因为 2048 的输入部分需要修改。61b 在写输入函数的时候默认使用的英文输入法，其他输入法的上下左右不能正确识别。需要定位到输入函数的相关部分，把上下左右按键改成 WASD 就没问题了。之后就可以快乐地享受自己的第一个 proj 游戏了。

Week 2

这周主要是讲 IntList，链表及其完善，顺便介绍了 Java 的单元测试和 Debug。

lab2 setup

注意：Lab2 Setup 的 Maven 库存在问题，需要手动引入 javalib，参考这里

我必须要吐槽一句，nm 的这个过期的 Maven 库让我折腾了好久。我不自量力地想要修复这个仓库，于是跟 deepseek 和 Gemini 较了半天劲。其实问题很简单，就是 pom 文件的相对目录应用不正确，导致项目不知道从哪里下载相关的依赖。我没有解决这个问题，只能手动导入修复。这就是网课比不上线下课的地方，如果有助教就可以直接询问助教，但是网课只能在网络上搜索，而且还不一定有相关的问题解决方案，只能靠自己慢慢摸索，有点浪费时间。

链表

裸链表

课程首先创建了一个裸链表 IntList.java:

public class IntList {
    public int first;
    public IntList rest;

    public IntList(int f, IntList r) {
        first = f;
        rest = r;
    }

    /** Return the size of the list using ... recursion! */
    public int size() {
        if (rest == null) {
            return 1;
        }
        return 1 + this.rest.size();
    }

    /** Return the ith item of this IntList. */
    public int get(int i) {
        if (i == 0) {
            return first;
        }
        return rest.get(i - 1);
    }

    public static void main(String[] args) {
        IntList L = new IntList(15, null);
        L = new IntLsist(10, L);
        L = new IntList(5, L);

        System.out.println(L.get(100));
    }
}

裸链表里面有什么？有两个部分，一个是存储的数据int first，另一个是指向下一个裸链表的指针IntList rest。这个链表还包含了两个方法size()和get(int i)。我们可以看到，这个链表在使用的时候不太方便:

• 创建新链表的时候必须手动指定 rest
• size()和get(int i)的时间复杂度为O(n)

针对第一条，课程介绍了改进过的 SLList(Single linked list)

public class SLList {
    private static class IntNode {
        public int item;
        public IntNode next;

        public IntNode(int i, IntNode n) {
            item = i;
            next = n;
        }
    }

    /** The first item (if it exists) is at sentinel.next. */
    private IntNode sentinel;
    private int size;

    /** Creates an empty SLList. */
    public SLList() {
        sentinel = new IntNode(63, null);
        size = 0;
    }

    public SLList(int x) {
        sentinel = new IntNode(63, null);
        sentinel.next = new IntNode(x, null);
        size = 1;
    }

    /** Adds x to the front of the list. */
    public void addFirst(int x) {
        sentinel.next = new IntNode(x, sentinel.next);
        size += 1;
    }

    /** Returns the first item in the list. */
    public int getFirst() {
        return sentinel.next.item;
    }

    /** Adds x to the end of the list. */
    public void addLast(int x) {
        size += 1;

        IntNode p = sentinel;

        /** Advance p to the end of the list. */
        while (p.next != null) {
            p = p.next;
        }

        p.next = new IntNode(x, null);
    }

    /** Returns the size of the list. */
    public int size() {
        return size;
    }

    public static void main(String[] args) {
        SLList L = new SLList();
        L.addLast(20);
    }
 }

泛型

改进链表使得其可以接受多种类型输入

数组链表

程序创建的目的是完成任务，面向对象的编程方式对用户屏蔽了实现细节，这就是我们所构建的抽象障碍。在这样的情况下，谁说链表一定要用链表来实现（QAQ），我们可以使用数组来实现！这就是 AList(ArrayList)

注意：java 的数组长度不可变，因此需要在索引超出数组长度的时候扩展数组。使用System.arraycopy函数来复制数组。

这里 61b 引入了时间复杂度的概念，因为如果按照size += 1的方式来扩展数组，创建数组的时间复杂度为O(n)，而按照size *= 2 的方式来扩展数组，时间复杂度为O(logn)。lab3 的任务就是为 AList 编写时间测试。

Java 关键字private和public

private static class IntNode {
        public int item;
        public IntNode next;

        public IntNode(int i, IntNode n) {
            item = i;
            next = n;
        }
    }

private class IntNode 中声明了 Public 变量 item, next, 和 IntNode，两者的作用域不同。对于 SLList 类来说，IntNode 中的变量是可访问的，而外部程序对于 SLList 类的应用无法直接访问 IntNode 类。这就是 Java 对于程序的封装，隐藏了类型创建中不必要的细节。

proj1A

没有什么比看到 checkpoint 全过更令人欣慰的了

我感觉我的 proj1 做的还是有点早了，磕了两天，结果MaxArrayDeque要求的实现中，Comparator 根本不知道要怎么实现。原来 61b 把 proj1 放在 Week3，但是整个的项目实现其实可以在听完第五章的 Java 语法之后再来做，这样做的时候就不会卡住了。其实我做的还是慢了，更多的原因还是因为没有专注在项目上，Debug 的能力还有待提高。唯一值得欣慰的是大模型的出现降低了单人学习的门槛，遇到实在看不懂的 Bug 可以去请教 AI。

Week 3

仍然还是链表和数组列表的实现。另外介绍了 Java 中的一些语法特性。

Week 4

lab6

这个 Lab 是 proj2 的前置，make 的配置在 win 下不正确，我的解决方案是启用 WSL，换了清华的源（有的文章会给过时的源，注意时效性，最好去官方的镜像站取源），然后重新配了一遍 java 环境。

5.29

什么都没干，感觉这两天还可以再赶赶进度的，起码要复习一下代码，但是还是懒惰了。该死的拖延…