Bonjour,
J'essaye de trier une liste simplement chainée, j'utilise donc la même méthode que pour un tableau cependant je ne vois pas où est l'erreur.
Quelqu'un pourrait-il m'aider svp ?Code:t_compte* tri(t_compte* liste, int val) { t_compte *precedent, *courant, *temp; courant=liste; while( courant != NULL ) { if( courant->nombre < precedent->nombre) { temp=precedent; precedent=courant; courant=temp; } courant = courant->suivant; } return liste; }
3 erreurs majeures:
- tu échanges des maillons sans modifier les liens de la liste, ça va te donner n'importe quoi. Dessine ce que tu fais avec une feuille, un crayon et une gomme et tu comprendras. Au lieu de cela, ce sont les valeurs des 2 maillons qu'il faut échanger, donc courant->val avec precedent->val
- à aucun moment tu ne définis precedent
- A la fin de la boucle while, seul un élément sera en place. Il faut réitérer avec le reste de la liste non triée (voir tri à bulle)
Dernière modification par Jack ; 23/02/2019 à 14h13. Motif: orthographe
Oui je m'en suis rendu compte après avoir posté que certains truc ont aucun sens ^^ j'essaye et je reviens
C’est très inefficace de trier une liste chaînée de cette façon. Il est sans doute préférable de stocker dans un élément le pointeur suivant et un pointeur vers les données (ou un entier comme dans ton cas)
Et on change simplement le pointeur ou dans ton cas on échange les nombres.
Cela revient à utiliser le même algorithme que pour un tableau : la structure ne bouge pas et on déplace les éléments.
Je dois surement mal comprendre car mes maillons ne bougent pas
Normal : ton code ne fait rien.Envoyé par lilili92
Mais il est écrit comme si tu allais changer les pointeurs au lieu de déplacer les contenus.
Il faut que j'échange 1 à 1 les champs de la structure ?
Si tu as plusieurs champs, tu les mets tous dans une structure différente.
Tu sépares le fait que tu as une structure de données du fait que tu vas l’utiliser dans une liste chaînée. Comme ça, si demain tu veux utiliser les mêmes données dans un tableau, une liste doublement chaînée, un arbre, une hashmap, tu peux le faire sans y toucher.
Et dans ta liste, tu déplaces juste le pointeur vers cette structure. En gros, ta liste chaînée contient 2 champs: donnees* et suivant*
Pour filtrer comme tout à l’heure, tu manipules les suivant*. Pour trier, tu manipules les donnees*.
je n'ai pas bien compris l'idée
Il existe de nombreuses méthodes pour réaliser un tri, avec chacune ses avantages et ses inconvénients. Pour déterminer quelle serait la meilleur, il faudrait s'intéresser au contexte d'utilisation du programme, car les critères de choix dépendent des performances requises par les objectifs, des contraintes imposées par la situation et du coût (en termes de ressources) des différentes opérations envisageables.
Concernant le tri d'une liste chaînée par un simple chaînage avant, la principale contrainte provient du fait qu'un élément ne peut être manipulé à l'intérieur de la liste que si l'élément qui le précède est connu (afin de pouvoir modifier son champ « suivant »), ce qui limite les méthodes de tri applicables directement sur cette liste.
Néanmoins , on peut facilement réaliser un tri à bulle classique, qui parcoure la liste du début à la fin autant de fois que nécessaire (comme Jack l'a indiqué plu haut). Il est d'ailleurs possible d'apporter quelques améliorations à cette technique.
On peut également créer provisoirement une image simplifiée des éléments de la liste dans une structure différente (e.g. liste bidirectionnelle ou tableau) mieux adaptée à une méthode de tri particulière qu'on sait plus efficace. Toutefois, cela rajoute une consommation de mémoire et des temps supplémentaires pour la conversion de la structure.
Pour en revenir au tri à bulle simple, son principe consiste à parcourir la liste du début à la fin. À chaque étape, considérant deux éléments consécutifs En et En+1, on inverse l'ordre de ces deux éléments dans la liste si leur classement est incorrect relativement au tri à réaliser. Pour réaliser cette inversion, on doit avoir accès à l'élément précédent En-1 (ou au pointeur de début de liste si n=0), qui a fort heureusement été manipulé à l'étape précédente : il suffit donc d'en garder une référence entre deux étapes successives. L'inversion est réalisée en réorganisant les pointeurs du chaînage dans les éléments En-1 (ou le pointeur de début de liste si n=0), En et En+1. La liste doit être re-parcourue jusqu'à ce qu'aucune inversion ne soit plus réalisée. Voici un exemple de code :
(non testé)Code:// Tri de la liste par ordre croissant du champ nombre t_compte* triElements(t_compte* liste) { if( liste == NULL ) return NULL; // liste vide, rien à trier if( liste->suivant == NULL ) return liste; // un seul élément, rien à trier t_compte* premier = liste; int recommencer; do { // commence au début de la liste t_compte* precedent = NULL; t_compte* element = premier; t_compte* suivant = element->suivant; recommencer = 0; while( suivant != NULL ) { if( suivant->nombre < element->nombre ) { // si le classement de l'élément et de son suivant est incorrect : // la liste devra être re-parcourue recommencer = 1; // inverse l'élément courant et son suivant if( precedent == NULL ) premier = suivant; else precedent->suivant = suivant; element->suivant = suivant->suivant; suivant->suivant = element; // avance dans la liste precedent = suivant; // nouveau précédent = ancien suivant // nouvel élément = ancien élément (inchangé) suivant = element->suivant; // nouveau suivant = suivant du nouvel élément } else { // si le classement de l'élément et de son suivant est correct : // avance dans la liste precedent = element; // nouveau précédent = ancien élément element = element->suivant; // nouvel élément = ancien suivant suivant = element->suivant; // nouveau suivant = suivant du nouvel élément } } } while( recommencer ); // retourne la nouvelle liste return premier; }
Merci beaucoup pour ces explications, cependant la tête de liste n'est pas affecté pas le tri lors de mes essais
Je n'ai pas de quoi tester ma fonction en ce moment, mais la tête de liste est modifiée ici :
Pour tenir compte de cette modification, la fonction de tri doit être appelée comme ceci :Code:if( precedent == NULL ) premier = suivant;
Code:liste = triElements(liste);
Sinon, voici une autre méthode de tri, qui utilise un tableau regroupant les pointeurs vers les éléments de la liste et la fonction C standard qsort() (penser à inclure malloc.h et stdlib.h) :
(non testé)Code:// Tri de la liste par ordre croissant du champ nombre // fonction de comparaison utilisée par qsort() static int compare (void const *e1, void const *e2) { return (*(t_compte**)e1)->nombre - (*(t_compte**)e2)->nombre; } t_compte* triElements(t_compte* liste) { // compte le nombre d'éléments t_compte* element = liste; size_t nb_elements = 0; while( element != NULL ) { nb_elements++; element = element->suivant; } if( nb_elements < 2 ) return liste; // rien à trier // crée la table des pointeurs vers les éléments t_compte** tableau = (t_compte**)malloc(sizeof(t_compte*)*nb_elements); if( tableau == NULL ) { // signaler l'erreur d'allocation // ... return liste; } // remplit la table avec les pointeurs vers les éléments element = liste; t_compte** p = tableau; while( element != NULL ) { *p++ = element; element = element->suivant; } // effectue le tri (fonction standard) qsort (tableau, nb_elements, sizeof(t_compte*), compare); // reconstitue l'enchaînement de la liste d'après le tableau trié t_compte* premier = tableau[0]; size_t n; for( n=1; n<nb_elements; n++ ) tableau[n-1]->suivant = tableau[n]; tableau[nb_elements-1]->suivant = NULL; free(tableau); return premier; }
Dernière modification par PA5CAL ; 23/02/2019 à 20h43.
Merci énormément pour tout !! tout fonctionne
Une petite explication du tri à bulle, sur la base d'un exemple simple.
Soit une liste chaînée A-B-C-D dont les éléments sont affectés respectivement des nombres 10, 6, 3 et 8 à trier par ordre croissant.
- On commence par comparer A et B, qu'on doit permuter parce qu'ils sont mal ordonnés (10>6). La liste devient B-A-C-D.
- On continue en comparant A et C, qu'on doit permuter parce qu'ils sont mal ordonnés (10>3). La liste devient B-C-A-D.
- On termine en comparant A et D, qu'on doit permuter parce qu'ils sont mal ordonnés (10>8). La liste devient B-C-D-A.
Comme il y a eu des permutations, on doit re-parcourir la liste B-C-D-A.
- On commence par comparer B et C, qu'on doit permuter parce qu'ils sont mal ordonnés (6>3). La liste devient C-B-D-A.
- On continue en comparant B et D, qui sont bien ordonnés (6<8).
- On termine en comparant D et A, qui sont bien ordonnés (8<10).
Comme il y a eu une permutation, on doit re-parcourir la liste C-B-D-A.
- On commence par comparer C et B, qui sont bien ordonnés (3<6).
- On continue en comparant B et D, qui sont bien ordonnés (6<8).
- On termine en comparant D et A, qui sont bien ordonnés (8<10).
Comme il y n'a pas eu de permutation, le tri est terminé et le liste résultante est C-B-D-A (3<6<8<10).
Re : Tri d'une liste chainée
Bonjour,
Je sais que c'est un peu trop tard mais je voudrai partager ma solution ici:
Code:void tri(liste l){ cellule *ptr,*ctr,temp; ptr=l.tete; while(ptr->suiv!=NULL){ ctr=ptr->suiv; while(ctr!=NULL){ if(ptr->moy<ctr->moy){ temp.moy=ptr->moy; temp.cin=ptr->cin; strcpy(temp.nom,ptr->nom); strcpy(temp.prenom,ptr->prenom); ptr->moy=ctr->moy; strcpy(ptr->nom,ctr->nom); strcpy(ptr->prenom,ctr->prenom); ctr->moy=temp.moy; strcpy(ctr->nom,temp.nom); strcpy(ctr->prenom,temp.prenom); }ctr=ctr->suiv; }ptr=ptr->suiv; } }
Dernière modification par gienas ; 17/03/2022 à 07h11. Motif: Ajouté les balises code obligatoires pour les programmes
Là, je n'ai pas le temps de voir si ça marche mais c'est assez propre.
2 remarques :
- tu devrais éviter les instructions juste après un } et aller à la ligne
- le coeur de ta boucle est l'échange de 2 données et d'avoir toutes ces instructions diminuent la lisibilité.
Tu devrais écrire un truc comme
et l'appeler dans ta boucle.Code:void swap(cellule* a, cellule* a) { cellule temp; /* échange a et b en passant par temp */ }
Je ne suis pas que tu aies besoin de faire des strcpy qui va sérieusement ralentir ton algo. Tu peux recopier les pointeurs.
Et pour aller plus loin, tu n'est pas non plus obligé de recopier les cellules : tu peux inverser juste les pointeurs dans la liste ou construire une nouvelle liste triée.
Merci pour tes remarques.
Oui, j'ai essayé le programme que j'ai ecrit et ça marche normalement.
J'ai essayé de travailler avec la fonction qsort comme tu as indiqué, mais j'ai pas su comment je peux le faire.
C'est PA5CAL qui en avait parlé. Il n'est pas beaucoup revenu sur le forum ces 2 dernières années.
Si tu débutes, ce n'est pas grave que tu n'utilises pas qsort. Apprendre à faire marcher du code comme celui que tu as écrit est un bon début.
Le reste viendra après.
Ah d'accord.
Merci pour ta réponse et pour la motivation!!
Les fonctions "toutes faites" sont des boites noires, et quand on débute et qu'on veut travailler l'algorithmie, il vaut mieux réfléchir et créer la fonction.Ah d'accord.
Merci pour ta réponse et pour la motivation!!
C'est dans ce sens qu'il faut prendre le message de pm42.
Ensuite, quand on a besoin vite fait d'un truc fonctionnel, on peut utiliser ces boites noires.
qsort pour pouvoir trier tout et n'importe quoi demande en paramètres une fonction utilisateur qui dit si un élément est supérieur ou inférieur à un autre. On trouve pas mal d'exemples sur le net.
Jusqu'ici tout va bien...
