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

肝完hw4了~

终于写完hw4了……一开始不太懂题目的意思，还是对inheritance理解得不扎实。。。另外在调bug的时候一直卡在一个地方：DList的constructor里写了head = newNode(Integer.MIN_VALUE, head, head)；编译的时候就一直出现nullpointerexception。个人理解是由于编译先读右边的，此时括号里的head参数并不指向head node， 而是无意义的地址（因head的指向还未被定义），因此head.next和head.prev指向不明会报错。

终于在各种网络资源的帮助下做出来了，感觉自己真的是个制杖... 非常感谢楼主、提供test代码的朋友和楼里各位的讨论


补充内容 (2018-8-4 09:56):
截图名字写反了！

Part 1:
Now we are testing DList.
Here is a list after insertBack 6, 9, 12: [  6  9  12  ]

Here is the same list after insertBack(15) and insertFront(3): [  3  6  9  12  15  ]

front() should be 3. It is: 3
front's next should be 6. It is: 6
front's next's prev should be 3. It is: 3
After remove the front, the front() should be 6. It is: 6
After insertBefore() and insertAfter(), The first 3 nodes should be 5,6,8. The list is: [  5  6  8  9  12  15  ]

Here is a list after construction: [  ]
isEmpty() should be true. It is: true
length() should be 0. It is: 0
Here is a list after insertFront(3) to an empty list: [  3  ]
Here is a list after insertBack(5) on an empty list: [  5  ]

Here is a list after insertFront 3, 2, 1: [  1  2  3  ]
isEmpty() should be false. It is: false
length() should be 3. It is: 3
Here is the same list after insertBack(4): [  1  2  3  4  ]

Here is a list after insertBack 6, 7: [  6  7  ]
isEmpty() should be false. It is: false
length() should be 2. It is: 2
Here is the same list after insertFront(5): [  5  6  7  ]





Part 2:
The argument note can be outside the list. After the operation, the list will change its size, but its nodes are not changed actually. In the end, the list have a wrong size.






Part 3:
Now we are testing LockDList.
Here is a list after insertBack 6, 9, 12: [  6  9  12  ]

Here is the same list after insertBack(15) and insertFront(3): [  3  6  9  12  15  ]

front() should be 3. It is: 3
front's next should be 6. It is: 6
front's next's prev should be 3. It is: 3
We lockNode front()= 3
After remove the locked front, the front() should still be 3. It is: 3
After remove the back, the back() should be 12. It is: 12
After insertBefore(3) and insertAfter(3), The first 3 nodes should be 5,3,8. The list is: [  5  3  8  6  9  12  ]

Here is a list after construction: [  ]
isEmpty() should be true. It is: true
length() should be 0. It is: 0
Here is a list after insertFront(3) to an empty list: [  3  ]
Here is a list after insertBack(5) on an empty list: [  5  ]

Here is a list after insertFront 3, 2, 1: [  1  2  3  ]
isEmpty() should be false. It is: false
length() should be 3. It is: 3
Here is the same list after insertBack(4): [  1  2  3  4  ]

Here is a list after insertBack 6, 7: [  6  7  ]
isEmpty() should be false. It is: false
length() should be 2. It is: 2
Here is the same list after insertFront(5): [  5  6  7  ]

override 了newnode()和remove（）两个办法。通过override newnode()实现了LockDList里面的node实际上都是LockDListNode，因此其他办法返回的DlistNode都可以做cast.

czbnlzd920706 发表于 2015-4-27 08:28
这次作业一开始轻视了。然后做到part3的时候才发现，有难度，而且难度不在于算法构造，而在于对于Java多态 ...

感谢分享，很有用的信息

第三部分有些难，看了回复里第一个的同学@czbnlzd920706很有启发，感谢！

