Jordy89
Messages postés4Date d'inscriptionjeudi 3 janvier 2008StatutMembreDernière intervention 4 janvier 2008
-
3 janv. 2008 à 17:00
cs_amar901130
Messages postés1Date d'inscriptiondimanche 14 septembre 2008StatutMembreDernière intervention27 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.
vecchio56
Messages postés6535Date d'inscriptionlundi 16 décembre 2002StatutMembreDernière intervention22 août 201013 3 janv. 2008 à 22:06
e étant l'élément à insérer au bon endroit dans ta liste.
Tu cherches e1 et e2 tels que e1 <= e et e <= e2 (comme tu le fais avec des vecteurs).
La seule chose qui change est la déplacement de l'élément. Si je n'oublies rien, ca doit donner ca:
e.précédent.suivant = e.suivant
e.suivant.precedent = e.precedent
e1.suivant = e
e2.precedent = e
e.precedent =e1
e.suivant = e2
Ceci est pour une liste chainée dans les deux sens
acx01b
Messages postés280Date d'inscriptiondimanche 7 septembre 2003StatutMembreDernière intervention 8 juillet 20146 4 janv. 2008 à 08:53
salut
typedef struct element {
struct element *suivant;
...
} element, *liste;
en général le prototype de la fonction inserer_element
ça sera
void inserer_element(liste *l, element e);
ou bien
liste inserer_element(liste l, element e);
en effet l'élément peu être rajouté au début de la liste et dans ce cas la liste change d'adresse, il faut donc que inserer_element puisse modifier l'adresse de la liste
Vous n’avez pas trouvé la réponse que vous recherchez ?
Jordy89
Messages postés4Date d'inscriptionjeudi 3 janvier 2008StatutMembreDernière intervention 4 janvier 2008 4 janv. 2008 à 09:53
Dans mon cas, tous les éléments sont déjà présents dans la liste. Il ne s'agit pas d'effectuer une insertion dans une liste triée, mais de trier une liste chainée d'élément.
Ca revient au même ?
On considère chaque élément et on modifie son pointeur afin de réordonner la totalité de la liste ?
Jordy89
Messages postés4Date d'inscriptionjeudi 3 janvier 2008StatutMembreDernière intervention 4 janvier 2008 4 janv. 2008 à 09:57
Ou alors on considère chaque élément, on recherche sa place définitive dans la liste, on le supprime de son ancienne place et on insère un nouvel élément à la bonne place avec l'information de celui qu'on a supprimé ?