Tri_fusion en C qui ne fonctionne pas

Tri_fusion en C qui ne fonctionne pas - C - Programmation

Marsh Posté le 11-11-2010 à 17:27:59    

Bonjour,
j'ai un problème avec mon tri et je n'arrive pas à voir où :

Code :
  1. void fusion (int A[], int debut, int milieu, int fin)
  2. {
  3. // n1: longueur de T[debut..milieu], n2: longueur de T[milieu+1..fin]
  4. int n1=milieu-debut+1, n2=fin-milieu;
  5. int L[n1+1], R[n2+1];
  6. int i,j,k;
  7. for(i=1;i<=n1;i++)
  8. L[i]=A[debut+i-1];
  9. for(j=1;j<=n2;j++)
  10. R[j]=A[milieu+j];
  11. i=1;
  12. j=1;
  13. L[n1+1]=101;L[n2+1]=101; // Je met 101 car les valeurs stockés dans le tableau vont de 1 100.
  14. for(k=debut;k<=fin;k++)
  15. {
  16. if (L[i]<=R[j])
  17.  {
  18.  A[k]=L[i];
  19.  i++;
  20.  }
  21. else
  22.  {
  23.  A[k]=R[j];
  24.  j++;
  25.  }
  26. }
  27. }
  29. void tri_fusion (int A[], int debut, int fin)
  30. {int milieu;
  31.   if(debut<fin)
  32.  {
  33.  milieu=(debut+fin)/2;
  34.  tri_fusion(A,debut,milieu);
  35.  tri_fusion(A,milieu+1,fin);
  36.  fusion(A,debut,milieu,fin);
  37.  }
  38. }


 
Merci de votre aide

Message cité 1 fois
Reply

Marsh Posté le 11-11-2010 à 17:27:59   

Reply

Marsh Posté le 11-11-2010 à 19:46:17    

Explique davantage...


---------------
Seul Google le sait...
Reply

Marsh Posté le 11-11-2010 à 20:13:37    

Ben quand j'execute mon code il me renvoit pas le tableau trié et il m'efface des valeurs j'ai l'impression.

Reply

Marsh Posté le 11-11-2010 à 23:10:33    

Code :
  1. int L[n1+1], R[n2+1];


ceci n'est pas possible en C. Le compilateur a besoin de connaitre une taille fixe pour allouer la zone mémoire. Comme n1 et n2 ne seront que connue lors de l’exécution de ton code, le compilateur alors alloue deux tableaux de dimension 1. ( c 'est a dire int tab[1] et non tab[n] )
 
Pour allouer des tableaux dynamiquement en C y faut utiliser la fonction malloc:
 
ex:

Code :
  1. int * copy_tab(int tab[], int debut, int fin){
  2.         int *copy= malloc(sizeof(int)*(fin-debut+1));
  3.         int j, i=0;
  5.         for(j=debut; j < fin+1; j++, i++)
  6.             copy[i]=tab[j];
  7.         return copy;
  8. }


 
 
et ne pas oublier de libérer les tableaux avec free. Afin d'éviter des fuites de mémoire.
par exemple dans ta fonction fusion ca donnerai:

Code :
  1. void fusion(int A[], int debut, int milieu, int fin)
  2. {
  3.     int * L= copy_tab(A, debut,milieu+1);
  4.     int * R= copy_tab(A, milieu+1,fin+1);
  5.     int i=0,j=0, k;
  7.     L[(milieu+1)-debut]=101;
  8.     R[fin-milieu]=101;
  10.     for(k=debut; k<=fin; k++) {
  11.         if ( L[i] <=R[j] ) {
  12.             A[k]=L[i];
  13.             i++;
  14.         } else {
  15.             A[k]=R[j];
  16.             j++;
  17.         }
  18.     }
  19.     free(L);
  20.     free(R);
  21. }

Message cité 2 fois
Message édité par lemxl le 11-11-2010 à 23:13:39
Reply

Marsh Posté le 12-11-2010 à 00:00:42    

Aussi, tu déclares en ligne 5 int L[n1+1] donc un tableau de n1+1 éléments indexés de 0 à n1 et tu dis en ligne 13 L[n1+1]=101, donc tu écris à l'extérieur de ton tableau, ça ne peut faire que des dégâts.

Reply

Marsh Posté le 12-11-2010 à 15:54:02    

lemxl a écrit :

Code :
  1. int L[n1+1], R[n2+1];


ceci n'est pas possible en C. Le compilateur a besoin de connaitre une taille fixe pour allouer la zone mémoire. Comme n1 et n2 ne seront que connue lors de l’exécution de ton code, le compilateur alors alloue deux tableaux de dimension 1. ( c 'est a dire int tab[1] et non tab[n] )

C'est tout a fait possible depuis le C 99. Chercher VLA (Variable Length Array) avec google pour plus de détails.
A+,


Message édité par gilou le 12-11-2010 à 15:57:05

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 15-11-2010 à 18:02:29    

kikoolol13 a écrit :

Bonjour,
j'ai un problème avec mon tri et je n'arrive pas à voir où


Je ne sais pas si c'est le seul problème, mais quand tu fusionnes L et R dans A il manque des vérifications pour que i et j ne débordent pas. Sans ces vérifications tu vas aller lire des valeurs non définies au delà des limites de L, jusqu'à ce que k == fin.
 

lemxl a écrit :

Pour allouer des tableaux dynamiquement en C y faut utiliser la fonction malloc:
 
ex:

Code :
  1. int * copy_tab(int tab[], int debut, int fin){
  2.         int *copy= malloc(sizeof(int)*(fin-debut+1));
  3.         int j, i=0;
  5.         for(j=debut; j < fin+1; j++, i++)
  6.             copy[i]=tab[j];
  7.         return copy;
  8. }



Pourquoi ne pas utiliser memcpy pour recopier les éléments ?
edit : pour clarifier l'exemple je suppose, non ?  [:arn0]


Message édité par Nico404 le 15-11-2010 à 18:05:33
Reply

Sujets relatifs:

Leave a Replay

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