hw5打卡

PART I:

DList:

  1 public DList() {
  2     // Your solution here.  Similar to Homework 4, but now you need to specify
  3     //   the `list' field (second parameter) as well.
  4     head = newNode(null, null, null, null);
  5     head.prev =head;
  6     head.next =head;
  7     size = 0;
  8   }
  9 
 10   /**
 11    *  insertFront() inserts an item at the front of this DList.
 12    *
 13    *  @param item is the item to be inserted.
 14    *
 15    *  Performance:  runs in O(1) time.
 16    **/
 17   public void insertFront(Object item) {
 18     // Your solution here.  Similar to Homework 4, but now you need to specify
 19     //   the `list' field (second parameter) as well.
 20     head.next = newNode(item, this, head, head.next);
 21     head.next.next.prev = head.next;
 22     size++;
 23   }
 24 
 25   /**
 26    *  insertBack() inserts an item at the back of this DList.
 27    *
 28    *  @param item is the item to be inserted.
 29    *
 30    *  Performance:  runs in O(1) time.
 31    **/
 32   public void insertBack(Object item) {
 33     // Your solution here.  Similar to Homework 4, but now you need to specify
 34     //   the `list' field (second parameter) as well.
 35     head.prev = newNode(item, this, head.prev, head);
 36     head.prev.prev.next = head.prev;
 37     size++;
 38   }
 39 DListNode:
 40 public void insertAfter(Object item) throws InvalidNodeException {
 41         if (!isValidNode()) {
 42           throw new InvalidNodeException("insertAfter() called on invalid node");
 43         }
 44         // Your solution here.  Will look something like your Homework 4 solution,
 45         //   but changes are necessary.  For instance, there is no need to check if
 46         //   "this" is null.  Remember that this node's "myList" field tells you
 47         //   what DList it's in.  You should use myList.newNode() to create the
 48         //   new node.
 49         DListNode newNode=new DListNode(item, (DList)this.myList, this, this.next);      
 50         this.next.prev=newNode;
 51         this.next=newNode;
 52         this.myList.size++;
 53       }
 54 
 55       /**
 56        *  insertBefore() inserts an item immediately preceding this node.  If this
 57        *  node is invalid, throws an exception.
 58        *
 59        *  @param item the item to be inserted.
 60        *  @exception InvalidNodeException if this node is not valid.
 61        *
 62        *  Performance:  runs in O(1) time.
 63        */
 64       public void insertBefore(Object item) throws InvalidNodeException {
 65         if (!isValidNode()) {
 66           throw new InvalidNodeException("insertBefore() called on invalid node");
 67         }
 68         // Your solution here.  Will look something like your Homework 4 solution,
 69         //   but changes are necessary.  For instance, there is no need to check if
 70         //   "this" is null.  Remember that this node's "myList" field tells you
 71         //   what DList it's in.  You should use myList.newNode() to create the
 72         //   new node.
 73         DListNode newNode=new DListNode(item,(DList)this.myList,this.prev,this);
 74         this.prev.next = newNode;
 75         this.prev=newNode;
 76         this.myList.size++;
 77 }
 78 
 79       /**
 80        *  remove() removes this node from its DList.  If this node is invalid,
 81        *  throws an exception.
 82        *
 83        *  @exception InvalidNodeException if this node is not valid.
 84        *
 85        *  Performance:  runs in O(1) time.
 86        */
 87       public void remove() throws InvalidNodeException {
 88         if (!isValidNode()) {
 89           throw new InvalidNodeException("remove() called on invalid node");
 90         }
 91         // Your solution here.  Will look something like your Homework 4 solution,
 92         //   but changes are necessary.  For instance, there is no need to check if
 93         //   "this" is null.  Remember that this node's "myList" field tells you
 94         //   what DList it's in.
 95         this.prev.next=this.next;
 96         this.next.prev=this.prev;
 97         this.myList.size--; 
 98 
 99         // Make this node an invalid node, so it cannot be used to corrupt myList.
100         myList = null;
101         // Set other references to null to improve garbage collection.
102         next = null;
103         prev = null;
104       }

View Code

结果无误，太长了所以不贴了hhh

PART II:

insert主要就是遍历list，然后找出合适的位置插入。一般情况下使用前插即可，遍历到list末端时可以使用后插。
union比较两个list，由于都是sorted list所以也是从前往后遍历即可。通常情况下也是使用前向插入。注意遍历到末尾的情况。
intersect操作方法类似，需要注意sList的长度问题，SList到达末端后需要依次删除curNode的内容。还有就是remove node的方式，之前使用curNode = curNode.next();

