一亩三分地论坛

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

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

[CS61B_Spring 2015] Lab3-Debugging, Doubly-Linked Lists

[复制链接] |试试Instant~ |关注本帖
hurricane_e 发表于 2015-6-2 13:02:42 | 显示全部楼层 |阅读模式

[其他]CS61B Data Structure #14 - 2015-05-25@Berkeley

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

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

x
RT~
karte_polo 发表于 2015-6-6 00:43:21 | 显示全部楼层
1. DoubleChain.java


public class DoubleChain {
       
        private DNode head;
       
        public DoubleChain(){
        }
       
        public DoubleChain(double val) {
                /* your code here. */
                head = new DNode(val);
        }

        public DNode getFront() {
                return head;
        }

        /** Returns the last item in the DoubleChain. */               
        public DNode getBack() {
                /* your code here */
                DNode p = head;
                while(p.next!=null){
                        p = p.next;
                }
                return p;
        }
       
        /** Adds D to the front of the DoubleChain. */       
        public void insertFront(double d) {
                /* your code here */
                DNode oldF = head;
                head = new DNode(d);
                head.next = oldF;
                oldF.prev = head;
        }
       
        /** Adds D to the back of the DoubleChain. */       
        public void insertBack(double d) {
                /* your code here */
               
                DNode p = head;
                if (p == null){
                        head = new DNode(d);
                }else{
                while (p.next!=null){
                        p = p.next;
                }
                DNode back = new DNode(p,d,null);
                p.next = back;
                }
        }
       
        /** Removes the last item in the DoubleChain and returns it.
          * This is an extra challenge problem. */
        public DNode deleteBack() {
                /* your code here */
                DNode p = head;
                if (p != null){
                while (p.next!=null){
                        p = p.next;
                }
                if (p.prev == null){
                        head = null;
                }else{
                p.prev.next = null;
                }
                return p;
                }
                return null;
        }
       
        /** Returns a string representation of the DoubleChain.
          * This is an extra challenge problem. */
        public String toString() {
                /* your code here */
                DNode p = head;
                String r = "<[";
                if (p!=null){
                while (p.next!=null){
                        r += ""+p.val;
                }
          }
                r+="]>";
                return r;
        }

        public static class DNode {
                public DNode prev;
                public DNode next;
                public double val;
               
                private DNode(double val) {
                        this(null, val, null);
                }
               
                private DNode(DNode prev, double val, DNode next) {
                        this.prev = prev;
                        this.val = val;
                        this.next =next;
                }
        }
       
}

由于JH61B好像有些问题,运行时提示不能支持该类,故改用ECLIPSE自带的JUNIT4进行测试,3个测试METHOD全部通过
2. TestDoubleChain.java

import static org.junit.Assert.*;

import org.junit.Test;

/** Perform tests of the DoubleChain class
*/

public class TestDoubleChain {
   
    /** Tests the constructor of DoubleChain */
        @Test
    public void testConstructor() {
        DoubleChain d = new DoubleChain(5);
        assertEquals(5,d.getFront().val, 1e-6);
        assertEquals(null, d.getFront().prev);
        assertEquals(null, d.getFront().next);
    }

    /** Tests some basic DoubleChain operations. */
        @Test
    public void testBasicOperations() {
        DoubleChain d = new DoubleChain(5);
        assertEquals(5, d.getFront().val, 1e-11);
        assertEquals(5, d.getBack().val, 1e-11);

        d.insertFront(2);
        d.insertFront(1);
        d.insertBack(7);
        d.insertBack(8);
        assertEquals(1, d.getFront().val, 1e-11);
        assertEquals(8, d.getBack().val, 1e-11);
    }
    /** Tests some advanced DoubleChain operations. */
        @Test
    public void testAdvancedOperations() {
        DoubleChain d = new DoubleChain(5);
        assertEquals(5, d.deleteBack().val, 1e-11);
        String emptychain = "<[]>";
        assertEquals(emptychain, d.toString());
        d.insertBack(1.0);
        d.insertBack(2.1);
        d.insertBack(3.3);
        d.insertBack(4.6);
        String expected = "<[5.0,1.0,2.1,3.3,4.6]>";
        assertEquals(expected, d.toString());
    }

