Fusion de 2 listes ordonnées par ordre croissant [Fermé]

Signaler
-
Messages postés
5434
Date d'inscription
mercredi 15 septembre 2004
Statut
Contributeur
Dernière intervention
29 octobre 2020
-
salut , s'il vous plait comment ecrire une fonction deux listes ordonnés par ordre croissant pour avoir une troisième liste ordonnée par ordre croissant sachant qu'il ne faut pas fusionner puis ordonner. Merci en avance

1 réponse

Messages postés
5434
Date d'inscription
mercredi 15 septembre 2004
Statut
Contributeur
Dernière intervention
29 octobre 2020
913
Salut liste,

Tu prends un papier et un crayon avec un exemple de deux listes ordonnées et tu vois comment tu fais pour créer une 3ème ordonnée.

Lorsque tu as compris cela, tu as compris l'algorithme, et tu es en mesure de l'implémenter en langage C.

Dal
Merci je vieux d' essayer de resoudre ce probleme mais je ne trouve la methode pratique j'espere que vous me corrigez la car cette methode comporte une etape répété mais je n'ai pas su comment la corriger . Et merci pour votr aide
Liste *fusion(liste *L1, liste *L2)
Liste *L3, *P;
{while(L1!=NULL)
{if(L1->val > L2->val)
{if(L3== NULL)
{P=(Liste*)malloc(sizeof(liste));
L3=P;}
else{P->suiv=(Liste*)malloc(sizeof(liste));
P=P->suiv;}
L3->val=L1->val;
L3->suiv=NULL;}
else{
{if(L3== NULL)
{P=(Liste*)malloc(sizeof(liste));
L3=P;}
else{P->suiv=(Liste*)malloc(sizeof(liste));
P=P->suiv;}
L3->val=L2->val;
L3->suiv=NULL;}
return L3;}
Messages postés
13066
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
13 novembre 2020
727
Il faut progresser dans la liste L1 ou dans la liste L2 après avoir inséré une valeur dans la liste L3.
Et dans le while, je suggére de continuer si L1 est vide et L2 ne l'est pas.
Je me demande si L3 et P ne sont pas utilisés un peu au hasard : as-tu bien décidé à quoi servaient L3 et P?
Messages postés
5434
Date d'inscription
mercredi 15 septembre 2004
Statut
Contributeur
Dernière intervention
29 octobre 2020
913
Je suppose que ce sont des listes chaînées. Note cependant que "Liste" et "liste" seraient deux types différents pour le C, alors que tu sembles les traiter similairement.

@yg_be : dans le while, je suggére de continuer si L1 est vide et L2 ne l'est pas

oui, mais je pense que la valeur NULL est à considérer dans L1->suiv et L2->suiv et qu'il faut rester dans la boucle de comparaisons tant que l'un ou l'autre n'est pas NULL (pas l'un et l'autre). Quand l'un seulement est NULL, cela signifie qu'on n'a plus de comparaisons à faire et que s'il reste des éléments dans l'autre liste, ils doivent juste être ajoutés à la suite dans L3 jusqu'à épuisement (les listes peuvent être de tailles différentes).

@ layal : tu n'as visiblement pas tenté de compiler ton code, car il ne compile pas. La première erreur frappante étant que la première accolade ouvrante délimitant le code de ta fonction est mal placée (elle devrait être au début de ta fonction (à la fin de la définition des paramètres de la fonction, et avant la déclaration des variables locales à la fonction) et ailleurs il te manque une accolade fermante, ou tu as des accolades répétées ou mal placées... ton style d'indentation est à améliorer, il t'évitera ce genre d'erreurs :

voir par exemple https://fr.wikipedia.org/wiki/Style_d%27indentation#Style_K.26R

Pour éviter de répéter ton allocation de mémoire, alloue ton premier élément de L3 en dehors du while, et alloue l'élément suivant avant la fin du while s'il reste des éléments dans les deux listes.

Si c'est croissant, je crois que tu t'es trompée dans l'ordre
if (L1->val > L2->val) { (...) L3->val=L1->val;
...

Je déterminerai plutôt lequel des deux est plus petit ou égal, et c'est celui-là que je mettrais dans L3.

Je ne vois pas comment tu passes à l'élément suivant de ta liste L1 ou L2 dont tu as pris un élément à mettre en L3... on dirait que ta boucle compare toujours la même chose.


Dal