Ich habe an einem Projekt mit Knoten gearbeitet und für dieses Projekt müssen wir die Knoten basierend auf der Priorität (0 - 2, wobei 0 die höchste und 2 die niedrigste ist) ordnen, die das Element in den Knoten enthält (in absteigender Reihenfolge) ). Jetzt funktioniert das teilweise so, als ob beim tatsächlichen Tausch beide Elemente gleich sind (ich versuche nur, die Elemente zu tauschen). Zum Beispiel: Ich würde Node_1 eingeben, das ein Prio von 0 enthält, und Node_2, das ein Prio von 1 enthält. Es sollte dann wie folgt bestellt werden:

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

Dann sollte die Methode ausgeführt werden, um sie wie folgt zu ordnen (mit abnehmender Priorität):

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

Stattdessen werden beide Knoten gleich (gleiche Priorität):

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

Dies bleibt gleich, egal wie viele Knoten ich hinzufüge. Sie alle wenden sich an denselben Knoten mit der höchsten Priorität. Jede Hilfe wäre großartig.

Code:

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;


        }

    }

}

Bitte lassen Sie mich wissen, ob es einen besseren Weg gibt, dies zu tun, da ich noch lerne.

-1
TheDasher 24 Feb. 2020 im 05:30

3 Antworten

Beste Antwort

Dies wurde in Andreas 'Antwort gesagt, aber ich werde weiter darauf eingehen. Da dies Java ist, hat Ihre Temperatur (in diesem Fall r) nur einen Verweis auf q. Wenn Sie also write q = p; ändern, ändert sich r auch vollständig. Weil sie auf dieselbe Instanz des Objekts verweisen. Sie müssen ein temporäres Element erstellen, um es ordnungsgemäß auszutauschen. Die richtige Lösung wäre, r ein Objekt zu sein und dann p.item = r zu setzen. Hoffe das hilft.

1
George 24 Feb. 2020 im 04:25

Etwas ähnlicheres vielleicht:

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);

    }

}

Sie behalten die Knoten in derselben Reihenfolge bei, tauschen jedoch die darin enthaltenen Elemente aus. Wir brauchen die Kopie hier nicht in einen dritten Dummy-Werttrick, da wir bereits Verweise auf die beiden Elemente haben (wir brauchten die Verweise trotzdem, um die Prioritäten zu erfassen).

1
Rick 24 Feb. 2020 im 04:22

Ist es möglich, PriorityQueue zu verwenden, anstatt die Sortierfunktion zu implementieren?

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;
0
Katha patel 24 Feb. 2020 im 03:40