CS61B 课程笔记（Examprep 06 Exceptions and Iterators Exam Prep）

1. 异常处理（Exceptions）

原理解析

在这个程序中，我们有一个 checkIfZero 方法，它用于检查输入的整数 x 是否为零。如果 x 为零，方法会抛出一个异常。

异常处理机制: 使用 try-catch 语句来捕获异常。try 块中的代码会被执行，如果在执行过程中抛出异常，程序会跳转到 catch 块，处理异常并继续执行后面的代码。
整数除法: 使用 x / 2 进行整数除法，结果会向下取整。这意味着如果 x 是奇数，结果会是 x 除以2的下一个整数。

代码实现

public static void checkIfZero(int x) throws Exception {
    if (x == 0) {
        throw new Exception("x was zero!"); // 抛出异常
    }
    System.out.println(x); // 打印非零的值
}

public static int mystery(int x) {
    int counter = 0; // 计数器初始化
    try {
        while (true) {
            x = x / 2; // 每次除以2
            checkIfZero(x); // 检查是否为零
            counter += 1; // 计数器加一
            System.out.println("counter is " + counter); // 打印计数器的值
        }
    } catch(Exception e) { // 捕获异常
        return counter; // 返回计数器的值
    }
}

public static void main(String[] args) {
    System.out.println("mystery of 1 is " + mystery(1)); // 调用
    System.out.println("mystery of 6 is " + mystery(6)); // 调用
}

2. 交替链表（AltList）

原理解析

AltList 是一个实现交替数据结构的链表，其中元素类型交替存储。比如 AltList<Integer, String> 中，偶数索引存储 Integer 类型，奇数索引存储 String 类型。

递归设计: pairsSwapped 方法通过递归调用自身来交换每一对相邻的元素。
非破坏性操作: 返回一个新的链表，不会改变原始链表的结构。

代码实现

public class AltList<X, Y> {
    private X item; // 当前节点的值
    private AltList<Y, X> next; // 下一个节点

    // 构造方法
    AltList(X item, AltList<Y, X> next) {
        this.item = item;
        this.next = next;
    }

    public AltList<Y, X> pairsSwapped() {
        // 创建新的链表节点，交换当前节点和下一个节点的值
        AltList<Y, X> ret = new AltList<Y, X>(next.item, new AltList<X, Y>(item, null));
        
        // 如果下一个节点存在，则递归处理剩余部分
        if (next.next != null) {
            ret.next.next = next.next.pairsSwapped();
        }
        return ret; // 返回新的链表
    }
}

示例

AltList<Integer, String> list = new AltList<>(5, 
    new AltList<>("cat", 
    new AltList<>(10, 
    new AltList<>("dog", null))));

调用 list.pairsSwapped() 将返回新的链表 [cat, 5, dog, 10]。

3. 每K个元素（Every Kth Element）

原理解析

KthIntList 是一个实现 Iterator 接口的类，用于遍历链表中的每第 K 个元素。

迭代器模式: 使用 Iterator 接口可以便捷地遍历集合，保持当前状态。
K步迭代: 在 next 方法中，通过循环迭代到链表的下一个元素，跳过 K 个元素。

代码实现

import java.util.Iterator;
import java.util.NoSuchElementException;

public class KthIntList implements Iterator<Integer> {
    public int k; // 步长
    private IntList curList; // 当前链表
    private boolean hasNext; // 是否还有下一个元素

    // 构造方法
    public KthIntList(IntList I, int k) {
        this.k = k;
        this.curList = I; // 初始化当前链表
        this.hasNext = true; // 初始化为有下一个元素
    }

    // 检查是否有下一个元素
    public boolean hasNext() {
        return this.hasNext;
    }

    // 返回下一个K个元素
    public Integer next() {
        if (curList == null) { // 如果链表为空
            throw new NoSuchElementException();
        }
        Integer toReturn = curList.head; // 获取当前元素
        for (int i = 0; i < k && curList != null; i++) {
            curList = curList.tail; // 向后移动K步
        }
        hasNext = (curList != null); // 更新hasNext状态
        return toReturn; // 返回当前元素
    }
}

示例

IntList L = new IntList(0, new IntList(1, new IntList(2, 
    new IntList(3, new IntList(4, new IntList(5, 
    new IntList(6, new IntList(7, null))))))));
for (Iterator<Integer> p = new KthIntList(L, 2); p.hasNext(); ) {
    System.out.println(p.next()); // 输出0, 2, 4, 6
}