[Liste Chainée]

[Liste Chainée] - C - Programmation

Marsh Posté le 19-10-2005 à 17:30:08    

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
 
 
 
 


---------------
Hihi j'suis là ou pas?
Reply

Marsh Posté le 19-10-2005 à 17:30:08   

Reply

Marsh Posté le 20-10-2005 à 09:17:55    

Anormal13 a écrit :

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"


---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le 21-10-2005 à 18:56:11    

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


---------------
Hihi j'suis là ou pas?
Reply

Marsh Posté le 21-10-2005 à 22:23:47    

Anormal13 a écrit :

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


---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le 22-10-2005 à 10:25:19    

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.


---------------
Les aéroports où il fait bon attendre, voila un topic qu'il est bien
Reply

Marsh Posté le 22-10-2005 à 11:08:15    

el muchacho a écrit :

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.


---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/
Reply

Marsh Posté le 23-10-2005 à 15:52:00    

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


---------------
Hihi j'suis là ou pas?
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed