Aide tri Eclatement/fusion

Aide tri Eclatement/fusion - C - Programmation

Marsh Posté le 23-12-2007 à 18:25:59    

Bonjour,
 
Alors voila, je suis actuellement en école d'ingénieur et j'ai un petit TP (langage C) qui me pose un petit soucis.
Voici le sujet (ça serait inutile de vous l'expliquer sans le répéter), il s'agit du TP numéro 6 concernant du tri par fusion : http://91.121.25.51/Sujets-TP.pdf
 
Bon pour la partie Eclatement, ça marche il n'y pas de problème, par contre c'est dans la fusion que j'ai un peu de mal.
 
Voici mon code :
 

Code :
  1. /****************** Définition structure ******************/
  2. typedef struct maillon
  3. {
  4. int a;
  5. struct maillon* suivant;
  6. } Maillon;
  9. /***************** Définition Remplissage *****************/
  10. void Remplir (Maillon* tete, int* liste, int n)
  11. {
  12. int i;
  13. Maillon *p = (Maillon*)malloc (sizeof (Maillon));
  14. Maillon *q = (Maillon*)malloc (sizeof (Maillon));
  16. p = tete;
  18. q->a = *liste;
  19. p->a = q->a;
  20. liste ++;
  22. for (i=0; i<n-1; i++)
  23. {
  24.  q->a = *liste;
  25.  p->suivant = q;
  26.  liste++;
  27.  p = p->suivant;
  28.  q++;
  29. }
  31. p->suivant = NULL;
  32. }
  35. /****************** Fonction Affichage ******************/
  36. void Affichage (Maillon* tete)
  37. {
  38. Maillon* courant = NULL;
  39.     courant = tete;  // Pour partir du début
  40.    
  41. while (courant != NULL)
  42.     {
  43.  printf("%d ", courant->a);
  44.         courant = courant->suivant;   // Passage au maillon suivant
  45.     }
  46. }
  49. /****************** Fonction Eclatement ******************/
  50. void Eclatement (Maillon* tete, Maillon* L1, Maillon* L2, int n)
  51. {
  52. int i, numListe=0, l1=0, l2=0;
  54. Maillon* p = tete;
  55. Maillon* p1 = L1;
  56. Maillon* p2 = L2;
  58. for (i=0; i<n; i++)
  59. {
  60.  switch (numListe)
  61.  {
  62.  case 0 :
  63.   if (i && l1)
  64.   {
  65.    p1->suivant = (Maillon*)malloc(sizeof(Maillon));
  66.    p1 = p1->suivant;
  67.   }
  68.   p1->a = p->a;
  69.   l1++;
  70.   break;
  71.  case 1 :
  72.   if (i && l2)
  73.   {
  74.    p2->suivant = (Maillon*)malloc(sizeof(Maillon));
  75.    p2 = p2->suivant;
  76.   }
  77.   p2->a = p->a;
  78.   l2++;
  79.   break;
  80.  }
  82. /*  switch (numListe)
  83.  {
  84.  case 0 :
  85.   p1->a = p->a;
  86.   l1++;
  87.   break;
  88.  case 1 :
  89.   p2->a = p->a;
  90.   l2++;
  91.   break;
  92.  }*/
  94.  if (i!=n-1)
  95.  {
  96.   if (p->a > p->suivant->a)
  97.   {
  98.    numListe = (numListe + 1)%2;
  99.   }
  100.  }
  102.  p = p->suivant;
  103. }
  105. p1->suivant = NULL;
  106. p2->suivant = NULL;
  107. }
  110. /******************** Fonction Fusion ********************/
  111. void Fusion (Maillon* L1, Maillon* L2, Maillon* tete, int taille)
  112. {
  113. int a=0, b=0;
  114. Maillon* p = tete;
  115. Maillon* p1 = L1;
  116. Maillon* p2 = L2;
  118. while (p1 != NULL || p2 != NULL)
  119. {
  120.  // (1)
  121.  while (p1 == NULL && p2 != NULL)
  122.  {
  123.   p->a = p2->a;
  124.   p = p->suivant;
  125.   p2 = p2->suivant;
  126.  }
  128.  // (2)
  129.  while (p2 == NULL && p1 != NULL)
  130.  {
  131.   p->a = p1->a;
  132.   p = p->suivant;
  133.   p1 = p1->suivant;
  134.  }
  136.  // (3)
  137.  while (p1 != NULL && p2 != NULL)
  138.  {
  139.   // Cas < <
  140.   if (p1->a < p1->suivant->a && p2->a < p2->suivant->a)
  141.   {
  142.    if (p1->a < p2->a)
  143.    {
  144.     p->a = p1->a;
  145.     p = p->suivant;
  146.     p1 = p1->suivant;
  147.    }
  148.    else
  149.    {
  150.     p->a = p2->a;
  151.     p = p->suivant;
  152.     p2 = p2->suivant;
  153.    }
  154.   }
  157.   // Cas > <
  158.   if (p1->a > p1->suivant->a && p2->a < p2->suivant->a)
  159.   {
  160.    if (p1->a < p2->a && !a)
  161.    {
  162.     p->a = p1->a;
  163.     p = p->suivant;
  164.     a=1;
  165.    }
  166.    else
  167.    {
  168.     p->a = p2->a;
  169.     p = p->suivant;
  170.     p2 = p2->suivant;
  171.    }
  172.   }
  174.   // Cas < >
  175.   if (p1->a < p1->suivant->a && p2->a > p2->suivant->a)
  176.   {
  177.    if (p2->a < p1->a && !b)
  178.    {
  179.     p->a = p2->a;
  180.     p = p->suivant;
  181.     b=1;
  182.    }
  183.    else
  184.    {
  185.     p->a = p2->a;
  186.     p = p->suivant;
  187.     p2 = p2->suivant;
  188.    }
  189.   }
  191.   // Cas > >
  192.   if (p1->a > p1->suivant->a && p2->a > p2->suivant->a)
  193.   {
  194.    if (!a && !b)
  195.    {
  196.     if (p1->a < p2->a)
  197.     {
  198.      p->a = p1->a;
  199.      p = p->suivant;
  200.      a=1;
  201.     }
  202.     else
  203.     {
  204.      p->a = p2->a;
  205.      p = p->suivant;
  206.      b=1;
  207.     }
  208.    }
  209.    if (a && !b)
  210.    {
  211.     p->a = p2->a;
  212.     p = p->suivant;
  213.     b=1;
  214.    }
  215.    if (!a && b)
  216.    {
  217.     p->a = p1->a;
  218.     p = p->suivant;
  219.     a=1;
  220.    }
  221.    else
  222.    {
  223.     p1 = p1->suivant;
  224.     p2 = p2->suivant;
  225.     a = 0;
  226.     b = 0;
  227.    }
  228.   }
  229.  }
  230. }
  231. }


 
 
 
Bon déjà il faut savoir que la fusion ne marche pas en fin de liste (je n'ai pas pris en compte dans les comparaison lorsque pX->suivant est NULL), tout simplement parce que je trouvais que c'était déjà asser le bazarre, et qu'avant de m'attaquer à cette partie, j'avais besoin d'un regard extérieur qui puisse me dire comment optimiser un peu de bronx.
Donc voila, ce que j'aimerais, c'est que vous me disiez ce qui peut et doit être simplifier, comment optimiser de bout de code pour le rendre un peu plus "beau".
 
Merci d'avance
 
PS : si vous voyez des erreurs/abérations dans le code, et que vous voulez me le signaler, merci de juste m'indiquer l'endroit sans me donner tout de suite la solution ^^.


---------------
Site de téléchargement d'animés : en reconstruction!
Reply

Marsh Posté le 23-12-2007 à 18:25:59   

Reply

Marsh Posté le 23-12-2007 à 22:21:05    

Salut
 
As-tu écris ton algo de fusion, en pseudo langage avant de l'écrire en C ? Il me parait bien compliqué.
Il me semble qu'une boucle avec un "tant que les deux listes à fusionner ne sont pas vides" est suffisant.
Ensuite lorsque l'une des listes est vide, le travail restant est évident.
A qiuoi te servent les deux nombres a et b ?

Reply

Sujets relatifs:

Leave a Replay

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