一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 8516|回复: 223
收起左侧

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

  [复制链接] |试试Instant~ |关注本帖
jaly50 发表于 2014-6-3 17:24:23 | 显示全部楼层 |阅读模式

[其他]CS 61B Data Structures #1 - 2014-06-03@Berkeley CS 61B Data Structures

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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
  1. //Line 122
  2. LockDListNode node = sl1.front(); //Wrong
  3. DListNode node = sl1.front(); //Right
  4. //Line 135
  5. LockDListNode back = sl1.back(); //Wrong
  6. DListNode back = sl1.back();  //Right
复制代码
那我就贴个TestDList和TestLockDList的输出图吧:

hw4_TestDList

hw4_TestDList
Hw4_TestLockDListNode.png




相关链接:      

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










评分

4

查看全部评分

czbnlzd920706 发表于 2015-4-27 08:28:29 | 显示全部楼层
这次作业一开始轻视了。然后做到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



















DList

DList

LockDList

LockDList

评分

12

查看全部评分

回复 支持 9 反对 0

使用道具 举报

enirinth 发表于 2015-5-25 16:06:29 | 显示全部楼层
本帖最后由 enirinth 于 2015-5-25 16:08 编辑

先贴作业~~~TestDList:


TestDList.png



TestLockDList:
TestLockDList.png


要override的函数:
remove()和newNode()是自然,另外要改front()和back():
  1. public LockDListNode front() {
  2.     return (LockDListNode)(super.front());
  3. }
复制代码
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.


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

评分

2

查看全部评分

回复 支持 3 反对 0

使用道具 举报

Eloise 发表于 2016-4-7 16:00:16 | 显示全部楼层
谢谢LZ提供test代码...
觉得front 和 back 函数其实不用重写,只要把TestLockDList 里面相应的部分从LockDlistNode 改成 DListNode 就好了啊。。
而且不是有其他函数同样返回DLisNode么?也没有全都重写啊.. 还是说这两个函数有什么特殊之处?
和LS遇到了同样的head的问题,想了一会才改过来,给LS的分析赞一个..
TestDList.jpg
TestLockDlist.jpg

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

小小溪 发表于 2015-5-30 01:19:17 | 显示全部楼层
一开始没看toString,不知道head一直指向sentinel node。。。 😂

BTW,觉得LockDList.java里的remove可以再简单一些
        @Override
        public void remove(DListNode node) {
                if(((LockDListNode) node).locked) {
                        return;
                }
                super.remove(node);
        }
result of DListTest.jpg
result of LockDListTest.jpg

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

hypsm 发表于 2016-1-27 00:06:42 | 显示全部楼层
本帖最后由 hypsm 于 2016-1-27 00:24 编辑

感谢首页大牛们的指点让我能这么快做完。LockDList在重载了newNode()之后,大部分函数直接继承父类即可,因为这些函数在构造过程中使用了newNode()来创建节点,而实际的LockDList对象会动态调用新的newNode(),而并不需要重新声明。

而remove() 和 lockNode() 两个函数,传入的参数是DListNode, 但实际上实参总是一个LockDListNode, 所以isLocked这个field只是我们看不到而已,使用cast之后便能访问:( (LockDListNode) node).isLocked = true;
另外注意 protected关键字:自身,子类及同一个包中类可以访问,不像C++一样是只能子类访问,所以同在list 包中的LockDList 也可以访问 hea.prev 这些field
  1. public void remove(DListNode node) {
  2.     if(node == null || node == head || ((LockDListNode) node).isLocked == true) return;
  3.     node.prev.next = node.next;
  4.     node.next.prev = node.prev;
  5.     size--;
  6.   }

  7.   public void lockNode(DListNode node) {
  8.     ((LockDListNode) node).isLocked = true;
  9.   }
复制代码

TestLockDList

TestLockDList


TestDList

TestDList



评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

lyc1994 发表于 2015-7-15 11:51:03 | 显示全部楼层
dennisyang 发表于 2015-7-14 09:43
为啥我compile DList.java的时候 会报错说 DListNode找不到符号呢? 我已经compile DListNode.java了啊 有c ...

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

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

windforce 发表于 2014-6-18 01:45:50 | 显示全部楼层
本帖最后由 windforce 于 2014-6-18 02:01 编辑
windforce 发表于 2014-6-17 10:38
我在这个作业上有个地方卡了很久了。 part I 和 part II都挺顺利地,可是part III一直被卡

