一亩三分地论坛

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

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

[CS61B_Spring 2015] HW03

[复制链接] |试试Instant~ |关注本帖
karte_polo 发表于 2015-7-4 23:34:32 | 显示全部楼层 |阅读模式

[其他]CS61B DATA STRUCTURES #5 - 2015-06-01@UC BERKELEY

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

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

x
RT~
 楼主| karte_polo 发表于 2015-7-4 23:37:56 | 显示全部楼层
part 1 q&A

Q1.
(a) SuperAnimal
(b) No
(c) RingDing
(d) Yes
(e) None
(f) dynamic

Q2.
(a) A
(b) Ringding
(c) Ringding
(d)  dynamic

Q3.
(a) true
(b) SuperAnimal
(c) SuperAnimal
(d) static


part2 SortedComparable list

import java.util.Formatter;

/**
* SortedComparableList.java
* A list of Comparables in ascending order.
*/
public class SortedComparableList {
    /** First element of list. */
    public Comparable head;
    /** Remaining elements of list. */
    public SortedComparableList tail;

    /** A list with head HEAD0 and tail TAIL0. */
    public SortedComparableList(Comparable head0, SortedComparableList tail0) {
        head = head0;
        tail = tail0;
    }

    /** A list with null tail, and head = 0. */
    public SortedComparableList(){
        head = 0;
        tail = null;
    }

    /** Inserts Comparable c into its correct location in this list. */
    public void insert(Comparable c) {
        // REPLACE THIS LINE WITH YOUR SOLUTION
            if (c !=null){
                    if (c.compareTo(head)<0){
                            tail = this;
                            head = c;
                    }else{
                            SortedComparableList l = this;
                            while (l.tail !=null && c.compareTo(l.tail.head)>0){
                                    l = l.tail;
                            }
                            l.tail = new SortedComparableList(c,l.tail);
                    }
            }
    }

    /** Returns the i-th int in this list.
     *  The first element, which is in location 0, is the 0th element.
     *  Assume i takes on the values [0, length of list - 1]. */
    public Comparable get(int i) {
            SortedComparableList l = this;
            if (head ==null || i==0){
                    return head;
            }
            while (i>0){
                    l = l.tail;
                    i--;
            }
            return l.head;
    }

    /** Adds every item in THAT to this list. */
    public void extend(SortedComparableList that) {
        SortedComparableList l = that;
        while (l != null) {
            insert(l.head);
            l = l.tail;
        }
        // REPLACE THIS LINE WITH YOUR SOLUTION
    }

    /** Returns a list consisting of the elements of L starting from
      * position START, and going all the way to the END. The head of the
      * list L is the 0th element of the list.
      *
      * This method should NOT modify L. */
    public static SortedComparableList subTail(SortedComparableList L, int start) {
            if (L.head == null || start ==0){
                    return L;
            }else{
                    return subTail(L.tail,start-1);
            }
    }

    /** Returns the sublist consisting of LEN items from list L,
     *  beginning with item START (where the first item is 0).
     *
     *  Does not modify the original list elements.
     *  Assume START and END are >= 0.
     */
    public static SortedComparableList sublist(SortedComparableList L, int start, int len) {
            if (len==0){
                    return null;
            }
            else if (start >0){
                    return sublist(L.tail,start-1,len);
            }
            return new SortedComparableList(L.head,sublist(L.tail,0,len-1));
    }

    /** Removes items from L at position len+1 and later. */
    public static void expungeTail(SortedComparableList L, int len) {
            if (L == null){
                    return;
            }else if (len==0){
                    L.tail = null;
                    return;
            }
            expungeTail(L.tail,len-1);
    }

    /**
     *  Takes this list and, wherever two or more consecutive items are
     *  equal, it removes duplicates so that only one consecutive copy
     *  remains. No two consecutive items in this list are equals at the
     *  end of this method.
     *
     *  You can assume the list is in sorted order when this method is
     *  called.
     *
     *  For example, if the input list is [ 0 0 0 0 1 1 3 3 3 4 ], the
     *  output list is [ 0 1 3 4 ].
     **/
    public void squish() {
            SortedComparableList p = this;
            while (p.head!=null && p.tail!=null){
                    if (p.head == p.tail.head){
                            p.tail = p.tail.tail;
                    }else{
                    p = p.tail;
                    }
            }
        // REPLACE THIS LINE WITH YOUR SOLUTION
    }

