J'ai besoin d'aide pour résoudre un problème de tri d'une liste chaînée prioritaire + en Java

Question

Bonjour J'essaie d'implémenter une file d'attente prioritaire en Java avec une liste chaînée mais j'ai un problème de tri des éléments lors de l'insertion. Voici mon programme jusqu'à présent, toute aide serait massivement appréciée.

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

sorties Actuellement:

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

Upadate: méthode addSort Changed être:

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

Cette Déclenche une exception pointeur NULL à

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

Answer 1

Dans la boucle

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

vous comparez toujours le nouveau mot au même élément, au lieu de itérer la liste (1a) (et vous continuez à attribuer temp la même valeur dans la boucle (1b)). [Mise à jour] Et vous comparez la sortie de compareTo à 1 au lieu de 0 (2). Ainsi, en fonction de la mise en œuvre de compareTo - le résultat peut toujours être faux. (Autant que je sache, il ne serait pas pour String.compareTo spécifiquement, car il peut renvoyer des valeurs supérieures à 1 - mais cela ne garantit en général.) [/ Mise à jour]

Et puis, quel que soit le résultat de vos chèques, vous toujours ajouter le nouvel élément après le dernier élément ajouté (3).

Cependant, puisque vous ne réglez pas lastAdded(4), il gardera pointant vers le même élément (tail), donc en effet tail sera toujours le premier article dans votre liste, pas le dernier.

Mise à jour 2: dans vos mises à jour, vous addSort questions fixes (2) et (4) ci-dessus, mais (1a-b) et (3) sont toujours là. Une partie du problème est que pour une liste à liaison unique au travail, vous devez garder une référence à tête à tout moment - sinon vous n'avez aucun moyen de le parcourir! Vous essayez en quelque sorte d'utiliser lastAdded à cette fin, mais cela ne fait que mélanger deux choses différentes, ce qui crée une confusion supplémentaire. Notez que vous n'avez pas réellement besoin d'une référence au dernier nœud ajouté - cette information ne sert à rien lorsque vous êtes sur le point d'insérer l'élément suivant dans la liste. Je recommande d'insérer une référence dédiée head dans l'image et de modifier le code en conséquence (et de laisser tomber lastAdded sauf si vous êtes sûr que vous en aurez besoin plus tard).Notez que ceci n'élimine pas le besoin de (4) - même si vous avez une référence head seulement, vous devez toujours le modifier (mais pas toujours - seulement en l'insérant au début de la liste).

Answer 2

Dans le addSort méthode que vous affectez un Node temp à (ce qui semble être) l'endroit où vous voulez insérer le nœud - mais ensuite vous n'utilisez pas cette référence à nouveau après la boucle for.