probleme algorithme

bonjour,
l'algorithme suivant fait la fusion de deux liste chainé(l1 et l2);
le probleme est dans la procedure fusionner,
en faite cet procedure fusion les deux listes,mais le résultat est stocké a fure et a mesure dans la liste l2 (j'ai deja la solution de fusionner les deux listes sur une 3eme liste,mais je veut économiser de l'espace memoire)

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

typedef struct maillon *ptr; struct maillon { int val; ptr lien;}; typedef maillon listechaine; listechaine l1,l2; void fusionner(struct maillon l1,struct maillon *l2) { ptr pp1,pp2,pp3,pp;pp=l1.lien; pp1=l1.lien; pp2=(*l2).lien; pp3=&(*l2); while((pp!=NULL)&&(pp2!=NULL)) { if((*pp2).val<=(*pp).val) {   pp2=(*pp2).lien; pp3=(*pp3).lien; } else{ pp=(*pp1).lien; (*pp3).lien=pp1; pp=(*pp).lien;   } } if(pp1!=NULL (*pp2).lien=pp1;   }

---

si vous avez pas compris quelque chose n'esitez pas a me le dire.
merci pour votre attention.

Serait-il possible de voir la déclaration de la structure maillon ?

Que veux-tu dire par le fais d'économiser de la mémoire? Éliminer l'utilisation d'une 3e liste?

Citation:

---

Envoyé par brakeche

(j'ai deja la solution de fusionner les deux listes sur une 3eme liste,mais je veut économiser de l'espace memoire)

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

typedef struct maillon *ptr; struct maillon { int val; ptr lien;}; typedef maillon listechaine; listechaine l1,l2; void fusionner(struct maillon l1,struct maillon *l2) { ptr pp1,pp2,pp3,pp;pp=l1.lien; pp1=l1.lien; pp2=(*l2).lien; pp3=&(*l2); while((pp!=NULL)&&(pp2!=NULL)) { if((*pp2).val<=(*pp).val) {   pp2=(*pp2).lien; pp3=(*pp3).lien; } else{ pp=(*pp1).lien; (*pp3).lien=pp1; pp=(*pp).lien;   } } if(pp1!=NULL (*pp2).lien=pp1;   }

---

si vous avez pas compris quelque chose n'esitez pas a me le dire.
merci pour votre attention.

---

Pour info, tu vas choper des ampoules aux doigts :

Code:

---

(*pp2).lien équivaut en C à pp2->lien

---

Mis à part ce détail peu intéressant, tu n'as pas besoin d'une troisième liste d'après moi. Tu as en revanche besoin d'un maillon auxiliaire pour faire tes branchements. Cela change la donne non ?
Utilise un profiler pour voir si ton algo consomme beaucoup en temps. Pour gérer la mémoire, je ne pense pas que tu puisses y faire grand chose...

salut,


je vois un controle sur la valeur de la cellule. IL y a donc un tri pendant la fusion ?

Deuxiemement, je vais faire un peu vieux con mais s'il vous plais commenter vos code. c'est tellement plus simple a comprendre quand c'est explique.



PS : ca confirme en tout cas que le C est vraiment inbuvable. vive les objet !!


cedric :D

Citation:

---

Envoyé par cedric49fr2000

salut,


je vois un controle sur la valeur de la cellule. IL y a donc un tri pendant la fusion ?

Deuxiemement, je vais faire un peu vieux con mais s'il vous plais commenter vos code. c'est tellement plus simple a comprendre quand c'est explique.



PS : ca confirme en tout cas que le C est vraiment inbuvable. vive les objet !!


cedric :D

---

Je ne peux qu'approuver. Mais simplment, ajouter des commentaires rend le code accessible. De plus, il montre une volonté de suivi du code. Il faut penser quand on programme que nous ne serons peut-être pas les futurs repreneurs de la source. Encore, si un jour cela te prend de revenir dessus, tu vas être paumé sans commentaires.

Pour l'objet => PAS MIEUX. On fait pas plus clair. Ou alors, il faut implanter des TAD dans le code... Mais bonjour les struct, malloc et compagnie... :aie:

bah je trouve beaucoup plus simple d'ajouter un objet a une liste ou une pile avec des simple accesseur ou de smethode plus complece dedie.

pas de gestioonde poointeur, ni de gestion memoire.

cedric :)

le principe de cet algorithme c'est de fusionner deux liste l1 et l2(chainé)
bon
on compare le premier element de la liste l2 avec le premier element de l1
si le 1er element de l2 est < au 1er element de l1 on avance l2 (car le reultat de le fusion on vas le mettre dans l2)
puis on continue...
si on trouve que la valeur de l1 est < alors on essaye de modifier son champ lien
bon c'est un peut compliquer , mais si vous derouler avec un stylo, vous comprendrer.

donc tu pars du principe que la liste L2 est ordonne et tu rend une liste L2 toujorus ordonne. une precision importante.

d'autre part, la procedure ne detruit pas la liste L1. celle ci est transmise en copie.



pour le reste , je vais reviser mes pointeurs en C et je reviens loll.




note : je suis vraiment heureux d'avoir appris la prog avec Turbo Pascal.
la gestion des pointeurs y est bien plus simple



cedric :lol:

Citation:

---

Envoyé par brakeche

le principe de cet algorithme c'est de fusionner deux liste l1 et l2(chainé)
bon
on compare le premier element de la liste l2 avec le premier element de l1
si le 1er element de l2 est < au 1er element de l1 on avance l2 (car le reultat de le fusion on vas le mettre dans l2)

---

et si on prend ce bout de code...

Code:

---

1 2 3 4 5 6 7 8

ptr pp1,pp2,pp3,pp;pp=l1.lien; pp1=l1.lien; pp2=(*l2).lien; pp3=&(*l2); while((pp!=NULL)&&(pp2!=NULL)) { if((*pp2).val<=(*pp).val)

---

bon excusez-moi, j'ai accroché des boutons...
mais tu ne compares jamais le premier élément de l2...

certainement par ce que L2 est deja ordonne !!!

cedric

une petite question :

j'ai l'impression que, pour chaque nouvelle element de L1, tu recommences tes comparaisons avec les elements de L2 au debut de L2.

Tu peux me confirmer ?

Ta Liste L1 est elle ordonne ou dans un ordre quelconque ?


cedric :)

merci pour

merci pour votre aide
le probleme est resolu.
si vous voulez plus de details n'esiter pas a m'envoyer des messages
merci