感谢楼主的测试代码！感谢2楼大佬对于多态的分析，自己来谈谈对于hw4以及对多态的理解：
P1：一开始对于List和DList的理解并不够透彻，首先单链表中head.item就开始存储数据，而双链表中head.item=null，从head.next.item才开始存储数据，在执行insert或者remove操作时务必要size++或者size--；P1中DList的构造器如何创建head node很重要，代码是：
Public DList(){
Size=0;
head=newNode(null,null,null);
head.next=head;
head.prev=head;
}
这里head=newNode(null,head,head)和head=newNode(null,null,null)是等价的，如果是head=newNode(null,head,head)，那么一开始head本来就是null，然后执行newNode()时在heap中创建了一个空间，该空间中item默认为item，prev和next均等于head等于null，然后该空间的地址返回给head，head才不等于null，这一句执行完之后head.prev和head.next均为null，所以后面两行代码必须要有；
关于remove函数自己有一问题尚未弄懂：能否remove head节点？
P2：个人没什么主见，也是看了地里的帖子，说在remove的过程中因为没有检查node是否存在从而造成size的减少；
P3：二话不说，直接上继承和多态：
1.重写：输入参数（类型、数目等）相同，返回值类型一般相同，注意！！！我在此作业就碰到返回值类型不同的重写，但是这两种返回值是父类和子类的关系，具体就是重写method的返回值类型属于子类，，，这个也是重写，，，这个也会发生多态！！
2.重载：输入参数不同，返回值类型可相同可不同，重载和多态关系就不大了吧？因为感觉是完全不同的method了；
3.只有一种情况会发生多态：（1）向上转型即父类引用指向子类对象（2）非静态method发生了重写（如果是静态method不会出现多态），这种情况又叫做覆盖；
4.与覆盖对应的是隐藏，子类继承了父类的field和static method，并且子类修改了field和static method，此时不会发生多态，举例：Father f=new Son();此时若引用f.field或者f.method(static)，其结果不是son中的field和method的结果，而是Father中的field和method；
5.继承的时候，private的field和method不能继承，不同package也不能继承；
6.关于构造器：若父类有默认构造器，则子类可以不用super，若父类没有显示默认无参构造器，则子类必须用super，且super必须位于构造器第一行；
7.子类向上转型为父类可以自动转，但是父类要向下转型为子类当且仅当父类的本质仍然是子类；子类转型为父类时非静态method会发生多态，而field和静态method则要重新使用父类的，（父类转型为子类时可使用子类的field、method？，这一部分目前还不太清楚，也没怎么碰到）
下面说正式作业部分：
DList中的newNode返回值类型为DListNode，而LockDList中的newNode返回值类型为LockDListNode，考虑到LockDListNode是DListNode的子类，因而LockDList中的newNode函数可以看成是发生了重写，从而导致多态，具体体现如下：
TestLockList中：
LockDList sl1 = new LockDList();
由于多态sl1的head为LockDlistNode类型，后来我们逐渐插入数据：
sl1.insertBack(new Integer(6));
在insertBack函数中，注意这一行：
DListNode node=newNode(item,head.prev,head);
newNode创建的LockDListNode被向上转为DListNode类型，即它的“本质”还是子类；
于是最终的sl1的各节点中，head为LockDListNode，而其余节点为DListNode，但是本质都是LockDListNode。
newTest函数中的第一行代码个人觉得可以作如下修改：
DListNode node = sl1.front();
这样得到的sl1.front()仍然是本质为LockDListNode的DListNode类型节点。

然后将此node送入lockNode函数：
sl1.lockNode(node);
这是我的lockNode函数：
   public void lockNode(DListNode node) {
    ((LockDListNode)node).locked=true;
   }
注意，送入的是DListNode类型节点，但是要访问子类对象（locked），必须要向下转为子类类型，而向下转的前提是该父类节点本质仍然是子类节点，满足条件，因而((LockDListNode)node).locked=true;这个代码是合理的，至此结束。
Hw4自己想了很长时间，依然还有一些地方没有完全明白，自己也会多次复习，希望每次都有新的收获，当然更希望和大家交流、探讨、相互指正！！
贴图：

喜欢这个作业！马上就把课上得东西理清楚了

