Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1886 connectés 

  FORUM HardWare.fr
  Programmation
  C

  Tri_fusion en C qui ne fonctionne pas

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Tri_fusion en C qui ne fonctionne pas

n°2035443
kikoolol13
Posté le 11-11-2010 à 17:27:59  profilanswer
 

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. }
  28. void tri_fusion (int A[], int debut, int fin)
  29. {int milieu;
  30.   if(debut<fin)
  31.  {
  32.  milieu=(debut+fin)/2;
  33.  tri_fusion(A,debut,milieu);
  34.  tri_fusion(A,milieu+1,fin);
  35.  fusion(A,debut,milieu,fin);
  36.  }
  37. }


 
Merci de votre aide

mood
Publicité
Posté le 11-11-2010 à 17:27:59  profilanswer
 

n°2035466
breizhbugs
Posté le 11-11-2010 à 19:46:17  profilanswer
 

Explique davantage...


---------------
Seul Google le sait...
n°2035479
kikoolol13
Posté le 11-11-2010 à 20:13:37  profilanswer
 

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

n°2035516
lemxl
Posté le 11-11-2010 à 23:10:33  profilanswer
 

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;
  4.         for(j=debut; j < fin+1; j++, i++)
  5.             copy[i]=tab[j];
  6.         return copy;
  7. }


 
 
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;
  6.     L[(milieu+1)-debut]=101;
  7.     R[fin-milieu]=101;
  8.     for(k=debut; k<=fin; k++) {
  9.         if ( L[i] <=R[j] ) {
  10.             A[k]=L[i];
  11.             i++;
  12.         } else {
  13.             A[k]=R[j];
  14.             j++;
  15.         }
  16.     }
  17.     free(L);
  18.     free(R);
  19. }

Message cité 2 fois
Message édité par lemxl le 11-11-2010 à 23:13:39
n°2035523
Trap D
Posté le 12-11-2010 à 00:00:42  profilanswer
 

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.

n°2035684
gilou
Modérateur
Modzilla
Posté le 12-11-2010 à 15:54:02  profilanswer
 

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é!  --
n°2036112
Nico404
Posté le 15-11-2010 à 18:02:29  profilanswer
 

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;
  4.         for(j=debut; j < fin+1; j++, i++)
  5.             copy[i]=tab[j];
  6.         return copy;
  7. }



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

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C

  Tri_fusion en C qui ne fonctionne pas

 

Sujets relatifs
onmouseover ne fonctionne pas[C++] Récupérer la taille d'un fichier binaire
structure en C++[C] Structure de données à utiliser pour le parcours de dossier
[C] Récuper l'utilisateur à partir de l'uid[C#] Erreur lors de l'ouverture d'un fichier
Methode de Tri par ordre alphabétique [Résolu]langage C, message d'erreur
Ouvrir fenêtre Glut depuis fenêtre C#Fonction ok sous ie6 mais ne fonctionne pas sous firefox
Plus de sujets relatifs à : Tri_fusion en C qui ne fonctionne pas


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR