CS 61B Data Structures 2014Spring 每日打卡

LAB2- Part2 :
System.out.println("\nTesting add:");

    Fraction sumOfTwo = f1.add(f2);              // Sum of f1 and f2.
    Fraction sumOfThree =f0.add(sumOfTwo);             // Sum of f0, f1, and f2.

    System.out.println("The sum of " + f1 + " and " + f2 + " is " + sumOfTwo);
    System.out.println("The sum of " + f0 + ", " + f1 + " and " + f2 + " is " +
                       sumOfThree);

LAB2- Part3 :
public void changeNumerator(int numerator) {
    if (numerator < 0) {
      System.out.println("Fatal error:  Negative numerator.");
      System.exit(0);
    }
    this.numerator = numerator;
  }

public int fracs() {                         // DO NOT CHANGE THIS SIGNATURE!
    // 将 numberOfFractions (instance variable)改为static
    return numberOfFractions;
  }

LAB2- Part4 :
static private int gcd(int x, int y) {
         if (x==y){
                 return x;
         }else if(x>y){
            if (y==0){
                    return x;
            }else{
                            return gcd(y,x%y);
                  }
    }else{
            return gcd(y,x);
    }
  }

交作业LAB3

/*Part I: Using SLists (1 point) -------------------------------
    In the main() method, construct a list that looks like:
    [ 6 9 12 ]
    and print the resulting list.*/
   
    public static void test(){
            SList list1 = new SList();
            for(int i=6; i<13;i+=3){ list1.insertEnd(new Integer(i));};
            System.out.println();
            System.out.println("Here is a list for PARTI: " + list1.toString());

    /*Add more lines to change this list to:
      [ 3 6 9 12 15 ]
    and print the resulting list.
    */
            
        list1.insertEnd(new Integer(15));
        list1.insertFront(new Integer(3));

交作业LAB3-Part2

public class SList {

    private SListNode head;
    private SListNode tail;
    private int size;

public void insertFront(Object obj) {        if (this.head ==null){
         this.head = new SListNode(obj, this.head);
         this.tail=this.head;
        }else{
         this.head= new SListNode(obj, this.head);
        }
        size++;
    }
      
public void insertEnd(Object obj){
     if (this.head ==null){
         this.head = new SListNode(obj, null);
         this.tail=this.head;
        }else{
         this.tail.next = new SListNode(obj, null);
        this.tail=this.tail.next;
        }
        size++;
    }

交作业hw3-part1



  /**
   *  smoosh() takes an array of ints.  On completion the array contains
   *  the same numbers, but wherever the array had two or more consecutive
   *  duplicate numbers, they are replaced by one copy of the number.  Hence,
   *  after smoosh() is done, no two consecutive numbers in the array are the
   *  same.
   *
   *  Any unused elements at the end of the array are set to -1.
   *
   *  For example, if the input array is [ 0 0 0 0 1 1 0 0 0 3 3 3 1 1 0 ],
   *  it reads [ 0 1 0 3 1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 ] after smoosh()
   *  completes.
   *
   *  @param ints the input array.
   **/


public static void smoosh(int[] ints) {
    if(ints.length<2){                         //如果ints长度小于2，直接返回。因为ints中至少需要两个elements才有得比
    return;
   }else{
    int r=1;                                          //r 为ints 中需要被替换的值的index。在ints中，只有第一个值(r=0) 永远不会被替换，别的都有可能被替换，所以让r从1开始计
    for(int i=0; i<ints.length-1;i++){     // loop的执行，不包括最后一个value；
       if(ints[i]!=ints[i+1]){                   //如果前一值跟后一个值不一样，用后一个值替换ints中的值；如果前后两个值一样，啥也不用做。
        ints[r]=ints[i+1];
         r++;
        }        
     }

     for(int i=r;i<ints.length;i++){  
      ints[i]=-1;
    }
   }
  }

交作业hw3-part2


/**
     *  squish() takes this list and, wherever two or more consecutive items are
     *  equals(), it removes duplicate nodes so that only one consecutive copy
     *  remains.  Hence, no two consecutive items in this list are equals() upon
     *  completion of the procedure.
     *
     *  After squish() executes, the list may well be shorter than when squish()
     *  began.  No extra items are added to make up for those removed.
     *
     *  For example, if the input list is [ 0 0 0 0 1 1 0 0 0 3 3 3 1 1 0 ], the
     *  output list is [ 0 1 0 3 1 0 ].
     *
     *  IMPORTANT:  Be sure you use the equals() method, and not the "=="
     *  operator, to compare items.
     **/


    public void squish() {
        if(this.size < 2) {
            return;
        }
        SListNode currentNode = this.head;                         //当前SListNode, [currentNode 的data type要跟this.head match
        SListNode nextNode = this.head.next;                     //下一个SListNode
        while(nextNode != null) {                                      
            if(currentNode.item.equals(nextNode.item)) {
                currentNode.next = nextNode.next;
                nextNode.next = null;
                nextNode = currentNode.next;
                size--;
            } else {
                currentNode = nextNode;
                nextNode = currentNode.next;
            }
        }
    }

交作业hw3-part3
   /**
     *  twin() takes this list and doubles its length by replacing each node
     *  with two consecutive nodes referencing the same item.
     *
     *  For example, if the input list is [ 3 7 4 2 2 ], the
     *  output list is [ 3 3 7 7 4 4 2 2 2 2 ].
     *
     *  IMPORTANT:  Do not try to make new copies of the items themselves.
     *  Make new SListNodes, but just copy the references to the items.
     **/


public void twin() {
      // Fill in your solution here.  (Ours is seven lines long.)
     SListNode currentNode = this.head;
  
     while(currentNode != null){                                        //currentNode 指的是variable本身（容器）。它是否存了地址？地址不是null的话，currentNode variable指向一个SListNode
                                                                                   //currentNode. 指的是currentNode所refer的那个object
      SListNode nextNode = currentNode.next;
      SListNode copy = new SListNode(currentNode.item,nextNode);
      currentNode.next = copy;
     }
}



-------------------------------------------------
错误1:
public void twin() {
     SListNode currentNode = this.head;
    SListNode nextNode = this.head.next;             //在这里不需要nextNode，因为你都不确定到底有没有下一个
     
     while(currentNode != null)
      SListNode copy = new SListNode(currentNode.item,nextNode);
      currentNode.next = copy;
      currentNode = nextNode;
      nextNode=currentNode.next;
     }
    }
-------------------------------------------------
错误2:
  public void twin() {
     SListNode currentNode = this.head;
  
     while(currentNode != null)
      SListNode nextNode = this.head.next;             //假设当前是第n个(currentNode), 需要有variable 去refer n+1个，怎么refer n+1 个？n+1个是n的下一个所以用currentNode.next。而this.head.next永远指的是第二个
      SListNode copy = new SListNode(currentNode.item,nextNode);
      currentNode.next = copy;
      currentNode = nextNode;
      nextNode=currentNode.next;
     }
    }
