選擇排序鏈接列表

Question

對於我的數據結構類中的賦值，給出了包含整數的鏈表的節點。我一直得到一個空指針異常，但我一直盯着它太久，而且我找不到我弄亂的地方。

---

這裏是我的排序類：

public class Sorter { 

public Sorter() { 

} 

/***** 
* Sorter 
* takes a linked list, sorts it 
* @param head linked list to sort 
* @return sorted linked list 
*/ 
public IntNode nodeSort(IntNode head) { 
    IntNode holderHead = new IntNode(-1, null); 
    IntNode cursor; 
    int currentMax = -1; 
    int count = 0; 

    while (count < head.listLength(head)) { 
     IntNode tempHead = new IntNode(-1, null); 
     for (cursor = head.getLink(); cursor.getLink() != null; cursor = cursor.getLink()) { 
      if (currentMax > cursor.getLink().getData()) { 
       tempHead.setLink(cursor.getLink()); 
      } 
     } 

     if (count == 0) { 
      holderHead.setLink(tempHead.getLink()); 
     } else { 
      tempHead.getLink().setLink(holderHead); 
      holderHead.setLink(null); 
      holderHead = tempHead.getLink(); 
     } 
     count+=1; 
    } 

    return holderHead; 
} 

---

這裏是IntNode類（由我的導師給定）：

public class IntNode { 
    private int data; 
    private IntNode link; 


    public IntNode(int initialData, IntNode initialLink) { 
     data = initialData; 
     link = initialLink; 
    } 


    public void addAfter(int item) { 
     link = new IntNode(item, link); 
    }   


    public int getData() { 
     return data; 
    } 


    public IntNode getLink() { 
     return link;            
    } 


    public static IntNode listCopy(IntNode source) { 
     IntNode copyHead; 
     IntNode copyTail; 

     if (source == null) 
     return null; 

     copyHead = new IntNode(source.data, null); 
     copyTail = copyHead; 

     while (source.link != null) 
     { 
     source = source.link; 
     copyTail.addAfter(source.data); 
     copyTail = copyTail.link; 
     } 

     return copyHead; 
    } 


    public static IntNode[ ] listCopyWithTail(IntNode source) { 
     IntNode copyHead; 
     IntNode copyTail; 
     IntNode[ ] answer = new IntNode[2]; 

     if (source == null) 
     return answer; 

     copyHead = new IntNode(source.data, null); 
     copyTail = copyHead; 

     while (source.link != null) 
     { 
     source = source.link; 
     copyTail.addAfter(source.data); 
     copyTail = copyTail.link; 
     } 

     answer[0] = copyHead; 
     answer[1] = copyTail; 
     return answer; 
    } 


    public static int listLength(IntNode head) { 
     IntNode cursor; 
     int answer; 

     answer = 0; 
     for (cursor = head; cursor != null; cursor = cursor.link) 
     answer++; 

     return answer; 
    } 


    public static IntNode[ ] listPart(IntNode start, IntNode end) { 
     IntNode copyHead; 
     IntNode copyTail; 
     IntNode cursor; 
     IntNode[ ] answer = new IntNode[2]; 

     copyHead = new IntNode(start.data, null); 
     copyTail = copyHead; 
     cursor = start; 

     while (cursor != end) 
     { 
     cursor = cursor.link; 
     if (cursor == null) 
      throw new IllegalArgumentException 
      ("end node was not found on the list"); 
     copyTail.addAfter(cursor.data); 
     copyTail = copyTail.link; 
     } 

     answer[0] = copyHead; 
     answer[1] = copyTail; 
     return answer; 
    }   


    public static IntNode listPosition(IntNode head, int position) { 
     IntNode cursor; 
     int i; 

     if (position <= 0) 
      throw new IllegalArgumentException("position is not positive"); 

     cursor = head; 
     for (i = 1; (i < position) && (cursor != null); i++) 
     cursor = cursor.link; 

     return cursor; 
    } 


    public static IntNode listSearch(IntNode head, int target) { 
     IntNode cursor; 

     for (cursor = head; cursor != null; cursor = cursor.link) 
     if (target == cursor.data) 
      return cursor; 

     return null; 
    } 


    public void removeNodeAfter() { 
     link = link.link; 
    }   


    public void setData(int newData) 
    { 
     data = newData; 
    }                


    public void setLink(IntNode newLink) { 
     link = newLink; 
    } 
} 

---

驅動程序類：

public class Driver { 
    public static void main(String args[]) { 
     IntNode head = new IntNode(-1, null); 
     Sorter sorter = new Sorter(); 

     head.addAfter(2); 
     head.addAfter(4); 
     head.addAfter(5); 
     head.addAfter(3); 
     head.addAfter(6); 
     head.addAfter(9); 
     head.addAfter(8); 
     head.addAfter(10); 

     head.setLink(sorter.nodeSort(head)); 

     for (IntNode i = head; i != null; i = i.getLink()) { 
      System.out.println(i.getData()); 
     } 
    } 
} 

Answer 1

問題在於你的排序方法。我爲您提供一個基於您的數據結構的實現。希望這有助於...

public void selectionSort(IntNode head) { 
    for (IntNode node1 = head; node1 != null; node1 = node1.getLink()) { 
     IntNode min = node1; 
     for (IntNode node2 = node1; node2 != null; node2 = node2.getLink()) { 
      if (min.getData() > node2.getData()) { 
       min = node2; 
      } 

     } 
     IntNode temp = new IntNode(node1.getData(), null); 
     node1.setData(min.getData()); 
     min.setData(temp.getData()); 
    } 
} 

而你並不需要返回頭節點，所以你的主要方法如下所示：

public static void main(String args[]) { 
    IntNode head = new IntNode(-1, null); 
    Sorter sorter = new Sorter(); 

    head.addAfter(4); 
    head.addAfter(5); 
    head.addAfter(2); 
    head.addAfter(3); 
    head.addAfter(6); 
    head.addAfter(9); 
    head.addAfter(8); 
    head.addAfter(10); 

    sorter.selectionSort(head); 

    for (IntNode i = head; i != null; i = i.getLink()) { 
     System.out.println(i.getData()); 
    } 
}