lec6 DLLists, Arrays

DLList

在lec5的 SLList中，如果想要实现获取、增加最后一个节点，需要耗费$O(n)$的时间。如何改进这一点呢？

可以考虑引入一个指针，指向最后一个节点。这样，就可以很方便地获取和增加最后一个节点。然而，如果要删除最后一个节点，这样的方法还需要找到倒数第二个节点，比较耗费时间。

因此，引入 DLList，也就是双向链表。这样，就可以方便地删除最后一个节点。

然而，如果按照原先只有一个哨兵，那么，有时候 last 会指向真正的最后节点，有时候会指向第一个哨兵，这样会引入许多条件判断，很不方便。

有两个解决办法：一、引入首尾两个哨兵。二、循环链表。

泛型

可以在类名定义后加上 <pineapple>，尖括号内是任意的名字。后续，可以用这个名字来指代类型。

数组

之后介绍了 java 的数组。因为和 C 语言的很像，所以没怎么记笔记。

guide A level 1

部分内容引用自TomLazy的CSDN博客。

紫胡子和他的奴才 Turquoisenail 正在10海里航行。为了更好地航行，他们希望能够创建一张地图。他们设法创建了他们的方形地图，但 Turquoisenail 被绊倒了，把它掉在了碎纸机里。他们设法将碎掉的图像存储到1D 阵列中，但他们需要将其拼成一张 NxN 地图。你很幸运，因为每一块上都写有经度和纬度。编写一个简短的程序来帮助把这些碎片重新组合起来。

问题示意图

在表格的左上角，0是经度，20是纬度，在这个问题上，你只能使用数组。

问题一

对于这个问题的第一部分，制作一个存储经度和纬度的 Piece 类。

1
2
3
4
5
6
7
8
9


public class Piece {  
    public int longitude;  
    public int latitude;  
  
    public Piece(int x, int y) {  
        longitude = x;  
        latitude = y;  
    }
}

问题二

这个问题的下一部分是把给定的一维 Piece 数组中的 Piece，(Piece 没有特定的顺序)，放到一个二维数组中，每一行都充满了具有相同纬度的 Piece。

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


public Piece[][] groupByLat(Piece[] p) {  
    int width = (int) Math.sqrt(p.length);  
    Piece[][] latGroup = new Piece[width][width];  
    for (int i = 0; i < p.length; i++) {  
        for (int j = 0; j < latGroup.length; j++) {  
            if (latGroup[j][0] == null) {  
                latGroup[j][0] = p[i];  
                break;  
            }  
            else if (latGroup[j][0].latitude == p[i].latitude) {  
                int counter;  
                for (counter = 0; counter < width; counter++) {  
                    if (latGroup[j][counter] == null) {  
                        break;  
                    }  
                }  
                latGroup[j][counter] = p[i];  
                break;  
            }  
        }  
    }  
    return latGroup;  
}

首先，需要计算二维数组的大小。因此使用 Math.sqrt() 函数并转换为 int 类型。然后创建二维数组。

一开始还没想出来怎么填空，主要是没有搞清楚 i、j 和 counter 的含义。实际上，这里的 i 遍历了 Piece[] p，而 j 则是便利了二维数组的行（第一个索引）。

每次对于一个碎片 p[i]，都首先看能否放在一个空的第 j 行当中，也就是 latGroup[j][0] == null。如果为真，直接把当前的碎片放入即可。否则，就看当前第 j 行元素的纬度是否和第 i 个碎片的纬度相同。如果不同，就跳过本次循环。如果相同，就利用 counter 遍历这一行，将当前元素放在第一个非空的位置。

经过以上操作，就通过纬度，将原先的一维数组转换为每一行家具有相同纬度的二维数组。

lec7 ALists, Resizing, vs. SLists

相比于链表，数组更方便访问其中的某一个元素。只需要记下数组的大小，就可以很方便地实现尾部元素的增加和减少。

不变量

