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

jaly50 · 2014-06-03

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

本帖最后由 yingy4 于 2016-5-21 20:17 编辑

作业入口：http://www.cs.berkeley.edu/~jrs/61b/hw/hw4/
所需知识点包括 java package, inheritance, linked list

这次的作业没有给测试数据，所以我把以前SList.java的测试数据改了一下，拿来用。
小伙伴们交作业可以试试用我的测试代码，看看能不能过~~~（测试代码有问题的话要提出来噢...）
或者欢迎小伙伴上传自己的测试数据！！

后面的小伙伴可以用我的测试代码测试一下DList和LockDList的正确性。
测试数据链接:http://pan.baidu.com/s/1dD5ql4P
下载TestDList.java, TestLockDList.java, TestHelper.java 放在你们的list文件夹，然后运行TestDList 和TestLockDList就可以啦！！！

汇总下面同学指出的问题：在TestLockDList.java中，newtest(LockDList sl1)方法，其中node和back应该定义为DListNode类型才符合本作业原本的要求，请各位同学注意并自行修改，再次感谢 jaly50 同学提供的测试代码。——by yingy4

//Line 122
LockDListNode node = sl1.front(); //Wrong
DListNode node = sl1.front(); //Right
//Line 135
LockDListNode back = sl1.back(); //Wrong
DListNode back = sl1.back(); //Right

复制代码

那我就贴个TestDList和TestLockDList的输出图吧：

相关链接：

   【公开课讨论+加分总贴】：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. 【英文版】

czbnlzd920706

这次作业一开始轻视了。然后做到part3的时候才发现，有难度，而且难度不在于算法构造，而在于对于Java多态，继承的理解，对超类转子类，子类转超类的理解。还有，为什么用继承对于工程设计来说会更加方便。所以正好在这里总结下，方便以后自己回头复习。
1.子类转超类
Father father = new Son();
此时，是向上转型。Son是子类，相较于父类来说，其功能更加强大复杂。但是向上转型后，父类中不存在但子类中存在的方法不会被包含到对象中，同时子类的field也不会被包含到该对象中。如果子类的某个方法与父类完全相同（返回值类型也必须相同），那么，该引用中的该方法会被重写（overrride）。但是，即使是相同名字的field，也不会被重写。也就是说，我们虽然用父类引用接收了子类对象，但我们却可以使用具有子类特色的方法。正如此题中，我重写了 remove(),newNode()方法。
overload，重载。指的应该是，完全重新构造了一个同名的方法，但该方法的返回值类型和输入参数与父类必须都不同。如果输入参数相同但返回值类型不同，我测试过，编译器错误。
重载(overload)时，同名同参数的方法，其返回值类型必须与父类相同，并且，其权限必须更高！
比如说，父类是protected，子类必须是protected or public. 若父类是public，则子类必须是public。
另外，子类转超类必须要明白的一点是，（此处摘抄自网络博客）
当我们用一个类型的构造器构造出一个对象时，这个对象的类型就已经确定的，也就说它的本质是不会再发生变化了。各种类型的转换，只不过是他的能力被临时消弱了而已（能力被削弱的意思是你访问这个对象用的指针能看到这个对象的多少的功能，虽然这个对象有很多的功能摆在那里），其本质的东西并没有任何的变化（这句话是重点）。

所以说，father 这个引用所指的内存块仍然包含那些子类特有的方法，但是该引用"看不见"这些方法。

2.超类转子类
Father father = new Father();
Son son = (Son) father;
这个情况下编译器会报错， Cast Exception
正如我刚说的，超类可以强制转换为子类，但前提要求是，该超类其本质（额。。自学的，所以专业术语不到位，见谅。。）必须是子类。
所以这么做是对的：
Father father = new Son();
Son son = (Son) father;

3.extends
当子类继承父类时，什么会被继承过来：
super类中的protected,public都可被子类继承，包括field 和 method.
同时，如果子类自己的某个field或者method与父类完全相同（prototype），那么，该field或method将会覆盖父类相对应的field或method。
同时，父类的构造器不能被继承，但必须被子类构造器调用！

public class Father {
int a;
public Father(int x) {
   this.a = x;
}
}

