Trier une liste chaînée de caractères

Bonjour a tous,
J'ai besoin dans un programme en C de trier une liste chaînée de caractère dans l'ordre alphabétique
(Trier une liste de mot pour les mettre comme dans un dictionnaire)

Et j'ais pas vraiment d'idée de comment faire sa...

Voila donc si quelqu'un a une idée d'une méthode simple et rapide merci ! ;)

Si c'est une liste de caractères, ce n'est pas une liste de mots.

Un moteur de recherche quelconque te donnera des milliers de réponses pour "trier liste chainée".

Tu voulais dire trier une liste chainé de chaines de caractère.

Tu as besoins d'une comparaison de deux chaines de caractères
(
elle existe déjà dans <string.h> -> int strcmp(const char *s1, const char *s2);
negatif -> alors s1<s2
0 -> s1=s2
positif -> si > s2
)



Tu as besoins d'une fonction pour échanger deux maillons.
(dans ce cas il faut connaitre les prédécesseurs)

-De manière générale:
Pour éviter la gestion du premier élément, tu peux stocker le pointeur du dernier élément de la liste
et faire que le suivant du dernier soit le premier (liste chaînée circulaire).
Du coup l'échange devient plus simple à utiliser :)

Ici la data est un pointeur
du coup il est aussi très interessant d'échanger les pointeurs des chaines (plus rapide)

Code:

---

1 2 3 4 5 6 7 8

//echange de 2 noeuds d'une liste chainé circulaire void echangerMaillon(liste* maillonPrecedent_1,liste* maillonPrecedent_2) { liste* tmp=maillonPrecedent_1->suivant;//on sauvegarde le lien vers le premier élément à échanger maillonPrecedent_1->suivant=maillonPrecedent_2->suivant;//on fait pointer vers le deuxième élément maillonPrecedent_2->suivant=tmp;//fin de l'échange }

---

Non, je pense qu'il faut supprimer la liste chainée

Liste chainée -> Tableau, Dictionnaire ou autre -> Tri -> Liste chainée

En théorie

• Le passage de "Liste chainée -> Tableau, Dictionnaire ou autre" coûte un parcours complet de sa liste et n insertions.
• Le tri, c'est simple c'est libre
• Le reconstruction en liste chainée, c'est un parcours complet de sa collection et des insertions en premier (donc cacahuète :mrgreen:)

Ou alors faire un tri à bulles, mais niveau temps cela risque d'être assez long :langue2:

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

procédure tri_bulle(Liste liste) si liste vide retourner fin si   Element* l0 Element* l1 Element* l2   booléen échange_effectué   faire échange_effectué <- faux   l0 <- NULL l1 <- liste l2 <- l1.suivant   tant que l2 non NULL faire si l1.mot après l2.mot faire échange_effectué <- vrai   // Pour échanger il faut 3 maillons // consécutifs pour refaire les liens echanger_2_maillons(l0, l1, l2)   fin si   l0 <- l1 l1 <- l1.suivant l2 <- l1.suivant fin tant que tant que échange_effectué fin procédure

---

Avec les listes chaînées les insertions ont une complexité constante
(contrairement à un tableau où il faut déplacer tous les éléments suivant l'insertion)

Le prix à payer est lors de l'accès au n-ième élément
(là c'est linéaire)

le quicksort peut être appliqué à une liste simplement chaînée ( avec quelques modifs bien sûr :p )

Effectivement, on peut choisir d'autres tris, mais il faut un peu oublier les/ certaines optimisations :mrgreen:

Approximatif, non testé, ... surtout que je fais les fins d'intervalle avec 1 de plus (fin.suivant) :whistle:

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 57 58 59 60 61 62 63 64 65

procédure tri_rapide(Liste liste) si liste vide retourner fin si   Element* l0 // Maillon avant pivot Element* l01 // Maillon avant l1 Element* l1 Element* fin Element* pivot   Pile pile Intervalle intervalle   // Intervalle(début, fin.suivant, précédent de début) pile.empiler( Intervalle(liste, NULL, NULL) )   faire intervalle = pile.depiler()   pivot <- intervalle.debut l0 <- NULL l01 <- pivot l1 <- pivot.suivant fin <- intervalle.fin   tant que l1 non NULL et l1 != fin faire si pivot.mot après l1.mot faire l01.suivant <- l1.suivant   si l0 non vide faire l0.suivant <- l1 sinon si intervalle.precedent non NULL intervalle.precedent.suivant <- l1 sinon liste <- l1 fin si fin si   l1.suivant <- pivot l0 <- l1   l1 <- l01.suivant sinon l1 <- l01 l1 <- l1.suivant fin si fin tant que   si l0 non NULL et intervalle.debut != l0 vide faire si intervalle.debut.suivant != l0 faire pile.empiler( Intervalle(intervalle.debut, pivot, intervalle.precedent) ) sinon tester_echanger_mot(l0, intervalle.debut) fin si fin si   si pivot != fin faire si pivot.suivant != fin faire pile.empiler( Intervalle(pivot.suivant, fin, pivot) ) sinon tester_echanger_mot(pivot.suivant, fin) fin si fin si tant que pile non vide fin procédure

---

* Une liste chainée de caractères est une catastrophe en terme d'espace mémoire utilisé.

Pour 1 caractère de "charge utile" dans un élément de liste il faut
- 1 octet pour le caractère
- 8 octets pour le pointeur sur l'élément (si on est en 64 bits)
- 7 octets de "padding" pour la structure
- 8 ou 16 octets supplémentaires pour les besoins de de l'allocation dynamique.

Soit un gaspillage de l'ordre de 95 %, record d'incompétence qui sera difficile à battre.

* un tri de liste basé sur les plus mauvais algorithmes sur les tableaux (insertion, bulles, sélection) sera encore très mauvais si on le transpose sur les chaines.

Pourtant, il est facile de faire des tris en n.log n sur les listes chainées. La méthode où l'on coupe les données en 2 pour les trier (récursivement) et fusionner ensuite est plus facile à réaliser sur les listes que sur les tableaux, parce qu'on n'a pas la problématique de "fusion sur place".