带有优先键的单链表，键不打印

Question

为什么会这样？除了未打印键外，元素的打印顺序也有误。

    pq.enqueue(1,"Some");
    pq.enqueue(2,"Words");
    pq.enqueue(3,"Strange");
    pq.enqueue(4,"Very");
    System.out.println(pq.size());
    pq.dequeue();
    pq.printPQueue();
    System.out.println("Is the list empty? " +pq.isEmpty());

此输出为：

4
Key = 0 Element= Strange
Key = 0 Element= Words
Key = 0 Element= Some
Is the list empty? false

我发现有两个问题，键保持为 0，元素打印顺序错误。

编辑：

接口class，定义方法：

public interface PQInterface {
    public void enqueue(int key, Object element);
    public Object dequeue();
    public int size();
    public boolean isEmpty();
    public void printPQueue();
}

节点class（设置器和获取器）：

public class Node {
    private int key;
    private Object element;
    private Node next;

    public Node(int priority, Object e, Node n){
        element = e;
        next = n;
    }

    public int getKey(){
        return key; 
    }

    public void setKey(int val){
        key = val;
    }

    public Node getNext(){
        return next;
    }

    public void setNext(Node n){
        next = n;
    }

public Object getElement(){
    return element;
}

    public void setElement(Object e){
        element = e;
    }

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

最后，实现接口中定义的方法的 MyPriorityQueueclass。

public class MyPriorityQueue implements PQInterface {

private Node head;
private int size;
private Node curr;
private Node prev;

public MyPriorityQueue() {
    head = null;
    size = 0;
    curr = null;
    prev = null;
}

private void setCurrent(int index){
    prev=null;
    curr=head;
    for(int k=1; k<index; k++){
        prev=curr;
        curr=curr.getNext();
    }
}

private int findInsertPosition(int newkey){
    Node aNode=head;
    boolean found;
    int position;
    found=false;
    position=1;
    while(aNode!=null && !found){
        if(aNode.getKey()>newkey){
            aNode=aNode.getNext();
            position=position+1;
        }
        else{
            found=true;
        }
    }
    return position;
}

public void add(int index, int priorkey, Object item){
    if(index==1){
        Node newNode = new Node(priorkey,item,head);
        head=newNode;
    }
    else{
        setCurrent(index);
        Node newNode = new Node(priorkey,item,curr);
        prev.setNext(newNode);
    }
    size=size+1;
}

private void add(int priorkey, Object element){
    Node newNode = new Node(priorkey,element,null);
    if(head==null){
        head=newNode;
    }
    else{
        setCurrent(size);
        curr.setNext(newNode);
    }
    size=size+1;
}

@Override
public void enqueue(int priorkey, Object item) {
    int index;
    index = findInsertPosition(priorkey);
    if (index > size) {
        add(priorkey, item);
    } else {
        add(index, priorkey, item);
    }

}

@Override
public Object dequeue(){
    Node toBeRemoved;
    toBeRemoved = head;
    head = head.getNext();
    size = size-1;
    return toBeRemoved;
}

@Override
public int size() {
    return size;
}

@Override
public boolean isEmpty() {
    if (size == 0) {
        return true;
    } else {
        return false;
    }
}

@Override
public void printPQueue(){
    Node aNode=head;
    while(aNode!=null){
        System.out.println("Key = "+aNode.getKey()+" Element= "+aNode.getElement());
        aNode=aNode.getNext();
    }
}

}

Answer 1

您永远不会将优先级存储在 Node 对象中：

public class Node {
    private int key;
    private Object element;
    private Node next;

    public Node(int priority, Object e, Node n){ // priority parameter is not used
        element = e;
        next = n;
    }
    ...

这就是密钥保持为 0 的原因。

改为：

public class Node {
    private int key;
    private Object element;
    private Node next;

    public Node(int priority, Object e, Node n){
        element = e;
        next = n;
        key = priority;
    }
    ...

Answer 2

public Node(int priority, Object e, Node n){
    element = e;
    next = n;
}

您从未在节点构造函数中设置密钥。

public Node(int priority, Object e, Node n){
    element = e;
    next = n;
    this.key = priority;
}

带有优先键的单链表，键不打印

Singly linked list with priority keys, keys don't get printed

java

queue

priority-queue

singly-linked-list