    /** Duplicates each Comparable so that for every original
     *  Comparable, there will end up being two consecutive Comparables.
     *
     *  You can assume the list is in sorted order when this method is
     *  called.
     *
     *  For example, if the input list is [ 2 3 4 7 ], the
     *  output list is [ 2 2 3 3 4 4 7 7 ].
     *
     *  NOTE: Do not try to make copies of the Comparables. Set
     *  the HEAD variable equal to the HEAD variable you are trying to
     *  duplicate.
     **/
    public void twin() {
            SortedComparableList p = this;
            while (p!=null){
                    p.tail = new SortedComparableList(p.head,p.tail);
                    p = p.tail.tail;
            }
    }

    /** Returns NULL if no cycle exists, else returns cycle location. */
    private int detectCycles(SortedComparableList A) {
        SortedComparableList tortoise = A;
        SortedComparableList hare = A;
        if (A == null) {
            return 0;
        }
        int cnt = 0;
        while (true) {
            cnt++;
            if (hare.tail != null) {
                hare = hare.tail.tail;
            }
            else{
                return 0;
            }
            tortoise = tortoise.tail;
            if (tortoise == null || hare == null) {
                return 0;
            }
            if (hare == tortoise) {
                return cnt;
            }
        }
    }

    /** Returns true iff X is a SortedComparableList containing the
     *  same sequence of Comparables as THIS. Cannot handle cycles. */
    public boolean equals(Object x) {
        if (!(x instanceof SortedComparableList)) {
            return false;
        }
        SortedComparableList L = (SortedComparableList) x;
        SortedComparableList p;
        for (p = this; p != null && L != null; p = p.tail, L = L.tail) {
            if (p.head != L.head) {
                return false;
            }
        }
        if (p != null || L != null) {
            return false;
        }
        return true;
    }

    @Override
    public String toString() {
        Formatter out = new Formatter();
        String sep;
        sep = "(";
        int cycleLocation = detectCycles(this);
        int cnt = 0;
        for (SortedComparableList p = this; p != null; p = p.tail) {
            out.format("%s%d", sep, p.head);
            sep = ", ";

            cnt++;
            if ((cnt > cycleLocation) && (cycleLocation > 0)) {
                out.format("... (cycle exists) ...");
                break;
            }
        }
        out.format(")");
        return out.toString();
    }
}

part3 和part2 很像就不贴了

PART 4 COMPARATORS

import java.util.Comparator;

/**
* MassComparator.java
*/

public class MassComparator implements Comparator<Planet> {

    public MassComparator() {
    }

    /** Returns the difference in mass as an int.
     *  Round after calculating the difference. */
    public int compare(Planet planet1, Planet planet2) {
            return (int)(planet1.getmass() - planet2.getmass());
    }
}

import java.util.Comparator;
public class RadiusComparator implements Comparator<Planet>{
        public RadiusComparator(){
               
        }
    public int compare(Planet planet1, Planet planet2) {
            return (int)(planet1.getradius() - planet2.getradius());
    }
       

}

回复 支持 反对

使用道具 举报

Casualet 发表于 2015-8-8 09:50:28 | 显示全部楼层
1: answer 不写了,有答案,做错了好几个;

2:SortedComparableList.java
import java.util.Formatter;

/**
* SortedComparableList.java
* A list of Comparables in ascending order.
*/
public class SortedComparableList {
    /** First element of list. */
    public Comparable head;
    /** Remaining elements of list. */
    public SortedComparableList tail;

    /** A list with head HEAD0 and tail TAIL0. */
    public SortedComparableList(Comparable head0, SortedComparableList tail0) {
        // REPLACE THIS LINE WITH YOUR SOLUTION
        this.head=head0;
        this.tail=tail0;
    }

    /** A list with null tail, and head = 0. */
    public SortedComparableList(){
        // REPLACE THIS LINE WITH YOUR SOLUTION
          this.head=null;
          this.tail=null;  
    }
    /** Inserts Comparable c into its correct location in this list. */
    public void insert(Comparable c) {
        // REPLACE THIS LINE WITH YOUR SOLUTION
        if(c==null) return;
        SortedComparableList temp=this;
        SortedComparableList pre=null;
       if(temp.head==null) System.out.println(">>>>>>>>>>");
        while(c.compareTo(temp.head)>=0){
            pre=temp;
            temp=temp.tail;
               if(temp==null){//do not forget the boarder
                  System.out.println(">>>>>>>>>>");
                  break;
               }
        }
        if(pre!=null){
            SortedComparableList node=new SortedComparableList(c,pre.tail);
            pre.tail=node;
        }else{
           SortedComparableList node=new SortedComparableList(this.head,this.tail);      
           this.tail=node;
           this.head=c;   
          //How to insert into the front??
        }//insert into the front
    }

