maintien de la liste des liens triés

Question

J'essaie de créer et de maintenir une liste de liens triés. Chaque nouvel élément doit être inséré de manière à ce que la liste reste triée. J'ai été capable de le coder mais je ne suis pas trop content de mon code.

Fondamentalement, il ya 4 conditions qui doivent être satisfaites selon moi et dans ma tentative de les atteindre je pense que j'ai rendu le code plus compliqué qu'il devrait l'être.

Je veux juste savoir si quelqu'un l'a codé plus efficacement et si vous pouvez me dire comment améliorer la fonction d'insertion ici. C'est mon code de travail ci-dessous et les conditions dans les commentaires. Pour le garder petit, je ne l'ai pas affiché les fonctions pour supprimer des éléments, détruire la liste etc.

#include <iostream> 

    using namespace std; 

    struct node{ 
     int _val; 
     node* _next; 
    }; 

    void printList(node **s){ 

     node *t = *s; 
     while(t){ 
      cout << t->_val << endl; 
      t = t->_next; 
     } 
    } 

    void insertSortElement(node** s, int val){ 

     node* t = *s; 
     if(t){ 
      if(t->_next == NULL || (t->_val > val)){ 
       node* p = new node(); 
       p->_val = val; 
       if(t->_val > val){ 
        //3. More than 1 element in the list but 1st element > val 
        p->_next = t; 
        *s = p; 
       } 
       else{ 
        //2. Only 1 element in the list and < val 
        t->_next = p; 
       } 
      } 
      else{ 
       //4. More than 1 element and 1st < val 
       node* prev = 0; 
       while(t){ 
        if(t->_val > val) 
         break; 
        prev = t; 
        t = t->_next; 
       } 
       node* p = new node(); 
       p->_val = val; 
       p->_next = t; 
       prev->_next = p; 
      } 
     } 
     else{ 

      //1. no element in the list 
      node* p = new node(); 
      p->_val = val; 
      p->_next = NULL; 
      *s = p; 
     } 
    } 

    int main(){ 
     struct node* s = 0 ; 

     insertSortElement(&s,5); 
     insertSortElement(&s,6); 
     insertSortElement(&s,4); 
     insertSortElement(&s,2); 
     insertSortElement(&s,8); 
     insertSortElement(&s,1); 
     printList(&s); 
    } 

EDIT:

a trouvé une autre mise en œuvre, beaucoup plus simple que le mien et gère tous les cas

void insertSorted(node**s , int val){ 
     node* current = *s; 

       if(current == NULL || current->_val >= val){ 
         node* p = new node(); 
         p->_val = val; 
         p->_next = current; 
         *s = p; 
       } 
       else{ 

         while(current->_next != NULL || current->_next->_val < val) 
           current = current->_next; 

         node* p = new node(); 
         p->_val = val; 
         p->_next = current->_next; 
         current->_next = p; 
       } 
} 

Answer 1

Je pense que vous devriez écrire une méthode insertElement et ensuite réécrire insertSortedElement comme "rechercher la position à insérer, puis appeler simplement insertElement" - Je pense que cela nettoierait le code et le rendrait beaucoup plus logique et lisible.

De cette façon, vous pouvez coder plus modulaire. Tous les cas de bord étranges peuvent être traités par insertElement et vous pouvez optimiser l'insertion et la recherche de position séparément, ce qui conduira à beaucoup moins de confusion.

Certains pseudo-code:

insertElement(node old_node, value val) 
    allocate memory for new node new_node 
    new_node.val = val 
    new_node.next = old_node 
    new_node.prev = old_node.prev 

insertSortedElement(value val) 
    actnode = first node 
    while actnode.next != NULL 
    if (actnode.val >= val) 
     insertElement(actnode, val) 
     break; 
    actnode = actnode.next 

devrait être aussi simple que cela, espère ne rien oublier ...

Answer 2

Une approche plus rapide sera en utilisant la recherche binaire pour trouver le bon endroit pour insérer. Il est appelé "liste de saut".

Vous pouvez également utiliser des santinels pour éviter de vérifier des cas particuliers pour les premier et dernier éléments.

Answer 3

Err ... pourquoi? N'est-ce pas ce que std::multiset est pour?

#include <set> //for std::multiset 
#include <iterator> //for std::ostream_iterator 
#include <algorithm> //for std::copy 
#include <iostream> //for std::cout 

int main() 
{ 
    //Put things in sorted collection. 
    std::multiset<int> collection; 
    collection.insert(5); 
    collection.insert(6); 
    collection.insert(4); 
    collection.insert(2); 
    collection.insert(8); 
    collection.insert(1); 

    //Print them to show sort. 
    std::copy(collection.begin(), collection.end(), std::ostream_iterator(std::cout, "\n")); 
}