试过了LZ的测 ...

昨天卡了很久。 其实是个小bug,纯粹自己疏忽
之所以我会出现ClassCastException,是因为我在 DList 里面虽然定义了newNode方法,但我的新建节点(各种插入)什么的都忘了利用这个方法!而是仍然用new DListNode(Object, DListNode, DListNode)来实现的
这样后来我虽然在LockDList里override了newNode,但实际上相当于没用,当然DListNode向LockDListNode转换会报错

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

melissami 发表于 2014-6-12 09:45:24 | 显示全部楼层
本帖最后由 melissami 于 2014-6-11 21:03 编辑

这个写了好久,还是调不出来,LockDList依然有错
  1. package list;

  2. public class LockDList extends DList {

  3.   protected LockDListNode head;
  4.   protected LockDListNode tailnode;
  5.   //protected LockDListNode temp;


  6.   protected DListNode newNode(Object item, DListNode prev, DListNode next) {
  7.     DListNode nnn = new LockDListNode(item,prev, next);
  8.         return nnn;
  9.   }


  10.   public LockDList() {
  11.         //super class constructor called by default
  12.   }

  13.   
  14.   public void insertFront(Object item) {
  15.     super.insertFront(item);
  16.   }
  17.   
  18.   
  19.   public void remove(DListNode node) {
  20.     LockDListNode curr = this.head;
  21.     while(curr.next != head){
  22.       if(curr.item == node.item && curr.prev == node.prev && curr.next == node.next){
  23.         if(curr.lockstatus == false){
  24.           super.remove(node);
  25.         }
  26.       }
  27.       curr = curr.next;
  28.     }
  29.   }
复制代码
在这一行会出错
    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代码也贴上来吧,方便挑错实在不行,我过两天再删掉~
  1. /* DList.java */

  2. package list;



  3. /**
  4. *  A DList is a mutable doubly-linked list ADT.  Its implementation is
  5. *  circularly-linked and employs a sentinel (dummy) node at the head
  6. *  of the list.
  7. *
  8. *  DO NOT CHANGE ANY METHOD PROTOTYPES IN THIS FILE.
  9. */

  10. public class DList {

  11.   /**
  12.    *  head references the sentinel node.
  13.    *  size is the number of items in the list.  (The sentinel node does not
  14.    *       store an item.)
  15.    *
  16.    *  DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
  17.    */

  18.   protected DListNode head;
  19.   protected DListNode tailnode;
  20.   protected int size;
  21.   
  22.   protected DListNode temp;

  23.   /* DList invariants:
  24.    *  1)  head != null.
  25.    *  2)  For any DListNode x in a DList, x.next != null.
  26.    *  3)  For any DListNode x in a DList, x.prev != null.
  27.    *  4)  For any DListNode x in a DList, if x.next == y, then y.prev == x.
  28.    *  5)  For any DListNode x in a DList, if x.prev == y, then y.next == x.
  29.    *  6)  size is the number of DListNodes, NOT COUNTING the sentinel,
  30.    *      that can be accessed from the sentinel (head) by a sequence of
  31.    *      "next" references.
  32.    */

  33.   /**
  34.    *  newNode() calls the DListNode constructor.  Use this class to allocate
  35.    *  new DListNodes rather than calling the DListNode constructor directly.
  36.    *  That way, only this method needs to be overridden if a subclass of DList
  37.    *  wants to use a different kind of node.
  38.    *  @param item the item to store in the node.
  39.    *  @param prev the node previous to this node.
  40.    *  @param next the node following this node.
  41.    */
  42.   protected DListNode newNode(Object item, DListNode prev, DListNode next) {
  43.     return new DListNode(item, prev, next);
  44.   }

  45.   /**
  46.    *  DList() constructor for an empty DList.
  47.    */
  48.   public DList() {
  49.     //  Your solution here.
  50.     head = newNode(null, null, null);
  51.     head.next = head.prev = head;
  52.     //tailnode = head;
  53.     size = 0;
  54.   }
  55.   /*
  56.   public DList returnDList(){
  57.   return this;
  58.   }
  59.   */

  60.   /**
  61.    *  isEmpty() returns true if this DList is empty, false otherwise.
  62.    *  @return true if this DList is empty, false otherwise.
  63.    *  Performance:  runs in O(1) time.
  64.    */
  65.   public boolean isEmpty() {
  66.     return size == 0;
  67.   }

  68.   /**
  69.    *  length() returns the length of this DList.
  70.    *  @return the length of this DList.
  71.    *  Performance:  runs in O(1) time.
  72.    */
  73.   public int length() {
  74.     return size;
  75.   }

  76.   /**
  77.    *  insertFront() inserts an item at the front of this DList.
  78.    *  @param item is the item to be inserted.
  79.    *  Performance:  runs in O(1) time.
  80.    */
  81.   public void insertFront(Object item) {
  82.     // Your solution here.
  83.     //DListNode temp;
  84.     if(size == 0){ // if list is empty
  85.       tailnode = newNode(item, null, null);
  86.       tailnode.prev = tailnode.next = head;
  87.       head.prev = head.next = tailnode;
  88.       //tailnode = temp;
  89.       size++;
  90.     }else{
  91.       temp = newNode(item, null, null);
  92.       temp.prev = head;
  93.       temp.next = head.next;
  94.       head.next = temp;
  95.       //(head.next).prev = temp;
  96.       (temp.next).prev = temp;
  97.       size++;
  98.     }
  99.   }

  100.   /**
  101.    *  insertBack() inserts an item at the back of this DList.
  102.    *  @param item is the item to be inserted.
  103.    *  Performance:  runs in O(1) time.
  104.    */
  105.   public void insertBack(Object item) {
  106.     // Your solution here.
  107.     //DListNode temp;
  108.     if(size == 0){ // if list is empty
  109.       tailnode = newNode(item, null, null);
  110.       tailnode.prev = tailnode.next = head;
  111.       head.prev = head.next = tailnode;
  112.       size++;
  113.     }else{
  114.       temp = newNode(item, null, null);
  115.       temp.next = head;
  116.       temp.prev = tailnode;
  117.       tailnode.next = temp;
  118.       tailnode = temp;
  119.       head.prev = tailnode;
  120.       size++;
  121.     }
  122.   }

  123.   /**
  124.    *  front() returns the node at the front of this DList.  If the DList is
  125.    *  empty, return null.
  126.    *
  127.    *  Do NOT return the sentinel under any circumstances!
  128.    *
  129.    *  @return the node at the front of this DList.
  130.    *  Performance:  runs in O(1) time.
  131.    */
  132.   public DListNode front() {
  133.     // Your solution here.
  134.     if(isEmpty() == true){
  135.       return null;
  136.     }else{
  137.       return head.next;
  138.     }
  139.   }

  140.   /**
  141.    *  back() returns the node at the back of this DList.  If the DList is
  142.    *  empty, return null.
  143.    *
  144.    *  Do NOT return the sentinel under any circumstances!
  145.    *
  146.    *  @return the node at the back of this DList.
  147.    *  Performance:  runs in O(1) time.
  148.    */
  149.   public DListNode back() {
  150.     // Your solution here.
  151.     if(head.next == head){
  152.       return null;
  153.     }else{
  154.       return tailnode;
  155.     }
  156.   }

  157.   /**
  158.    *  next() returns the node following "node" in this DList.  If "node" is
  159.    *  null, or "node" is the last node in this DList, return null.
  160.    *
  161.    *  Do NOT return the sentinel under any circumstances!
  162.    *
  163.    *  @param node the node whose successor is sought.
  164.    *  @return the node following "node".
  165.    *  Performance:  runs in O(1) time.
  166.    */
  167.   public DListNode next(DListNode node) {
  168.     // Your solution here.
  169.     if(isEmpty() == true){
  170.       return null;
  171.     }else{
  172.       return node.next;
  173.     }
  174.   }

  175.   /**
  176.    *  prev() returns the node prior to "node" in this DList.  If "node" is
  177.    *  null, or "node" is the first node in this DList, return null.
  178.    *
  179.    *  Do NOT return the sentinel under any circumstances!
  180.    *
  181.    *  @param node the node whose predecessor is sought.
  182.    *  @return the node prior to "node".
  183.    *  Performance:  runs in O(1) time.
  184.    */
  185.   public DListNode prev(DListNode node) {
  186.     // Your solution here.
  187.     if(isEmpty() == true){
  188.       return null;
  189.     }else{
  190.       return node.prev;
  191.     }
  192.   }

  193.   /**
  194.    *  insertAfter() inserts an item in this DList immediately following "node".
  195.    *  If "node" is null, do nothing.
  196.    *  @param item the item to be inserted.
  197.    *  @param node the node to insert the item after.
  198.    *  Performance:  runs in O(1) time.
  199.    */
  200.   public void insertAfter(Object item, DListNode node) {
  201.     // Your solution here.
  202.     //DListNode temp;
  203.     if(node.item != null){
  204.       if(node == tailnode){
  205.         temp = newNode(item, null, null);
  206.         temp.prev = node;
  207.         temp.next = head;
  208.         node.next = temp;
  209.         tailnode = temp;
  210.         size++;
  211.       }else{ // not the end of DList
  212.         temp = newNode(item, null, null);
  213.         temp.prev = node;
  214.         temp.next = node.next;
  215.         node.next = temp;
  216.         size++;
  217.       }
  218.     }
  219.   }

  220.   /**
  221.    *  insertBefore() inserts an item in this DList immediately before "node".
  222.    *  If "node" is null, do nothing.
  223.    *  @param item the item to be inserted.
  224.    *  @param node the node to insert the item before.
  225.    *  Performance:  runs in O(1) time.
  226.    */
  227.   public void insertBefore(Object item, DListNode node) {
  228.     // Your solution here.
  229.     //DListNode temp;
  230.     if(node.item != null){
  231.       if(node == head.next){
  232.         temp = newNode(item, null, null);
  233.         temp.prev = head;
  234.         temp.next = node;
  235.         node.prev = temp;
  236.         head.next = temp;
  237.         size++;
  238.       }else{ // not the beginning of DList
  239.         temp = newNode(item, null, null);
  240.         temp.prev = node.prev;
  241.         temp.next = node;
  242.         (node.prev).next = temp;
  243.         node.prev = temp;
  244.         size++;
  245.       }
  246.     }
  247.   }

  248.   /**
  249.    *  remove() removes "node" from this DList.  If "node" is null, do nothing.
  250.    *  Performance:  runs in O(1) time.
  251.    */
  252.   public void remove(DListNode node) {
  253.     // Your solution here.
  254.       if(node.item == tailnode.item){
  255.         // && node.prev == tailnode.prev && node.next == tailnode.next
  256.       //System.out.println("*******************remove: The node that's going to remove is tailnode");
  257.       tailnode = node.prev;
  258.       }
  259.     if(node.item != null){
  260.       //System.out.println("*******************remove");
  261.       (node.prev).next = node.next;
  262.       (node.next).prev = node.prev;

  263.     }
  264.   }

  265.   /**
  266.    *  toString() returns a String representation of this DList.
  267.    *
  268.    *  DO NOT CHANGE THIS METHOD.
  269.    *
  270.    *  @return a String representation of this DList.
  271.    *  Performance:  runs in O(n) time, where n is the length of the list.
  272.    */
  273.   public String toString() {
  274.     String result = "[  ";
  275.     DListNode current = head.next;
  276.     while (current != head) {
  277.       //System.out.println("while starts!!!! current is" );
  278.       result = result + current.item + "  ";
  279.       current = current.next;
  280.     }
  281.     return result + "]";
  282.   }
  283.   

  284.    
  285. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-6-12 13:05:03 | 显示全部楼层
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 发表于 2014-6-13 09:45:27 | 显示全部楼层
本帖最后由 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 发表于 2014-6-13 13:25:49 | 显示全部楼层
melissami 发表于 2014-6-13 09:45
谢谢版主的回复

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

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

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

那么我有override的其实就这两个,我也不知道这样处理对不对>.<
  1. public LockDListNode(Object i, LockDListNode p, LockDListNode n) {
  2. super(i,p,n);
  3. prev = p;
  4. next = n;
  5. }
  6. public LockDListNode(Object i) {
  7.                 // TODO Auto-generated constructor stub
  8.           super(i);
  9.         }
复制代码
回复 支持 反对

使用道具 举报

melissami 发表于 2014-6-14 00:02:33 | 显示全部楼层
jaly50 发表于 2014-6-13 00:25
嗯  那我重写 且改了类型的 应该是overload了

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

越改越乱了
这个作业折腾了两个星期,要疯掉了
能不能把你的code发来看看,让我研究一下啊:/
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-6-14 10:53:35 | 显示全部楼层
melissami 发表于 2014-6-14 00:02
越改越乱了
这个作业折腾了两个星期,要疯掉了
能不能把你的code发来看看,让我研究 ...

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

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

但总之程序可以走了!
回复 支持 反对

使用道具 举报

melissami 发表于 2014-6-15 05:06:35 | 显示全部楼层
jaly50 发表于 2014-6-13 21:53
你说得我觉得我也不会了……
当时也是代码改不出来,所以我原来以为要用override,不能改Prototype的代 ...

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

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

使用道具 举报

windforce 发表于 2014-6-17 10:38:13 | 显示全部楼层
我在这个作业上有个地方卡了很久了。 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 发表于 2014-6-18 01:40:01 | 显示全部楼层
总算通过了!

hw4-part1

hw4-part1

hw4-part3

hw4-part3

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

melissami 发表于 2014-6-21 00:21:56 | 显示全部楼层
也来贴一下吧
经过了半个多月的挣扎,终于可以运行了 1.gif


2.gif

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

galaxy2 发表于 2014-6-25 04:36:47 | 显示全部楼层
hw4 screenshot
              
hw41.png
hw42.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

marshallou 发表于 2014-7-5 11:11:26 | 显示全部楼层
谢谢lz提供test code

1.png
2.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

gougou9901 发表于 2014-7-7 00:40:08 | 显示全部楼层
hw4交作业,其中LockDList的测试代码用的是GitHub上的
hw4(2).PNG
hw4.PNG

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

gloria_wwj 发表于 2014-7-9 17:02:31 | 显示全部楼层
看了讨论,写好了,跑起来了,不知道我对overridden的理解对不对
class LockDListNode extends DListNode{
        boolean lock;
        LockDListNode(Object i, DListNode p, DListNode n){
                super(i, p, n);
                lock = false;
        }
}
**************************
class LockDList extends DList{

        protected DListNode newNode(Object item, DListNode prev, DListNode next) {
                DListNode myNode = new LockDListNode(item,prev,next);
                //System.out.println("overriden newNode");
                return myNode;
        }

        public void lockNode(DListNode node){
                LockDListNode tempNode = (LockDListNode)node;
                tempNode.lock = true;
        }

        public void remove(DListNode node) {
                if (((LockDListNode)node).lock!=true) {
                    if (node!=null) {
                              node.prev.next = node.next;
                              node.next.prev = node.prev;
                              size--;      
                    }
                }       
        }
}
homework4(1).png
homework4(2).png

评分

3

查看全部评分

回复 支持 反对

使用道具 举报

krist 发表于 2014-7-14 17:08:54 | 显示全部楼层
回复 支持 反对

使用道具 举报

krist 发表于 2014-7-14 17:12:08 | 显示全部楼层
gloria_wwj 发表于 2014-7-9 17:02
看了讨论,写好了,跑起来了,不知道我对overridden的理解对不对
class LockDListNode extends DListNode{ ...

感谢!给了我启发!
不过你的newNode和remove还可以更精炼(remove可以复用父类的):
protected DListNode newNode(Object item, DListNode prev, DListNode next) {
                return new LockDListNode(item, prev, next);
        }
public void remove(DListNode node){
        LockDListNode tmp = (LockDListNode)node;
        if(tmp.lock == true)
                return;
        else
                super.remove(node);
}
回复 支持 反对

使用道具 举报

gloria_wwj 发表于 2014-7-14 18:05:10 | 显示全部楼层
krist 发表于 2014-7-14 17:12
感谢!给了我启发!
不过你的newNode和remove还可以更精炼(remove可以复用父类的):
protected DList ...

想到了调用父类,但是调代码的时候说必须super是第一个statement~所以就放弃了
回复 支持 反对

使用道具 举报

gloria_wwj 发表于 2014-7-14 18:07:17 | 显示全部楼层
krist 发表于 2014-7-14 17:12
感谢!给了我启发!
不过你的newNode和remove还可以更精炼(remove可以复用父类的):
protected DList ...

你的方法我再试试,主要自己写super的时候调试说必须第一句,谢谢提醒!^^
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 03:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表