CS61B Data Structure Notes

Moksha

IC设计｜系统软件｜计算机体系结构

Java Syntax

Java除了8种基本类型(按值传递) byte , short , int , long , float , double , boolean , char 之外，其他一切，包括 数组 ，不是原始类型，而是 Reference Type (引用类型)，说白了就是指针。
声明任何引用类型(Reference Type)的变量，java会分配一个64-bit的box，这64-bit种不包含数据(如对象的属性等)，而是包含该数据的在内存中的地址。

Walrus a = new Walrus(1000, 8.3);
Walrus b;             
b = a;                // 将a在内存中的地址赋给b，使a和b指向同一内容。

嵌套类(Nested Class)。经验法则：如果不使用外部类的任何实例成员，则将嵌套类定义为 static 。因为被声明为static的嵌套类不能访问外部类的实例成员, 同时也节约了内存。
文件名必须和类名相同，每个文件必须只包含一个外部类。
泛型(Generic Type)仅适用于引用类型，尖括号内不能放入原始类型比如:int, double, 但是可以放入原始类型的引用版本，如: Integer , Double , Character , Boolean , Long , Short , Byte , Float 。

public class DLList<genericTypeName> {
    public class IntNode {
        public IntNode prev;
        public genericTypeName item;
        public IntNode next;
        public IntNode(IntNode _prev, genericTypeName _item, IntNode _next) {
            this.prev = _prev;
            this.item = _item;
            this.next = _next;
    public DLList(genericTypeName x) {
        prev = new IntNode(null, x, null);
    public static void main(String args[]) {
        DDList<String> d1 = new DLList<>("hello");
        DDList<Integer> d2 = new DDList<>(5);
        // 上一行代码和这行是相等的实例化尖括号声明类型可以省略
        DDList<Integer> d2 = new DDList<Integer>(5);

创建数组的三种方法:

x = new int[3];
y = new int[]{1, 2, 3, 4, 5};
int[] z = {9, 10, 11, 12, 13};   // 类似第二种方法，但只能和声明结合时使用

java数组仅在运行时执行边界检查。System.arraycopy()方法非常方便使用。
[] 允许我们在运行时指定想要的索引，而类中指定字段就不行。
创建泛型对象数组的方法(虽然java不允许，而且编译器会报错)

Glorp[] items = (Glorp []) new Object[8];

判断两个字符串是否相等使用 equals 而不是 == 的原因是， == 比较的是地址，而 equals 比较的是存储单元中的值。
java不允许使用 > 运算符在字符串之间比较，而是用 str1.compareTo(str2) 来进行比较，如果相等则返回0，str1 > str2则返回一个正数。
org.junit 库提供了很多方法来简化测试的编写, Junit官方文档 ; import static org.junit.Assert.* import org.junit.Test 之后，就可以省略掉 org.junit.Assert 前缀，进而直接使用 assertEquals 方法; 需要在每个方法前加上 @org.junit.Test 来替代 @Test , IDEA中Junit可视化测试是根据 @Test 标签在运行时自动检测的。
获取String的第i个字符的方法 str.charAt(i) 。
Java中字符使用单引号，字符串则使用双引号。
public class AList<Item> implements List61B<Item>{...} , implements, 接口继承，子类可以使用父类的方法，也可以覆盖父类的方法; AList 将保证拥有并定义 List61B 接口中指定的所有属性和方法; AList is a List61B , 他们之间是 is a 关系; 在 AList 中实现 List61B 的方法时， @Override 是必要的, 这是为了提醒编译器通知你可能发生的错误。
List61B<Item> lst = new AList<>(); 完成多态。
StdRandom 库生成随机数文档。
assertEquals(message, expected, actual) , JUnit测试失败时输出有用信息, 将预期值和实际值作为 message 。
Difference between implement and extends 。
实现继承 extends (is a关系, 继承...)关键字，子类继承父类的所有成员包括(构造函数不被继承)：

所有实例和静态变量

所有方法

所有嵌套类
在子类的构造函数中需要调用父类的构造函数，在子类的构造函数中使用 super() 关键字。原因: 比如 TA extends Human (TA is a Human), 先需要创建一个人，接着创建TA才有意义; 当然如果我们不这样做，Java会自动调用super类的 无参构造函数 。
Java中的每个类都是 Object Class 或者是它的后代(descendant), 类没有 显示地 extends仍然会 隐式地 extends Object Class 。
Java可以用 interface (接口)类型来充当函数指针。
通过接口继承来定义一个比较接口 CompareTo ，解决 Object 对象之间不能比较的问题。
抽象数据类型(Abstract Data Type), 简称ADT, 指的是一种数据类型，只带有行为，没有任何具体的方式来实现展示这些行为(抽象的); java.util 库中包含三个最重要的ADT:

白色框是接口, 蓝色框是具体的类

List , 比较流行的实现是(ArrayList) List<String> lst = new ArrayList<String>();

Set , 比较流行的实现是(HashSet) Set<String> ss = new HashSet<>();

Map 。比较流行的实现是(HashMap) Map<String, Integer> counts = new HashMap<String, Integer>();
接口(interface)的特性:

所有方法都必须是 public

所有变量都必须是 public static final ， final 类似于cpp的 const

无法实例化

默认情况 下，所有方法都是 abstract 的，除非指定为 defualt

每个类可以 Implements 多个 Interface 。
抽象类(Abstract类似cpp), 介于 interface 和 concrete class 之间。

方法可以是 public 也可以是 private ，或者 protected

可以有任何类型的变量

无法实例化

默认情况 下，方法是 concrete 的，除非指定为 abstract

每个类只能 Implements 一个 Abstract

public




    
 abstract class GraphicObject {
    public int x, y;
    public void meveTo(int newX, int newY) { ... }
    public abstract void draw();
    public abstract void resize();

wrapper class(包装类)，如int的包装类是Integer。Java可以在原始类型和包装类型(也成为引用类型)之间进行 隐式转换 。两个方向的转换成为装箱(box)(int->Integer), 拆箱(unbox)(Integer->int); 注意:

数组永远不会自动装箱或自动拆箱

自动装箱和拆箱会对性能产生影响

包装类型比原始类型使用更多的内存, 关于内存使用信息的拓展此链接或链接
Java同如CPP这样的语言，会自动隐式向上类型转换，若占用字节较大的类型转换为较小的类型则需要手动去转换。
不可变数据类型，如String或加上 final 关键字修饰的基本类型。

优点：防止错误并使调试更容易

缺点：需要创建一个新对象才能更改属性。
在Java中异常是对象，抛出异常的格式 throw new IllegalArgumentException("can't add null");
在Java中可以定义一个迭代器接口, 如ADT需使用则 extend 或者Implement这个接口，需要有next, hasNext方法。

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

Java中创建 Package (类似于cpp的namespace), 存储package的文件夹名称应该和包一致

package ug.joshh.animal;
public class Dog {
    private String name;
    private String breed;

JAR 文件就像zip文件一样，完全可以将文件解压缩并转换回.java文件。
public、protected、package-private、private的访问控制权限:

Image
Java中操作文件，查看 File javadocs 和使用 Utils.java 类，该类具有许多有用的文件操作辅助函数。
序列化(seralize), 将java 对象序列化为文件(持久性)，通过implements Serializable 接口
使用 Utils 类(proj Gitlet提供的子集)中的辅助函数来序列化和反序列化

Model m;
File outFile = new File(saveFileName);
// Serializing the Model object
writeObject(outFile, m);
// ----------------------------------
Model m;
File inFile = new File(saveFileName);
// Deserializing the Model object
m = readObject(inFile, Model.class);

可变参数形式 static void writeContents(File file, Object... contents)
常用ADT的操作

Stacks

push(int x) : 将x放在栈顶

int pop() : 获取栈顶元素

Lists

add(int i) : 添加一个元素

int get(int i) : 获取索引i处的元素

Sets

add(int i) : 添加一个元素

contains(int i) : 返回集合是否包含值得布尔值

Maps

put(K key, V value) : 将键值放入哈希表中

V get(K key) : 获取key对应得值
Java泛型 bounded type parameter

IDEA Skill

左键点击行号的右侧打断点
条件断点，在断点的基础上右键增加条件。进入Debug模式后，拖动console到右侧可以同时显示console和Debugger。
比较好用的Plugin: Java visualizer , IdeaVim , IDEA自带的 Sheck Style 。
Step into vs. Step over , Step into进入函数，而Step over则不进入函数直接向下执行。 Step out 跳出函数。
Resuming 类似于continue，跳到条件断点的下一个条件，在step over的左下侧向右的绿色箭头
Destructive vs. Non-Destructive , 非破坏性调用函数没有修改传入的数据结构，相反破坏性则修改了传入的数据结构。
创建JAR文件

File -> Project Structure -> Artifacts -> JAR -> "From modules with dependencies
IDEA将生成的 .class 文件存储在 out 或 target 文件夹中。

Algorithm

1.(Big-Theta \Theta 来代替order of growth(增长级))

- Only consider the worst case.
- Pick a representative operation (aka: cost model)
- Ignore lower order terms
- Ignore multiplicative constants.

2.并查集

属性和方法

- Connect()
- isConnect()
- find()
- parent[]

优化

路径压缩
lg^*n := \begin{cases}0, & \text {if n $\leq$ 1}\\ 1+lg^*(lgn), & \text{if n $>$ 1} \end{cases}

int find(int p) { while (p != id[p]) { id[p] = id[id[p]]; // 路径压缩，使得下次查找更快 p = id[p]; return p;

按秩合并

规则：将 height 较小的Set连接到 height 较大的Set

3.渐近线分析

并不是所有两层for循环的复杂度都为 \Theta(N^2) , 比如下面这个for loop的复杂度为 C(N) = 1 + 2 + 4 + ... + N = 2N-1 (如何N为2的幂)

public static void printParty(int N) {
    for (int i = 1; i <= N; i = i * 2) {
        for (int j = 0; j < i; j += 1) {
            System.out.println("hello");   
            int ZUG = 1 + 1;

递归, 复杂度为 C(N) = 1 + 2 + 4 + 8 + ... + 2^{N-1} = 2(2^{N-1})-1 = 2^N-1 = \Theta(N)

public static int f3(int n) {
    if (n <= 1) 
        return 1;
    return f3(n-1) + f3(n-1);