    public static void main(String[] args) {
            TestDoubleChain t= new TestDoubleChain();
            t.testConstructor();
            t.testBasicOperations();
        t.testAdvancedOperations();
    }
}

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| hurricane_e 发表于 2015-6-8 17:50:18 | 显示全部楼层
public class DoubleChain {
       
        private DNode head;
       

       
        public DoubleChain(double val) {
                head = new DNode (val);
        }
               

        public DNode getFront() {
                return head;
        }

        /** Returns the last item in the DoubleChain. */               
        public DNode getBack() {
                DNode p = head;
                while (p.next != null) {
                        p = p.next;
                }
                return p;
        }
       
        /** Adds D to the front of the DoubleChain. */       
        public void insertFront(double d) {
                DNode oldFront = head;
                head = new DNode (d);
                head.next = oldFront;
                oldFront.prev = head;
        }
       
        /** Adds D to the back of the DoubleChain. */       
        public void insertBack(double d) {
                DNode p = head;
                while (p.next != null){
                        p = p.next;
                }
                p.next = new DNode (d);
                DNode t = p.next;
                t.prev = p;
        }
       
        /** Removes the last item in the DoubleChain and returns it.
          * This is an extra challenge problem. */
        public DNode deleteBack() {
                DNode p  = head;
                if (p == null){
                        return null;
                } else {
                        while (p.next != null){
                                p = p.next;
                        }
                        p.prev.next = null;
                        p.prev = null;
                        }
                        return p;
                }
       
       
        /** Returns a string representation of the DoubleChain.
          * This is an extra challenge problem. */
        public String toString() {
                DNode p = head;
                StringBuilder sb = new StringBuilder();
                while (p.next != null){
                        sb.append(p.val);
                        sb.append(" ");
                        p = p.next;
                }
                sb.append(p.val);
                return sb.toString();
        }

        public static class DNode {
                public DNode prev;
                public DNode next;
                public double val;
               
                private DNode(double val) {
                        this(null, val, null);
                }
               
                private DNode(DNode prev, double val, DNode next) {
                        this.prev = prev;
                        this.val = val;
                        this.next =next;
                }
        }
}
回复 支持 反对

使用道具 举报

baiery 发表于 2015-6-10 17:19:02 | 显示全部楼层
本帖最后由 baiery 于 2015-6-10 17:54 编辑

public class DoubleChain {
       
        private DNode head;
       
        public DoubleChain(double val) {
                head = new DNode(val);
        }

        public DNode getFront() {
                return head;
        }

        /** Returns the last item in the DoubleChain. */               
        public DNode getBack() {
                DNode p = head;
                while(p.next != null){
                        p = p.next;
                }
                return p;
        }
       
        /** Adds D to the front of the DoubleChain. */       
        public void insertFront(double d) {
                DNode oldFront = head;
                head = new DNode(d);
                head.next = oldFront;
                oldFront.prev = head;
        }
       
        /** Adds D to the back of the DoubleChain. */       
        public void insertBack(double d) {
                DNode p = head;
                if (p == null){
                        head = new DNode(d);
                }else{
                        while(p.next != null){
                        p = p.next;
                        }

                DNode oldBack = p;
                p = new DNode(d);
                oldBack.next = p;
                p.prev = oldBack;
                }
        }
       
        /** Removes the last item in the DoubleChain and returns it.
          * This is an extra challenge problem. */
        public DNode deleteBack() {
                DNode p = head;
                if (p == null){
                        return null;
                }else{
                        while(p.next != null){
                        p = p.next;
                        }
                        if (p.prev == null){
                                head = null;
                        }else{
                        p.prev.next = null;
                        p.prev = null;
                        }
                         return p;
                 }
        }
       
