tri simple d'insertion sur une liste unidirectionnelle C++

Question

Pour l'instant, je ne suis pas inquiet de l'efficacité et je suis en train d'apprendre. Je me demandais si quelqu'un pouvait m'aider à apprendre une sorte d'insertion simple pour une liste unique. C'est pour mes devoirs, donc je voudrais le comprendre. Voici le code:

char c[13]; 
    r >> c; 
    r >> NumberOfInts; 

    Node *node = new Node; 
    head = node; //start of linked list 

    for(int i = 0; i < NumberOfInts; i++) //this reads from the file and works 
    { 
     r >> node->data; 
     cout << node->data << endl; 
     node ->next = new Node; //creates a new node 
     node = node->next; 

     if(_sortRead) //true 
     { 
      for(int k = 0; k < i; k++) 
      { 
         //insertion sort 
      } 
     } 
    } 

jusqu'à présent je l'ai lu dans un istream donc je dois trier comme il est lu dans le nœud est un struct btw.. Quelqu'un pourrait-il m'aider, s'il vous plaît?

Answer 1

Il semble que vous ajoutiez un noeud supplémentaire à la fin de votre liste. Je suppose que vous finirez avec des données non initialisées dans votre dernier nœud.

Actuellement, vous ajoutez simplement chaque nouveau noeud à la fin de la liste. Au lieu d'ajouter chaque nœud à la fin de la liste, vous devez parcourir la liste entière à partir de l'avant et trouver l'emplacement trié correct. Insérez ensuite le nœud dans cet emplacement trié plutôt qu'à la fin (je crois que c'est la logique que vous avez tenté d'implémenter dans votre boucle //insertion sort)

Answer 2

Essayez d'en construire une en fonction de la liste STL Si vous avez une liste ordonnée, vous pouvez trouver le bon endroit par lower_bound.

template<class T> std::list<T>::iterator insert(std::list<T> &my_list, const T &value) 
{ 
    return my_list.insert(std::lower_bound(my_list.begin(), my_list.begin(), value), value); 
}