-------------------------------------------------
错误3：
    public void twin() {
     SListNode currentNode = this.head;

     while(currentNode != null)
      SListNode nextNode = currentNode.next;
      SListNode copy = new SListNode(currentNode.item,nextNode);
      currentNode.next = copy;
      currentNode = nextNode;
      nextNode=currentNode.next;                    //没有必要更新nextNode，因为一次loop中，nextNode只需要更新一次，有这行的话更新了2次
                                                                   //即使有更新2次的必要，nextNode是local variable，在这里更新了它后，它马上就被gc了，它在下一次loop中不会存在
                                                                   //而且，currentNode可能是null, 如果真是null的话， currentNode.next会引发nullPointerException
     }
    }

交作业 Lab4-Part1-2
public class DListNode1 {
  public int item;
  public DListNode1 prev;
  public DListNode1 next;
----------------------------------
public class DList1 {
  protected DListNode1 head;
  protected DListNode1 tail;
  protected long size;


  /**
   *  insertFront() inserts an item at the front of a DList1.
   */


  public void insertFront(int i) {
    DListNode1 newNode=new DListNode1(i);
    newNode.next=this.head;
    if(this.head!=null){
     this.head.prev=newNode;                         //如果this.head==null，没法this.head.prev，这会引发nullPointerException，因为没有this.head(object)怎么会有prev(a field bundled with an obj)。      
    } else{
     this.tail=newNode;
    }
    this.head=newNode;
    this.size++;
  }

/**
   *  removeFront() removes the first item (and node) from a DList1.  If the
   *  list is empty, do nothing.
   */
  public void removeFront() {
    if(this.size<1){
     return;
    }else if(this.size==1){
     this.head=null;
     this.tail=null;
     this.size--;
    }else{
     this.head=this.head.next;
     this.head.prev.next=null;
     this.head.prev=null;
     this.size--;
    }
  }

交作业lab4-part3-4
public class DListNode2 {
  public int item;
  public DListNode2 prev;
  public DListNode2 next;  
--------------


/**
* A DList2 is a mutable doubly-linked list. Its implementation is
* circularly-linked and employs a sentinel (dummy) node at the head
* of the list.
*/


public class DList2 {
  protected DListNode2 head;
  protected long size;

/**
   *  insertFront() inserts an item at the front of a DList2.
   */
  public void insertFront(int i) {
    DListNode2 newNode = new DListNode2(i);
    // if(this.size==0){
    //   newNode.prev=this.head;
    //   newNode.next=this.head.next;
    //   this.head.next = newNode;
    //   this.head.prev=newNode;                        //this.head.prev==newNode.next.prev
      
    // }else {
      newNode.prev=this.head;
      newNode.next=this.head.next;
      this.head.next=newNode;
      newNode.next.prev=newNode;
      this.size++;
  }

/**
   *  removeFront() removes the first item (and first non-sentinel node) from
   *  a DList2.  If the list is empty, do nothing.
   */
  public void removeFront() {
    if(this.size!=0){
      DListNode2 toBeRemoved=this.head.next;
      this.head.next=toBeRemoved.next;
      toBeRemoved.next.prev=this.head;
      toBeRemoved.next=null;
      toBeRemoved.prev=null;
      this.size--;
    }
  }

总结：
1.从general的情况（size==2时）出发去写methods，然后再看写好的methods适不适用于边界条件（size==1、size==0时，如果不适用，再写if-stmt ..
2. insert时，应当先操作newNode的prev跟next, 而不是this.head（sentinel)的，因为会失去reference

Lab5 -Part 1
Let Y be a subclass of X, and let y and x be variables of classes Y and X respectively. From lecture, you know that the assignment "x = y" is valid, but the assignment "y = (Y) x" requires a cast to compile, and will cause a run-time error if x references an object that isn’t a Y.
    What about arrays of objects? Suppose xa is an array of X's,【 X类型的array，由xa指向它，不是X的 array instance variable... -_-|||】 and ya is an array of Y's.                                             

(a) At compile-time, can we assign xa to ya, and vice versa? When is a cast required?

public class X{
}-------------------------------
public class Y extends X {

public static void main(String[] args){
  X [] xa = new X[10];
  Y [] ya = new Y[10];
xa=ya;                //np

  // ya=xa;            //不行.. 反过来不行

  ya = (Y[])xa;      //casting... 别忘了跟在Y后面的[]，否则是把array（xa) casts 成obj，黑人问号脸！
}
}

-------------------------------------
(b) At run-time, if ya references an array of Y’s, can we assign it to xa? Can we then assign it back from xa to ya?

可以。不行，编译不过跑不了
-----------------------------------------


(c)  If xa references an array of X’s (that are not Y’s), can we assign it to ya? 不行
     Can we then assign it back from ya to xa?  不行
     Does it make a difference if the array of type X[] references objects that are all of class Y ？ 没有difference，还是不行
public static void main(String[] args){
    X [] xa = new Y[10];
    Y [] ya = new Y[10];
    ya=xa;               
}
}

目前刚刚做完PJ1，求个队友一起学习啊~