0

我有一个项目，我必须编写一堆排序方法并测量每个方法的时间复杂度，并将结果输出到输出文本文件。程序运行但我在冒泡排序方法中得到一些空指针异常。这是我的代码和错误，如果你能告诉我如何修复我的排序方法，那就太棒了！

链表类：

public class LinkedList {
protected static class Node {
    Comparable item;
    Node prev, next;

    public Node(Comparable newItem, Node prev, Node next) {
        this.item = newItem;
        this.prev = prev;
        this.next = next;
    }

    public Node (Comparable newItem) {
        this(newItem, null, null);
    }

    public Node() {
        this(null, null, null);
    }

    public String toString() {
        return String.valueOf(item);
    }
}

private Node head;
private int size;
public int dataCompares, dataAssigns;
public int loopCompares, loopAssigns;
public int other;

public LinkedList() {
    head = new Node(null, null, null);
    head.prev = head;
    head.next = head;
    size = 0;
}

public boolean add(Comparable newItem) {
    Node newNode = new Node(newItem);
    Node curr;
    if(isEmpty()) {
        head.next = newNode;
        head.prev = newNode;
        newNode.next = head;
        newNode.prev = head;
    } else {
        newNode.next = head;
        newNode.prev = head.prev;
        head.prev.next = newNode;
        head.prev = newNode;
    }
    size++;
    return false;
}

public boolean remove(Comparable item) {
    if(!isEmpty()) {
        Node prev = null;
        Node curr = head;
        while(curr!=null) {
            if(curr.item.compareTo(item)==0) {
                if(prev==null) {
                    head=curr.next;
                } else {
                    prev.next = curr.next;
                    curr=curr.next;
                }
                size--;
                return true;
            }else{
                prev=curr;
                curr = curr.next;
            }
        }
    }
    return false;
}

public void removeAll() {
    this.head.prev = null;
    this.head.next = null;
    size = 0;
}

public boolean isEmpty() {
    return size == 0;
}

public boolean remove(Object item) {
    return true;
}

public void insertSortNode() {  
    Node back = head;
if (size < 2)
    return;
    back = back.next;           // SECOND entry in the list
    while ( back != null ) {      // I.e., end-of-list
           Comparable value = back.item;
        Node curr = head;        // Start at the front
  // Find insertion point for value;
    while (curr != back && value.compareTo(curr.item) >= 0)
            curr = curr.next;
  // Propogate values upward, inserting the value from back
    while (curr != back){  
            Comparable hold = curr.item;
        curr.item = value;
        value = hold;
        curr = curr.next;
    }
    back.item = value;      // Drop final value into place!
    back = back.next;       // Move sorted boundary up
}
} // end insertSort()

       public void selSort() {  
    Node front = head;
   // Nothing to do on an empty list
      if ( front == null )
         return;
      while ( front.next != null ) {     // skips a one-entry list
         Node tiny = front;
         Node curr = front.next;
         Comparable temp = front.item; // start the swap
         for ( ; curr != null ; curr = curr.next ) {  
                if ( tiny.item.compareTo(curr.item) > 0 )
                tiny = curr;
         }
         front.item = tiny.item;       // Finish the swap
         tiny.item = temp;
         front = front.next;           // Advance to the next node
      }
      // The structure is unchanged, so the validity of tail is unchanged.
       }


public void bubbleSort() {
    Node Trav=head.next;
    Node Trail=head.next;
    Comparable temp;
    if (Trav != null)
       Trav = Trav.next;
    while(Trav!=null) {
      if (Trav.item.compareTo(Trail.item)<0) {
        temp = Trail.item;
        Trail.item=Trav.item;
        Trav.item = temp;
      }
      Trail=Trav;
      Trav=Trav.next;
    }
   }

public void insertSortArray() {
    Node insert1, cur, tmp1;
    Comparable temp;
    for(insert1 = this.head.next.next; insert1!=this.head; insert1 = insert1.next) {
    //++loopcompares; ++loopassigns;
        for (cur = head.next; cur!=insert1; cur=cur.next) {
        //++loopCompares; ++loopassigns;
        //++datacompares;
            if(insert1.item.compareTo(cur.item)<0) {
                temp=insert1.item;
                //++dataassign
                tmp1=insert1;
                //++other
                while(tmp1!=cur.prev) {
                //++loopcomares
                    tmp1.item=tmp1.prev.item;
                    tmp1=tmp1.prev;
                    //++dataassign+=2
                }
                //++loopcompares
                cur.item = temp;
                //++dataassign;
                break;
            }
        }
        //++loopcompares; ++loopassigns;
    }
    //++loopcompares; ++loopassigns
}

public void disp6sortsFile(boolean disp, String fileName, String header, String data) {
    FileWriter fw = null;
    PrintWriter pw = null;
    try {
        File file = new File(fileName);
        fw = new FileWriter(file, true);
        pw = new PrintWriter(fw, true);
    } catch (IOException e) {
        System.err.println("File open failed for " +fileName+ "\n" + e);
        System.exit(-1);
    }
    if (disp) {
        pw.print(header + "\n");
    }
        pw.print(data + "\n");
        pw.close();
}
}

这是我的错误：

Exception in thread "main" java.lang.NullPointerException
    at LinkedList.bubbleSort(LinkedList.java:149)
    at LinkListTester.main(LinkListTester.java:51)

linkedlisttester 错误只是 list1.bubbleSort(); 所以冒泡排序是问题所在。

4

1 回答 1

0

改变：

public String toString() {
    return this.item.toString();
}

至：

public String toString() {
    return String.valueOf(item); // Handle null too.
}

为add返回真。如果需要，可能会检查该项目是否为空。

remove是为单个链表编写的。

头部有remove一个空项目，这可能导致错误。此外，由于我们有一个带有虚拟节点的循环列表，因此终止不应该测试空值，而是测试头。否则不存在的项目将无限循环。

public boolean remove(Comparable item) {
if(!isEmpty()) {
    Node prev = null;
    Node curr = head.next; // !
    while(curr!=head) { // !
        if(curr.item.compareTo(item)==0) {
            if(prev==null) { // ! WRONG, but I will not correct home work ;)
                head=curr.next;
            } else {
                prev.next = curr.next;
                curr=curr.next;
            }
            size--;
            return true;
        }else{
            prev=curr;
            curr = curr.next;
        }
    }
}
return false;
}

swap 是为单个链表编写的。

在这里我停止阅读，因为我已经了解了用法。

第二次编辑：

所有算法函数，即bubbleSort，都有以下控制流程：

while(Trav!=null) { ... Trav = Trav.next; }

但是数据结构是循环定义的，所以最终你回到head那里，项目为空。

解决方案是为第一个 Node 设置 prev null，为最后一个 Node 设置 next null。

为了使这一点清晰易读，您可以将其替换为Node head：

Node first;
Node last;
于 2012-05-08T09:08:17.563 回答