Voila pas mal tout est dans le titre je cherche à faire un tri par insertion sur une liste simplement chaine (sur un champ string....).

Seulement je tourne en rond, j'ai regarder comment faire le tri par insertion et je n'ai pas trop de probleme a comprendre le concept vive wikipedia (http://fr.wikipedia.org/wiki/Tri_par_insertion)

Alors la ou je ne comprend c'est comment convertir le pseudo code pour qu'il soit appliccable à une liste simplement chainée :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
  procédure tri_insertion(tableau T, entier n)
      pour i de 1 à n - 1
          x := T[i]
          j = i
          tant que j > 0 et T[j - 1] > x
              T[j] = T[j - 1]
              j = j - 1;
          T[j] = x
Bon ok ce code est fait pour un tableau, le truc quand je veux l'appliquer a une liste chainée simple c'est que je ne comprend pas comment recup L[j-1]

Je suis arrivé à un truc du genre :

Ma liste chainé :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
struct produits {
    int numeroProduit;
    string description;
    struct produits *nxt;
};
Mon code de tri :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
 
void trie(produits * &listProduit){
    produits * tmp1 = listProduit;      // tmp est le pointeur qui parcour la liste non trie
    while(tmp1 != NULL){                // pour i de 1 à n - 1
        string desc1 = tmp->description;
        produits *tmp2 = tmp1;          // j = i
        while (tmp2 != NULL) {          // tant que j > 0 et T[j - 1] > x ICI JE NE COMPREND PAS COMMENT ACCEDER A tmp2->j-1..
            tmp2 = tmp2->next;
        }
        tmp1 = tmp1->next;
    }
}
Est ce que quelqu'un pourrait m'aider ce probleme me rend ch....

J'ai essayé tout un tas de chose qui ne fonctionne pas, au beoin je peux montrer mes tests !!! mais je crois que ce qui me manque sont les bases (gestion correct de la liste chaine).

Merci a ceux qui ont lu jusque la et meci a ceux qui pourront m'aider.