public class Son extends Father {

}
报错。编译器会寻找Son类中的构造函数。但是没找到，就执行default constructor，
Son() { }
然后编译器进入该构造器。他没有发现super关键字，默认执行 super();（构造函数不能被继承，但必须被调用！）
然后去父类中找super()构造函数。没找到。于是就会报错。
所以应该是，
public class Son extends Father {
   Son(int x) {
      super(x);
   }
}

我之前在想，为什么一定要在子类构造器中最先一步，调用父类构造器。现在觉得，通过调用父类构造器，将子类从父类那里继承过来的成员先按照父类的规则进行初始化。然后，再由我们自己进一步设计具有该子类特色的初始化方式。

之前一直对继承这个东西用处多大，不是很清楚。现在的想法是：
一开始我设计了DList,DListNode这样的最基本的链表。功能也是最基本的。
后来用着用着发现不够用了，需要添加一些新的功能，比如，锁住某些节点让其不能被删除。
于是我新写了一个类LockDListNode extends DListNode. 然后里面加入了boolean isLocked。
但是如果仍使用DList中的方法insert,remove,forward,back....来处理LockDListNode.就会发生类型转换错误。
我一开始的想法是，用lockNode方法来处理。将那些需要lock的node由DListNode强制转换为LockDListNode.然后报错了，因为传入的DListNode其本质还是DListNode...不是 LockDListNode.所以不能强制转换。
所以必须想一种方法，在LockDList中每次生成新的结点时，该结点必须都是LockDListNode类型，然后返回值是DListNode,从而在返回过程中完成向上转型。之后，那些方法虽然传入的仍然是DListNode类型，但其本质已经全部变成了LockDListNode类型。这个时候我才发现了 newNode() 的作用。老师让我们生成所有结点不要通过DListNode的构造器，而是通过这个newNode()来调用.就是因为该newNode()可被子类重写，创建出新的类型的结点。然后之后的其他链表操作可以完全继承不用改写，依然可以正常工作。(当然除了remove() )
所以我觉得楼主给的测试代码中，TestLockDList.java 有块地方有问题.
newtest(LockDList sl1)中，不应该用LockDListNode来接收 s11.front()的返回值。而应该用 DListNode 来接收，这才能体现出Java三大特性，封装，多态，继承，给软件设计带来的方便。我们不需要知道LockDListNode到底是怎么实现的，甚至不用知道LockDListNode这个类的名字。这些都有其他人写好。然后我们直接使用LockDList来完成我们需要的操作，同时依然用DListNode来接收相应操作返回的结点，其实此时这些结点的本质已经发生了改变，但Java保证我们依然可以用超类来接收他们。

不知不觉写了这么多。之前在阿里的同学和我说，Java的多态和继承是面试必考题，所以学得比较认真。但是自学的毕竟也是自学的，术语什么的都不到位，理解肯定也有错误。欢迎讨论。
附上我参考的几个博客，写的都很好。可以看下。
http://www.cnblogs.com/chenssy/p/3393160.html
http://www.cnblogs.com/chenssy/p/3372798.html
http://www.cnblogs.com/stemon/p/3394464.html

wynnforce

本帖最后由 enirinth 于 2015-5-25 16:08 编辑

先贴作业~~~TestDList:

TestLockDList:

要override的函数:
remove()和newNode()是自然,另外要改front()和back():

public LockDListNode front() {
return (LockDListNode)(super.front());
}

复制代码

1.我感觉很多人有误解,题目总强调method signature不变.实际上signature仅仅是只函数名+param list. signature是不包含return type的....你总可以在overriden的函数里return一个more specific的return type. 不敢改return type会导致写不出来...
2.front和back的return type要改是因为method call严格按照static type,这是个资格问题;虽然call的实际内容是dynamic type.

求加分呀求加分~~~冲击高农中.....

lyc1994

dennisyang 发表于 2015-7-14 09:43
为啥我compile DList.java的时候会报错说 DListNode找不到符号呢？我已经compile DListNode.java了啊有c ...