        /** Returns a string representation of the DoubleChain.
          * This is an extra challenge problem. */
        public String toString() {
                DNode p = head;
                String s = "";
                if (p == null){

                }
                 else{
                         while(p.next != null){
                        s = s + p.val+"->" ;
                        p = p.next;
                        }
                        s = s + p.val;
                }       
                return s;
        }

        public static class DNode {
                public DNode prev;
                public DNode next;
                public double val;
               
                private DNode(double val) {
                        this(null, val, null);
                }
               
                private DNode(DNode prev, double val, DNode next) {
                        this.prev = prev;
                        this.val = val;
                        this.next =next;
                }
        }
       
}



test 所有方法都过了
真是作死了进度这么慢。。。。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

baiery 发表于 2015-6-10 17:24:04 | 显示全部楼层

抱歉啊我又来挑刺了,就是在toString这个方法while循环里,你是不是少了p = p.next;这句啊?否则怎么向后传递指针啊?就咱们三个在跟所以我就每次都看看你们的答案分析分析更加好的解法~
回复 支持 反对

使用道具 举报

karte_polo 发表于 2015-6-10 21:36:12 | 显示全部楼层
baiery 发表于 2015-6-10 17:24
抱歉啊我又来挑刺了,就是在toString这个方法while循环里,你是不是少了p = p.next;这句啊?否则怎么向 ...

同学你好细心!我这次的LAB确实是问题多多,除了你提到的那个问题我还发现了很多其他的BUG,多谢你提醒我啦~^_^


回复 支持 反对

使用道具 举报

karte_polo 发表于 2015-6-10 21:38:53 | 显示全部楼层

我改了一下这次LAB几个METHOD的CODE,算是订正吧。这题不能设SENTINEL NODE真是麻烦啊

        public DNode getBack() {
                /* your code here */
                DNode p = head;
                if (p==null){
                        return null;
                }
                while(p.next!=null){
                        p = p.next;
                }
                return p;
        }

        public void insertBack(double d) {
                /* your code here */
                DNode p = this.getBack();
                if (p == null){
                        head = new DNode(d);
                }else{
                        p.next = new DNode(p,d,null);
                }
        }

        public DNode deleteBack() {
                /* your code here */
                DNode p = this.getBack();
                if (p==null){
                        return null;
                }else if (p.prev==null){
                        this.head = null;
                }else{
                p.prev.next = null;
                }
                return p;
        }

        public String toString() {
                /* your code here */
                DNode p = head;
                String r = "<[";
                if (p!=null){
                        r+=""+p.val;
                        while(p.next!=null){
                                p=p.next;
                                r+=","+p.val;
                        }
                }               
                r+="]>";
                return r;
        }
回复 支持 反对

使用道具 举报

baiery 发表于 2015-6-11 00:36:34 | 显示全部楼层
karte_polo 发表于 2015-6-10 21:38
我改了一下这次LAB几个METHOD的CODE,算是订正吧。这题不能设SENTINEL NODE真是麻烦啊

        public DNode  ...

哈哈一起进步,我发现我总是漏掉p = null的情况,我的getback也漏掉了这个if
回复 支持 反对

使用道具 举报

whosays 发表于 2015-6-22 05:49:33 | 显示全部楼层
private DNode head;
        public DoubleChain(double val) {
                /* your code here. */
                head = new DNode(val);
        }

        public DNode getFront() {
                return head;
        }

        /** Returns the last item in the DoubleChain. */               
        public DNode getBack() {
                /* your code here */
                DNode p = head;
                while (p.next != null) {
                        p = p.next;
                } // close while loop
                return p;
        }
       
        /** Adds D to the front of the DoubleChain. */       
        public void insertFront(double d) {
                /* your code here */
                DNode oldHead = head;
                head = new DNode(oldHead.prev, d, oldHead);

        }
       
        /** Adds D to the back of the DoubleChain. */       
        public void insertBack(double d) {
                /* your code here */
                DNode p = head;
                while (p.next != null) {
                        p = p.next;
                } // close while
                // DNode oldBack = p;
                p.next = new DNode(p, d, null);
        }
       
        /** Removes the last item in the DoubleChain and returns it.
          * This is an extra challenge problem. */
        public DNode deleteBack() {
                /* your code here */
                DNode p = head;
                while (p.next != null) {
                        p = p.next;
                } // close while
                p = p.prev;
                return p;
        }
       
        /** Returns a string representation of the DoubleChain.
          * This is an extra challenge problem. */
        public String toString() {
                /* your code here */
                // present front-to-back chain       
                String chain = "The double chain is: ";
                String arrow = "->";
                DNode p = head;
                while (p.next != null) {
                        chain = chain + p.val + arrow;
                        p = p.next;
                }
                chain += "null;";
                return chain;
        }

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Casualet 发表于 2015-6-26 11:07:57 | 显示全部楼层
1.
a==b compares in terms of id rather than the values of the two integers.
when i<128, the two ids are the same, but they are not when i surpasses 128.

