Tri_fusion en C qui ne fonctionne pas

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Tri_fusion en C qui ne fonctionne pas

kikoolol13

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

Code :

void fusion (int A[], int debut, int milieu, int fin)
{
// n1: longueur de T[debut..milieu], n2: longueur de T[milieu+1..fin]
int n1=milieu-debut+1, n2=fin-milieu;
int L[n1+1], R[n2+1];
int i,j,k;
for(i=1;i<=n1;i++)
L[i]=A[debut+i-1];
for(j=1;j<=n2;j++)
R[j]=A[milieu+j];
i=1;
j=1;
L[n1+1]=101;L[n2+1]=101; // Je met 101 car les valeurs stockés dans le tableau vont de 1 100.
for(k=debut;k<=fin;k++)
{
if (L[i]<=R[j])
{
A[k]=L[i];
i++;
}
else
{
A[k]=R[j];
j++;
}
}
}
void tri_fusion (int A[], int debut, int fin)
{int milieu;
if(debut<fin)
{
milieu=(debut+fin)/2;
tri_fusion(A,debut,milieu);
tri_fusion(A,milieu+1,fin);
fusion(A,debut,milieu,fin);
}
}

Merci de votre aide

Message cité 1 fois

Publicité

breizhbugs

Explique davantage...

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

kikoolol13

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

lemxl

Code :

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 :

int * copy_tab(int tab[], int debut, int fin){
int *copy= malloc(sizeof(int)*(fin-debut+1));
int j, i=0;
for(j=debut; j < fin+1; j++, i++)
copy[i]=tab[j];
return copy;
}

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 :

void fusion(int A[], int debut, int milieu, int fin)
{
int * L= copy_tab(A, debut,milieu+1);
int * R= copy_tab(A, milieu+1,fin+1);
int i=0,j=0, k;
L[(milieu+1)-debut]=101;
R[fin-milieu]=101;
for(k=debut; k<=fin; k++) {
if ( L[i] <=R[j] ) {
A[k]=L[i];
i++;
} else {
A[k]=R[j];
j++;
}
}
free(L);
free(R);
}

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

Trap D

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.

gilou

Modérateur
Modzilla

lemxl a écrit :

Code :

int L[n1+1], R[n2+1];

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é! --

Nico404

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 :

int * copy_tab(int tab[], int debut, int fin){
int *copy= malloc(sizeof(int)*(fin-debut+1));
int j, i=0;
for(j=debut; j < fin+1; j++, i++)
copy[i]=tab[j];
return copy;
}

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

FORUM HardWare.fr

Programmation

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

Page générée en 0.076 secondes