java - 我需要一些帮助来解决在 Java 中对优先级队列+链表进行排序的问题

Question

你好我正在尝试使用链表从头开始在 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));

Answer 1

在循环中

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

您总是将新单词与同一元素进行比较，而不是迭代列表(1a)(并且您不断在循环内为temp分配相同的值(1b))。 [更新] 然后将 compareTo 的输出与 1 而不是 0(2) 进行比较。因此，根据 compareTo 的实现，结果可能始终为假。 (据我所知，它不适用于 String.compareTo，因为它可以返回大于 1 的值 - 但这通常不能保证。)[/更新]

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

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

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

问题的一部分是，要使单链表正常工作，您需要始终保留对其头的引用 - 否则您将无法遍历它!您尝试使用 lastAdded 来达到此目的，但这只是混合了两种不同的东西，导致进一步的困惑。请注意，您实际上不需要对最后添加的节点的引用 - 当您要将下一个元素插入列表中时，此信息没有用处。我建议将专用的 head 引用引入图片中，并相应地更改代码(并删除 lastAdded ，除非您确定稍后会需要它)。请注意，这并不能消除对 (4) 的需要 - 即使您只有 head 引用，您仍然需要修改它(尽管并非总是如此 - 仅当在列表开头插入时) .