CS61B sp18

发表于 更新于

Gradescope Autograder

Spring 2018

44个Assn，偏向数据结构
邀请码：MNXYKX
学校：UC Berkeley
直接输入，不要选择2U-UC Berkeley，否则将提示COURSE ENTRY CODE IS INVALID

Spring 2021

19个Assn，偏向软件工程
邀请码：MB7ZPY

文章收录

The Law of the Broken Futon 浮沙筑高台法则

“Since I’m fine now, can’t I add that missing piece later, when it’s actually needed?” Sometimes, yes. But it’s much harder.
Adding the missing piece later means waiting until the damage is already underway, and hellishly difficult to undo.

A Response to “Why Most Unit Testing is Waste”

(Unit Tests) They are based on programmers’ fantasies about how the function should work. But programmers break down requirements into smaller components all the time – this is how you program. Sometimes there are misunderstandings, but that is the exception, not the rule, in my opinion.

2.1 Mystery of Java Restore

When instantiate an Object, obj = new Object(), obj stores the address of the Object, not the specific data struction.

(That is why all type of variables create memory boxes of 64 bits. It is just the memory of the address.)

Therefore, When we use obj2 = obj, Java simply copy the addr of obj and assign it to obj2 (They are pointing to the same Object), that is why when we change obj2.weight it effects obj.weight too.

2.2 SLList

Static

if you don’t use any instance members of the outer class, make the nested class static.

Overloaded

// Share the same name but have different parameters.
private static int size(IntNode p) {
    if (p.next == null) {
        return 1;
    }
    return 1 + size(p.next);
}

public int size() {
   return size(first);
}

Sentinel Node

public SLList() {
    first = null;
    size = 0;
}

public void addLast(int x) {
    if (size == 0) {
        addFirst(x);
        return;
    }
    // This solution works, but special case code like that shown above should be avoided when necessary.
    IntNode p = first;
    while (p.next != null) {
        p = p.next;
    }
    p.next = new IntNode(x, null);
    size++;
}

We can do this by creating a special node that is always there, which we will call a sentinel node. The sentinel node will hold a value, which we won’t care about.

public void addLast(int x) {
    IntNode p = sentinel;
    while (p.next != null) {
        p = p.next;
    }
    p.next = new IntNode(x, null);
    size++;
}

3.0 Testing

The == operator

== operator simply compares the literal bits in the memory boxes. (e.g., for objects it only compares their address.)

Private Recursive Helper

/** Sorts strings destructively starting from item start. */
private static void sort(String[] x, int start) { 
   int smallestIndex = findSmallest(x);
   swap(x, start, smallestIndex);
   sort(x, start + 1);
}

/** Sorts strings destructively. */
public static void sort(String[] x) { 
   sort(x, 0);
}

This approach is quite common when trying to use recursion on a data structure that is not inherently recursive, e.g. arrays.

JUnit

import org.junit.Test;
import static org.junit.Assert.*;

@Test
public void test() {
    // your test code
    assertEquals(actual, expected);
}

Autograder vs JUnit

Rely on an Autograder, there is plenty of time that you’re not in control of neither your workflow or your code.

Test-Driven Development (TDD)

TDD is a development process in which we write tests for code before writing the code itself. The steps are as follows:

  1. Identify a new feature.
  2. Write a unit test for that feature.
  3. Run the test. It should fail.
  4. Write code that passes the test. Yay!
  5. Optional: refactor code to make it faster, cleaner, etc. Except now we have a reference to tests that should pass.

You should definitely write tests but only when they might be useful!

4.1 Overload

public static String longest(SLList<String> list);
public static String longest(AList<String> list);

Java will choose the right method according to the parameter you pass in.

However, it is ugly, repetitive and hard to maintain.

@Override

Override is something like a proofreader. It will remind you when you make a typo and named method in error.

4.2 Interface

Summary:

  • All methods must be public.
  • All variables must be public static final.
  • Cannot be instantiated
  • All methods are by default abstract unless specified to be default
  • Can implement more than one interface per class

Default

// Use `default` to define a method in `interface`
default public void print() {
    // your code
}

Extends

The extends keyword defines “is-a”.

By using the extends keyword, subclasses inherit all members of the parent class. “Members” includes:

  1. All instance and static variables
  2. All methods
  3. All nested classes

Note that constructors are not inherited, and private members cannot be directly accessed by subclasses.

Subclass Constructor

A subclass is firstly its parentclass. Using the super keyword.

public VengefulSLList() {
    super();
    deletedItems = new SLList<Item>();
}

Or, if we choose not to, Java will automatically make a call to the superclass’s no-argument constructor for us.

Compile-time Error

VengefulSLList<Integer> vsl = new VengefulSLList<Integer>(9);
SLList<Integer> sl = vsl;

sl.addLast(50);
sl.removeLast();

sl.printLostItems(); // 会出错
VengefulSLList<Integer> vsl2 = sl; // 会出错

尽管运行时sl是动态的VengefulSLList类型，Java编译器将对象看作静态类型；SLList没有printLostItems方法，因此会报错；最后一句也是一样。

4.3 Polymorphism

public interface OurComparable {
    public int compareTo(Object o);