2.通过所有Test包括自写test, 这是我第一次根据Test来反推题目要求做题=_=
public class DoubleChain {
    private DNode head;
    public DoubleChain(double val) {
        /* your code here. */
            DNode temp=new DNode(val);   
                temp.next=null;
                temp.prev=null;
                head=temp;
    }

    public DNode getFront() {
        return head;
    }


    /** Returns the last item in the DoubleChain. */        

    public DNode getBack() {
        /* your code here */
           DNode temp=head;
               while(temp.next!=null){
                     temp=temp.next;
               }
               return temp;
    }

   
    /** Adds D to the front of the DoubleChain. */   
    public void insertFront(double d) {
        /* your code here */
            DNode temp=new DNode(null,d,head);
            head.prev=temp;
            head=temp;
          }
   
    /** Adds D to the back of the DoubleChain. */   
    public void insertBack(double d) {
        /* your code here */
               DNode temp=head;
               while(temp.next!=null){
                  temp=temp.next;
               }
               DNode temp2=new DNode(temp,d,null);
               temp.next=temp2;  
        }
   
    /** Removes the last item in the DoubleChain and returns it.
      * This is an extra challenge problem. */
    public DNode deleteBack() {
        /* your code here */
               DNode temp=head;
               while(temp.next.next!=null){
                  temp=temp.next;  
              }
               DNode temp2=temp.next;
               temp.next=null;
               return temp2;
               
    }
   
    /** Returns a string representation of the DoubleChain.
      * This is an extra challenge problem. */
    public String toString() {
        /* your code here */        
                String temp="<[";
                DNode d=head.next;
                if(d.next==null)
                  return "<["+d.val+"]>";               

                temp+=head.val;
                temp+=", ";
                while(d.next!=null){
                    temp+=d.val;
                    temp+=", ";   
                    d=d.next;                 
              }
              temp+=d.val;
              temp+="]>";   
             return temp;
    }
        public void deleteByIndex(int i){
             DNode temp=head;
             int index=0;
             if(i==0){
                head=head.next;
                return;
             }//forget to return;
             while(index!=i){
                index++;
                temp=temp.next;
            }
             if(temp.next==null){
                  temp.prev.next=null;
                  return ;
             }
            temp.prev.next=temp.next;
            temp.next.prev=temp.prev;   
       }
       public void deleteByValue(double val){
              int index=0;
              DNode temp=head;
              while(temp!=null){
                  double value=temp.val-val;
          if(value==0.0||(value<=0&&-value<=1e-6)||(value>=0&&value<=1e-6)){                  
                     deleteByIndex(index);
                     index--;
                    // if(val==5.0) System.out.println(index+" value:"+value);
                     //System.out.println("delete secceed");
                 }else{
                     // System.out.println(index+" value:"+value);
                     
                      //System.out.println("delete fail"+value);
                 }            
                     index++;
                     temp=temp.next;
             }      
       }
    public static class DNode {
        public DNode prev;
        public DNode next;
        public double val;
        
        private DNode(double val) {
            this(null, val, null);
        }
        
