Bonjour à tous,  
Je voudrais poser une 'tite question sur les listes chainnées et plus particulierement sur l'optimisation.
Je veux pouvoir insérer en ordre croissant deux listes triées chainées dans une autre.Tout cela pour l'instant est assez simple.
J'ai codé une solution avec trois listes triées chainées simple. Mais je me dis aussi que je peux déclarer une structure chainées comme ceci :
 
struct maillon{
         int val;
         struct maillon* next;   //pointeur pour la liste trié (l1+l2)  
         struct maillon* next2; //pointeur pour la premiere liste trié(l1)
         struct maillon* next3; //pointeur pour la seconde liste trié(l2)
}  
 
ainsi on éconnomiserais de la place en mémoire car on ferais qu'une seule liste de la taille de la premiere liste(l1 & l2) au lieu de trois. En fait lors de l'insertion d'un élément  
il faudrait chainée en ordre pour l3 et en ordre pour la liste l2 ou l1.
Et on pourrais afficher l1, l2 et l3 séparement!
Il faut comprendre de ce fait que chaque maillon seras chainée par au moins deux pointeurs!
Je voudrais savoir si il existe un moyen simple de comparer ces deux méthodes au niveau de l'éxécution? En fait je cherche a savoir qu'elle est la meilleur méthode??
 
Merci d'avance,
 
22 v'la l'anormal
 
 
 
 

 
Pas de pb. Tu as absolument raison.
Ton pb est similaire à celui qui veut faire une liste triée sur plusieurs critères. Il met alors autant de pointeur que de critères mais il n'a qu'une seule liste en mémoire.
 
Seul détail: "next", "next1" et "next2" ne sont pas très parlants. Et, il est d'usage de nommer ses structures "s_qqchose" => "s_maillon" au lieu de "maillon".
Et si tu veux pas avoir à mettre le mot "struct" chaque fois que tu déclares un élément de type "struct s_maillon" tu peux même faire un  
typedef struct s_maillon {...} t_maillon;
Après, tu ne travailles plus qu'avec des "t_maillon"

Merci beaucoup pas de souci pour le typedef je connaissais deja!!!
Mais je voudrais savoir quel est la meilleur solution en termede temps d'exécution??
Existe-t-il un moyen de comparer les deux méthodes  facilement!!
Merci d'avance
 
22 v'la l'anormal

 
A mon avis il n'y a aucune différence en terme de temps.
Que tu aies 3 listes avec un pointeur par liste... ou une seule liste avec 3 ptrs est identique. En final, tu ne manipules à chaque fois que des adresses.  
 
Si tu veux essayer de comparer les deux solutions, tu peux utiliser le profiling avec "gprof"
Il te faut d'abord tout recompiler avec l'option "-pg" et sans l'option "-O"
Ensuite, tu exécutes ton programme comme d'habitude. Cela te génère un fichier appelé "gmon.out" contenant le profil de ton exécution.
Enfin tu utilises la commande "gprof" et celle-ci te décortiquera "gmon.out" pour te donner les temps d'exécution de tes fonctions et leur taux d'occupation par rapport au pgm complet.
 
Plus d'infos ici... http://www.crihan.fr/calcul/tech/doc_ibm/ProfTools

D'un point de vue de la conception, à perfs égales, c'est presque tjrs mieux d'avoir des structures de données bien réfléchies plutôt que des tableaux de données éparpillées qu'il faut gérer indépendamment.

Tout à fait d'accord.

Oki merci beaucoup pour toutes ces réponses!! Longue vie à vous!!