CS61B 学习笔记 - Java Basic

Posted 2024-07-12 Updated 2024-07- 30

By Administrator

28~36 min read

2. Defining and Using Classes

类方法 vs. 实例方法

Class methods, a.k.a. static methods
Instance methods, a.k.a. non-static methods

实例方法只能由类特定的实例执行。静态方法是类本身采用的操作

和 public 没什么关系，不要混淆

静态变量

尽管 Java 允许使用实例来访问类变量，但这种方式并不被认可

While Java technically allows you to access a static variable using an instance name, it is bad style, confusing, and in my opinion an error by the Java designers.

Using Libraries

One of the most important skills as a programmer is knowing how to find and use existing libraries.

这门课似乎很鼓励使用现成的库（虽然只能用他们给的）

In this course, you're welcome to do this, with the following caveats:
Do not use libraries that we do not provide.
Cite your sources.
Do not search for solutions for specific homework or project problems.

3. References, Recursion, and Lists

没有指针

The exact memory address is below the level of abstraction accessible to us in Java. This is unlike languages like C where you can ask the language for the exact address of a piece of data

就像你不能直接控制自己的心跳一样。Java 认为你不应该费精力关心这个

GRoE

Java 中，任意一个使用 = 的 Assginment 都是对 bits 的复制

Reference Types, Instantiation

8 primitive types: byte, short, int, long, float, double, boolean, char.

其他的都叫 reference types. （String，你自己定义的类...）

new 所做的是，在某处存储这个实例，然后返回这个存储的地址

像 int []x，x = new int[]{1, 1, 4, 5, 1, 4} 类似

the new keyword creates 6 boxes of 32 bits each and returns the address of the overall object for assignment to x.

所有新建的类都是 Object 的子类

4-8. List

尽量不要为特殊情况加一个 if ，因为你会发现特殊情况会越来越多，然后你的代码会从各种意义上越来越难看。我们需要一个"harmony story"，即一个更好的结构

你需要在每完成一个实现后进行充分地测试，未测试的代码永远是错的，除非你有点享受 Debug 时毫无头绪的感觉

IntList: 裸露递归的链表
SLLists: 封装后的链表
DLLists: 双向链表。你需要一个或两个哨兵（sentinel）节点
ArrayList: 其实是一个循环数组，超出既定大小后会扩容至自身两倍长度，利用率不足时则会缩容。

9. Interface and Implementation Inheritance

Interface Inheritance

上几节课我们实现了 SLList, DLList, AList 几种 List，现在我们有一个函数 longest，通过调用这些 List 共有的方法，找到 List 中长度最长的字符串。但问题是，我们好像需要为每一种 List 都单独写一份一模一样的 longest，只有传参不同。

public static String longest(SLList<String> list){..}
public static String longest(DLList<String> list){..}
public static String longest(AList<String> list){..}
public static String longest(QList<String> list)   // who are you?
......

好吧，这看起来有点蠢，而且 Copy-paste 是老师直言”恶心“的 Style。假如你复制了五份这样的函数然后发现实现有 bug......好吧，这是五等分的 Copy-paste bug-fixing .ver。但假如你复制了上百份......还是重开吧

解决方案是，我们可以弄一个 Interface，将上面的几个 List 统一成一个 List61B

public interface List61B<Item> {
    public void addFirst(Item x);
    public void add Last(Item y);
  ......
}

然后它的子类需要加上一个 implements List61b<item>

public class AList<Item> implements List61B<Item>{...}

子类必须包含 interface 里面所有的方法，不然编译不过。我们可以在子类中的方法实现前面加上一个 @Override 标签。其实可以不加，加了...可以防止你抄错？

在 interface 中我们可以使用 default 关键字，这样子类可以无需重写

default public void print() {
    for (int i = 0; i < size(); i += 1) {
        System.out.print(get(i) + " ");
    }
    System.out.println();
}

若是默认的方法并不合适（比如太慢了），子类可以重写此方法

@Override
public void print() {
    for (Node p = sentinel.next; p != null; p = p.next) {
        System.out.print(p.item + " ");
    }
}

然后我们就可以写出可以接受多种 List 的函数了

public static void peek(List61B<String> list) {
    System.out.println(list.getLast());
}

Static & dynamic type

List61B<String> lst = new SLList<String>

根据声明，lst 的类型是 List61B ，这被称为静态类型

但是 lst 所指向的对象的类型是 SLList ，称为动态类型

Java 中的每个变量都有一个“编译时类型”，又称“静态类型”。这是声明时指定的类型。永不改变
变量还有“运行时类型”，又称“动态类型”。这是实例化时指定的类型（例如，使用 new 时）。等于所指向对象的类型。

Overloaded methods

在 Java 运行被重写（Override）的方法时，它会在其动态类型里搜索适当的方法并运行它，但这对重载方法（Overloaded methods）不起作用，也就是有两个名字一模一样但参数列表不同的方法

比如同一类中有如下两个方法：

public static void peek(List61B<String> list) {
    System.out.println(list.getLast());
}
public static void peek(SLList<String> list) {
    System.out.println(list.getFirst());
}

那这是会更据传入参数的静态变量来决定调用哪一个

