CS61B 课程笔记（Midterm 1）

Q4: Destructively Create a Copy of IntList Without a Given Value

题目描述

编写一个方法 dilsans，用于在不使用 new 关键字的情况下，递归地创建一个 IntList 的副本，但不包含给定的值 y。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/** Destructively creates a copy of x that contains no y. You may not use new. */
public static IntList dilsans(IntList x, int y) {
    // 基本情况：如果 x 为空，返回 null
    if (x == null) {
        return null;
    }

    // 递归调用，处理 x 的剩余部分
    x.rest = dilsans(x.rest, y);

    // 检查当前节点的值是否等于 y
    if (x.first == y) {
        // 如果相等，返回下一个节点，丢弃当前节点
        return x.rest;
    }

    // 否则，保留当前节点，返回它
    return x;
}

代码分析

  1. 基本情况：
    • 如果传入的 IntList x 为 null，则直接返回 null。
  2. 递归处理：
    • 使用 x.rest = dilsans(x.rest, y) 递归调用该方法，处理 x 的下一个节点。这样可以构建剩余节点的副本。
  3. 节点检查：
    • 检查当前节点的值是否等于 y：
      • 如果是，则返回 x.rest，丢弃当前节点。
      • 如果不是，则返回当前节点 x，保留它。

Q5: Purge Method for Stack Interface

题目描述

为 Stack 接口添加一个默认方法 purge(Item x)，用于从栈中消除所有实例的 x，但保持栈的其他内容不变。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public interface Stack<Item> {
    void push(Item x);
    Item pop();
    int size();

    default void purge(Item x) {
        // 如果栈为空，直接返回
        if (size() == 0) {
            return;
        }
        
        // 弹出栈顶元素
        Item top = pop();
        
        // 递归调用 purge 方法
        purge(x);
        
        // 如果栈顶元素不等于 x，则重新入栈
        if (!x.equals(top)) {
            push(top);
        }
    }
}

代码分析

  1. 基本情况：
    • 如果栈的大小为 0，直接返回，无需处理。
  2. 弹出元素：
    • 使用 Item top = pop(); 弹出栈顶元素。
  3. 递归调用：
    • 递归调用 purge(x)，处理栈中剩余的元素。
  4. 条件判断：
    • 检查 top 是否等于 x：
      • 如果不等，则将其重新推入栈中，保持栈的状态不变。
      • 如果相等，则不做任何操作，继续处理下一个元素。