可以试试javac -g list/*.java，同时编译所有.java文件，而不要分别编译。

melissami

本帖最后由 melissami 于 2014-6-11 21:03 编辑

这个写了好久，还是调不出来，LockDList依然有错

package list;
public class LockDList extends DList {
protected LockDListNode head;
protected LockDListNode tailnode;
//protected LockDListNode temp;
protected DListNode newNode(Object item, DListNode prev, DListNode next) {
DListNode nnn = new LockDListNode(item,prev, next);
return nnn;
}
public LockDList() {
//super class constructor called by default
}
public void insertFront(Object item) {
super.insertFront(item);
}
public void remove(DListNode node) {
LockDListNode curr = this.head;
while(curr.next != head){
if(curr.item == node.item && curr.prev == node.prev && curr.next == node.next){
if(curr.lockstatus == false){
super.remove(node);
}
}
curr = curr.next;
}
}

复制代码

在这一行会出错
while(curr.next != head){
java.lang.NullPointerException

明明现在curr不是空，这个list已经有5个item了，为什么curr.next会说是空指针呢？
其他的function，比如insertFront, insertBack之类的都是直接继承super class，没有修改，不知道这样可行咩~

输出如下（借用的lz的test case）：

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
lockNode: size is: 5
Exception in thread "main" java.lang.NullPointerException
      at list.LockDList.lockNode(LockDList.java:45)

感觉还是我的继承有问题，但是不知道怎么改:/

我把DList代码也贴上来吧，方便挑错

实在不行，我过两天再删掉~

/* DList.java */
package list;
/**
* A DList is a mutable doubly-linked list ADT. Its implementation is
* circularly-linked and employs a sentinel (dummy) node at the head
* of the list.
*
* DO NOT CHANGE ANY METHOD PROTOTYPES IN THIS FILE.
*/
public class DList {
/**
* head references the sentinel node.
* size is the number of items in the list. (The sentinel node does not
* store an item.)
*
* DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
*/
protected DListNode head;
protected DListNode tailnode;
protected int size;
protected DListNode temp;
/* DList invariants:
* 1) head != null.
* 2) For any DListNode x in a DList, x.next != null.
* 3) For any DListNode x in a DList, x.prev != null.
* 4) For any DListNode x in a DList, if x.next == y, then y.prev == x.
* 5) For any DListNode x in a DList, if x.prev == y, then y.next == x.
* 6) size is the number of DListNodes, NOT COUNTING the sentinel,
* that can be accessed from the sentinel (head) by a sequence of
* "next" references.
*/
/**
* newNode() calls the DListNode constructor. Use this class to allocate
* new DListNodes rather than calling the DListNode constructor directly.
* That way, only this method needs to be overridden if a subclass of DList
* wants to use a different kind of node.
* @param item the item to store in the node.
* @param prev the node previous to this node.
* @param next the node following this node.
*/
protected DListNode newNode(Object item, DListNode prev, DListNode next) {
return new DListNode(item, prev, next);
}
/**
* DList() constructor for an empty DList.
*/
public DList() {
// Your solution here.
head = newNode(null, null, null);
head.next = head.prev = head;
//tailnode = head;
size = 0;
}
/*
public DList returnDList(){
return this;
}
*/
/**
* isEmpty() returns true if this DList is empty, false otherwise.
* @return true if this DList is empty, false otherwise.
* Performance: runs in O(1) time.
*/
public boolean isEmpty() {
return size == 0;
}
/**
* length() returns the length of this DList.
* @return the length of this DList.
* Performance: runs in O(1) time.
*/
public int length() {
return size;
}
/**
* insertFront() inserts an item at the front of this DList.
* @param item is the item to be inserted.
* Performance: runs in O(1) time.
*/
public void insertFront(Object item) {
// Your solution here.
//DListNode temp;
if(size == 0){ // if list is empty
tailnode = newNode(item, null, null);
tailnode.prev = tailnode.next = head;
head.prev = head.next = tailnode;
//tailnode = temp;
size++;
}else{
temp = newNode(item, null, null);
temp.prev = head;
temp.next = head.next;
head.next = temp;
//(head.next).prev = temp;
(temp.next).prev = temp;
size++;
}
}
/**
* insertBack() inserts an item at the back of this DList.
* @param item is the item to be inserted.
* Performance: runs in O(1) time.
*/
public void insertBack(Object item) {
// Your solution here.
//DListNode temp;
if(size == 0){ // if list is empty
tailnode = newNode(item, null, null);
tailnode.prev = tailnode.next = head;
head.prev = head.next = tailnode;
size++;
}else{
temp = newNode(item, null, null);
temp.next = head;
temp.prev = tailnode;
tailnode.next = temp;
tailnode = temp;
head.prev = tailnode;
size++;
}
}
/**
* front() returns the node at the front of this DList. If the DList is
* empty, return null.
*
* Do NOT return the sentinel under any circumstances!
*
* @return the node at the front of this DList.
* Performance: runs in O(1) time.
*/
public DListNode front() {
// Your solution here.
if(isEmpty() == true){
return null;
}else{
return head.next;
}
}
/**
* back() returns the node at the back of this DList. If the DList is
* empty, return null.
*
* Do NOT return the sentinel under any circumstances!
*
* @return the node at the back of this DList.
* Performance: runs in O(1) time.
*/
public DListNode back() {
// Your solution here.
if(head.next == head){
return null;
}else{
return tailnode;
}
}
/**
* next() returns the node following "node" in this DList. If "node" is
* null, or "node" is the last node in this DList, return null.
*
* Do NOT return the sentinel under any circumstances!
*
* @param node the node whose successor is sought.
* @return the node following "node".
* Performance: runs in O(1) time.
*/
public DListNode next(DListNode node) {
// Your solution here.
if(isEmpty() == true){
return null;
}else{
return node.next;
}
}
/**
* prev() returns the node prior to "node" in this DList. If "node" is
* null, or "node" is the first node in this DList, return null.
*
* Do NOT return the sentinel under any circumstances!
*
* @param node the node whose predecessor is sought.
* @return the node prior to "node".
* Performance: runs in O(1) time.
*/
public DListNode prev(DListNode node) {
// Your solution here.
if(isEmpty() == true){
return null;
}else{
return node.prev;
}
}
/**
* insertAfter() inserts an item in this DList immediately following "node".
* If "node" is null, do nothing.
* @param item the item to be inserted.
* @param node the node to insert the item after.
* Performance: runs in O(1) time.
*/
public void insertAfter(Object item, DListNode node) {
// Your solution here.
//DListNode temp;
if(node.item != null){
if(node == tailnode){
temp = newNode(item, null, null);
temp.prev = node;
temp.next = head;
node.next = temp;
tailnode = temp;
size++;
}else{ // not the end of DList
temp = newNode(item, null, null);
temp.prev = node;
temp.next = node.next;
node.next = temp;
size++;
}
}
}
/**
* insertBefore() inserts an item in this DList immediately before "node".
* If "node" is null, do nothing.
* @param item the item to be inserted.
* @param node the node to insert the item before.
* Performance: runs in O(1) time.
*/
public void insertBefore(Object item, DListNode node) {
// Your solution here.
//DListNode temp;
if(node.item != null){
if(node == head.next){
temp = newNode(item, null, null);
temp.prev = head;
temp.next = node;
node.prev = temp;
head.next = temp;
size++;
}else{ // not the beginning of DList
temp = newNode(item, null, null);
temp.prev = node.prev;
temp.next = node;
(node.prev).next = temp;
node.prev = temp;
size++;
}
}
}
/**
* remove() removes "node" from this DList. If "node" is null, do nothing.
* Performance: runs in O(1) time.
*/
public void remove(DListNode node) {
// Your solution here.
if(node.item == tailnode.item){
// && node.prev == tailnode.prev && node.next == tailnode.next
//System.out.println("*******************remove: The node that's going to remove is tailnode");
tailnode = node.prev;
}
if(node.item != null){
//System.out.println("*******************remove");
(node.prev).next = node.next;
(node.next).prev = node.prev;
}
}
/**
* toString() returns a String representation of this DList.
*
* DO NOT CHANGE THIS METHOD.
*
* @return a String representation of this DList.
* Performance: runs in O(n) time, where n is the length of the list.
*/
public String toString() {
String result = "[ ";
DListNode current = head.next;
while (current != head) {
//System.out.println("while starts!!!! current is" );
result = result + current.item + " ";
current = current.next;
}
return result + "]";
}
}

