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

Part 1: DList:


Part2: LockList


搞定～求加学分～

part2弄了很久，最后有借鉴网上的程序。要在LockDListNode里面call DListNode 的constructor，因为构造函数不能被继承，应该用super去调用父类的构造函数。
LockDlist里面需要把所有的DListNode 的Node全部改成LockDListNode类型。这是因为在父类里面的method和parameter都是DListNode，这里用到了多态的概念，父类里声称的变量可以reference子类的对象。因此除了lockNode和remove method之外，其他父类的method子类都可以直接call了。
remove method 是override父类的method, 当需要移除的node不是locked的时候，用super父类的方法来做就好啦。
因为是自己看的各种资料和想象，可能有不对的地方，哪里说错了还请指正。

LockDList中需要override的method是newNode和remove，涉及到了Polymorphism，很容易出错。
个人觉得要规避Polymorphism造成的bug，需要注意两点：一是不能把superclass的reference赋值给subclass的reference；二是不能用superclass的reference去调用subclass中新增的methods或fields。
在这次作业中还学到了另外一点就是overridden method的return type可以是subclass

在如何实现locked功能这块卡了很久，突然发现自己简直就是sb

LockDList其实只需要newNode，lockNode, remove三个method，newNode的使用很巧妙呀，做第一部分的时候就有提到newNode是为了减少override method的部分，有打下伏笔，小作业大智慧~哈哈测试结果都差不多，上传一个好了

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

http://www.1point3acres.com/bbs/ ... icid=6274#pic_block

http://www.1point3acres.com/bbs/ ... icid=6275#pic_block

Part3有点tricky， 通过override newNode() 来构造LockDList，然后再进行后面的操作。
一开始想直接把DListNode转换为LockDListNode来利用其中的isLocked这个field进行判断，结果编译器报出cast的错误。其本质是这个Object就是DListNode不能直接cast。
如果想实现cast，那么这个Object必须是LockDListNode，所以只能从源头开始思考就是newNode();
我们可以开始写这个newNode(), 但是它的返回值其实可以是他的父类或者父类的之类。

1.     /*
   
2.     protected LockDListNode newNode(Object item, DListNode prev, DListNode next) {
   
3.         return new LockDListNode(item, prev, next);
   
4.     }
   
5.     */
   
6. 
   
7.     protected DListNode newNode(Object item, DListNode prev, DListNode next) {
   
8.         return new LockDListNode(item, prev, next);
   
9.     }

复制代码

这两种情况都可以通过编译，这一点一些书本上可能有些不同。
如果return type是DListNode， 实质山就是将LockDListNode cast成 DListNode；

改变了return type后，本质每个node都是LockDListNode。
如果需要引用LockDListNode的值，就可以将DListNode cast成 LockDListNode。

其实，这里考虑的一个问题就是 reference variable 的作用， 按照head first java本质相当于一个遥控器， 用来搜寻method， 当你将本质是LockDListNode cast成 DListNode， 实际上得到的是哪个小遥控器， 只能操控DListNode的方法。 只有将其重新cast为LockDListNode，才可以调用里面的method和field。

1. /Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/bin/java "-javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=55065:/Applications/IntelliJ IDEA CE.app/Contents/bin" -Dfile.encoding=UTF-8 -classpath /Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/charsets.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/deploy.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/cldrdata.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/dnsns.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/jaccess.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/jfxrt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/localedata.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/nashorn.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/sunec.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/sunjce_provider.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/sunpkcs11.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/zipfs.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/javaws.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/jce.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/jfr.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/jfxswt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/jsse.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/management-agent.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/plugin.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/resources.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/rt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/ant-javafx.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/dt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/javafx-mx.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/jconsole.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/packager.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/sa-jdi.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/tools.jar:/Users/Lim/@inbox/cs61b14/hw/hw4/out/production/hw4 list.TestDList
   
2. Now we are testing DList.
   
3. Here is a list after insertBack 6, 9, 12: [  6  9  12  ]
   
4. 
   
5. Here is the same list after insertBack(15) and insertFront(3): [  3  6  9  12  15  ]
   
6. 
   
7. front() should be 3. It is: 3
   
8. front's next should be 6. It is: 6
   
9. front's next's prev should be 3. It is: 3
   
10. After remove the front, the front() should be 6. It is: 6
    
11. After insertBefore() and insertAfter(), The first 3 nodes should be 5,6,8. The list is: [  5  6  8  9  12  15  ]
    
12. 
    
13. Here is a list after construction: [  ]
    
14. isEmpty() should be true. It is: true
    
15. length() should be 0. It is: 0
    
16. Here is a list after insertFront(3) to an empty list: [  3  ]
    
17. Here is a list after insertBack(5) on an empty list: [  5  ]
    
18. 
    
19. Here is a list after insertFront 3, 2, 1: [  1  2  3  ]
    
20. isEmpty() should be false. It is: false
    
21. length() should be 3. It is: 3
    
22. Here is the same list after insertBack(4): [  1  2  3  4  ]
    
23. 
    
24. Here is a list after insertBack 6, 7: [  6  7  ]
    
25. isEmpty() should be false. It is: false
    
26. length() should be 2. It is: 2
    
27. Here is the same list after insertFront(5): [  5  6  7  ]
    
28. 
    
29. Process finished with exit code 0
    

复制代码

1. /Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/bin/java "-javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=55074:/Applications/IntelliJ IDEA CE.app/Contents/bin" -Dfile.encoding=UTF-8 -classpath /Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/charsets.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/deploy.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/cldrdata.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/dnsns.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/jaccess.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/jfxrt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/localedata.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/nashorn.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/sunec.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/sunjce_provider.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/sunpkcs11.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/zipfs.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/javaws.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/jce.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/jfr.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/jfxswt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/jsse.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/management-agent.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/plugin.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/resources.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/rt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/ant-javafx.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/dt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/javafx-mx.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/jconsole.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/packager.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/sa-jdi.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/tools.jar:/Users/Lim/@inbox/cs61b14/hw/hw4/out/production/hw4 list.TestLockDList
   
2. Now we are testing LockDList.
   
3. Here is a list after insertBack 6, 9, 12: [  6  9  12  ]
   
4. 
   
5. Here is the same list after insertBack(15) and insertFront(3): [  3  6  9  12  15  ]
   
6. 
   
7. front() should be 3. It is: 3
   
8. front's next should be 6. It is: 6
   
9. front's next's prev should be 3. It is: 3
   
10. We lockNode front()= 3
    
11. After remove the locked front, the front() should still be 3. It is: 3
    
12. After remove the back, the back() should be 12. It is: 12
    
13. After insertBefore(3) and insertAfter(3), The first 3 nodes should be 5,3,8. The list is: [  5  3  8  6  9  12  ]
    
14. 
    
15. Here is a list after construction: [  ]
    
16. isEmpty() should be true. It is: true
    
17. length() should be 0. It is: 0
    
18. Here is a list after insertFront(3) to an empty list: [  3  ]
    
19. Here is a list after insertBack(5) on an empty list: [  5  ]
    
20. 
    
21. Here is a list after insertFront 3, 2, 1: [  1  2  3  ]
    
22. isEmpty() should be false. It is: false
    
23. length() should be 3. It is: 3
    
24. Here is the same list after insertBack(4): [  1  2  3  4  ]
    
25. 
    
26. Here is a list after insertBack 6, 7: [  6  7  ]
    
27. isEmpty() should be false. It is: false
    
28. length() should be 2. It is: 2
    
29. Here is the same list after insertFront(5): [  5  6  7  ]
    
30. 
    
31. Process finished with exit code 0
    

复制代码