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

[CS61B_Spring 2015] Discussion2 - Diagramming, Iterative vs. Recursive

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

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

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

x
本帖最后由 hurricane_e 于 2015-5-28 04:14 编辑

Rt~

上一篇:[CS61B_Spring 2015] HW1 加分讨论帖
下一篇:[CS61B_Spring 2015] Lab2 - JUnit Testing
推荐
Casualet 2015-6-16 19:41:27 | 只看该作者
全局:
本帖最后由 Casualet 于 2015-6-16 19:43 编辑


public class d2{

    public static IntList SquareDestructive(IntList l){
        if(l.tail==null){
             l.head=l.head*l.head;
             return null;
        }  
        l.head=l.head*l.head;
        SquareDestructive(l.tail);
        return l;
    }//recursive

     
    public static IntList SquareDestructiveV2(IntList l){
        IntList L=l;
       while(l.tail!=null){
          l.head=l.head*l.head;
          l=l.tail;
       }  
          l.head=l.head*l.head;
        return L;
    }//iterative

    public static IntList SquareNonDestructive(IntList l){
           if(l.tail==null)
              return new IntList(l.head*l.head,null);
           return new IntList(l.head*l.head,SquareNonDestructive(l.tail));            
           

    }//recursive
   
   public static IntList SquareNonDestructiveV2(IntList l){
         IntList L,next,temp;
         L=new IntList(l.head*l.head,null);
         next=L;              
         while(l.tail!=null){
           l=l.tail;
           temp= new IntList(l.head*l.head,null);
           next.tail=temp;
           next=next.tail;
       }
       //  next.tail=new IntList(l.head*l.head,null);   
        return L;
   }//iterative

   public static IntList reverseNonDestructive(IntList lst){
         IntList cur,next,myCur,myNext=null;
         cur=lst;
         next=cur.tail;
         myCur=new IntList(cur.head,null);
         if(next==null) return myCur;
         while(next!=null){              
          myNext=new IntList(next.head,null);
          myNext.tail=myCur;
          myCur=myNext;
          cur=cur.tail;
          next=next.tail;           
        }

          return myNext;
    }
   
    public static IntList reverseDestructive(IntList lst){
          IntList cur,next,nextTemp;
          cur=lst;
          next=cur.tail;
          cur.tail=null;
          if(next==null) return cur;
          while(next!=null){
            if(next.tail!=null){
                nextTemp=next.tail;
                next.tail=cur;
                cur=next;
                next=nextTemp;   
           }else{

             break;
         }
            
               
       }
          next.tail=cur;
          return next;
              
    }

    public static void printList(IntList l){
       while(l.tail!=null){
            System.out.print(l.head+" ");
            l=l.tail;
       }
            System.out.println(l.head);   
      
    }

    public static void main(String args[]){
                     
          IntList l=new IntList(4,null);
          l=new IntList(3,l);
          l=new IntList(2,l);
          l=new IntList(1,l);   

          printList(l);
          SquareDestructive(l);
          printList(l);
          SquareDestructiveV2(l);
          printList(l);
          IntList L=SquareNonDestructive(l);
          printList(L);
          L=SquareNonDestructive(L);
          printList(L);
          L= reverseNonDestructive(L);
          printList(L);
          L= reverseDestructive(L);
          printList(L);         

}
}

第一题不知道为什么倒了;图片是测试结果,0是因为overflow; V2表示的是bonus版本;

回复

使用道具 举报

推荐
karte_polo 2015-6-2 20:14:19 | 只看该作者
全局:
自己写了个LINKEDLIST 勉勉强强能完成这个LAB吧

最后一个NonDestructive的逆转链表好奇怪- -我在METHOD里面DEBUG出来结果是正确的,跳回MAIN之后链表就变成一个长度只有一的链表了- - 求JAVA 大神指点

import java.util.*;

public class CS61B_LAB02 {
        public static class IntList{
                private class Node{
                        private int Data;
                        Node(int data){
                                this.Data = data;
                        }
                       
                }
                private Node Header;
                private IntList tail;
                public IntList(IntList L1,IntList L2){
                        L1.tail = L2;
                }
                public IntList(int d,IntList nl){
                        this.Header = new Node(d);
                        this.tail = nl;
                }
               
