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

作业入口：http://www.cs.berkeley.edu/~jrs/61b/hw/hw5/

虽然不难，但又一次写了很久...TAT

我不明白的是interface Comparable里明明没有declare compareTo的内容...为什么我们就可以直接用了？！！！

作业的知识点主要就是：package, interface,linkedList, inheritance,exception

我的Set.java和DList.java的输出如下：

相关链接：      

       【公开课讨论+加分总贴】：UC Berkeley CS 61B Data Structures(in Java)
       【课程网站】：http://www.cs.berkeley.edu/~jrs/61b/
       【视频网站】:【Youtube】【Youku】
        【教材】：Head First Java 【中文版】【英文版】
                      Data Structures and Algorithms in Java, 5th Edition. 【英文版】

收获
0、Set.java 与package list真正体现了protected不作用于package之外。Set.java只能调用list中声明的public函数来调用相关信息。对于set来讲，set看不到list内部数据结构的实现形式：DList或者SList。
1、封装：ListNode加入了List类型的field，使两个class更加紧密的耦合在一起，避免错误的调用外部节点。同样的，这些信息在Set看来，都是隐藏于list之内的。list向外呈现的只有：
inEmpty();length();insertFront();insertBack();front();back();/isValidNode();item();setItem();prev();next(); insertAfter(); insertBefore(); remove();
2、注意方法的归属要准确。
ListNode类：【isValidNode();item();setItem();prev();next(); insertAfter(); insertBefore(); remove();】
List类：【inEmpty();length();insertFront();insertBack();front();back();】
3、接口可以用来引用实现这个接口的对象，这也是接口的意义所在，如Comparable接口。始终注意：“可以引用”不等于“可以调用对象所有属性与方法”----接口的遥控按钮与对象所属类的遥控按钮不一致。
4、Set类的intersection（）函数花了很长时间。原因在于：本质算法没有一步一步的清晰搞懂，只靠模糊的思想写出来的程序必定会有bug！
如：set1与set2求intersection时（升序），思想：set2的每一个元素与set1的元素进行比较，只要比set1元素大，则set1的这个元素删除，同时继续与set1的下一个元素比较，直到不满足set2的这个元素大于set1的元素的情况。这种情况又有2中子情况：==或者<。“==”的时候删除set1的这个元素，set2的元素插入set1后边；“<”的时候set2的下一个元素与该元素进行比较，重复前边操作。注意点：为了防止访问invalidnode，分别对set1与set2的最后一个点进行单独处理，则加入while控制条件，使最后一个点不进入循环体（j>1 / i>1)，则在循环体外检查并操作j==1/i==1的情况。j==1时，有3种情况：< 、==、 >。分别讨论。
5、在调用对象函数前，注意检查是否valid，用if来判断。这之后才能调用相关函数。
6、外部类Set使用DList时，最好用DList的父类类型List声明，以免后期需要使用List的其他子类，如SList类。
7、类DList需要用DListNode（）构造函数来创建新节点时候，避免直接使用DListNode（），而是创建方法method newNode(),在方法中返回DListNode()。这样后期需要使用其他节点类型：如SListNode时候，不需要对DList类中换掉所有DListNode（），只需要在方法newNode中，返回SListNode（）即可。
8、注意Exception的使用。try-catch-finally或者throw exception

gocong 发表于 2016-1-9 05:10
您好，part II 我有个疑问。 set（）构造函数怎么初始化呢？ 我看了看github上code， 都是 new DList（） ...

好吧，我来自己回答吧，做完以后，我发现，List没有构造函数的原因就是作者想让你在这步来决定你用哪个List；所以如果你在这用new SList（）， 那么set就是用SList完成的，用DList就是用DList完成的，但是对于用Set的人完全没影响，他不在乎你真正实现的是SList还是DList。这是你自己选择用List实现了算法的优化。如果有新的developer想用一个更好的List结构，他要做的就是创造一个新的List和ListNode ADT，然后在Set构造函数中引用new 新List（）；

Homework 5Part 1

Part 2

part 2的intersect()要考虑多种边界条件。比如空集的情况；s1.intersect(s2)时，s2触发了exception，s1能不能继续把剩下的元素删掉。
下面是我的test cases，抛砖引玉。