下一个元素的位置总是 size。
size 总是 AList 中元素的个数。
最后一个元素的索引总是 size-1。

更改大小

数组的大小是有限的。如果超出了大小，就需要创建新的数组，满足大小，并且将旧数组都复制到新数组当中。

如果需要更改大小 $n$ 次，这样做的代价大约是 $O(n^2)$。

每一次重新分配大小，将大小变为原先的两倍。这样可以明显地提升速度。同时，如果相比于数组的大小，使用的数据量过于小（通常选择 0.25），那么可以将数组大小缩小一半，节省空间。

泛型数组

使用 items = (type[]) new Object[n] 来创造泛型的数组。

lec8 Inheritance, Implements

method overload

在 java 中，一个类中的方法可以有相同的名字，但是有不同的参数。通过不同的参数，编译器可以判断具体使用哪一个方法。

接口（Interface）

有的方法对各种列表都适用，但是非要制定具体的 AList 或 SLList。如果使用 overload，需要复制粘贴代码，修改起来很麻烦。

解决方法是创造一个 interface，可以代表多种列表。在新的文件中，像这样命名：

1

public interface List<Item> { ... }

对于接口，可以描述它们做什么，但是不用描述怎么做。例如，主需要写下方法即可：

1

public Item get(int i);

接着，在 AList 和 SLList类中，修改为这样：

1

public AList<Item> implements List<Item> { ... }

这样，就可以使用其他方法，对于所有的 List 都有用。

覆盖（Override）

对于具体的类，可以选择覆盖方法：

1
2


@Override
public Item get(int i) { ... }

这里的 @Override 虽然不是必须的，但是建议这样写，一方面可以避免拼写错误，另一方面方便其他程序员明白这个方法在 Override。

在接口中，也可以使用 default 关键字，内置一个方法：

1

default public void method() { ... }

该方法中可以使用其他接口中的方法。

Static vs. Dynamic Type

Static type 是唯一确定的，仅仅取决于声明变量时的类型。而 Dynamic Type 可以随着程序而变化，取决于当前指向的对象的类型。

project1 前半部分

这个项目分为两个部分，第一个部分需要实现数据结构，第二个部分则需要利用数据结构实现应用。

项目介绍

Package

有两个包：deque 用来实现数据结构，gh2 用来实现吉他英雄的合成器。

包可以包含许多类，实现一个更大的目标。利用文件开头的 package deque;，就表明当前类在 deque 包当中。

如果其他程序员想用使用某个方法，要么使用全名，也就是 deque.ArrayDeque，要么 import deque.ArrayDeque 后使用简称 ArrayDeque。

同时，全名是倒着写的。例如，JUnit 库在 junit.org，于是包写成 org.junit。因为不同库当中可能有相同的方法，所以要制定全名或者使用 import。

Deque

一般读作"deck"，代表两端队列，既可以从头加入、移除元素，也可以从尾部加入、移除元素。在 The Deque API 中，说明了希望的 API。该项目需要用两种方法来实现 Deque——双向链表和数组。

LinkedListDeque

有一些要求：

add 和 remove 必须消耗常数的时间。
get 要使用迭代而不是递归。
size 要消耗常数的时间。
使用 for 循环来遍历链表。
不要保留对于不在队列当中物品的引用。

我选择了循环链表加上一个哨兵实现，这样的代码确实比较简洁。在 LinkedListDeque 的内部，我创建了 private Node 类。LinkedListDeque有两个实例变量——Node sentinel 和 int size。

在只有一个哨兵的时候，哨兵的 prev 和 next 都设置成自身。对于头部和尾部加入元素，需要考虑清楚改变哪些指针即可。

特别注意，对于 remove 操作，需要考虑 size 为 0 时，如果用户执行 remove，那么 size 还应该为 0。这一点我一开始还没有考虑到，经过测试才发现。

对于 getRecursive 操作，可以创建一个私有的 helper 函数，输入 Node 和 index，利用递归完成获取第 index 节点的 item。

完整代码如下：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102