    public static OurComparable max(OurComparable[] items) {
        int maxDex = 0;
        for (int i = 0; i < items.length; i += 1) {
            int cmp = items[i].compareTo(items[maxDex]);
            if (cmp > 0) {
                maxDex = i;
            }
        }
        return items[maxDex];
    }
}

public class Dog {
    public int compareTo(Object o) {
        Dog uddaDog = (Dog) o;
        return this.size - uddaDog.size;
    }
}

使用多态，就可以写出一个统一的max()方法，而不需要考虑各个类的数据结构

Final

The final keyword prevents the variable from being changed after its first assignment.

Notice: it doesn’t work for reference!

public final ArrayDeque<String>() deque = new ArrayDeque<String>();

deque不可改变，然而deque指向的ArrayDeque可变

Specific Generic Types

public static <K extends Comparable<K>, V> K maxKey(Map61B<K, V> map) {...}

The K extends Comparable<K> means keys must implement the comparable interface and can be compared to other K’s.

ArraySet

注意Set的add()方法需要检查是否已包含元素。

Iterator

For code on the right to work:

  1. Compiler checks that Lists have a method called iterator() that returns an  Iterator<Integer>.
  2. Then, compiler checks that Iterators have:
    • hasNext()
    • next()
import java.util.Iterator;

public class ArraySet<T> implements Iterable<T> {
    @Override
    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;
        }
    }
}

The Philosophy of Exceptions

Exceptions keep error handling separate from the rest of the program.

Program without exceptions:

if (theFileIsOpen) {
    determine its size;
    if (gotTheFileLength) {
        allocate that much memory;
    } else {
        return error("fileLengthError");
    }
...

Program with exceptions:

try {
    open the file;
    determine its size;
    allocate that much memory;
    read the file into memory;
    close the file;
} catch (fileOpenFailed) {
    doSomething;

Exceptions: Catch and Specify

Catch the error when you can handle the problem there. Keep it from escaping!

public static void main(String[] args) {
    try {
        gulgate();
    } catch(IOException e) {
        System.out.println("Averted!");
    }
}

Specify the error when someone else should handle the error. Make sure the caller knows the method is dangerous!

public static void main(String[] args) throws IOException {
    gulgate();
}

Abstract

If an implementing class fails to implement any abstract methods inherited from an interface, then that class must be declared abstract.

public abstract class AbstractBoundedQueue {

    /* the method must be defined with the abstract keyword 
     * and without an implementation (without braces, and 
     * followed by a semicolon) 
     */
     abstract void moveTo(double deltaX, double deltaY);
}

Package

It is very possible that with all the code in this world, you would create classes that share names with those from a different project.

the package — a namespace that organizes classes and interfaces.
naming convention: package name starts with the website address, backwards.

com.joshh.animal // joshh.com

JAR

JAR files are just like zip files.
JAR files do not keep your code safe, and thus you should not share your .jar files of your projects with other students.

Access Control

  • private: Only the given class can access. Subclass cannot.
  • package private: Only the class from the same package can access.
  • protected: the same package or subclass can access.

Encapsulation

A module is said to be encapsulated if its implementation is completely hidden, and it can be accessed only through a documented interface.

Delegation

Extension tends to be used when you know what is going on in the parent class.

Delegation is when you do not want to consider your current class to be a version of the class that you are pulling the method from.

Assn

Proj0

[!NOTE]
注意严格按照讲义要求编程，不要有讲义以外的函数或方法，否则Gradescope OJ会扣掉API的10分！

计算ForceExertedByX/Y，不要使用Math.abs()或者a < 0 ? -a : a来通过本地测试，否则OJ会报错。力的方向（正负）需要根据行星的相对位置来定。

Proj1

  • 注意构造空的Deque时，确保哨兵正确指向自己。
  • add()需要更改4个指针的方向。修改指针指向时，注意备份原指针指向位置。
  • 对于循环Deque，注意print()的迭代条件。
  • remove()方法需要检查isEmpty()，否则不应该执行。
  • get()方法，index从0开始，LinkedList和ArrayList的对应关系是一样的。

Array Deque

  • 先设计，再编码。好好想想要设计怎样的ArrayDeque。分离传入index和实际index。
  • 取模！！！一定要注意-1 % size = -1是取余数，Math.floorMod(-1, size) = size-1才是取模！（当Gradescope出现index=-1一般就是取模问题）
  • addFirst()后调用removeLast()时，size变回0，但是没有调整下标的话head和end不会连在一起（错误状态）
  • 考虑resize()的实现方法。浮点数运算比整数运算慢很多！

Proj2

思路：在房间旁边画房间，并在房间重合边缘处打洞，实现迷宫。

  1. 首先设计Room.java，内置画一个房间，在房间旁边生成房间的方法。
    稀里糊涂地生成了不错的迷宫出来。但是不好打洞！

HW2

蒙特卡罗渗透实验。原理是使用集合连接打通的节点，检查是否从top到bottom都连通了，连通了即渗透成功。
因此使用集合UF时，可以生成N*N+2个节点，作为top节点和bottom节点。但是这样做会导致倒灌(backwash)，可以创建两个UF，一个有bottom，另一个没有。一个用于检查是否渗透，另一个用于检查isFull。