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(),objstores 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. |
Sentinel Node
public SLList() { |
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) { |
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. */ |
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; |
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:
- Identify a new feature.
- Write a unit test for that feature.
- Run the test. It should fail.
- Write code that passes the test. Yay!
- 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); |
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` |
Extends
The
extendskeyword defines “is-a”.
By using the
extendskeyword, subclasses inherit all members of the parent class. “Members” includes:
- All instance and static variables
- All methods
- 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() { |
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); |
尽管运行时sl是动态的VengefulSLList类型，Java编译器将对象看作静态类型；SLList没有printLostItems方法，因此会报错；最后一句也是一样。
4.3 Polymorphism
public interface OurComparable { |
使用多态，就可以写出一个统一的max()方法，而不需要考虑各个类的数据结构
Final
The
finalkeyword 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可变
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()的实现方法。浮点数运算比整数运算慢很多！