Tri d'insertion avec une liste individuellement chaînée en C++

Question

J'essaie d'écrire une méthode pour ma classe LinkedList qui va trier une liste chaînée d'objets Person par leur nom. Ma méthode compile bien mais quand j'essaye de trier une liste de personnes, la sortie est incorrecte. Il ne s'arrête jamais non plus. Par exemple, ce code

Person *p1 = new Person("Kirstie", "Booras"); 
Person *p2 = new Person("Alex", "Arosenius"); 
Person *p3 = new Person("Stephanie", "Moewe"); 
Person *p4 = new Person("Bella", "Moewe"); 

LinkedList ll; 
ll.insertFront(*p1); 
ll.insertFront(*p2); 
ll.insertFront(*p3); 
LinkedList newList = ll.insertionSort(); 
newList.print(); 
cout << endl; 

donne cette sortie

Booras, Kirstie 

Arosenius, Alex 

Quelqu'un pourrait-il me aider à comprendre où je suis allé mal avec mon algorithme? Merci!

C'est la méthode que j'utilise pour trier les noms par la première et dernière:

int Person::compareName(Person p) 
{ 
    if (lName.compare(p.lName) > 0) 
    { 
     return 1; 
    } 
    else if (lName.compare(p.lName) == 0) 
    { 
     if (fName.compare(p.fName) > 0) 
     { 
      return 1; 
     } 
     else return -1; 
    } 
    else return -1; 
} 

insertion Méthode de tri:

LinkedList LinkedList::insertionSort() 
    { 
    //create the new list 
    LinkedList newList; 
    newList.front = front; 

    Node *n; 
    Node *current = front; 
    Node *trail = NULL; 

    for(n=front->link; n!= NULL; n = n->link)//cycle through old chain 
{ 
    Node* newNode = n; 

    //cycle through new, sorted chain to find insertion point 
    for(current = newList.front; current != NULL; current = current->link) 
    { 
     //needs to go in the front 
     if(current->per.compareName(n->per) < 0) 
     { 
      break; 
     } 

     else 
     { 
      trail = current; 

     } 
    } 

    //if it needs to be added to the front of the chain 
    if(current == front) 
    { 
     newNode->link = newList.front; 
     newList.front = newNode; 
    } 
    //else goes in middle or at the end 
    else{ 
     newNode->link = current; 
     trail->link = newNode; 
    } 

    return newList; 
} 

Answer 1

Vous avez courant-> dans votre intérieur pour la boucle, et dans l'autre à l'intérieur pour la boucle. Je suppose que vous avez vraiment current = current-> lien dans la boucle for ou il ne fait rien. Si c'est le cas, vous sauteriez tous les autres éléments.

Vous avez également un problème de langage: vous ne créez pas de nouveaux nœuds, vous modifiez les nœuds de votre liste d'origine. Cela signifie que vous modifiez la liste au fur et à mesure que vous la parcourez, ce qui corrompra la liste au fur et à mesure que vous la triez. Le comportement n'est pas défini et dépend de l'ordre dans lequel vous ajoutez des éléments.

Answer 2

Même après avoir corrigé les problèmes de gestion de liste liée (que je n'ai pas examinés), votre fonction compareName() a un défaut - en comparant Person objets qui ont le même nom de famille, il peut retourner de la fonction sans fournir un valeur (dans les cas où Name.compare(p.fName) <= 0). Obtenir un résultat indéterminé à partir de la fonction de comparaison cassera à peu près n'importe quel type.

Puisqu'il s'agit probablement de devoirs, je vais laisser corriger le problème comme un exercice.