Tri sur une liste chainée

Bonsoir à tous.

J'ai un petit pépin dans pour finaliser un de mes projets. Vous pourriez peut-être me donner un coup de pouce.

Je lis des donnés à partir d'un fichier texte puis je crée une liste chainée que j'utilise plus tard dans mon code. Dans chaque noeud, on retrouve la description d'un produit.

Je voudrais donc trier ma liste chainée ( à la création ou post-création) par ordre alphabetique de produit. Je ne dois pas utliser la libraire STL donc pas de sort(), tous doit etre fais manuellement. Voici mon noeud:

Code:

---

1 2 3 4 5 6 7 8 9

struct Produit { int numProduit; char description [29]; float prix; int quantite; int qteVendue; Produit* suiv; };

---

Et voici la fonction qui me permet d'inserer un nouveau noeud a la liste déja présente.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

//Insertion produits a la fin void InsertionProduit(DescListe &DL, Produit* n){ Produit* pt = DL.teteProd;   if(DL.teteProd == NULL){//si Ma liste est vide DL.teteProd = n;   }else{ //On rajoute a la fin while(pt->suiv != NULL) pt = pt->suiv; pt->suiv = n; } }

---

Je dois donc comparer le champ "description" et inserer à la bonne position.
Trier à la l'insertion me parait l'option la plus propre. Donc si je ne fais pas fausse route, il faudra gérer 4 cas:

1. Liste vide
2. Inserer à la place de la tete
3. Inserer en plein mileu
4. Inserer à la fin

Merci pour votre aide.

Il te faut pour celà surcharger les opérateurs >, < et == dans ta classe produit. Celà te permettra d'effectuer ensuite facilement le tri.

Salut,

Citation:

---

Envoyé par Leclandestin

1. Liste vide
2. Inserer à la place de la tete
3. Inserer en plein mileu
4. Inserer à la fin

---

Ce sera déjà un bon début.

Mais sinon, c'est quoi la question ? Qu'on te le fasse à ta place ?

Même question c'est quoi la question?
Sinon on peut, suivant la taille de la liste :

Ajouter
Trier

Mais il faut bien sur réaliser une fonction de tri.

Bonjour,

Me guider vers la bonne démarche à suivre serait apprecié. J'imagine qu'il y a plusieurs facon d'effectuer ce tri. Je ne vous demande pas de le faire à ma place(n'est ce pas 3D archi). Mais plutot de me guider vers la meilleure option à prendre. J'ai réussi à effectuer le tri à l'insertion: voici le code.

Quelqu'un voit une meilleure solution?

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

void InsertionProduit(DescListe &DL, Produit* n){ Produit *temp,*pt2,*pt1; int i=0;//ns indique combien de fois on a comparer et le resultat >0 bool b=false;//ns indique si on a inserer l element if(DL.teteProd== NULL){//si Ma liste est vide DL.teteProd = n; }else{ pt2 = DL.teteProd; pt1=DL.teteProd; while(pt2 != NULL && !b){ if (strcmp(n->description,pt2->description)>0){ pt1=pt2; pt2=pt2->suiv; i++; } else{ temp=pt2; n->suiv=temp; if(i>0) pt1->suiv=n; else n=DL.teteProd; b=true; } } if (!b) pt1->suiv=n; //cas ou l element a inserer doit etre a la fin } DL.nbProd++; }

---

c'est une liste simplement chainée. Pas forcément que ca va être galère, mais déjà un tri par bulle pourrait déjà marcher. Pour des choses plus efficaces, il se pourrait que tu doives utiliser une liste doublement chaînée a la place.
http://en.wikipedia.org/wiki/Sorting...ing_algorithms