                public void print(){
                        IntList p = this;
                        System.out.println();
                        while (p!=null){
                                System.out.print(" "+p.Header.Data);
                                p = p.tail;
                        }
                       
                }
               
        }
// above is an awkward implementation of LinkedLists
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                //test code below
                IntList L = new IntList(4, null);
                L.print();
                L = new IntList(3, L);
                L.print();
                L = new IntList(2, L);
                L.print();
                L = new IntList(1, L);
                L.print();
                SquareDestructive(L);
                L.print();
                reverseDestructive(L);
                L.print();

        }
        public static IntList SquareDestructive(IntList L) {
                while (L != null){
                        L.Header.Data =L.Header.Data*L.Header.Data;
                        L = L.tail;
                }
                return L;
        }
        public static IntList SquareNonDestructive(IntList L) {
                if (L == null){
                        return L;
                }
                int d = L.Header.Data;
                return new IntList(d*d,SquareNonDestructive(L.tail));
        }
       
        public static IntList reverseNonDestructive(IntList L) {
                IntList N = null;
                while (L!=null){
                        N = new IntList(L.tail,N);
                        L = L.tail;
                }
                return N;
        }
        public static void reverseDestructive(IntList L) {
                IntList tmp = L.tail;
                L.tail = null;
                IntList p;
                while (tmp!=null){
                        p = tmp.tail;
                        tmp.tail = L;
                        L = tmp;
                        tmp = p;               
                }
        }
}
回复

使用道具 举报

全局:
2a.
        public static IntList SquareDestructive(IntList L){
                IntList M = L;
                while (L != null){
                        L.head = L.head * L.head;
                        L = L.tail;
                }
                return M;
        }

2b.
        public static IntList SquareNonDestructive(IntList L){
                if (L == null){
                        return null;
                }else{
                        return new IntList(L.head * L.head, SquareNonDestructive(L.tail));
                }
        }

3a.
        public static IntList reverseNonDestructive(IntList lst){
                IntList M = new IntList(lst.head, null);
                IntList N = lst.tail;
                int i = 1;
                while (i < lst.size()){
                        M = new IntList(N.head, M);
                        N = N.tail;
                        i += 1;                       
                }
                return M;
        }

3b.
        public static void reverseDestructive(IntList L) {
                int i = 1;
                while (i < L.size()){
                        move0thToNth(L, L.size() - i);
                        i += 1;
                }
    }
       
        public static void exchangeTheFirstTwo(IntList lst){
                int temp = lst.head;
                lst.head = lst.tail.head;
                lst.tail.head = temp;
                //return lst;
        }
       
        public static void move0thToNth(IntList lst, int n){
                if (n != 0){
                        exchangeTheFirstTwo(lst);
                        move0thToNth(lst.tail, n - 1);
                }
        }

最后一题我自己又建了两个函数,方法略显麻烦。
回复

使用道具 举报

🔗
 楼主| hurricane_e 2015-5-29 06:45:57 | 只看该作者
全局:



回复

使用道具 举报

🔗
baiery 2015-5-29 11:56:54 | 只看该作者
全局:
奇怪,为什么我无法贴图?不是选择附件吗?
回复

使用道具 举报

🔗
 楼主| hurricane_e 2015-5-29 12:11:32 | 只看该作者
全局:
baiery 发表于 2015-5-29 11:56
奇怪,为什么我无法贴图?不是选择附件吗?

我一般是通过 ”回复-->高级模式-->图片“ 里面贴图的 有时候要等一等
回复

使用道具 举报

🔗
baiery 2015-5-29 12:50:50 | 只看该作者
全局:
图片是第一题
//2 Squaring a List

/** Destructively squares each element of the given IntList L.
* Don’t use ’new’; modify the original IntList.
* Should be written iteratively. */
public static IntList SquareDestructive(IntList L) {
        while(L!=null){
                L.head = L.head * L.head;
                L = L.tail;
        }
}


