cs61b-sp21 笔记

作者 ： Kumikosoli

package(包)

• 把多个类封装在一个包中，用于完成共同的功能。

意义

如org.junit.Assert.assertArrayEquals中，org.junit是包,Assert是类名，assertArrayEquals 是方法名

用法

在每个类文件开头加上 package package_name 表示这个类在包中

引用

• java中，除八种基本类型外，其他类型都是作为引用被初始化,引用变量存储的是指向结构的地址

使用junit进行test

• 使用org.junit.Assert.assertArrayEquals(expected,input)验证输入与期望的数组是否相等

Debug工具

• conditional breakpoint:条件断点，当且仅当在该断点处满足条件为True时才会停止
• resume:恢复程序，使程序继续运行直到回到断点

files

通过File constructor,可以在Java中生成file对象File f = new File("dummy.txt");这并不会实际创造文件dummy.txt。要生成时可以使用f.createNewFile();。可以用f.exists()检测文件是否存在。 file对象也可以代表文件目录。要生成该目录时使用d.mkdir()

链表Linklist

• nested class：嵌套类，在类中定义一个类。在list类中定义node类，把初始化的list作为头节点。

• 为链表提供头节点可简化添加元素时的代码。

• 对于双向链表，可添加头尾两个哨兵节点或者将链表设置为环，简化删除、添加节点等代码。

• 类中可将成员类型推迟到初始化或声明中决定。具体代码

  1 2 3 4 5 6 7 8 9 10

  public class Sllist<BleepBLORP>{ private Node sentinel private int size public class Node{ public BleepBlorp item; public Node next; ………… } } …………

  使用时在初始化对象时语法 Sllist<String> lt1 = new Sllist<>("Hi!") <>中的泛型要使用引用类型。 对应关系：

  基本类型	引用
  double	Double
  int	Integer
  char	Character
  boolean	Boolean
  long	Long

类继承

implement

形如public class RotatingSLList<Item> implement SLList<Item>的类定义，用于表示类继承，子类拥有父类中定义的所有方法（一般要在子类中写出继承的接口的实现）。也可以用父类中已定义好的方法。

• 哪怕父类中已经定义了方法，也可以在子类中重写。在方法上方添加 @override 显式表示这是继承自父类的方法并给出定义。

extends

形如public class RotatingSLList<Item> extends SLList<Item>的类定义，表示子类继承了父类的所有非private成员（属性、方法、嵌套类）,可以直接使用，并且可以在子类中添加新的方法等。

• extends创建的子类，在调用构造函数时首先调用父类的构造函数，然后再回到子类新的构造函数中。
• 可以显式调用父类构造函数super()，若不显式调用，编译器会自动完成。

interface

与类相似，定义类似public interface Mycontrast{……} ，但其中只能包含子类需要实现的方法，并在子类中给出定义。 子类通过implement继承interface，一个子类可以继承多个interface。

高阶函数

java没有函数指针，无法直接传递函数。想要使用类似函数指针的效果，可以通过interface和类继承，让子类implement同一个接口override接口的方法，并将子类传入函数中充当函数指针作用。例如

1
2
3

public static int do_twice(IntUnaryFunction f, int x) {
    return f.apply(f.apply(x));
}

java库 java.util

内含多种数据结构

List interface

具有子类Arraylist

hashset

java的set interface 的子类

Sets

存储不重复元素的无序集合。

方法

• add() 加入元素
• contain() 检测是否包含元素
• size() 返回集合大小

异常处理

throw 关键字

• 使用格式throw new ExceptionObject(parameter1, ...)
• 例子：

1
2
3

if (x == null) {
        throw new IllegalArgumentException("can't add null");
}

new 后的是异常类；括号中的是对异常的解释。

Iteration

1
2
3

for (String city : s) {
    System.out.println(city);
}

这是对for循环的强化使用。其具体为：

1
2
3
4
5
6
7

Set<String> s = new HashSet<>();
...
Iterator<String> seer = s.iterator();
while (seer.hasNext()) {
    String city = seer.next();
    ...
}

因此，若想在自己定义的类中使用迭代器，则需要让此类extend Iterable<T>``iteratior()方法返回一个iterator对象。该对象应在类中定义私有嵌套类（定义hasNext方法和next方法），此时就可以使用第二个的具体形式。 如果想要使用简洁的for(T city : s)形式，则需要给嵌套的Iterator类加上implement Iterator()

Object

所有类都隐式继承了Object类，拥有其定义的方法。常用的为String tostring()和boolean equals(Object obj)。一般需要在自己定义的类中override这些方法

toString

在发生类到String的类型转换时会隐性调用。默认实现是返回类存储的地址。

• 由于使用 String a=a+“qqq"时会产生新的字符串，时间复杂度为$O(n)$，Java新增了StringBuilder类使拼接字符串的时间复杂度为 $ O(1) $。

使用StringBuilder类凭借字符串代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

equals

默认对比两个对象地址是否相同（等价于==），返回True/False. 通过重写可以比较对象不同的属性。

Data Structure 部分

时间复杂度

$Θ(f(n))$

