Problème de récursivité

**tazmania** · 12/12/2005, 08h37

Slaut à tous, c'est encore moi.

Désolé.
Voila, j'ai encore un petit problème avec les pointeurs et les passages par adresses et par valeur.

Voila, je mets le code, enfin juste l'essentiel (là où il y a l'erreur)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
tab Fusion(tab *T,int p,int q,int r)
{
	int i,j,k;
	tab B;
 
	i=p;
	k=p;
	j=q;
	while(i<q&&j<=r)
	{
		if(T->t[i]<T->t[j])
		{
			B.t[k]=T->t[i];
			i++;
		}
		else
		{
			B.t[k]=T->t[j];
			j++;
		}
		k++;
	}
	while(i<q)
	{
		B.t[k]=T->t[i];
		i++;
		k++;
	}
	while(j<=r)
	{
		B.t[k]=T->t[j];
		j++;
		k++;
	}
	T=&B;
 
	return *T;
 
}
 
tab TriFusion(tab *T, int p, int r)
{
	int q;
 
	if(p<r)
	{
		q=(p+r)/2;
		TriFusion(&T,p,q);
		TriFusion(&T,q+1,r);
		Fusion(&T,p,q,r); 
 
		return *T;
	}
}
 
int main(int arg, char** argv) 
{ 
	int d,f,i;
 
	F.fin = 0;
	for(i=0;i<M;i++) 
	  { 
		  F.t[i]=-1;
		  F.fin++;
	   } 
 
	inserer(&F,9); 
	inserer(&F,4); 
	inserer(&F,3); 
 
	d=0;
	f=6;
	TriFusion(&F,d,f);
 
}

Encore désolé de vous demander de l'aide mais je suis pas encore tout à fait habituer au C.

**khayyam90** · 12/12/2005, 09h06

Envoyé par tazmania

Voila, j'ai encore un petit problème avec les pointeurs et les passages par adresses et par valeur.

les passages par adresse, c'est bien simple, il n'y en a pas en C, comme ca, c'est regle.

et pour ce qui est du code, elle est ou l'erreur ? c'est quoi le probleme ?

**tazmania** · 12/12/2005, 09h31

Ok pour le passage par adresse. Je retiens, merci pour l'info.
Le problème vient d'ici :

TriFusion(&T,p,q);
TriFusion(&T,q+1,r);
Fusion(&T,p,q,r);

Lorsque je compile, il m'indique ceci :

passing argument 1 of 'TriFusion' from incompatible pointer type et
passing argument 1 of 'Fusion' from incompatible pointer type
mais également no newline at end of file.
Je comprends que les deux premières erreurs viennent d'un problème de pointeurs.
La dernière, je ne vois pas ce que cela peut être.
Et au final, il ne me rend pas mon tableau trié.

**fearyourself** · 12/12/2005, 09h35

passing argument 1 of 'TriFusion' from incompatible pointer type et
passing argument 1 of 'Fusion' from incompatible pointer type
mais également no newline at end of file.

Logique, tes fonctions ont comme prototype:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
tab Fusion(tab *T,int p,int q,int r);
tab TriFusion(tab *T, int p, int r);

Mais toi tu passe en argument:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 TriFusion(&T,p,q);
TriFusion(&T,q+1,r);
Fusion(&T,p,q,r);

Donc un

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

tab**

Par contre, je te conseille de revoir tes définitions de pointeurs, ce qu'ils représentent et surtout je te conseillerais (vu comment tu t'en sers de transformer tes fonctions pour qu'elles aient comme prototype):

:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
void Fusion(tab *T,int p,int q,int r);
void TriFusion(tab *T, int p, int r);

Jc

**tazmania** · 12/12/2005, 10h05

Donc je vais relire la partie pointeurs.
Mais dans ta solution je vois pas très bien comment je pourrais mettre void devant ma fonction, sachant qu'elle doit renvoyer une partie de mon tableau.
Et ou c'est que je dois mettre tab** dans mon code. Pour tout mes passages de tableaux dans mes fonctions ?
En tout cas, merci pour ta réponse.

**fearyourself** · 12/12/2005, 10h38

sachant qu'elle doit renvoyer une partie de mon tableau.

Dans ton esprit, il faut qu'elle rende quelque chose mais en fait tu fais travailler toutes les fonctions sur la même zone mémoire... On voit bien que tu comprends tout de même un peu cela vu que tu fais:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
TriFusion(&T,p,q);
TriFusion(&T,q+1,r);
Fusion(&T,p,q,r);

et non

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
T = TriFusion(&T,p,q);
T = TriFusion(&T,q+1,r);
T = Fusion(&T,p,q,r);

**tazmania** · 12/12/2005, 10h48

