CS

CS61B week4 学习笔记

包括第四周讲座内容，lab4和project1后半部分

lec 9 Extends, Casting, Higher Order Functions

继承

  • 接口继承（Interface Inheritance）：只声明方法。
  • 实现继承（Inplementation Inheritance）：同时说明如何使用。

对于一个类继承另一个类，使用关键词 extends。通过 extends，可以继承所有实例变量和类变量，继承所有方法，还有嵌套的类。然而，却无法继承 private 的成员。

Super

使用 super 来表示父类，使用 super.method 来访问父类的方法。

每次子类的 constructor 运行时，首先会运行父类的 constructor。但是，对于有输入参数 x 的 constructor，只会调用没有参数的父类方法。因此，此时必须明确地说明 super(x);。

Object 类

Java 当中所有的类，都是 Object 的子类。Object 也有一些方法。

Is vs. Has

类的继承应该是 is 的关系，而不是 has 的关系。因为子类会继承所有父类的方法，如果说子类是 Stack，父类是 List，那么 Stack 会继承 List 的各种 index, insert 方法，这显然不是我们想要的。

封装（Encapsulation）

为了管理复杂性，需要封装。通过接口来访问对象。需要在正确的抽象层级上思考。

继承破坏了封装

假设 Dog 类中有以下方法：

1
2
3
4
5
6
7
8
9

public void bark() {
    barkMany(1);
}

public void barkMany(int N) {
    for (int i = 0; i < N; i += 1) {
        System.out.println("bark");
    }
}

假设子类 VerboseDog 中有如下方法：

1
2
3
4
5
6
7

@Override
public void barkMany(int N) {
    System.out.println("As a dog, I say: ");
    for (int i = 0; i < N; i += 1) {
        bark();
    }
}

那么，调用父类的 bark ()后，会再次调用子类的 barkMany ()，从而陷入无限循环。

编译器类型检查

只会检查静止类型。如果发现静止类型有可能出错，那么就会编译出错。通常，如果赋值右侧的编译类型是左侧类型的父类，那么会出错。

使用 Casting 来改变类型，实现类型转换。然而，这也可能会带来风险。

lec10 Subtype Polymorphism vs. HoFs

高阶函数

在 java 中，可以使用 interface 继承，通过在类中定义函数，来做到这一点。

多态（Polymorphism）

子类（Subtype）多态

对于不同的实现方式，使用同样的接口访问。

Max 函数

为了实现一个普遍的 max 函数，可以比较各种各样的对象，考虑定义一个 OurComparable 的接口。

在接口中，声明有 public int compareTo(Object o); 方法。然后，在 Dog 类中，实现该接口，并 Override 该比较方法。

但是，需要先把 Object 的类型转换为 Dog：

1

Dog otherDog = (Dog) o;

根据编译器的静态类型检查，无法使用 o.size，只能用 otherDog.size。

对于比较函数，可以返回 this.size - otherDog.size。负数代表小于，0 代表等于，正数代表大于。

缺点

  • 类型转换可能会带来错误。
  • 没有现成的类实现了 OurComparable。不支持其他的正数，浮点，字符串等等。

解决方法

使用 java 自带的接口 Comparable，拥有 compareTo 方法。同时，接受参数的时候使用泛型，避免转换。通过 implements Comparable<Dog> 实现。

比较名字

通过实现 Comparator，并 Override compare 方法来实现。

1
2
3
4
5
6

public class NameComparator implements Comparable<Dog> {
	@Override
	public int compare(Dog o1, Dog o2) {
		return o1.name.compareTo(o2.name);
	}
}

之后，将 NameComparator 类嵌套在 Dog 类当中，最好加上 static，同时将 public 改成 private。

然后，创建 public 的获得比较方法的方法：

1
2
3

public static Comparator<Dog> getNameComparator() {
	return new NameComparator();
}

使用

1

Comparator<Dog> nc = Dog.getNameComparator();

来获取方法。

总结

简单来说，Comparable 是将自己与其他对象比较，Comparator 是一个机器比较两个对象。

lec11 Exceptions, Iterators, Object Methods

本节需要利用数组来实现 Set 集合。可以方便地实现 void add(T x)，boolean contains(T x) 等方法。

Iteration

增强 for 循环

for(int i : javaset) {...} 实际上，这些代码利用到了迭代器 iterator。

Iterator

在类当中，需要定义一个 private 的类继承 Iterator：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

private class ArraySetIterator implements Iterator<T> {
	private int wizPos;
	public ArraySetIterator() { wizPos = 0; }
	public boolean hasNext() { return wizPos < size; }
	public T next() {
		T returnItem = items[wizPos];
		wizPos += 1;
		return returnItem;
	}
}

同时，需要定义一个公开的方法，来返回 Iterator：

1
2
3

public Iterator<T> iterator() {
	return new ArraySetIterator();
}

最后，为了让 java 知道这个类实现了迭代器，需要将这个类继承 Iterable：

1
2
3
4

public class ArraySet<T> implements Iterable<T> {
	...
	public Iterator<T> iterator() { ... }
}

