Как вы меняете данные между двумя узлами? (Java)

Question

Я работал над проектом, использующим узлы, и для этого проекта мы должны упорядочить узлы в соответствии с приоритетом (0 - 2, где 0 - самый высокий, а 2 - самый низкий), который содержится в элементе узлов ( в порядке убывания). Теперь у меня это работает частично, так как когда он действительно выполняет обмен, он превращает оба элемента в один и тот же (я только пытаюсь обменять элементы). Например: я бы ввел Node_1, который содержит prio 0, затем Node_2, который содержит prio 1, тогда он должен быть упорядочен как:

Node_2(holds prio 1) --> Node_1(holds prio 0)

, тогда он должен запустить метод для упорядочить их как (с уменьшением приоритета):

Node_1(holds prio 0) --> Node_2(holds prio 1)

, но вместо этого он просто превращает оба узла в один и тот же (один и тот же приоритет):

Node_1(holds prio 0) --> Node_1(holds prio 0)

, независимо от того, как много узлов я добавляю к нему. Все они превращаются в один и тот же узел с наивысшим приоритетом. Любая помощь будет отличной.

Код:

private void sortJobs() {
    Node p, q, r;

    p = jobs;
    q = null;
    r = null;
    //only runs if there is more than 1 job
    while (p != null && p.next != null) {
        q = p;
        p = p.next;

        if (q.item.getPriority() > p.item.getPriority()) {
            r = q;
            q.item = p.item;
            p.item = r.item;


        }

    }

}

Пожалуйста, дайте мне знать, если есть лучший способ сделать это, поскольку я все еще учусь.

Answer 1

Может быть, что-то похожее на это:

private void sortJobs(Node p) {

    if (p != null && p.next != null) {

        Node q = p.next;

        Item pItem = p.getItem();
        Item qItem = q.getItem();

        // check for nulls???  Safety???
        if (qItem.getPriority() < pItem.getPriority()) {

            p.setItem(qItem);
            q.setItem(pItem);

         }

         // almost forgot the recursion
         sortJobs(q);

    }

}

Вы держите узлы в том же порядке, но поменяете местами элементы в них. Нам не нужна копия в третьем трюке с фиктивными значениями, потому что у нас уже есть ссылки на эти два элемента (нам все равно нужны ссылки, чтобы получить приоритеты).

Answer 2

Это было сказано в ответе Андреаса, но я уточню подробнее. Так как это Java, ваш temp (в данном случае r) имеет только ссылку на q. Вот почему при изменении записи q = p;, r также полностью меняется. Потому что они ссылаются на один и тот же экземпляр объекта. Вам нужно создать временный элемент, чтобы поменять местами. Правильным решением было бы иметь объект r, а затем установить p.item = r. Надеюсь, это поможет.

Answer 3

Можно ли использовать PriorityQueue вместо реализации функции сортировки?

PriorityQueue<Node> pq = new PriorityQueue(new Comparator<Node>(){
    public int compare(Node a, Node b){
        return a.item.getPriority()-b.item.getPriority();
    }
});
p=jobs;
if(p==null) return p;
//add all jobs in PriorityQueue
while (p != null) {
    pq.add(p);
    p=p.next;
}
//Change next pointer
Node head=pq.poll();
Node prev=head;
while(pq.size()>0){
    Node n = pq.poll;
    prev.next=n;
    prev=n;
}
return head;