Berkeley CS 61B Data Structures(in Java) Homework5 加分+讨论帖

认真学习了exception~交作业~

hw5交作业～

hw5 耗时大致8h；
写方法前最好 先用数学表达式表达；
注意考虑特殊情况，及出发条件；
弄清楚循环条件；
循环结束条件；

An empty list should be [  ]: [  ]
l.isEmpty() should be true: true
l.length() should be 0: 0
Finding front node p of l.
p.isValidNode() should be false: false
p.item() should throw an exception, and did.
p.setItem() should throw an exception, and did.
p.next() should throw an exception, and did.
p.prev() should throw an exception, and did.
p.insertBefore() should throw an exception, and did.
p.insertAfter() should throw an exception, and did.
p.remove() should throw an exception, and did.
Finding back node p of l.
p.isValidNode() should be false: false
p.item() should throw an exception, and did.
p.setItem() should throw an exception, and did.
p.next() should throw an exception, and did.
p.prev() should throw an exception, and did.
p.insertBefore() should throw an exception, and did.
p.insertAfter() should throw an exception, and did.
p.remove() should throw an exception, and did.
l after insertFront(10) should be [  10  ]: [  10  ]
l is a list of 3 elements: [  1  2  3  ]
n.item() should be 1: 1
n.item() should be 2: 2
n.item() should be 2: 2
n.item() should be 4: 4
n.item() should be 3: 3
n.item() should be 6: 6
After doubling all elements of l: [  2  4  6  ]
p.isValidNode() should be false: false
p.item() should throw an exception, and did.
p.setItem() should throw an exception, and did.
p.next() should throw an exception, and did.
p.prev() should throw an exception, and did.
p.insertBefore() should throw an exception, and did.
p.insertAfter() should throw an exception, and did.
p.remove() should throw an exception, and did.
n.item() should be 6: 6
n.item() should be 12: 12
n.item() should be 4: 4
n.item() should be 8: 8
n.item() should be 2: 2
n.item() should be 4: 4
After doubling all elements of l again: [  4  8  12  ]
p.isValidNode() should be false: false
p.item() should throw an exception, and did.
p.setItem() should throw an exception, and did.
p.next() should throw an exception, and did.
p.prev() should throw an exception, and did.
p.insertBefore() should throw an exception, and did.
p.insertAfter() should throw an exception, and did.
p.remove() should throw an exception, and did.
Removing middle element (8) of l: 8
l is now: [  4  12  ]
p.isValidNode() should be false: false
p.item() should throw an exception, and did.
p.setItem() should throw an exception, and did.
p.next() should throw an exception, and did.
p.prev() should throw an exception, and did.
p.insertBefore() should throw an exception, and did.
p.insertAfter() should throw an exception, and did.
p.remove() should throw an exception, and did.
Removing end element (12) of l: 12
l is now: [  4  ]
p.isValidNode() should be false: false
p.item() should throw an exception, and did.
p.setItem() should throw an exception, and did.
p.next() should throw an exception, and did.
p.prev() should throw an exception, and did.
p.insertBefore() should throw an exception, and did.
p.insertAfter() should throw an exception, and did.
p.remove() should throw an exception, and did.
Removing first element (4) of l: 4
l is now: [  ]
p.isValidNode() should be false: false
p.item() should throw an exception, and did.
p.setItem() should throw an exception, and did.
p.next() should throw an exception, and did.
p.prev() should throw an exception, and did.
p.insertBefore() should throw an exception, and did.
p.insertAfter() should throw an exception, and did.
p.remove() should throw an exception, and did.

不知道o(n)到没到要求啊。。。

终于做完了。图片里的test code 用了楼里的大神的。 我自己写的怕不保险。part2 compile完后出现note：Set.java uses unchecked or unsafe operations.虽然可以运行，但是不知道怎么消除这个note啊。希望大神指点下！
对我来说，这次作业的难点是interface还是理解不够。开始以为要implements comparable. 最后发现不用。union和intersect开始是把空集分出来，最后看楼里的提示，不用单独分类，直接比较最小值，也就是从头开始比较两个集的node。这样写出来的code更简洁易读。关于时间复杂度，因为要求是this.cardinality() + s.cardinality()，我是只写一个循环，只要不在循环里调用insert，这样最坏的情况就是走完两个集。学习了exception，只要调用的函数有throw exception就必须catch。自定义exception确实方便debug。
另外感觉逻辑感真的很重要啊。我是需要在纸上画出各种情况来验证code结构对不对。希望以后可以脑子动得快一些。

最后那个afterthought：If you use SLists instead of DLists, do your union() and intersect() methods
still run within the time bounds? If not, how easy would it be to fix them so
that they do?我的union调用了insertBefore，里面用到prev()，SList de prev()的时间复杂度是O(n),这样的话复杂度就变成O(n2)了。我想到的是把用currentNode1.insertBefore的换成tempNode1.insertAfter
（tempNode1 = currentNode1;
                    currentNode1 = currentNode1.next();）。另外需要在constructor里改成SList。希望大家讨论一下呀。

做是做出来了，一开始忘记Set s其实是sorted，所以纠结了好久不知道除了遍历外该怎么做。另外有大神知道该怎么消除那个黄色警告，关于comparable，Comparable is a raw type. References to generic type Comparable<T> should be parameterized 吗？感觉自己很多都是靠eclipse提示才加上()。觉得得回去好好看下书，加深理解再继续往下学下去。

错了一堆，占个坑吧

打卡打卡打卡

还做了蛮久的  时间复杂度那里卡了一下，收获还挺大的。分别是DList个set的输出