Object 方法

ToString 方法

通过 Override toString 方法，可以实现类的打印。也可以使用 StringBuilder 类。

Equals

== 只会比较内存中是否有相同的值，对于引用类型，也只会比较是否指向相同的内存。

Isinstanceof 使用

1

if (o instanceof Dog uddaDog) {...}

如果 o 不是 Dog 的实例，那么返回 false；否则，将引用内容转换为 Dog，返回 uddaDog。

lab4 Git and Debugging

这一个 lab 包括如何解决 git 的分支冲突，以及一个特别微妙的 bug。

Git

在 git 当中，通常合并分支可以自动完成。如果遇到分支冲突，需要手动选择要保留的分支，然后再 commit。

同时，利用 git checkout some_version -- <file> 命令，可以手动选择恢复某一个版本的特定文件。这个功能很有用，可以方便地将某个文件恢复为之前的状态。

Integer bug

如果对于 Integer 的实例使用 == 来比较，那么这只对于-128 到127 之间的数才有效。因为这个本质上用到了 caching 之类的技巧。因此，要使用 Object.equal(Integer1, Integer2) 来比较。

project1 后半部分

Extra Credit

这分为两个任务：第一个是使用随机化测试，将有 bug 的代码与没问题的代码对比，找出错误。第二个是每次记录下执行的操作，然后当做错误信息打印出来。

第二问其实很简单，只需要在一个 str 上不断扩展每一次的操作即可。然而，我却想复杂了，以为只用打印最近几次的操作，从而还使用了队列。事实上，全部打印出来就可以。

MaxArrayDeque

这需要写一个新的类，继承 ArrayDeque，并且加入一些比较的方法。

因此，首先需要储存比较器，并且初始化：

1
2
3
4
5

private Comparator<T> originalComparator;  
  
public MaxArrayDeque(Comparator<T> c) {  
     originalComparator = c;  
}

然后，实现 max 方法：

1
2
3
4
5
6
7
8
9

public T max() {  
    int maxIndex = 0;  
    for (int i = 0; i < size(); i++) {  
        if (originalComparator.compare((T) get(i), (T) get(maxIndex)) > 0) {  
            maxIndex = i;  
        }  
    }  
    return (T) get(maxIndex);  
}

注意，这当中的类型转换较多，可以说是 Java 多态的特点。

然后，实现另一个比较方法，可以接受任意的比较器：

1
2
3
4
5
6
7
8
9

public T max(Comparator<T> c) {  
    int maxIndex = 0;  
    for (int i = 0; i < size(); i++) {  
        if (c.compare((T) get(i), (T) get(maxIndex)) > 0) {  
            maxIndex = i;  
        }  
    }  
    return (T) get(maxIndex);  
}

本来我以为这就完了，结果在测试的时候，发现原先 ArrayDeque 的 get 方法有问题。仔细一看，才发现原来之前是直接把输入的 index 当成实际数组当中的索引！这明显打破了抽象层级，自然出错。

于是，进行修改。首先判断 index 是否在范围之内。然后，如果不是环形的话，index 就是 nextIndex(nextFirst) + index。这里之所以使用 nextIndex 方法，就是为了防止 nextFirst 为最后一个索引的情况。

如果数组是环形的，还需要分类讨论。如果当前索引较小，元素位于数组的右侧，那么索引为 nextFirst + 1 + index；如果当前索引较大，元素位于数组的左侧，那么索引为 index - items.length + nextFirst + 1。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public T get(int index) {  
    if (index < 0 || index >= size) {  
        return null;  
    }  
    if (!isCircular()) {  
        return items[nextIndex(nextFirst) + index];  
    }  
    if (nextFirst + 1 + index < items.length) {  
        return items[nextFirst + 1 + index];  
    }  
    return items[index- items.length+nextFirst+1];  
}

注意

Equals 方法需要对于 Deque 通用，也就是说具有相同元素的 LinkedListDeque 和 ArrayDeque 应该判断为相同。因此，这个比较需要使用一般的接口方法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

@Override  
public boolean equals(Object o) {  
    if (this == o) {  
        return true;  
    }  
    if (o == null) {  
        return false;  
    }  
    if (!(o instanceof Deque<?>)) {  
        return false;  
    }  
  
    Deque<?> other = (Deque<?>) o;  
    if (size != other.size()) {  
        return false;  
    }  
    for (int i = 0; i < size; i++) {  
        if (!get(i).equals(other.get(i))) {  
            return false;  
        }  
    }  
    return true;  
}

GuitarHero

使用 Karplus-Strong 算法来实现。分为三步：

  1. 将 Deque 中每个元素都换成随机噪音，介于 -0.5 到 0.5 的 double 值。
  2. 移除第一个元素，并与接下来第二个元素取平均，乘以衰减因素 0.996，加入 Deque 的最后。
  3. 播放第二步去除的元素。然后重复第二步。

具体的代码相当容易，只要跟着 TODO 一步步写就行。

© 2024 Ovid的博客
使用 Hugo 构建
主题 Stack 由 Jimmy 设计