    /** Returns the i-th int in this list.
     *  The first element, which is in location 0, is the 0th element.
     *  Assume i takes on the values [0, length of list - 1]. */

    public Comparable get(int i) {
        int count=0;
        SortedComparableList temp=this;
        for(;count<i;count++){
             temp=temp.tail;
       }        
        return temp.head; // REPLACE THIS LINE WITH YOUR SOLUTION
    }

    /** Adds every item in THAT to this list. */
    //then we should distinguish between a node and a list
    public void extend(SortedComparableList that) {
        // REPLACE THIS LINE WITH YOUR SOLUTION
       while(that!=null){
         this.insert(that.head);
         that=that.tail;
       }                        
    }

    /** Returns a list consisting of the elements of L starting from
      * position START, and going all the way to the END. The head of the
      * list L is the 0th element of the list.
      *
      * This method should NOT modify L. */
    public static SortedComparableList subTail(SortedComparableList L, int start) {
        SortedComparableList temp,pre,result;
        temp=L;
        int count=0;
        while(count<start){
           temp=temp.tail;
           count+=1;

        }

        pre=result=new SortedComparableList(temp.head,null);
        temp=temp.tail;

        while(temp!=null){
           SortedComparableList inTemp=new SortedComparableList(temp.head,null);
           pre.tail=inTemp;
           pre=inTemp;
           temp=temp.tail;            
        }
        return result;
        // REPLACE THIS LINE WITH YOUR SOLUTION
    }

    /** Returns the sublist consisting of LEN items from list L,
     *  beginning with item START (where the first item is 0).
     *
     *  Does not modify the original list elements.
     *  Assume START and END are >= 0.
     */
    public static SortedComparableList sublist(SortedComparableList L, int start, int len) {
        int count=0;
        SortedComparableList temp=L;
        while(count < start){
           temp=temp.tail;
           count++;
        }
        count=0;
        SortedComparableList result=new SortedComparableList(temp.head,null);
        SortedComparableList pre=result;
        temp=temp.tail;
        while(count<len&&temp!=null){
            SortedComparableList inTemp= new SortedComparableList(temp.head,null);
            pre.tail=inTemp;
            pre=inTemp;
            temp=temp.tail;
            count++;//always forget this
        }
        return result; // REPLACE THIS LINE WITH YOUR SOLUTION
    }

    /** Removes items from L at position len+1 and later. */
    public static void expungeTail(SortedComparableList L, int len) {
        // REPLACE THIS LINE WITH YOUR SOLUTION
        SortedComparableList temp=L;
        int count=0;
        while(count<len){
            L=L.tail;
            count++;
        }            
        L.tail=null;
        L=temp;
    }

    /**
     *  Takes this list and, wherever two or more consecutive items are
     *  equal, it removes duplicates so that only one consecutive copy
     *  remains. No two consecutive items in this list are equals at the
     *  end of this method.
     *
     *  You can assume the list is in sorted order when this method is
     *  called.
     *
     *  For example, if the input list is [ 0 0 0 0 1 1 3 3 3 4 ], the
     *  output list is [ 0 1 3 4 ].
     **/
    public void squish() {
        SortedComparableList pre,cur;
        pre=this;
        cur=this.tail;
        while(cur!=null){
         if(pre.head.compareTo(cur.head)==0){
               cur=cur.tail;
               pre.tail=cur;//do not forget this
          }else{
             pre=pre.tail;
             cur=cur.tail;
        }
       }  
        // REPLACE THIS LINE WITH YOUR SOLUTION
    }

    /** Duplicates each Comparable so that for every original
     *  Comparable, there will end up being two consecutive Comparables.
     *
     *  You can assume the list is in sorted order when this method is
     *  called.
     *
     *  For example, if the input list is [ 2 3 4 7 ], the
     *  output list is [ 2 2 3 3 4 4 7 7 ].
     *
     *  NOTE: Do not try to make copies of the Comparables. Set
     *  the HEAD variable equal to the HEAD variable you are trying to
     *  duplicate.
     **/
    public void twin() {
        // REPLACE THIS LINE WITH YOUR SOLUTION
        SortedComparableList temp=this;
        SortedComparableList create;
        while(temp!=null){//differentiate between temp!=null and temp.tail!=null
            create=new SortedComparableList(temp.head,temp.tail);
            temp.tail=create;
            temp=create.tail;
        }

    }

