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

传个part2就够了吧。。part1输出太长了
这次作业难度感觉比起前面的大了好多。。争取3月能结课！

这次作业花了好长时间，谢谢前面的人的总结。

混乱，晕

1. Set s = {  3  4  }
   
2. Set s2 = {  4  5  }
   
3. Set s3 = {  3  5  8  }
   
4. After s.union(s2), s = {  3  4  5  }
   
5. After s.intersect(s3), s = {  3  5  }
   
6. s.cardinality() = 2
   
7. [code]An empty list should be [  ]: [  ]
   
8. l.isEmpty() should be true: true
   
9. l.length() should be 0: 0
   
10. Finding front node p of l.
    
11. p.isValidNode() should be false: false
    
12. p.item() should throw an exception, and did.
    
13. p.setItem() should throw an exception, and did.
    
14. p.next() should throw an exception, and did.
    
15. p.prev() should throw an exception, and did.
    
16. p.insertBefore() should throw an exception, and did.
    
17. p.insertAfter() should throw an exception, and did.
    
18. p.remove() should throw an exception, and did.
    
19. Finding back node p of l.
    
20. p.isValidNode() should be false: false
    
21. p.item() should throw an exception, and did.
    
22. p.setItem() should throw an exception, and did.
    
23. p.next() should throw an exception, and did.
    
24. p.prev() should throw an exception, and did.
    
25. p.insertBefore() should throw an exception, and did.
    
26. p.insertAfter() should throw an exception, and did.
    
27. p.remove() should throw an exception, and did.
    
28. l after insertFront(10) should be [  10  ]: [  10  ]
    
29. l is a list of 3 elements: [  1  2  3  ]
    
30. n.item() should be 1: 1
    
31. n.item() should be 2: 2
    
32. n.item() should be 2: 2
    
33. n.item() should be 4: 4
    
34. n.item() should be 3: 3
    
35. n.item() should be 6: 6
    
36. After doubling all elements of l: [  2  4  6  ]
    
37. p.isValidNode() should be false: false
    
38. p.item() should throw an exception, and did.
    
39. p.setItem() should throw an exception, and did.
    
40. p.next() should throw an exception, and did.
    
41. p.prev() should throw an exception, and did.
    
42. p.insertBefore() should throw an exception, and did.
    
43. p.insertAfter() should throw an exception, and did.
    
44. p.remove() should throw an exception, and did.
    
45. n.item() should be 6: 6
    
46. n.item() should be 12: 12
    
47. n.item() should be 4: 4
    
48. n.item() should be 8: 8
    
49. n.item() should be 2: 2
    
50. n.item() should be 4: 4
    
51. After doubling all elements of l again: [  4  8  12  ]
    
52. p.isValidNode() should be false: false
    
53. p.item() should throw an exception, and did.
    
54. p.setItem() should throw an exception, and did.
    
55. p.next() should throw an exception, and did.
    
56. p.prev() should throw an exception, and did.
    
57. p.insertBefore() should throw an exception, and did.
    
58. p.insertAfter() should throw an exception, and did.
    
59. p.remove() should throw an exception, and did.
    
60. Removing middle element (8) of l: 8
    
61. l is now: [  4  12  ]
    
62. p.isValidNode() should be false: false
    
63. p.item() should throw an exception, and did.
    
64. p.setItem() should throw an exception, and did.
    
65. p.next() should throw an exception, and did.
    
66. p.prev() should throw an exception, and did.
    
67. p.insertBefore() should throw an exception, and did.
    
68. p.insertAfter() should throw an exception, and did.
    
69. p.remove() should throw an exception, and did.
    
70. Removing end element (12) of l: 12
    
71. l is now: [  4  ]
    
72. p.isValidNode() should be false: false
    
73. p.item() should throw an exception, and did.
    
74. p.setItem() should throw an exception, and did.
    
75. p.next() should throw an exception, and did.
    
76. p.prev() should throw an exception, and did.
    
77. p.insertBefore() should throw an exception, and did.
    
78. p.insertAfter() should throw an exception, and did.
    
79. p.remove() should throw an exception, and did.
    
80. Removing first element (4) of l: 4
    
81. l is now: [  ]
    
82. p.isValidNode() should be false: false
    
83. p.item() should throw an exception, and did.
    
84. p.setItem() should throw an exception, and did.
    
85. p.next() should throw an exception, and did.
    
86. p.prev() should throw an exception, and did.
    
87. p.insertBefore() should throw an exception, and did.
    
88. p.insertAfter() should throw an exception, and did.
    
89. p.remove() should throw an exception, and did.

复制代码

[/code]

时间复杂度应该要在O（总长度）而不能是O（s1*s2）

交作业啦，原来图片超过一定尺寸就一直会失败……搞得我心态崩了

刚刚传的图片好像太小了，晕

谢谢前面同学的测试代码！

做了两个下午 泪奔啊...看着不难 实际操作起来还挺不容易的～～
作业5开始融入了一些算法思想，比如用merge sort的思想来控制计算难度
关于实现： 我犯了一个错误 for(int i=0;i<length;i++）对length也进行变动 希望能减少计算难度...但是实际上根本就不需要...
还有就是关于if 如果是多个if连着 没有else的话 实际上是从上到下 依次进行判断 是否可以进入 有的忘记break了 就继续进入下一个if了... 感觉自己虽然用的是mergesort的思想，但是代码还是挺冗余的 还有很多进步空间
这次作业也帮助我们更好地了解ADT、封装 part1的作业要求实际上也是hw4的“污染数据结构”问题的答案(当时想了半天 死活想不出来hh
关于接口 用的不多 感觉还要再去研究一下... 这次作业就只需要知道 Comparable对象可以直接调用比较方法 就行了...
以下是运行结果：

感谢althinking提供的test case
对于insurrect 和 union，我用的是nested while loop

看起来略长，但分析之后，对于list来说应该已经是最优了。