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

谢谢楼主的测试代码！看大家的讨论也很有收获！

其实作业并不难，但是在做pt3的时候子类的节点类型思考得比较复杂，因为父类基本上每一个method返回值都是DListNode而不是LockDListNode，实际上只需要对LockDList中newNode这个method进行override就行，另外它的返回值必须是LockDListNode。

shaonan 发表于 2018-3-21 23:35
同学，想请教一下part 2. 不知道我这样理解对不对：当用Dlist实例化出一个list对象后，例如调用了list.re ...

hi, 同学你好～ 前面大家好像都很少说到part2， 我看了一下你说的～ 感觉很有道理；但是 DListNode 是package protected，我们在包外无法调用DListNode的构造方法... 我试着写了写 似乎不能成功编译～～

shaonan 发表于 2018-3-21 23:35
同学，想请教一下part 2. 不知道我这样理解对不对：当用Dlist实例化出一个list对象后，例如调用了list.re ...

不好意思 刚刚又试了一下 虽然 DListNode 的构造函数 是packaged protected， 但是还是可以 构造一个 DListNode对象， 你提供的修改DList 的size参数 很有道理～～ 谢谢

vincentli1 发表于 2018-3-22 01:50
part2我也没想到太靠谱的只通过调用方法就搞乱整个链表的办法。不过我感觉你的想法站得住脚，程序不会遍历 ...

才看到你的回应。。。不好意思。。多谢！

part1难度不大，注意用newNode() “代替” new DListNode()即可
part3 需要进一步理解继承、强制类型转换～ 做的时候没有理解override newNode，一开始以为对 锁住的node 进行cast 其余node还是保持DListNode，做了一天发现根本就不行... 如果按照hw要求的思路就很简单了 所有node的dynamic type都是 LockDListNode，用boolean locked变量作为flag变量 来判断是否可以remove；只需要重写newNode 和remove方法
继承涉及的知识点很细碎，通过实践能够帮助我们更好理解java的多态、如何利用继承提高效率、有利于后期代码维护....^_^
以下是运行结果：

总之，结合lab，越发感觉，好的方法真的会让编程变容易很多，感觉sentinel node真的是特别好用

Part I:



Part II:
个人觉得hw4最难的是Part II，考察对于权限的理解，之前一直没思路，后来看到了第308垅 shaonan 同学的回复，才有了思路，非常感谢这位同学！
GRADER内添加的描述如下：

Due to package protected, application out of the list package cannot violate
the invariant related to the DListNode. But the following 3 methods have some
flaws:

public void insertAfter(Object item, DListNode node) {}
public void insertBefore(Object item, DListNode node) {}
public void remove(DListNode node) {}

The flaw is that these method don't check if the node argument is within the
DList object being called on. They just operate on the node, and then change the
size of the DList object being called on.

For example,

DList list1 = new DList();
DList list2 = new DList();
list1.insertAfter(3, list2.front());

The code will insert a node with item 3 after list2.front(). So it's the list2
that gets inserted, but it's list1 whose size gets changed. Therefore, the
size invariant gets violated.

自己写了一个测试函数，如下：

1. import list.*;
   
2. 
   
3. public class HostialApp {
   
4.     public static void main(String[] args) {
   
5.         DList l1 = new DList();
   
6.         DList l2 = new DList();
   
7. 
   
8.         for (int i = 1; i <= 10; i++) {
   
9.             l1.insertBack(10 + i);
   
10.             l2.insertBack(20 + i);
    
11.         }
    
12. 
    
13.         show(l1, l2);
    
14. 
    
15.         l1.insertAfter(100, l1.front());
    
16.         System.out.println("l1.insertAfter(100, l1.front()); // correct");
    
17.         show(l1, l2);
    
18. 
    
19.         l1.insertAfter(100, l2.front());
    
20.         System.out.println("l1.insertAfter(100, l2.front()); // violate the size invariant for both l1 and l2!");
    
21.         show(l1, l2);
    
22. 
    
23.         l1.remove(l1.front());
    
24.         System.out.println("l1.remove(l1.front()); // correct");
    
25.         show(l1, l2);
    
26. 
    
27.         l1.remove(l2.front());
    
28.         System.out.println("l1.remove(l2.front()); // violate the size invariant for both l1 and l2!");
    
29.         show(l1, l2);
    
30.     }
    
31. 
    
32.     public static void show(DList l1, DList l2) {
    
33.         System.out.println("l1.size == " + l1.length() + ": " + l1);
    
34.         System.out.println("l2.size == " + l2.length() + ": " + l2);
    
35.         System.out.println();
    
36.     }
    
37. }
    

复制代码

输出结果为：



Part III:

我对PartII的理解：

单纯调用methods就能违反invariants。当我们向list添加第一个node时，用insertFront(item)这个方法，而它调用insertAfter()这个方法，这个方法一开始要创造一个新的node，调用newNode()，如果你写newNode(item, node, node.next)，没有任何问题，但如果写insertAfter(item. node, next(node))，即调用next()这个方法代替node.next，运行的时候就会报错。原因在于此时node是head，node.next != next(node)。因为head.next还是head，而根据定义，next(head)不能返回head，只能返回null。所以如果在insertAfter里用next(node)的话，新加的node的next就是null，违反了invariants里面的第2)条。类似地可以调用insertBack()和prev(node)破坏invariants。

不过我也有一点疑问，当list为空时，head能否算作第一个node或最后一个node？

还有一个问题，lockNode()这个方法要permanently locks a node，这个怎么做到？