复制代码

jaly50

melissami 发表于 2014-6-12 09:45
这个写了好久，还是调不出来，LockDList依然有错在这一行会出错
while(curr.next != head){
...

我之前也有一样的问题！感觉是继承没有真正的搞懂！
后来我是这样改的：
除了作业里要求参数一定要是DListNode以外，LockDList里面所有的结点都必须设成LockDListNode类型，返回的链表都必须是LockDList!这才符合这个List的设定啊！
所以继承的method都必须要重写，修改返回的类型！
只有那个LockNode里的参数要求必须是DListNode,那么也要记得cast成LockDListNode

**一定要记得每个新create的Node都必须是LockDListNode的类型才能在用DlistNode declare了以后还能转回LockDListNode

melissami

本帖最后由 melissami 于 2014-6-12 21:27 编辑

jaly50 发表于 2014-6-12 00:05
我之前也有一样的问题！感觉是继承没有真正的搞懂！
后来我是这样改的：
除了作业里要求参数一定要是DL ...

谢谢版主的回复

还想请教一点，关于修改返回值，readme里面有这样一句话

To override a method, you must write a new method in the subclass with EXACTLY the same prototype. You can't change a parameter's type to a subclass. Overriding won't work if you do that.

我理解的override是不能修改传入参数和返回值的类型，不知道是不是我理解的有问题:/

========================================================================

当时不敢每一个method都override，是因为在readme里面有这样一段

Your overriding methods should include calls to the overridden superclass methods whenever it makes sense to do so. Unnecessary code duplication will be penalized.

就想尽量减少override，如果每个method都要重写，那代基本上和DList都重复了里面还提到，newNode就是为了尽量较少代码重复，如果所construct node的method都需要override，那这个method就没用了，直接new DListNode(item, prev, next)或者new LockDListNode(item, prev, next)就行了

不好意思，太多问题鸟

jaly50

melissami 发表于 2014-6-13 09:45
谢谢版主的回复

还想请教一点，关于修改返回值，readme里面有这样一句话

嗯那我重写且改了类型的应该是overload了

就是说override必须要引用superclass的内容喽

那么我有override的其实就这两个，我也不知道这样处理对不对>.<

public LockDListNode(Object i, LockDListNode p, LockDListNode n) {
super(i,p,n);
prev = p;
next = n;
}
public LockDListNode(Object i) {
// TODO Auto-generated constructor stub
super(i);
}

复制代码

melissami

jaly50 发表于 2014-6-13 00:25
嗯那我重写且改了类型的应该是overload了

就是说override必须要引用superclass的内容喽

越改越乱了

这个作业折腾了两个星期，要疯掉了

能不能把你的code发来看看，让我研究一下啊:/

jaly50

melissami 发表于 2014-6-14 00:02
越改越乱了
这个作业折腾了两个星期，要疯掉了
能不能把你的code发来看看，让我研究 ...

你说得我觉得我也不会了……
当时也是代码改不出来，所以我原来以为要用override，不能改Prototype的代码

最后都改成了lockDList类型...只能算是overload了
也不知道对不对

但总之程序可以走了！

melissami

jaly50 发表于 2014-6-13 21:53
你说得我觉得我也不会了……
当时也是代码改不出来，所以我原来以为要用override，不能改Prototype的代 ...

我错了:/ 把你也搞糊涂了

不知道是不是我个人偏见，从testing开始，lecture讲得就不太好，少了很多重要的知识点，顺序也有点混乱，可能是课堂时间不够吧，总觉得和作业衔接不上

windforce

我在这个作业上有个地方卡了很久了。 part I 和 part II都挺顺利地，可是part III一直被卡

试过了LZ的测试代码，以及在google上搜索到的各种测试代码。为什么总是有提示
java.lang.ClassCastException，说是DListNode cannot be cast to LockDListNode

像((LockDListNode)node).locked==true 这样的expression老是要报错

我已经override了newNode方法了啊......

windforce

总算通过了！

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

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

评分

评分

评分

点评

点评

评分

浏览过的版块