    /** Returns NULL if no cycle exists, else returns cycle location. */
    private int detectCycles(SortedComparableList A) {
        SortedComparableList tortoise = A;
        SortedComparableList hare = A;
        if (A == null) {
            return 0;
        }
        int cnt = 0;
        while (true) {
            cnt++;
            if (hare.tail != null) {
                hare = hare.tail.tail;
            }
            else{
                return 0;
            }
            tortoise = tortoise.tail;
            if (tortoise == null || hare == null) {
                return 0;
            }
            if (hare == tortoise) {
                return cnt;
            }
        }
    }

    /** Returns true iff X is a SortedComparableList containing the
     *  same sequence of Comparables as THIS. Cannot handle cycles. */
    public boolean equals(Object x) {
        if (!(x instanceof SortedComparableList)) {
            return false;
        }
        SortedComparableList L = (SortedComparableList) x;
        SortedComparableList p;
        for (p = this; p != null && L != null; p = p.tail, L = L.tail) {
            if (p.head != L.head) {
                return false;
            }
        }
        if (p != null || L != null) {
            return false;
        }
        return true;
    }
    public String printInt(){
       SortedComparableList temp=this;
       String re="";
       while(temp!=null){
           re=re+((imComparable)(temp.head)).forCompare+" ";
           temp=temp.tail;
       }
       return re;
    }

    @Override
    public String toString() {
        Formatter out = new Formatter();
        String sep;
        sep = "(";
        int cycleLocation = detectCycles(this);
        int cnt = 0;
        for (SortedComparableList p = this; p != null; p = p.tail) {
            out.format("%s%d", sep, p.head);
            sep = ", ";

            cnt++;
            if ((cnt > cycleLocation) && (cycleLocation > 0)) {
                out.format("... (cycle exists) ...");
                break;
            }
        }
        out.format(")");
        return out.toString();
    }
}
part3:
import java.util.Formatter;

/**
* ApplicableIntList.java
* A list that stores integers in ascending order.
*/
public class ApplicableIntList{
    /** First element of list. */
    public int head;
    /** Remaining elements of list. */
    public ApplicableIntList tail;

    /** A list with head HEAD0 and tail TAIL0. */
    public ApplicableIntList(int head0, ApplicableIntList tail0) {
        // REPLACE THIS LINE WITH YOUR SOLUTION
        this.head=head0;
        this.tail=tail0;      
    }

    /** A list with null tail, and head = 0. */
    public ApplicableIntList() {
        this.head=-1;
        this.tail=null;
        // REPLACE THIS LINE WITH YOUR SOLUTION
    }
    /** Inserts int i into its correct location, doesn't handle cycles. */
    public void insert(int i) {
         System.out.println("insert");
         ApplicableIntList pre,cur;
         cur=this;
         pre=null;
         if(cur.head>=i){
          ApplicableIntList temp= new ApplicableIntList(this.head,this.tail);
          this.tail=temp;
          this.head=i;
          return ;
         }//insert into the first node
      
         while(cur!=null){
            if(cur.head<=i){
                pre=cur;
                cur=cur.tail;
            }else break;//do not forget this branch
          }
          if(cur==null){//do not forget this case
             ApplicableIntList temp= new ApplicableIntList(i,null);            
             pre.tail=temp;
          }else{         
         ApplicableIntList temp= new ApplicableIntList(i,cur);
         pre.tail=temp;
         }
        // REPLACE THIS LINE WITH YOUR SOLUTION

    }

    /** Returns the i-th int in this list.
     *  The first element, which is in location 0, is the 0th element.
     *  Assume i takes on the values [0, length of list - 1]. */
    public int get(int i) {
        // REPLACE THIS LINE WITH YOUR SOLUTION
        int count=0;
        ApplicableIntList temp=this;
        while(count<i){
          temp=temp.tail;           
           count++;
        }
        return temp.head;
    }

    /** Applies the function f to every item in this list. */
    public void apply(IntUnaryFunction f) {
        // REPLACE THIS LINE WITH YOUR SOLUTION
       ApplicableIntList temp=this;
       while(temp!=null){
            temp.head=f.apply(temp.head);
            temp=temp.tail;
       }

    }

