Tri par insertion sur une liste chainé simple.

Version imprimable

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:

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:

1 2 3 4 5 struct produits { int numeroProduit; string description; struct produits *nxt; };
Mon code de tri :
Code:

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.

20/03/2011, 08h36
3DArchi

Salut,
C'est pour le boulot ou c'est un exercice/projet de cours ?
C'est du C ou du C++ ?

Alors c'est un exercice et c'est en C++.

Et je vous jure je ne veux pas qu on fasse mon exo a ma place, en fait j ai passé la journée de hier sans succés....

Je vous met du code que j'ai testé :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
bool isIn(produits * &listProduit,string desc){
    if(listProduit == NULL) {
        return 1;
    } 
    else {
        if (listProduit->description == desc) {
            return 1;
        } 
        else {
            if(listProduit->description > desc) {
                return 0;
            }
            else {
                return isIn(listProduit->nxt,desc);
            } 
        }
    }
}
 
void add_sort(produits * &listProduit, string desc){
    if(!isIn(listProduit,desc)){
        printf("Test\n");
        produits * tmp = new produits;
        tmp->description = desc;
        if(listProduit == NULL) { 
            listProduit = tmp;
            tmp->nxt = NULL;
        }
        else {
            if(listProduit->description > desc) {
                tmp->nxt    = listProduit;
                listProduit = tmp;
            }
 
void clean(produits *  &listProduit){
    while(listProduit != NULL){
        produits * tmp = listProduit;
                   tmp = listProduit;
           listProduit = listProduit->nxt;
       delete tmp;
    }
}
 
void trie(produits * &listProduit){
    produits * listProduitTrie = NULL; // on cree notre liste qui sera trie
    produits * tmp1 = listProduit;      // tmp est le pointeur qui parcour la liste non trie
 
   while(tmp != NULL){
        add_sort(listProduitTrie,tmp->description);// on ajoute en ordre dans listProduitTrie
        tmp = tmp->nxt;
    }
    produits * aDetruire = listProduit;
    listProduit          = listProduitTrie;
    afficheProduits(listProduitTrie);
    clean(aDetruire); // on detruit ptr pour effacer la liste non triee
}

Probleme, mes deux liste semble vide à la fin :(.

20/03/2011, 14h26
Trademark
Je n'ai pas lu ton code mais au vu de la théorie que tu as exposé, pour moi le plus simple serait de :
- Parcourir la liste jusqu'à trouver la position de l'élément à insérer
- Sauvegarder le pointeur suivant de l'élément courant
- Modifier le pointeur de l'élément courant et le faire pointé sur l'élément à insérer
- Modifier le pointeur de l'élément à insérer par le pointeur précédemment sauvegardé
Il faut également faire attention à :
- Si l'élément doit se placer en tête, il ne faut pas qu'un autre élément pointe sur lui
- Si l'élément doit se placer à la fin, il doit pointer sur NULL
Notez que lorsqu'on fait un tri par insertion sur une liste il ne faut surtout pas déplacer tous les éléments mais modifier les bons pointeurs comme indiqué précédemment.

Bonne chance.

J'en suis finalement arrivé à moitié en effet j'ai reussi a trier la liste chainé par numero de produit mais il était demandé de trié la liste par ordre alphabetique, seulement cela ne fonctionne pas.

Peut etre que vous pourriez m'aider a trouver pourquoi, j'ai le code suivant pour le tri:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
   void tri(produits* &debut) {
        produits* Courant1;
        produits* Courant2;
        int n_numProd,n_quantite,n_quantiteIni;
        float n_prix;
        // char n_desc[27];
        string n_desc;
        Courant1 = debut;
        if (Courant1 == 0) {
            printf("liste vide\n");
        }
        else {
            Courant2 = Courant1->nxt;
            while (Courant1->nxt != 0) {
                while (Courant2 != 0 ) {
                    if (Courant2->numeroProduit > Courant1->numeroProduit) {
                   // if (atoi(Courant2->description.c_str()) > atoi(Courant1->description.c_str())) {
                        // Recupere les valeurs qui vont aller dans courant2
                        n_numProd     = Courant1->numeroProduit;
                        n_quantite    = Courant1->quantite;
                        n_quantiteIni = Courant1->quantiteIni;
                        n_prix        = Courant1->prix;
                        n_desc        = Courant1->description;
                        // Change les valeurs de Courant1
                        Courant1->numeroProduit = Courant2->numeroProduit;
                        Courant1->quantite      = Courant2->quantite;
                        Courant1->quantiteIni   = Courant2->quantiteIni;
                        Courant1->prix          = Courant2->prix;
                        Courant1->description   = Courant2->description;
                        // Change les valeurs de courant2
                        Courant2->numeroProduit = n_numProd;
                        Courant2->quantite      = n_quantite;
                        Courant2->quantiteIni   = n_quantiteIni;
                        Courant2->prix          = n_prix;
                        Courant2->description   = n_desc;
                    }
                    Courant2 = Courant2->nxt;
                }
                Courant1 = Courant1->nxt;
                if (Courant1->nxt != 0) {
                    Courant2 = Courant1->nxt;
                }
            }
        }
    }

Si je fait un tri par numero de produit je n'ai pas de problème par contre lorsque je fait un tri par ordre alphabètique cela ne semble pas correct
j'ai pourtant tester les choses suivantes pour comparer les chaine de caratere :

Code:

1
2
atoi(Courant2->description.c_str()) > atoi(Courant1->description.c_str()))
strcmp(Courant2->description.c_str()),atoi(Courant1->description.c_str()))

Ces deux methodes ne me trie definitivement pas les produits par ordre alphabetique.
Cela viens peut etres de m'on remplissage de la table produit que j'ai effectuer de la facon suivante :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
struct produits {
    int numeroProduit;
    string description;
    float prix;
    int quantite;
    int quantiteIni;
    struct produits *prv;
    struct produits *nxt;
};
 
void insertfin(produits* &debut, int numProd, string desc, float prix, int quantite) {
 
    produits * courant;
    if (debut==0) {
        debut                = new produits;
        debut->numeroProduit = numProd;
        debut->description   = desc;
        debut->prix          = prix;
        debut->quantite      = quantite;
        debut->quantiteIni   = quantite;
        debut->nxt           = 0;
        debut->prv           = 0;
    }
    else {
        courant = debut;
        while (courant->nxt != 0) {
            courant = courant->nxt;
        }
        courant->nxt                = new produits;
        courant->nxt->numeroProduit = numProd;
        courant->nxt->description   = desc;
        courant->nxt->prix          = prix;
        courant->nxt->quantite      = quantite;
        courant->nxt->quantiteIni   = quantite;
        courant->nxt->nxt           = 0;
        courant->nxt->prv           = courant;
    }
}
 
produits * creerProduits() {
    FILE * fproduits;
    fproduits = fopen ("PRODUITS.DON","r");
 
    produits * listProduit = NULL;
    while (!feof(fproduits)) {
        //produits * nouveauProduit  = new produits;
        char tmp[27];
        int numProd, quantite;
        float prix;
        fscanf(fproduits,"%d %26c %f %d\n",&numProd,tmp,&prix,&quantite);
        string desc = tmp;
        insertfin(listProduit, numProd, desc, prix, quantite);
    }
    fclose(fproduits);
    return listProduit;
}

21/03/2011, 13h49
r0d

Bonjour,

la classe string possède des opérateurs de comparaison qui sont parfaits pour ce que tu veux faire. Pourquoi ne les utilises-tu pas directement?
Cela donnerait quelque chose du style:

Code:

Courant2->description > Courant1->description
21/03/2011, 14h54
loula427

:scarymov::boulet:

Je chercher le smiley qui a le sac sur la tete !!! pas trouve... Ca fonctionne parfaitement.
c"est bizarre j'ai pourtant l'impression d'avoir teste ca hier et de me dire ca fonctionne pas !!!!

M'enfin si ca fonctionne tres bien en fait :)