1.   public static void main(String[] argv) {
   
2.     System.out.println("Testing insert()");
   
3.     Set s = new Set();
   
4.     s.insert(new Integer(3));
   
5.     s.insert(new Integer(4));
   
6.     s.insert(new Integer(3));
   
7.     System.out.println("Set s should be { 3 4 }: " + s);
   
8. 
   
9.     Set s2 = new Set();
   
10.     s2.insert(new Integer(4));
    
11.     s2.insert(new Integer(5));
    
12.     s2.insert(new Integer(5));
    
13.     System.out.println("Set s2 should be { 4 5 }: " + s2);
    
14. 
    
15.     Set s3 = new Set();
    
16.     s3.insert(new Integer(5));
    
17.     s3.insert(new Integer(3));
    
18.     s3.insert(new Integer(8));
    
19.     System.out.println("Set s3 should be { 3 5 8 }: " + s3);
    
20. 
    
21.     System.out.println();
    
22.     System.out.println("Tesing union()");
    
23.     s.union(s2);
    
24.     System.out.println("After s.union(s2), s should be { 3 4 5 }: " + s);
    
25.     s2.union(s3);
    
26.     System.out.println("After s2.union(s3), s2 should be { 3 4 5 8 }: " + s2);
    
27.     Set s4 = new Set();
    
28.     System.out.println("Empty set s4 = " + s4);
    
29.     s.union(s4);
    
30.     System.out.println("After s.union(s4), s should be { 3 4 5 }: " + s);
    
31.     s4.union(s);
    
32.     System.out.println("After s4.union(s), s4 should be { 3 4 5 }: " + s4);
    
33. 
    
34.     System.out.println();
    
35.     System.out.println("Tesing intersect()");
    
36.     Set s5 = new Set();
    
37.     Set s6 = new Set();
    
38.     s6.insert(new Integer(1));
    
39.     s5.intersect(s6);
    
40.     System.out.println("{}.intersect({1}) should be { }: " + s5);
    
41.     s6.intersect(s5);
    
42.     System.out.println("{1}.intersect({}) should be { }: " + s6);
    
43.     s6.insert(new Integer(1));
    
44.     Set s7 = new Set();
    
45.     s7.insert(new Integer(1));
    
46.     s7.insert(new Integer(2));
    
47.     s6.intersect(s7);
    
48.     System.out.println("{1}.intersect({1 2}) should be { 1 }: " + s6);
    
49.     s6.insert(new Integer(2));
    
50.     s6.insert(new Integer(3));
    
51.     s6.intersect(s7);
    
52.     System.out.println("{1 2 3}.intersect({1 2}) should be { 1 2 }: " + s6);
    
53.     s6.insert(new Integer(3));
    
54.     s6.insert(new Integer(5));
    
55.     s7.insert(new Integer(4));
    
56.     s7.insert(new Integer(7));
    
57.     s7.intersect(s6);
    
58.     System.out.println("{1 2 4 7}.intersect({1 2 3 5}) should be { 1 2 }: " + s7);
    
59. 
    
60.     System.out.println();
    
61.     System.out.println("Tesing cardinality()");
    
62.     System.out.println("s.cardinality() should be 3: " + s.cardinality());
    
63.     System.out.println("s4.cardinality() should be 3: " + s4.cardinality());
    
64.     System.out.println("s5.cardinality() should be 0: " + s5.cardinality());
    
65.     System.out.println("s6.cardinality() should be 4: " + s6.cardinality());
    
66.     System.out.println("s7.cardinality() should be 2: " + s7.cardinality());
    
67.   }

复制代码

不知道具体 内容。但是许多基本的class, compareTo都是有定义的。你inherit了而且 。

http://docs.oracle.com/javase/7/docs/api/java/lang/String.html

比如说String
All Implemented Interfaces:
Serializable, CharSequence, Comparable<String>

compareTo 是从Object里继承下来的

这个homework我也写了很久。 主要有两点，一个是对接口的 raw type 和 generic type还是没真正掌握
这次作业里我没用泛型，而是用的(Comparable)currentNode.item()).compareTo(c) 这种表达式，也能运行。。。

还有就是Set测试时对涉及空集的case,我改了很久才通过。光用作业里提供的测试数据我还真可能发现不了自己写的方法的缺陷

这次作业也改了很长时间，感觉这门课越来越难了，怎么破
在intersect的时候，为了不超过复杂度，想了很多种方法，代码越写越长，但其实最后真正运行成功的很短
union的时候，还因为一个低级错误，传入参数set s循环的时候，我忘记了写s.head,直接写head，然后陷入死循环，好长时间才找到错误
Part I

Part II

windforce 发表于 2014-6-20 20:56
这个homework我也写了很久。 主要有两点，一个是对接口的 raw type 和 generic type还是没真正掌握
这次 ...

你的测试好详细，赞！
不知道是否方便分享一下你的测试代码，我也想测试一下自己哪些细节不够完善
谢谢~

melissami 发表于 2014-6-28 22:54
你的测试好详细，赞！
不知道是否方便分享一下你的测试代码，我也想测试一下自己哪些细节不够完善
谢谢 ...

其实就是在自带test code 加了个空集的情况，没插入任何数据，直接进行intersect 和 union的测试。

我也不清楚这样算不算完备。 我自己之前的代码对空集的处理有点问题（明明空集交非空集应该为空，我之前运行时会莫名其妙多出一个数据），后来改过来了。

话说lz开始写project2了吗，这个要求2-3个人的小组要怎么做，一个人亚历山大啊:/

我也做了好久。。