        private DNode(DNode prev, double val, DNode next) {
            this.prev = prev;
            this.val = val;
            this.next =next;
        }
    }
   
}

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

HNAKXR 发表于 2016-2-1 16:46:45 | 显示全部楼层
  1. public class DoubleChain {
  2.        
  3.         private DNode head;
  4.        
  5.         public DoubleChain(double val) {
  6.                 /* your code here. */
  7.                 head = new DNode(null, val, null);
  8.         }

  9.         public DNode getFront() {
  10.                 return head;
  11.         }

  12.         /** Returns the last item in the DoubleChain. */               
  13.         public DNode getBack() {
  14.                 /* your code here */
  15.                 DNode p = head;
  16.                 while (p.next != null) {
  17.                         p = p.next;
  18.                 }
  19.                 return p;
  20.         }
  21.        
  22.         /** Adds D to the front of the DoubleChain. */       
  23.         public void insertFront(double d) {
  24.                 /* your code here */
  25.                 head = new DNode(null, d, head);
  26.         }
  27.        
  28.         /** Adds D to the back of the DoubleChain. */       
  29.         public void insertBack(double d) {
  30.                 /* your code here */
  31.                 DNode p = head;
  32.                 while (p.next != null) {
  33.                         p = p.next;
  34.                 }
  35.                 p = new DNode(p, d, null);
  36.                 p.prev.next = p;
  37.         }
  38.        
  39.         /** Removes the last item in the DoubleChain and returns it.
  40.           * This is an extra challenge problem. */
  41.         public DNode deleteBack() {
  42.                 /* your code here */
  43.                 DNode p = head;
  44.                 while (p.next != null) {
  45.                         p = p.next;
  46.                 }
  47.                 p.prev.next = null;
  48.                 return new DNode(p.prev, p.val, null);
  49.         }
  50.        
  51.         /** Returns a string representation of the DoubleChain.
  52.           * This is an extra challenge problem. */
  53.         public String toString() {
  54.                 /* your code here */               
  55.                 DNode p = head;
  56.                 String result = String.valueOf(p.val);
  57.                 while (p.next != null) {
  58.                         p = p.next;
  59.                         result = result + " " + String.valueOf(p.val);
  60.                 }
  61.                 return result;
  62.         }

  63.         public static class DNode {
  64.                 public DNode prev;
  65.                 public DNode next;
  66.                 public double val;
  67.                
  68.                 private DNode(double val) {
  69.                         this(null, val, null);
  70.                 }
  71.                
  72.                 private DNode(DNode prev, double val, DNode next) {
  73.                         this.prev = prev;
  74.                         this.val = val;
  75.                         this.next = next;
  76.                 }
  77.         }
  78.        
  79. }
复制代码

  1. import static org.junit.Assert.*;

  2. import org.junit.Test;

  3. /** Perform tests of the DoubleChain class
  4. */

  5. public class TestDoubleChain {

  6.     /** Tests the constructor of DoubleChain */
  7.     @Test
  8.     public void testConstructor() {
  9.         DoubleChain d = new DoubleChain(5);
  10.         assertEquals(5,d.getFront().val, 1e-6);
  11.         assertEquals(null, d.getFront().prev);
  12.         assertEquals(null, d.getFront().next);
  13.     }

  14.     /** Tests some basic DoubleChain operations. */
  15.     @Test
  16.     public void testBasicOperations() {
  17.         DoubleChain d = new DoubleChain(5);
  18.         assertEquals(5, d.getFront().val, 1e-11);
  19.         assertEquals(5, d.getBack().val, 1e-11);

  20.         d.insertFront(2);
  21.         d.insertFront(1);
  22.         d.insertBack(7);
  23.         d.insertBack(8);
  24.         System.out.println(d.toString());
  25.         assertEquals(1, d.getFront().val, 1e-11);
  26.         assertEquals(8, d.getBack().val, 1e-11);
  27.     }

  28.     public static void main(String[] args) {
  29.         jh61b.junit.textui.runClasses(TestDoubleChain.class);
  30.     }
  31. }
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 20:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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