curNode.prev().remove(); 这样在最后一个node的情况不太好处理，于是更改了一下

  1 /**
  2    *  insert() inserts a Comparable element into this Set.
  3    *
  4    *  Sets are maintained in sorted order.  The ordering is specified by the
  5    *  compareTo() method of the java.lang.Comparable interface.
  6    *
  7    *  Performance:  runs in O(this.cardinality()) time.
  8    **/
  9       public void insert(Comparable c) {
 10           try {
 11           if(setList.isEmpty()) {
 12               setList.insertFront(c);          
 13           }else {
 14                ListNode currentNode=setList.front();
 15          while(currentNode.isValidNode()) {                        
 16             if(((Comparable)currentNode.item()).compareTo(c)==0) {
 17             break;
 18            }else if(((Comparable)currentNode.item()).compareTo(c)>0) {
 19                currentNode.insertBefore(c);            
 20                break;
 21            }else if(!currentNode.next().isValidNode()){
 22             currentNode.insertAfter(c);            
 23             break;
 24             }
 25             currentNode=currentNode.next();
 26             }
 27                }
 28             }catch(InvalidNodeException e) {
 29                       System.out.println(e);
 30                   }
 31           }
 32 
 33   /**
 34    *  union() modifies this Set so that it contains all the elements it
 35    *  started with, plus all the elements of s.  The Set s is NOT modified.
 36    *  Make sure that duplicate elements are not created.
 37    *
 38    *  Performance:  Must run in O(this.cardinality() + s.cardinality()) time.
 39    *
 40    *  Your implementation should NOT copy elements of s or "this", though it
 41    *  will copy _references_ to the elements of s.  Your implementation will
 42    *  create new _nodes_ for the elements of s that are added to "this", but
 43    *  you should reuse the nodes that are already part of "this".
 44    *
 45    *  DO NOT MODIFY THE SET s.
 46    *  DO NOT ATTEMPT TO COPY ELEMENTS; just copy _references_ to them.
 47    **/
 48   public void union(Set s) {
 49     // Your solution here.
 50     if(s != null && !s.setList.isEmpty()){
 51       ListNode curNode = setList.front();
 52       ListNode sNode = s.setList.front();
 53       Comparable curItem, sItem; 
 54       try{
 55       while(curNode.isValidNode() && sNode.isValidNode()){
 56         curItem = (Comparable)curNode.item();
 57         sItem = (Comparable)sNode.item();
 58         if(curItem.compareTo(sItem) == 0){
 59           
 60           sNode = sNode.next();
 61         }else if(curItem.compareTo(sItem) < 0){
 62           if(curNode.next().isValidNode()) {
 63               curNode = curNode.next();}
 64           else {
 65              curNode.insertAfter(sItem);
 66              curNode=curNode.next();
 67              sNode = sNode.next();
 68           }
 69         }else{          
 70           curNode.insertBefore(sItem);
 71           sNode = sNode.next();
 72           
 73         }
 74       }    
 75     }catch(InvalidNodeException e){
 76       System.err.println("union() failed");
 77     }
 78   }
 79   }
 80   /**
 81    *  intersect() modifies this Set so that it contains the intersection of
 82    *  its own elements and the elements of s.  The Set s is NOT modified.
 83    *
 84    *  Performance:  Must run in O(this.cardinality() + s.cardinality()) time.
 85    *
 86    *  Do not construct any new ListNodes during the execution of intersect.
 87    *  Reuse the nodes of "this" that will be in the intersection.
 88    *
 89    *  DO NOT MODIFY THE SET s.
 90    *  DO NOT CONSTRUCT ANY NEW NODES.
 91    *  DO NOT ATTEMPT TO COPY ELEMENTS.
 92    **/
 93   public void intersect(Set s) {
 94     // Your solution here.
 95          ListNode curNode = setList.front();
 96       ListNode sNode = s.setList.front();
 97       Comparable curItem, sItem;
 98       try{
 99         while(curNode.isValidNode()){
100         if (!sNode.isValidNode()){
101               ListNode node=curNode;
102               curNode=curNode.next();
103               node.remove();
104 
105         }else {
106           curItem = (Comparable)curNode.item();
107           sItem = (Comparable)sNode.item();
108           if(curItem.compareTo(sItem) == 0){
109           curNode = curNode.next();
110           sNode = sNode.next();
111           }else if(curItem.compareTo(sItem) < 0){              
112               ListNode node=curNode;
113               curNode=curNode.next();
114               node.remove();
115 
116           }else if(curItem.compareTo(sItem) > 0){
117                 sNode = sNode.next();
118           }
119         }
120       }
121       }catch(InvalidNodeException e){
122         System.err.println("intersect() failed.");
123       }
124 
125     }

View Code

结果：