public class LinkedListDeque<T> {

    private Node sentinel;
    private int size;
    private class Node {
        T item;
        Node prev;
        Node next;

        private Node(T item,Node prev,Node next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }
    public LinkedListDeque() {
        this.sentinel = new Node(null, null, null);
        this.sentinel.next = sentinel;
        this.sentinel.prev = sentinel;
        size = 0;
    }

    public void addFirst(T item) {
        Node temp = new Node(item, sentinel, sentinel.next);
        sentinel.next.prev = temp;
        sentinel.next = temp;
        size += 1;
    }

    public void addLast(T item) {
        Node temp = new Node(item, sentinel.prev, sentinel);
        sentinel.prev.next = temp;
        sentinel.prev = temp;
        size += 1;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void printDeque() {
        Node p = sentinel;
        while(p.next != sentinel){
            System.out.print(p.item);
            System.out.print(' ');
            p = p.next;
        }
        System.out.println();
    }

    public T removeFirst() {
        if (size == 0) {
            return null;
        }
        T value = sentinel.next.item;
        sentinel.next.next.prev = sentinel;
        sentinel.next = sentinel.next.next;
        size -= 1;
        return value;
    }

    public T removeLast() {
        if (size == 0) {
            return null;
        }
        T value = sentinel.prev.item;
        sentinel.prev.prev.next = sentinel;
        sentinel.prev = sentinel.prev.prev;
        size -= 1;
        return value;
    }

    public T get(int index) {
        if (index >= size) {
            return null;
        }
        Node p = sentinel.next;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        return p.item;
    }

    public T getRecursive(int index) {
        if (index >= size) {
            return null;
        }
        return recursiveHelper(sentinel.next, index);
    }

    /** Private helper for recursively get item. */
    private T recursiveHelper(Node p, int index) {
        if (index == 0) {
            return p.item;
        }
        return recursiveHelper(p.next, index-1);
    }
}

Array Deque 简单部分

要求：

add 和 remove 应该消耗常数时间，除非需要 resize。
get 和 size 必须消耗常数时间。
开始的数组大小为 8。
对于长度大于等于 16 的数组，可用率至少为 25%。即 remove 时，如果让可用率低于 25%，则需要 resize。

推荐使用环形的数组。

环形数组示意图

初始化

首先，创造相应数量为 8 的数组。然后，size 赋值为 0，并将 nextFirst 赋值为最后一个索引，nextLast 赋值为 0。

1
2
3
4
5
6


public ArrayDeque() {  
    items = (T[]) new Object[INIT_SIZE];  
    size = 0;  
    nextFirst = INIT_SIZE-1;  
    nextLast = 0;  
}

环形索引

为了方便地实现环形，定义两个私有的 helper 方法，nextIndex 和 prevIndex。

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


private int nextIndex(int n) {  
    if (n+1 == items.length) {  
        return 0;  
    }  
    return n+1;  
}  
  
private int prevIndex(int n) {  
    if (n == 0) {  
        return items.length-1;  
    }  
    return n-1;  
}

增减元素（不考虑 resize）

对于增加第一个元素，首先需要将索引为 nextFirst 的元素赋值为 item，然后更改 nextFirst 为前一个索引，最后增加 size。

1
2
3
4
5


public void addFirst(T item) {  
    items[nextFirst] = item;  
    nextFirst = prevIndex(nextFirst);  
    size += 1;  
}

对于移除第一个元素，需要首先判断 size 是否为 0。如果是，直接返回 null 阶数函数。如果还有元素，则先将元素暂存下来，并清空数组中对元素的 reference，然后更改 nextFirst 和 size，最后返回该元素。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


public T removeFirst() {  
    if (size == 0) {  
        return null;  
    }  
    T item = items[nextIndex(nextFirst)];  
    items[nextIndex(nextFirst)] = null;  
    nextFirst = nextIndex(nextFirst);  
    size -= 1;  
    return item;  
}

对于 addLast 和 removeLast 函数，方法也是类似的，这里就不再重复了。

容易实现的方法

get，isEmpty 和 size 都很好实现，这里就不再赘述。（其实这里的 get 有 bug，在 week4 的 MaxArrayDeque 中有修改）

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


public T get(int index) {  
    if (index >= items.length){  
        return null;  
    }  
    return items[index];  
}  
  
public boolean isEmpty() {  
    return size == 0;  
}  
  
public int size() {  
    return size;  
}

ArrayDeque Resize

终于来到了最有意思的地方。相比于双向链表，数组总是有一个固定的大小。如果需要更改大小，就需要手动赋值数组。

同时，我们是通过循环数组来实现的。这就意味着，必须要判断当前的数组是否是循环的。例如，[X, 2, 3, 4, X, X] 就是不循环的，因为所有的元素都在中间部分；[2, 3, X, X, 5, 6]就是循环的，因为该数组的第一个元素是 5，然后是 6，接着因为循环，下一个元素变为 2，然后是 3。因此，需要编写函数来判断当前数组是否循环。

isCircular

跟函数需要返回是否循环。利用之前的 Index 操作，可以方便地找到当前数组的首元素索引和尾元素索引。然后，如果首元素的索引大于尾元素的索引，就代表存在循环；否则，不存在。

1
2
3
4
5
6


/** If circular, return true.*/  
private boolean isCircular() {  
    int first = nextIndex(nextFirst);  
    int last = prevIndex(nextLast);  
    return first > last;  
}

CheckExpand

每次扩张数组时，都有可能使得当前元素个数超出数组范围。因此，每次 add 操作前都需要判断。为此编写判断的函数：

1
2
3
4
5
6
7
8


/** Check whether after add new item,  
 * the AList needs to expand. If so, call expandSize.*/
private void checkExpand() {  
    if (size != items.length) {  
        return;  
    }  
    resize(size * 2);  
}

这里选择每次扩大一倍，因为一开始的大小也是 8，这样成倍扩大后数字比较整齐。

Resize

对于数据的更改大小，首先需要创造一个新的数组，然后将当前数组中的元素复制进新的数组。这需要分类讨论：

如果当前数组循环，则需要从首元素到数组末尾赋值到新数组，然后从数组头部到尾元素复制到新数组。
如果当前数组不循环，则只需要复制中间部分到新数组。

复制完成后，将 items 指向新的数组，然后更新 nextFirst 为新的大小-1，nextLast 为原先大小。

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


/** Expand array to newSize.*/  
private void resize(int newSize) {  
    T[] newArray = (T[]) new Object[newSize];  
    int first = nextIndex(nextFirst);  
    // if the items are circular  
    if (isCircular()){  
        System.arraycopy(items,first,newArray,  
                0,items.length-first);  
        System.arraycopy(items,0,newArray,  
                items.length-first,nextLast);  
    }  
    else {  
        System.arraycopy(items,first,newArray,0,size);  
    }  
    items = newArray;  
    nextFirst = newSize-1;  
    nextLast = size;  
}

checkEmptySpace

如果一开始加入了很多元素，之后又减少了很多元素，那么数组不应该耗费太多空间。所以，每次删除元素的时候，都需要检查是否有多余的空间。为此编写 checkEmptySpace 函数。

根据要求，如果当前数组长度大于 16，并且空闲率（元素个数除以数组长度）小于 0.25，那么就需要缩小数组。此时，因为空闲率小于 0.25，所以可以将数组缩小为原先长度的一半。

1
2
3
4
5
6
7
8


/** Check whether empty space exists.*/  
private void checkEmptySpace() {  
    if (items.length >= MAX_EMPTY_SIZE  
            && size < 0.25*items.length) {  
        resize(items.length / 2);  
    }  
    return;  
}

经过这些函数，数组双向队列可以基本实现。

完整的项目代码见github上的my-cs61b。

CS61B week3 学习笔记

包括第三周讲座内容，以及project1前半部分