java - 选择对链接列表进行排序

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());
    }
}

并且您不需要返回头节点，因此您的 main 方法可以如下所示:

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());
    }
}