    /** Returns NULL if no cycle exists, else returns cycle location. */
    private int detectCycles(ApplicableIntList A) {
        ApplicableIntList tortoise = A;
        ApplicableIntList hare = A;
        if (A == null) {
            return 0;
        }
        int cnt = 0;
        while (true) {
            cnt++;
            if (hare.tail != null) {
                hare = hare.tail.tail;
            }
            else{
                return 0;
            }
            tortoise = tortoise.tail;
            if (tortoise == null || hare == null) {
                return 0;
            }
            if (hare == tortoise) {
                return cnt;
            }
        }
    }

    /** Returns true iff X is a ApplicableIntList containing the
     *  same sequence of Comparables as THIS. Cannot handle cycles. */
    public boolean equals(Object x) {
        if (!(x instanceof ApplicableIntList)) {
            return false;
        }
        ApplicableIntList L = (ApplicableIntList) x;
        ApplicableIntList p;
        for (p = this; p != null && L != null; p = p.tail, L = L.tail) {
            if (p.head != L.head) {
                return false;
            }
        }
        if (p != null || L != null) {
            return false;
        }
        return true;
    }

    @Override
    public String toString() {
//        System.out.println("----------------------");
        Formatter out = new Formatter();
        String sep;
        sep = "(";
        int cycleLocation = detectCycles(this);
        int cnt = 0;
        for (ApplicableIntList p = this; p != null; p = p.tail) {
            out.format("%s%d", sep, p.head);
            sep = ", ";

            cnt++;
            if ((cnt > cycleLocation) && (cycleLocation > 0)) {
                out.format("... (cycle exists) ...");
                break;
            }
        }
        out.format(")");
        return out.toString();
    }
}
part4:
MassCompatator.java
import java.util.Comparator;

/**
* MassComparator.java
*/

public class MassComparator implements Comparator<Planet> {

    public MassComparator() {
    }

    /** Returns the difference in mass as an int.
     *  Round after calculating the difference. */
    public int compare(Planet planet1, Planet planet2) {
        // REPLACE THIS LINE WITH YOUR SOLUTION
        double result=planet1.getMass()-planet2.getMass();
        System.out.println(planet1.getMass()+" : "+planet2.getMass()+" : "+result);
        return (int)result;
    }
RadiusCompatator 类似;

MaxPlanet.java
public class MaxPlanet {
   public static Planet getPlanet(In in){
        double x=in.readDouble();
        double y=in.readDouble();
        double vx=in.readDouble();
        double vy=in.readDouble();
        double mass=in.readDouble();
        String s="ss";
        double radius=in.readDouble();
        return new Planet(x,y,vx,vy,mass,s,radius);
   }

    /** Returns the Planet with the maximum value according to Comparator c. */
    public static Planet maxPlanet(Planet[] planets, Comparator<Planet> c) {
        // REPLACE THIS LINE WITH YOUR SOLUTION
       int length=planets.length;
       int index=0;
       Planet temp=planets[0];

       for(int i=0;i<length;i++){
          if(c.compare(planets[index],planets[i])<0) index=i;
      }
       return planets[index];
    }


    public static void main(String args[]){
       In in= new In("data/planets.txt");
       int numOfPlanets=in.readInt();
       double radius=in.readDouble();

       Planet [] pArray=new Planet[numOfPlanets];

       for(int i=0;i<numOfPlanets;i++){
            pArray[i]=getPlanet(in);
       //   pArray.draw();  
       }
       //it is essitially a kind of function pointer
      Planet p= maxPlanet(pArray,new MassComparator());
         System.out.println(p.mass);
    }
}


看似简单,但是还是写了非常久。。。。。




回复 支持 反对

使用道具 举报

Casualet 发表于 2015-8-8 09:51:26 | 显示全部楼层
楼主CS61B跟完了么,为什么后面好多没更新了?
回复 支持 反对

使用道具 举报

HNAKXR 发表于 2016-2-8 22:40:43 | 显示全部楼层
这个homework好长啊……虽然不难

Part 1: Basic inheritance exercises
Q1.
(a) SuperAnimal
(b) No
(c) Ringding
(d) Yes
(e) None
(f) dynamic

Q2.
(a) A
(b) Ringding
(c) Ringding
(d) dynamic

Q3.
(a) True
(b) SuperAnimal
(c) SuperAnimal
(d) static

Part 2: Recursive linked data structure
hw3_1.jpeg

Part 3: Function container class
hw3_2.jpeg

Part 4: Comparators
hw3_3.jpeg

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 19:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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