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

交作业了！

啊啊啊点错了，很久没交作业刚刚打了字按了回车直接发出去了，sorry

刚刚想换行按了ctrl+回车又自动发出去了。。不敢按了我就不换行了，说一下这次的经验：第一时间复杂度部分需要使用迭代，union的时候使用了for循环实际上不需要，用while更好，在intersect部分大家说需要考虑空的情况，我的代码中判断空集和正常的处理的一样的，不知道算法是不是和大家不同，感觉union写了一下午，intersect写了10分钟，欢迎交流！

Part I:

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

复制代码

Part II:

1. ➜  hw5 git:(master) ✗ javac Set.java      
   
2. Note: Set.java uses unchecked or unsafe operations.
   
3. Note: Recompile with -Xlint:unchecked for details.
   
4. ➜  hw5 git:(master) ✗ java Set
   
5. Set s = [  3  4  ]
   
6. Set s2 = [  4  5  ]
   
7. Set s3 = [  3  5  8  ]
   
8. After s.union(s2), s = [  3  4  5  ]
   
9. After s.intersect(s3), s = [  3  5  ]
   
10. s.cardinality() = 2
    
11. ➜  hw5 git:(master) ✗

复制代码

交作业~感谢首页提供的test code
union写了挺长时间的，有很多情况要考虑到。intersect还挺快的，就是比较时要注意分类讨论：如果this中的元素比s中的小，则删除this中的元素，再与this中下一个元素进行比较；如果this元素比s元素大，则this元素不动，与s下一个元素进行比较。
另外一开始在怎么implement comparable interface的问题上卡了很久……后来发现直接用就好了

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

复制代码

1. Part 2:
   
2. Set s = [  3  4  ]
   
3. Set s2 = [  4  5  ]
   
4. Set s3 = [  3  5  8  ]
   
5. After s.union(s2), s = [  3  4  5  ]
   
6. After s.intersect(s3), s = [  3  5  ]
   
7. s.cardinality() = 2
   

复制代码

1. Test :
   
2. Testing insert()
   
3. Set s should be { 3 4 }: [  3  4  ]
   
4. Set s2 should be { 4 5 }: [  4  5  ]
   
5. Set s3 should be { 3 5 8 }: [  3  5  8  ]
   
6. 
   
7. Tesing union()
   
8. After s.union(s2), s should be { 3 4 5 }: [  3  4  5  ]
   
9. After s2.union(s3), s2 should be { 3 4 5 8 }: [  3  4  5  8  ]
   
10. Empty set s4 = [  ]
    
11. After s.union(s4), s should be { 3 4 5 }: [  3  4  5  ]
    
12. After s4.union(s), s4 should be { 3 4 5 }: [  3  4  5  ]
    
13. 
    
14. Tesing intersect()
    
15. {}.intersect({1}) should be { }: [  ]
    
16. {1}.intersect({}) should be { }: [  ]
    
17. {1}.intersect({1 2}) should be { 1 }: [  1  ]
    
18. {1 2 3}.intersect({1 2}) should be { 1 2 }: [  1  2  ]
    
19. {1 2 4 7}.intersect({1 2 3 5}) should be { 1 2 }: [  1  2  ]
    
20. 
    
21. Tesing cardinality()
    
22. s.cardinality() should be 3: 3
    
23. s4.cardinality() should be 3: 3
    
24. s5.cardinality() should be 0: 0
    
25. s6.cardinality() should be 4: 4
    
26. s7.cardinality() should be 2: 2
    

复制代码

开学了homework刷起来~

挺费神的，调了好久
Set s = {  3  4  }
Set s2 = {  4  5  }
Set s3 = {  3  5  8  }
After s.union(s2), s = {  3  4  5  }
Empty set s4 = {  }
After s.union(s4), s should be { 3 4 5 }: {  3  4  5  }
After s4.union(s), s4 should be { 3 4 5 }: {  3  4  5  }
{}.intersect({1}) should be { }: {  }
{1}.intersect({}) should be { }: {  }
{1}.intersect({1 2}) should be { 1 }: {  1  }
{1 2 3}.intersect({1 2}) should be { 1 2 }: {  1  2  }
{1 2 4 7}.intersect({1 2 3 5}) should be { 1 2 }: {  1  2  }

Tesing cardinality()
s.cardinality() should be 3: 3
s4.cardinality() should be 3: 3
s5.cardinality() should be 0: 0
s6.cardinality() should be 4: 4
s7.cardinality() should be 2: 2

1.在set构造方法中，使用DList的原因是在List中创建一个DList，但是使用者并不需要知道这些。如果之后要更改，他可以直接写一个其他类型的list，再重写这个构造方法。2.因为Set是在list package外部的，它无法看到list中被protected保护的部分，所以多数时候都要通过调用公开的方法来访问到list里面，这样就实现了良好的封装。3.能看到list中两个文件有可能throw exception，所以在应用到的方法中要使用try-catch来抓住exception。4.insert方法可以先排除极端情况（空list），再加一个指针到第一个node上。然后把指针指向的this node值和要插入的值相比，如果相等就不插入，如果this node > 要插入的值，就直接在this node前面insertbefore插入，如果this node < 要插入的值，就把指针换到下一个node，循环回来比较this node和要插入的值，直到this node > 要插入的值。另一种极端情况：如果到最后要插入的值还是大于this node，就在最后insertback要插入的值5.union方法要建立两个指针，一个在this set，一个在参数set。首先排除两个set为空的极端情况，然后建立两个嵌套while loop，把指针先都定位到第一个值，用compareTo做比较，再根据各种情况使用insert方法实现插入，然后移动指针。6.compareTo方法是在comparable interface下实现的，调用这个方法的对象一定要是comparable，所以需要cast一下。但是被比较的括号里的参数不一定是comparable，所以不用cast。7.在有两个while loop的情况下，可以在最前面加loop: ，然后中间用continue loop;实现直接跳到最外层loop继续。8.如果一个String会经常变化，可以先建立一个StringBuilder来存储，用append()方法加入元素，最后再用toString()方法把StringBuilder转化成String。

本次hw说难不难，说简单也不简单 下面是我总结的一些要点
1.part 1中要注意构建DList()的时候head=newNode(item,null,null,null);  newNode的第二个参数应该是null !!即哨兵结点的isvalidNode field为null！
2.part 1中 DListNode类中insertAfter()、insertBefore()、以及remove()方法都要注意调整表的 size field
3.part 2 中比较两个数的大小的时候，用c.compareTo(node.item()会更好，如果反过来比较，需要注意将node.item()强制转化为 Comparable类型
4.part 2 中要注意 union()和intersect() 实现的逻辑，第一次做我还是参考了一下github上别人的逻辑，他们的代码在边界处的判定比较巧妙。