Ah, je vois ce que tu veux dire. En fait, mes modifications du tableau vont s'opérer dans ma procédure donc void.
Et une fois la procédure terminé, les modifications que j'ai apporté vont être garder dans une partie de la mémoire de l'ordinateur à la place de mon ancien tableau.
Mais dans ce cas, ma fonction inserer peut aussi être une procédure.
Voici ma fonction Inserer :

tab inserer(tab *S, int elt)
{
int i=0;
while(S->t[i]!=-1)
{
i++;
}

return *S;
}

**fearyourself** · 12/12/2005, 10h53

Et une fois la procédure terminé, les modifications que j'ai apporté vont être garder dans une partie de la mémoire de l'ordinateur à la place de mon ancien tableau.

Non! Tu modifies directement ton tableau de départ!!!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
tab inserer(tab *S, int elt)
{
int i=0;
while(S->t[i]!=-1)
{
i++;
}
 
return *S;
}

Pour une fonction qui se nomme inserer, tu n'inseres pas grand chose...

Et enfin, je peux utiliser ce logo:

**Médinoc** · 12/12/2005, 10h55

qu'est-ce qu'un tab exactement ?

**fearyourself** · 12/12/2005, 11h01

qu'est-ce qu'un tab exactement ?

Je parierais sur:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
typedef struct stab
{
  int t[M];
  int fin;
}tab;

**tazmania** · 12/12/2005, 11h07

Alors voila, un tab c'est sa

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
typedef struct tab { 
   int t[M]; 
   int fin; 
}tab; 
 
tab F;

et si si, j'insere bien quelque chose dans mon tableau. J'ai fais une fonction afficher et elle me resort tout les éléments que j'ai insérer dans mon tableau.

Sinon j'ai essayé de mettre void devant mes fonctions afin de les transformer en procédures. Mais j'ai toujours les mêmes erreurs avec les pointeurs passés en paramètre.

Et si je mets tab **T, j'ai une autre erreur qui apparaît et qui est :
request for member 't' in something not a structure or union.

**fearyourself** · 12/12/2005, 14h15

et si si, j'insere bien quelque chose dans mon tableau. J'ai fais une fonction afficher et elle me resort tout les éléments que j'ai insérer dans mon tableau.

Explique moi comment ta fonction insère quelque chose si tu n'as jamais de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
S->t[i] = .....

dans ta fonction?

**fearyourself** · 12/12/2005, 14h36

Après la digestion, j'ai eu un peu de temps à regarder à ton problème, ta fonction d'insertion serait plutôt:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
void inserer(tab *S, int e)
{
  int i=0;
  while((i<M)&&(S->t[i]!=-1))
  	i++;
 
  if(i<M)
  	{
	S->t[i] = e;
	(S->fin)++;
	}
}

Ensuite, dans ton main, j'écrirais plutôt:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
   F.fin = 0;
   for(i=0;i<M;i++)
     {
        F.t[i]=-1;
      }

La variable fin étant la taille courante du tableau...

Il y a une erreur d'algorithme dans ta fonction fusion, j'ai changé l'initialisation de i et de j et j'ai mis un inférieur ou égal pour le i aussi. C'est pour gérer correctement le cas où il n'y a un seul élément dans ta partie gauche...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void Fusion(tab *T,int p,int q,int r)
{
   int i,j,k;
 
   int tmp[M];
 
   i=p;
   k=p;
   j=q+1;
 
   while(i<=q&&j<=r)
   {
      if(T->t[i]<T->t[j])
      {
         tmp[k]=T->t[i];
         i++;
      }
      else
      {
         tmp[k]=T->t[j];
         j++;
      }
      k++;
   }
 
   while(i<=q)
   {
      tmp[k]=T->t[i];
      i++;
      k++;
   }
   while(j<=r)
   {
      tmp[k]=T->t[j];
      j++;
      k++;
   }
 
   //Recopie
   for(i=p;i<=r;i++)
	T->t[i] = tmp[i];
 
}

Finalement dans le main, j'appelle ta fonction Fusion comme ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
TriFusion(&F,0,F.fin-1);

Je te laisse comme exercice de changer les prototypes des fonctions pour que ceci marche chez toi...

Jc

**tazmania** · 13/12/2005, 12h19

En fait pour l'insertion, j'ai pris le mauvais codé, excuser moi c'était en fait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
 
tab inserer(tab *S, int elt)
{
    int i=0;
    while(S->t[i]!=-1)
    {
      printf("coucou \n");
      i++;
    }
    printf("indice i : %d \n",i);
    S->t[i]=elt;
 
    return *S;
}

Pour le reste je n'ai pas encore testé ton code, je vais l'adapter avec le mieux et je te dirais comment ça se passe.
En tout cas, merci pour ta réponse complète.

