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

做完HW5了，要抓紧时间了，快点刷完61B，来领学分~

gocong 发表于 2016-1-14 07:48
好吧，我来自己回答吧，做完以后，我发现，List没有构造函数的原因就是作者想让你在这步来决定你用哪个Li ...

1－－List没有构造函数，是因为List是abstract class，不能用（new＋构造函数）来实体化。
2－－另外一点，我倒觉得老师给出的ListNode的实例参数不好，不应该把List myList这个变量声明放在ListNode这个abstract class中的。因为：在后续实现SListNode或DListNode的方法时，凡是涉及到用超类List引用DList或SList时，每次都需要强制转换［ 如  ((DList)myList).newNode();  ］。如此这般并非继承的意义，我觉得ListNode这个抽象类中只需要含有int size即可，在继承它的子类DListNode／SListNode中分别加入有自己特色的DList mylist／SList mylist会更好。

继续继续~~

收获
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

看到复杂度的要求设计出算法并不难，主要是一些封装、继承的关系容易搞不清楚。

做了挺久，小错误太多，总是会碰到Exception的问题，还有就是要注意封装接口的问题，有时候容易调用到package里面protected的东西

感谢althinking 分享的测试代码，让我发现了corner case的小问题~
debug了好久。。。特别是insert()

每次做完作业，对professor的敬仰之情都加深一份，作业设计得太好了！

               

做完后还有一个疑问，求大神指点

在union() method 中，有这样一句代码，请问这是“shallow copy” 吗？

ListNode thisNode = this.list.front();

ListNode otherNode = s.list.front();

......

thisNode.insertBefore(otherNode.item());                // ??? shallow copy

otherNode = otherNode.next();        

.....                        

如果是，那怎么实现 "deep copy"呢？

我试了：

• Object o = new Object(otherNode.item());     // 不行，object的constructor 只有Object()
• Object o = new Object();
  

   o =  otherNode.item();                       // 不行，这还是 shallow copy啊

大概是花时间最多的一次作业了，主要是union函数的边界条件。先去睡觉了，明天再来分析作业心得。。。
补充：

说说一开始犯的几个错误吧。
1. DList的构造函数：head = newNode(null, null, null, null)。一开始写成head = newNode(null, this, null, null)，当时写this的时候，感觉怪怪的，够来改过来发现能够运行正确，但是理由还是说不上来，请高人指点。
2. 因为ListNode类里面几个对node进行操作的函数，都涉及到throws InvalidNodeException，所以在Set类的时候，如果使用到这几个对node操作的函数，一定要写try, cathc语句。
3. 设置Set的num这个field。一开始我直接使用List里的size，后来发现这样不对。这里认识到protected的作用，protected只能被子类或者同一个package下的类使用。所以要想表达Set里面的元素个数，就只能在declare一个num。
4. 因为在ListNode类中增加了myList这个field，myList是List类。在具体实现DListNode类的时候，新建节点使用newNode方法，而这个newNode方法是在DList中定义的，所以我们要显示类型转换，这个myList是一个DList，才能使用newNode方法。就像下面这样：
this.next = ((DList)myList).newNode(item, (DList) myList, this, this.next);
5. 在Set里面，insert方法插入的是一个Comparable类的对象，自带了compareTo()方法。但是在实现union和intersect的时候，需要比较两个Set的中的链表的节点的Item的大小，item是object类，没有compareTo()方法。但是，它本质是comparable类的对象，这是我们在insert方法里做的，所以这里要使用显示类型转换，（Comparable）this.list.front().item，这样这个就是一个Comparable对象，可以使用compareTo()方法。
6. Union实现的算法。这个题目要求是不允许copy this这个Set，也就是说，要直接在this本身上进行操作，这样好处不需要再额外开辟空间，但是给编程带来一些不便。我的算法是先考虑掉两种特殊情况，即一个Set的最大值比另一个Set的最小值要小，或者是一个Set的最小值比另一个Set的最大值要大，这样可以直接进行插入操作。但是具体实现起来还有点复杂，下面我只说一下s最小值大于this最大值的情况。1）s只有一个元素，并且等于this最大值，不需要操作，直接结束。2）s只有一个元素，并且大于this最大值，直接把这个元素插入this最后一个元素后面，结束。3）s不只一个元素，我们首先判断一下第一个元素是否和this最大值相等，如果相等就跳过这个元素，下面正常处理把s后面的元素依次插入this最后一个元素的后面。
处理完特殊情况后，一般情况的算法是这样：用两个变量nt和ns来遍历this和s中的链表。只要s中的元素小于this的元素，肯定插入，并且ns向后移动一位。s中的元素大于this的元素，nt向后移动一位。s中的元素等于this中的元素，ns和nt都向后移动一位。这样一直到最后，肯定有一个链表被遍历完，然后我是分情况讨论，三种情况：this被遍历完但s没有被遍历完，其实就是把s身下的元素插入到this最后一个元素的左边还是右边。s被遍历完但是this没有遍历完，其实就是把s最后一个元素插入到this剩下的元素里去。s和this都刚好被遍历完，其实就是this最后一个元素和s最后一个元素比较大小，谁前谁后。
7. intersect函数写起来就要比union快多了，没有Union的两种特殊情况。还是像union中那样遍历，s中比this中大，此时this中的该元素一定被删除。s中比this中的小，ns向后移动一位。两者相等，ns和nt都向后移动一位。最后还是要处理遍历完的情况。这里不再赘述。有一点是怎么样remove一个点。我之前是直接nt.remove()，发现抛出异常，后来发现应该是先保存nt.next()，然后再nt.remove(),最后把暂存的引用赋回nt。
8. 源代码中提供的测试集不够丰富，大家可以自己试试多种边界情况。