📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2642| 回复: 10
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:
公开课
学校名称: Berkeley
Unit号: 14
开课时间: 2015-05-25
课程全名: CS61B Data Structure
平台: 其他

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

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

x
RT~

上一篇:[CS61B_Spring 2015] Discussion3-Arrays vs. Linked Lists
下一篇:[CS61B_Spring 2015] HW2
🔗
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();
    }
}
回复

使用道具 举报

🔗
 楼主| 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 所有方法都过了
真是作死了进度这么慢。。。。
回复

使用道具 举报

🔗
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;
        }
回复

使用道具 举报

🔗
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;
        }
    }
   
}
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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