**tazmania** · 13/12/2005, 12h45

Bon, j'ai compiler le fichier.c avec les modifications que vous m'avez apportés.
A la compilation, j'ai toujours trois warnings qui sont identiques sauf qu'ils ne concernent pas la même ligne.

Les warnings sont :

TriFusion.c:73: warning: passing argument 1 of 'TriFusion' from incompatible pointer type
TriFusion.c:74: warning: passing argument 1 of 'TriFusion' from incompatible pointer type
TriFusion.c:75: warning: passing argument 1 of 'Fusion' from incompatible pointer type

Et lorsque j'exécute le programme, il me donne mon tableau sans aucn tri dessus, en fait il me recrache le tableau avec les éléments que j'ai placé dedans.

En fait voici le code algoritmique de ce que je veux faire en C:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
Fusion(T: Tableau d'entiers,p: entier,q:entier,f:entier)
    Entrées : T(tableau d'entiers), p,q,r  (indice du tableau tel que p=q<r)
    Sortie : Tableau trié T entre les indices p et r
 
Début
  i,j,k : entier
  B : tableau d'entiers
  i <- p; k <- p; j <-q;
  Tq (i<q et j=r) faire

**tazmania** · 13/12/2005, 13h02

Désolé j'ai l'habitude de faire des tab pour l'indentation.
Je reprends alors

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
    si T(i) < T(j) alors
         B(k) <- T(i)
         i <- i +1
    sinon
         B(k) <- T(j)
         j <- j+1
    fsi
    k <- k + 1
Ftq
Tq (i < q) faire
      B(k) <- T(i)
      i <- i+1
      k <- k+1
Ftq
Tq ( j = r) faire
        B(k)  <- T(i)
        j <- j+1
        k <- k+1
Ftq
T <- B
Fin
 
TriFusion( T: Tableau d'entier, p: entier, r :entier)
   Entrée : T (tableau d'entier)
   Sortie : Tableau trié T entre les indices p et r
 
   Debut
       Si p < r alors
           q <- (p+r)/2
          TriFusion (T,p,q)
          TriFusion (T, q+1,r)
          Fusion (T,p,q,r)
      Fsi
   Fin

**fearyourself** · 13/12/2005, 16h59

Je suppose:

Tq ( j = r) faire

devrait être:

Tq ( j <= r) faire

Ok mais attention pour ton T <- B tu dois faire une copie à la main avec une boucle...

Je suis d'accord pour ton algo, maintenant ton problème c'est que ton code n'est pas bon... C'est inutile de continuer lorsque tu as un warning comme celui-ci:

TriFusion.c:73: warning: passing argument 1 of 'TriFusion' from incompatible pointer type
TriFusion.c:74: warning: passing argument 1 of 'TriFusion' from incompatible pointer type
TriFusion.c:75: warning: passing argument 1 of 'Fusion' from incompatible pointer type

Cela veut dire que les arguments sont mal passés... Montre les prototypes de tes fonctions et comment tu les appelles...

**tazmania** · 14/12/2005, 09h56

C'est exacte

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
Tq ( j = r) faire

corresponf à

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
Tq ( j <= r) faire

Oui, j'ai vu pour T<-B devait être fait par une boucle, comme tu l'avais fait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
 
   //Recopie
   for(i=p;i<=r;i++)
   T->t[i] = tmp[i];

Sinon voici mes prototypes de mes fonctions :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
void Fusion(tab *T,int p,int q,int r)
void TriFusion(tab *T, int p, int r)

et voici comment je les appelle tout d'abord dans la procédure Trifusion:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
	TriFusion(&T,p,q);
	TriFusion(&T,q+1,r);
	Fusion(&T,p,q,r);

puis dans le main, juste l'appel de la procédure TriFusion:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
TriFusion(&F,0,F.fin-1);

Les warnings sont déclencher par les appels des différentes procédures dans la procédure Trifusion

**fearyourself** · 14/12/2005, 10h39

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

void TriFusion(tab *T, int p, int r)

Normal, T est déjà un pointeur...

Il ne faut pas faire comme ceci

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
   TriFusion(&T,p,q);
   TriFusion(&T,q+1,r);
   Fusion(&T,p,q,r);

Mais comme ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
   TriFusion(T,p,q);
   TriFusion(T,q+1,r);
   Fusion(T,p,q,r);

**tazmania** · 14/12/2005, 12h27

Lol, à la compilation j'ai aucune erreur et lors ce que je l'exécute j'ai un segmentation fault.
Je crois que cela s'arrive lorsque l'on affecte le tableau T par le tableau tmp c'est à dire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
   //Recopie
   for(i=p;i<=r;i++)
   T->t[i] = tmp[i];

Problème de récursivité

C

Discussions similaires

Partager

Partager