Trier une liste chaînée circulaire unique

Question

J'essaie de trier la liste chaînée circulaire unique après chaque modification. Mais mon code ne fonctionne pas. Je me suis basé sur l'algorithme de tri de sélection. Je fais cela depuis des heures mais je n'arrive pas à obtenir le bon code.

void editList(node *head, int value, int newValue) 
{ 
    node *traverser = head; 
    do { 
     traverser = traverser -> next; 
    }while(traverser -> data != value); 

    traverser -> data = newValue; 

    node *index; 
    node *selection; 
    node *temp = new node; 

    for(index = head; index -> next != head; index = index -> next) { 

     for(selection = head; selection -> next != head; selection = selection -> next) { 
      if(index -> data > selection -> data) { 
       temp -> data = index-> data; 
       index -> data = selection -> data; 
       selection -> data = temp -> data; 

      } 
     }//End of outer loop 

    }//End of sorting 

    return; 
}//End of editList() 

Answer 1

Lors de l'analyse du code source fourni, l'algorithme de tri proposé est très proche de l'attendu « algorithme de tri de sélection ».

Les deux boucles imbriquées sont présentes mais exécutent des fonctions indépendantes.

Étape 1 - exécution d'une véritable boucle imbriquée en incluant la condition de la première dans la deuxième boucle.

Pour trier toute la liste, la sélection commence à partir du nœud suivant de l'index .

for(index = head; index -> next != head; index = index -> next) { 
    // start the selection from the index->next 
    for(selection = index->next; selection -> next != head; selection = selection -> next) { 
     if(index -> data > selection -> data) { 
      temp -> data = index-> data; 
      index -> data = selection -> data; 
      selection -> data = temp -> data; 

     } 
    }//End of outer loop 
}//End of sorting 

Bonus 1 - parce que la permutation est effectuée uniquement au niveau data, au lieu d'utiliser un noeud temporaire, il suffit d'utiliser un nombre entier.

// use just an integer 
int temp; 
... 
temp = index-> data; 
index -> data = selection -> data; 
selection -> data = temp; 

Au lieu de:

// allocated but never freed 
node *temp = new node; 
... 
temp -> data = index-> data; 
index -> data = selection -> data; 
selection -> data = temp -> data; 

Bonus 2 - pour la première partie de recherche pour localiser le noeud ayant le int value à remplacer, pourquoi ne pas utiliser la même structure en boucle pour éviter un ne ayant jamais fumé boucle de fin si aucun noeud n'a la valeur recherchée.

node *traverser; 
// a ending loop to search a value into a circular-list 
for(traverser = head; traverser->next != head; traverser = traverser -> next) { 
    if (traverser -> data == value) { 
     traverser -> data = newValue; 
     break; 
    } 
} 

Au lieu de

node *traverser = head; 
do { 
    traverser = traverser -> next; 
}while(traverser -> data != value); 

traverser -> data = newValue;