Tri par insertion sur liste simplement chainée

Résolu
Jordy89
Messages postés
4
Date d'inscription
jeudi 3 janvier 2008
Statut
Membre
Dernière intervention
4 janvier 2008
- 3 janv. 2008 à 17:00
cs_amar901130
Messages postés
1
Date d'inscription
dimanche 14 septembre 2008
Statut
Membre
Dernière intervention
27 avril 2009
- 27 avril 2009 à 19:08
Bonjour,

Dans le cadre de la manipulation d'une liste chaînée, je suis amené à effectuer un tri; Je me suis renseigné à gauche et à droite, et il apparait que le tri par insertion serait particulièrement bien adapté.

Cependant, je n'arrive pas à mettre au point l'algorithme réalisant ce tri !
J'ai déjà effectué des tris par insertion sur des vecteurs, et ça ne pose aucun problème.

Quelqu'un pourrait-il m'aider ?

Merci

8 réponses

acx01b
Messages postés
280
Date d'inscription
dimanche 7 septembre 2003
Statut
Membre
Dernière intervention
8 juillet 2014
5
4 janv. 2008 à 10:42
salut

créer une liste chainée se fait en 2 temps (enfin tu peux faire les 2 en même temps aussi)

allouer de la mémoire ou simplement créer les noeuds, puis les connecter ensembles

dans ton cas tu as les noeuds qui sont déja créés suffit de les connecter ensemble

liste trier_liste(liste l) {
  liste liste_tree = NULL;
  while(l) {
    element *e = l;
    l = l->suivant;
    liste_triee = inserer_element(liste_triee, e);
  }
  return liste_triee;
}

tu considères simplement ta liste non triée comme une liste d'éléments à insérer successivement au bon endroit dans la liste vide

c'est pour ça que la fonction trier_liste se résume en fait à inserer_element (le reste est trivial)
si tu comprends pas dis moi
1