代表时间复杂度与 $f(n)$ 同阶

$O(f(n))$

代表时间复杂度与 $f(n)$ 同阶或更低阶

抽象数据类型(ADT)

仅有操作而不由具体实现定义的数据类型。如Deque是一个ADT，可以由数组或者链表实现。不同的实现对应的操作是相同的。

常见ADT

Stacks

实现后进先出的数据类型

操作

• push(int x)
• int pop()

Lists

有序列表

操作

• add(int i)
• int get(int i)

Sets

无序无重复元素集合

操作

• add(int i)
• contains(int i)

Maps

键值对集合

操作

• put(k key,V value)
• V get(K key)

不相交集(disjoint set)

用于在一个无重复元素集合中跟踪两个元素是否在同一个集合中，以及合并两个元素所在的集合。

基本功能

• connect(x, y) 合并x y 所在的集合
• isConnected(x, y)当x,y在同一个集合中时，返回true，否则返回false

实现方法

• 使用n个元素数组arr存储元素0 ~ n-1的父元素，当元素没有父元素时，这个元素为根，数组下标对应的值为-k(k为根对应的集合下元素数量).

• connect(x, y):对x,y向上遍历，找到x和y分别对应的根，并将根链接。

• isConnected(x, y)：对x，y向上遍历，查看x和y对应的根节点是否相同

• 加权快速联合:每次调用connect(x, y)时，把集合元素较少的根的父元素改为另一个根，并修改另一个根存储的集合元素数量.

• 路径压缩：每次调用isConnected(x, y)时，将遍历到的节点的父元素全部变为根节点。

使用加权快速联合和路径压缩下的操作时间复杂度

二叉搜索树（Binary Search Trees）

包含节点（存储值与指向左右子节点的边）

满足性质

1. 左子树所有键值小于其根节点键值
2. 右子树所有键值大于其根节点键值
3. 左、右子树都是二叉搜索树

定义

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

private class BST<Key> {
    private Key key;
    private BST left;
    private BST right;

    public BST(Key key, BST left, BST Right) {
        this.key = key;
        this.left = left;
        this.right = right;
    }

    public BST(Key key) {
        this.key = key;
    }
}

操作

• static BST find(BST T, Key sk)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

static BST find(BST T, Key sk) {
   if (T == null)
      return null;
   if (sk.equals(T.key))
      return T;
   else if (sk ≺ T.key)
      return find(T.left, sk);
   else
      return find(T.right, sk);
}

• static BST insert(BST T, Key ik)

1
2
3
4
5
6
7
8
9

static BST insert(BST T, Key ik) {
  if (T == null)
    return new BST(ik);
  if (ik ≺ T.key)
    T.left = insert(T.left, ik);
  else if (ik ≻ T.key)
    T.right = insert(T.right, ik);
  return T;
}

• static void Delete(key ik) 删除一个节点需要考虑节点孩子的情况。

1. 没有孩子节点：直接删除节点

2. 一个孩子节点：让父节点指向被删除节点的边指向被删除节点的孩子节点

3. 两个孩子节点：找到左子树最大/右子树最小的节点，交换其与被删除节点的值，然后删除交换后的节点。

时间复杂度

各个操作，平均时间复杂度、最好时间复杂度为$O(log n)$,最坏情况时间复杂度为$O(n)$.

树的遍历

1. 层序遍历 (Level order traversal) 从树的根开始从上到下，从左到右遍历。方法：通过队列把当前节点的子节点加入队列中实现。
2. 深度优先遍历（DFS）
   1. 前序遍历 (pre-order) 先访问左子树，再处理当前节点，再处理右子树
   2. 中序遍历 (in-order) 先处理当前节点，再访问左子树，再处理右子树
   3. 后序遍历 (post-order) 先访问左子树，再处理右子树，再处理当前节点

B-树

一种平衡树。每个节点可以拥有m个元素，m+1个儿子节点。m=2时称为2-3树；m=3时称为2-3-4树。第k个子节点中的元素大于第k-1个元素，小于第k个元素。

操作

• find() 类似二叉搜索树。
• insert() 把新元素插入到已有节点中。若插入后节点元素多于限制数，（对于2-3-4树）把第二个元素作为该节点
• delete()

时间复杂度

查找、插入和删除操作的时间复杂度为稳定$O(log n)$量级。

红黑树

• 前置知识：通过旋转保持树的平衡。

1. 左旋：将某个节点的右子树提升为新的根节点，并将原根节点变为其左子树。原根节点的右指针指向右孩子的左子树。
2. 右旋：将某个节点的左子树提升为新的根节点，并将原根节点变为其右子树。原根节点的左指针指向左孩子的右子树。

性质(左倾红黑树)

1. 与2-3树一一对应。
2. 没有节点拥有2个红色边
3. 没有红色向右的边
4. 每条从树叶到根的路径中，黑色边的数量一致。
5. 高度不高于对应2-3树的两倍

操作

• find() 类似二叉搜索树。
• insert() 把新元素插入到已有节点中。

