0

您好，我正在尝试使用链表从头开始在 Java 中实现优先级队列，但在插入时对元素进行排序时遇到问题。到目前为止，这是我的程序，任何帮助将不胜感激。 

import java.util.Scanner;

public class T0 {

    public static void main(String args[]) {
        Scanner keyboard = new Scanner(System.in);

        PQ myList = new PQ();

        myList.addSort("Z");
        myList.addSort("B");
        myList.addSort("C");
        myList.addSort("B");
        myList.addSort("Z");

        System.out.println(myList.view(0));
        System.out.println(myList.view(1));
        System.out.println(myList.view(2));
        System.out.println(myList.view(3));
        System.out.println(myList.view(4));
    }
}


class PQ {

    Node tail = new Node(null, null);
    int elementCount = 0;

    Node lastAdded = tail;

        public void add(String word) {
        Node added = new Node(word, lastAdded);
        lastAdded=added;
        elementCount++;
    }

    public void addSort(String word){
                Node temp = new Node(null, null);
        for(int n = 0; n<elementCount && word.compareTo(lastAdded.next().toString()) >1; n++){
            temp=lastAdded.next();
        }
        Node added = new Node(word, lastAdded.next());
        lastAdded.changeNext(added);
        elementCount++;
    }

    public String view(int i){
        Node temp = lastAdded;

        for(int n = elementCount; n > i; n--){
            temp=temp.next();
        }
        return temp.toString();

    }
    public String toString() {
        return lastAdded.toString();
    }



    class Node {

        String name;
        Node nextNode;

        public Node(String s, Node n) {
            name = s;
            nextNode = n;
        }
        public void changeNext(Node n){
            nextNode=n;
        }
        public Node next() {
            return nextNode;
        }

        public String toString() {
            return name;
        }
    }
}

目前输出：

   run:
Z
B
C
B
Z
BUILD SUCCESSFUL (total time: 1 second)

更新：将 addSort 更改为：

    public void addSort(String word){
            Node temp = lastAdded;
for(int n = 0; n<elementCount && word.compareTo(lastAdded.next().toString()) > 0; n++){
    temp=lastAdded.next();
}
    Node added = new Node(word, lastAdded.next());
    lastAdded.changeNext(added);
    elementCount++;
    lastAdded=temp;
}

这会引发空指针异常

System.out.println(myList.view(0));
4

2 回答 2

1

在循环

    for(int n = 0; n<elementCount && word.compareTo(lastAdded.next().toString()) >1; n++){
        temp=lastAdded.next();
    }

您总是将新单词与相同的元素进行比较，而不是遍历列表(1a)temp （并且您一直在循​​环(1b)内分配相同的值）。[更新]你比较compareTo1 而不是 0 (2)的输出。因此 - 根据实施compareTo- 结果可能总是错误的。（AFAIK 不会String.compareTo专门针对它，因为它可以返回大于 1 的值 - 但通常不能保证。）[/Update]

然后，无论您的检查结果如何，您总是在最后添加的元素(3)之后添加新元素。

但是，由于您不调整lastAdded (4)，它将一直指向同一个元素 ( tail)，因此实际上tail将始终是列表中的第一项，而不是最后一项。

更新 2：在您的更新addSort中，您修复了上述问题 (2) 和 (4)，但 (1a-b) 和 (3) 仍然存在。

部分问题在于，要使单链表正常工作，您需要始终保持对其头部的引用- 否则您无法遍历它！您有点试图将其lastAdded用于此目的，但这只是将两种不同的东西混合在一起，从而造成了进一步的混乱。请注意，您实际上不需要对最后添加的节点的引用 - 当您将下一个元素插入列表时，此信息没有用。我建议在图片中引入一个专门的head参考，并相应地更改代码（lastAdded除非你确定以后会需要它，否则放弃）。请注意，这并不能消除对 (4) 的需要 - 即使您有head仅供参考，您仍然需要修改它（尽管并非总是如此 - 仅在插入列表开头时）。

于 2010-09-26T11:58:00.933 回答
0

在该addSort方法中，您要分配一个Node temp到（似乎是）要插入节点的位置 - 但是在 for 循环之后您不会再次使用此引用。

于 2010-09-26T11:57:22.353 回答