一.part1整体比较简单 但是要注意几点 1.我们创建head这个哨兵结点的时候，要注意 head=newNode(item,null,null)，再重新设置head.next=head;  head.prev=head;否则会有空指针的错误，实际上如果我们用head=newNode(item,head,head) ,我们知道程序是从右往左走的，因此当head没有被指定赋予一个object的时候，head还是为null,因此不管我们用哪一种，我们都要加上head.next=head;  head.prev=head;这样才完成了一个 cycle linkedlist
2.注意删除增加结点的时候不要忘了size++或者size--

part3一开始感觉比较容易，但是真正自己去做的时候才发现是自己天真烂漫了，下面先总结一下我认为比较容易被忽视，相对有价值的point
1.子类继承的要求 (1)method参数与method返回值要与父类的method定义一致
    (2)子类中的method不能less accessible，意思是子类方法的访问性必须和父类一样或者更加friendier

2.比如father类的remove方法和son类的remove方法不一样，father f=new son()之后f.remove是son的方法
when we invoke overridden method, Java calls methods for ojbect dynamic type, regardless of static type 这个是老师上课的笔记

3.overload与继承和多态没关系 只是method碰巧有了一样的名字

4.简单的说 多态是指variable reference 和object的类型可以不一样 比如 Animal mydog=new Dog();
variable reference的类型是 Animal，但是我们在heap中创造的对象是Dog

5.instance variable 没有被子类overridden 因为他们不需要，他们没有定义任何具体的行为

6.只有构造器才必须把super放在第一行，method没有这个规定

7.当子类继承父类时，什么会被继承过来：
super类中的protected,public都可被子类继承，包括field 和 method.
同时，父类的构造器不能被继承，但必须被子类构造器调用！

8.shadowing 与 overrding 不一样，shadowing是指子类覆盖了父类中的field 或者静态方法，此时
老师上课说过  choice at methods dictated by dynamic type
   choice of fields dictated by static type
即如果我们 Father f=new Son();  假设Father一个 int x=2 的field，son重写了这个field 并且 int x=4
那么f.x=2  ((Son)f).x=4  

9. "final" method-> cannot be overridden
"final" class -> cannot be be extend

然后我们来看下作业的要点
1.我们在写LockListNode时候其实只需要加一个 boolean islocked的field就可以，其他的field variable（结点的prev结点和next结点）我们用父类的field variable即可
2.在LockListNode中，我们构建constructor的时候，直接调用父类的方法，并且设置islocked=false 即可；
3.在LockDList中，我们也不需要加多余的field variable（即我们不需要写 LockDList head)，同1，我们直接继承父类的属性即可
4.readme.pdf中提到（由于父类的构造器是不能继承的），第一个我们需要重写的是newNode方法，并且我们newNode方法的返回值是LockDListNode。
这样的话，当我们调用 LockDList sl1=new LockDList() 的时候，我们的head结点的static type是 DListNode，然而实际上heap中的对象是LockDListNode，自动完成了从子类到父类（超类）的转型这样我们在LockDList中直接可以继承大部分DList中的method，并且运行不会出错。比如insertEnd方法，我们在方法中每次插入结点的时候都将结点定义为DListNode的static type，但是由于我们重写了 newNode()方法，每次实际上在heap中创建的对象都是LockDListNode类型。
5.我们重写remove()方法的时候，传入的parameter的类型是DListNode，这个在readme.pdf中也强调不能被修改
现在问题来了：我们在其他方法中都不需要用到LockDListNode的islocked这个field，但是在remove方法中我们需要用到了，如果我们传入的这个node还是DListNode，是无法访问islocked的，
因此我们需要强制转型，将node这个披着DListNode的羊皮给扒掉，cast为LockDListNode的狼毛，（前面也提到过，实际上在heap中每个node都是创建为LockDListNode），这样转换后
我们就可以访问islocked方法。
6. 我们理解了5后，在lockNode方法中，也会很清晰的理解我们同样需要一个转型

最后要致谢所有之前总结知识点的同学，让我对java的多态、封装、继承有了一个更加深刻的理解，并且知道如何在实际问题中应用。
以上自己写的要点可能存在错误或者疏漏，后来的同学也要带着批判，思考的态度来看待。如有错误，还望同学指出，不吝赐教，感谢~