1. 插入时使用一条红色边。
2. 当对应的2-3树出现“节点有第三个元素”时，左旋对应节点修复违反规则的链接。
3. 当出现两个连续的黑色边时，右旋修复。
4. 当出现一个节点连着两条左倾红色边时，让该节点连着的所有边颜色调转。 伪代码实现：

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

private Node put(Node h, Key key, Value val) {
    if (h == null) { return new Node(key, val, RED); }

    int cmp = key.compareTo(h.key);
    if (cmp < 0)      { h.left  = put(h.left,  key, val); }
    else if (cmp > 0) { h.right = put(h.right, key, val); }
    else              { h.val   = val;                    }

    if (isRed(h.right) && !isRed(h.left))      { h = rotateLeft(h);  }
    if (isRed(h.left)  &&  isRed(h.left.left)) { h = rotateRight(h); }
    if (isRed(h.left)  &&  isRed(h.right))     { flipColors(h);      } 

    return h;
}

• delete()

时间复杂度

查找、插入和删除操作的时间复杂度为稳定$O(log n)$量级。(实现易于B-树，实际中更常用)

哈希表

把输入的元素通过哈希函数转化为整型数字后，将该数字作为数组下标存储到数组中。可以判断表中是否存在某元素。

存储的数据不需要具有可比较性

操作

1. add() 把元素加入到哈希表中。
2. contain() 判断元素是否在哈希表中。

字符串to整型 存储

若存在n个可用字符，我们可以对这n个字符编号为1，2……n,t为字符编号。对于长度为m的字符串，我们可以使用公式 $N = \sum_{k=1}^m tn^{k-1}$ 计算字符对应的整形值，保证每个字符对应的整形值相同。

由于整型存在最大存储值上限2147483647，无法用整形表示所有字符串。

因此，不同字符串可能拥有相同的哈希值，导致哈希冲突。

Hash Codes

可以把计算得到的整型数字取余数减小哈希表大小。（余数为质数时更好避免哈希冲突） java中object存在.hashcode()方法，为对象计算哈希值。我们同样也可以重写这个函数。

性质

1. 必须为整型
2. 对同一个对象多次调用必须返回相同值
3. 两个对象只有当哈希值相同时才能被认为.equals()

哈希冲突

链地址法

哈希表中每个元素都是一个链表，把哈希值相同的元素都加入到该链表中。（由于哈希表不允许重复元素，需要先判断元素是否存在于表中）。

时间复杂度（链地址法）

Q:元素链表中的元素个数

1. add() $Θ(Q)$ 使用动态数组后变为$Θ(1)$
2. contain() $Θ(Q)$ 使用动态数组后变为$Θ(1)$

时间复杂度处理

为了防止链表过长降低时间复杂度

1. 改进哈希函数使元素尽量均匀分布
2. 动态增大数组大小（当 $M = 存储元素数/数组长度$ ） ,M大于一定值时创建大小为2倍的数组，并把旧的哈希表中的数据重新加入新的哈希表（可能导致存储位置的改变）。 改变数组大小的时间复杂度 $Θ(N)$。

堆与优先队列

类似于二叉搜索树，但是每次只能获取或者移除堆中最大/最小的元素。 下面以最小堆为例子。

性质

1. 完全性： 只有最底层的节点有元素缺失，所有元素都尽可能存在于左边。
2. 最小堆性质： 所有节点值都不大于其父节点

操作

1. public void add(Item x) 在优先队列中加入元素
2. public Item getSmallest() 获取最小元素
3. `public Item getSmallest() 移除最小元素
4. public int size() 返回优先队列大小

实现方法

使用数组keys[]存储优先队列。从下标1开始按序存储元素。可以得到leftChild(k)=k∗2 rightChild(k)=k∗2+1 parent(k)=k/2. 数组需要动态改变大小。

1. public void add(Item x) 在优先队列中加入元素到堆的最后，然后让元素上浮直到满足堆性质。
2. public Item getSmallest() 返回堆的根节点元素
3. public Item removeSmallest() 把根节点元素的值变为堆的最后一个元素，删除堆的最后一个元素。把根节点元素下沉到满足性质的位置。

辅助函数public void swim(int k)

1
2
3
4
5
6
7

// 使k节点从下到上移动，满足堆性质
public void swim(int k) {
    if (keys[parent(k)] ≻ keys[k]) {
       swap(k, parent(k));
       swim(parent(k));              
    }
}

时间复杂度

图(Graphs)

图：包括一系列节点，一系列连接两个节点的边。

简单图(Simple Graphs)：任意两条边连接的节点不完全相同。一条边不能连接一个节点到它本身。

无向图(undirected graphs)：边没有方向

有向图(directed graphs)：边有方向

无环图(acyclic graphs): 图中没有环。即不存在能从一个节点出发，最终到达同一个节点的路径。

有环图(cyclic graphs)：图中存在环。

图论问题

连通性问题

判断是否存在链接节点s,t的路径。使用深度优先遍历（DFS）。 用一个数组mark遍历过的节点。mark下当前节点后进入相邻的下一个节点。

1
2
3
4
5
6
7
8

if (s == t):
    return true;

for child in unmarked_neighbors(s):
    if isconnected(child, t):
        return true;

return false;