/** Non-destructively squares each element of the given IntList L.
* Don’t modify the given IntList.
* Should be written recursively*/
public static IntList SquareNonDestructive(IntList L) {
        if (L == null){
                return null;
        }
        else{
                IntList N = new IntList(L.head * L.head, SquareNonDestructive(L.tail));
                return N;
        }
}

//Destructive, recursively
public static IntList SquareDestructiveRecursive(IntList L) {
        if (L == null){
                return null;
        }
        else{
                L.head = L.head * L.head;
                return SquareDestructiveRecursive(L.tail); //Not sure here, should I use "return"?
        }
}

//Non-destructive, iteratively
public static IntList SquareNonDestructiveIterative(IntList L) {
        IntList N = new IntList();
       
        while(L!=null){
                N.head = L.head * L.head;
                L = L.tail;
                N = N.tail;
        }
}


//3 Reversing Linked Lists
/** Takes in an IntList and non-destructively returns an IntList whose
elements have been reversed.*/
public static IntList reverseNonDestructive(IntList lst) {
        IntList N = new IntList();

        while(lst!=null){
                N = IntList(lst.head, N);
                lst = lst.tail;
        }
        return N;
}


/** Bonus for bosses: Write reverseDestructive, which takes in an IntList
and destructively returns the same IntList with reversed elements.
You should not use ’new’.*/
public static void reverseDestructive(IntList L) {

}

最后一题不会啊,求解答啊,想了半天!
另外SquareDestructiveRecursive这个方法里,不知道要不要return,求解答!
感觉自己太搓了,三道discussion竟然搞了一上午,崩溃。。

Screen Shot 2015-05-29 at 11.58.53 AM.png (108.97 KB, 下载次数: 1)

Screen Shot 2015-05-29 at 11.58.53 AM.png
回复

使用道具 举报

🔗
 楼主| hurricane_e 2015-5-29 12:59:30 | 只看该作者
全局:
baiery 发表于 2015-5-29 12:50
图片是第一题
//2 Squaring a List

最后那个bonus方法我也不会╮(╯﹏╰)╭
同样学弱 做了好久。。也不太确定自己到底会了没。。

慢慢来吧=。=
回复

使用道具 举报

🔗
baiery 2015-5-29 13:41:13 | 只看该作者
全局:
hurricane_e 发表于 2015-5-29 12:59
最后那个bonus方法我也不会╮(╯﹏╰)╭
同样学弱 做了好久。。也不太确定自己到底会了没。。

//Destructive, recursively
public static IntList SquareDestructiveRecursive(IntList L) {
        if (L == null){
                return null;
        }
        else{
                L.head = L.head * L.head;
                return SquareDestructiveRecursive(L.tail); //Not sure here, should I use "return"?
        }
}
你觉得这里要写return嘛?可以直接写 SquareDestructiveRecursive(L.tail);吗?

另外我看你的代码里,最后一题第一句是 IntList M = null; 不用先 IntList M = new IntList(); 然后再赋初值吗?我好多格式化的问题都没搞清楚
回复

使用道具 举报

🔗
go7going 2015-5-29 18:27:06 | 只看该作者
全局:
求lz给个61B的课程链接呗~
回复

使用道具 举报

🔗
 楼主| hurricane_e 2015-5-30 03:16:08 | 只看该作者
全局:
go7going 发表于 2015-5-29 18:27
求lz给个61B的课程链接呗~

http://www.1point3acres.com/bbs/thread-135059-1-1.html
都在主帖第一楼里~
回复

使用道具 举报

🔗
 楼主| hurricane_e 2015-5-30 03:23:22 | 只看该作者
全局:
baiery 发表于 2015-5-29 13:41
//Destructive, recursively
public static IntList SquareDestructiveRecursive(IntList L) {
        ...

你的code有一点点问题,我觉得应该是这样:
public static IntList squareDestructiveRecursive(IntList L) {
        if (L == null){
                return null;
        }
        return new IntList (L.head * L.head, squareDestructiveRecursive(L.tail));
}

另外那个IntList M = null 的我其实也不太确定,但是可以compile,所以应该是可以的吧
回复

使用道具 举报

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

本版积分规则

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