10. Extends, Casting, Higher Order Functions

Extends

extends 关键字会继承父类的所有细节（实例，静态变量，所有的方法和嵌套类，除了构造函数）。

extends 只用于 is 的关系，而不是 has（想想 List 和 Set）

super

假如我为 SLList 做了一个子类 VengefulSLList，在调用 removeLast 时会收集被 remove 的元素。显然，这时候我们需要重写这个方法

好吧，我们就先从父类 Copy-paste 吧，然后你会发现父类用 private 声明的变量，子类无法访问

所以此时我们可以先用 super 关键字调用父类的函数，再进行追加的操作

@Override
public Item removeLast() {
    Item oldBack = super.removeLast(); 
    deletedItems.addLast(oldBack);
    return oldBack;
}

在子类的构造函数里面，在首行加上语句 super() 调用父类的构造函数，虽然不写 Java 也会隐式地调用。

但如果构造函数要传参的话，就需要把 super(args) 写出来了

Encapsulation

我们的敌人不是分号，而是大型程序的复杂性。构建的方法主要有两点：

抽象：构建抽象层，围绕对象设计程序，让对象决定做什么事情
隐藏：隐藏用户不需要知道的信息

Complier

Java 编译器十分保守，在检查编译时哪怕动态类型没有问题，但静态类型不符，编译器会拒绝编译。解决的方法是加上 (Type) 进行转换

Higher order function

老版本（Java 7）以前搞得很麻烦，比如你要给 do_twice 传一个函数：

public interface IntUnaryFunction {
    int apply(int x);
}

public class TenX implements IntUnaryFunction {
    public int apply(int x) {
           return 10 * x;
    }
}

public class HoFDemo {
    public static int do_twice(IntUnaryFunction f, int x) {
           return f.apply(f.apply(x));
    }
    
    public static void main(String[] args) {
           System.out.println(do_twice(new TenX(), 2));
    }
}

这点 Python 着实简单不少

def tenX(x):
   return 10*x
 
def do_twice(f, x):
   return f(f(x))
 
print(do_twice(tenX, 2))

11. Subtype Polymorphism, Comparators

Comparable

Comparable 是一个已由 Java 定义的接口，并被无数的库使用。

public interface Compareable<T> {
    public int compareTo(T obj) ;
}

我们可以重写我们的类以实现 Compareable 接口，比如

public class Dog implements Comparable<Dog> {
    ...
    public int compareTo(Dog uddaDog) {
        return this.size - uddaDog.size;
    }
}

Comparator

public interface Comparator<T> {
    int compare(T o1, T o2);
}

同样，我们也可以写一个比较器

import java.util.Comparator;

public class Dog implements Comparable<Dog> {
    ...
    public int compareTo(Dog uddaDog) {
        return this.size - uddaDog.size;
    }

    private class NameComparator implements Comparator<Dog> {
        public int compare(Dog a, Dog b) {
            return a.name.compareTo(b.name);
        }
    }

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

然后我们就可以以此法创建一个比较器对象

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

就如同前文提及的接口一样，我们就可以向函数传递比较器了

12. Iterators, Object Methods

Exceptions

请勤用，我们需要保证我们的实现是在正确地运行的

throw new IllegalArgumentException(String info);

Iterator

public interface Iterator<T> {
    boolean hasNext();
    T next();
}

我们可以参照以下代码实现一个迭代器，需要实现 next() 与 hasNext（）

另外，在 hasNext() 返回 false 后继续调用 next() 是 UB

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;
    }
}

若是我们期望使一个类是可迭代的，那我们就需要实现此类的 Iterable 接口和 iterator 方法，此方法返回一个这个类的迭代器对象。我们刚刚展示的迭代器类将嵌在这个类里面

public class ArraySet<T> implements Iterable<T> {
    private T[] items;
    private int size; // the next item to be added will be at position size

   public ArraySet() {
        items = (T[]) new Object[100];
        size = 0;
   }

    /** returns an iterator (a.k.a. seer) into ME */
    public Iterator<T> iterator() {
        return new ArraySetIterator();
    }

    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;
        }
    }

StringBuilder

在 Java 中使用字符串连接时（returnString += keys[i];），实际上是在创建一个全新的字符串，然后进行复制。可以想象这种语句重复 1000 遍是怎样的低效

为了解决这个问题，Java 有一个特殊的类，称为StringBuilder。它创建一个可变的字符串对象，我们可以继续向同一个字符串对象添加内容，而不必每次都创建一个新的字符串对象。

public String toString() {
        StringBuilder returnSB = new StringBuilder("{");
        for (int i = 0; i < size - 1; i += 1) {
            returnSB.append(items[i].toString());
            returnSB.append(", ");
        }
        returnSB.append(items[size - 1]);
        returnSB.append("}");
        return returnSB.toString();
    }

Instanceof

java 的一个关键字，用于测试左边的对象是否是右边类或接口的实例，返回 true/false

在判断类型的同时还可以有转化功能

public boolean equals(Object o) {
  if (o instanceof Dog d) {         // 相当于又用了 Dog d = (Dog) o;
    return this.size == d.size;
  }
}

Courses, Notes

CS61B

License: CC BY 4.0