[Debutante] Fonction recursive avec un pointeur

**kidney** · 23/03/2006, 10h43

Bonjour,
J'apprend le C cette année et j'ai un projet de graphe où l'on doit sortir le plus court chemin. On a bossé les structures, trouver l'algorithme dijistraka qu'on va devoir programmer. Mais j'ai un p'tit souci sur une fonction recursive qui a un pointeur en paramètre. En effet, mon programme compile mais affiche erreur de segmentation a l'execution. J'ai beaucoup de mal avec les pointeurs, et j'avoue je bute, si au cas, vous voyez mon erreur. Merci bcp

Structure du graphe:

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
 
/*SOMMET*/
typedef struct Sommet
{
	char *nomSommet;
	int code;
	struct Sommet *predecesseur;
	struct ChainonRue *premiereRue;
}Sommet;
 
typedef struct ChainonRue
{
	char			*nomRue;
	int			poids;
	Sommet			*sommetSucc;
	struct ChainonRue	*chainonRueSuivant;
}ChainonRue;

Fonction recursive

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
 
/*Ajoute les arcs*/
void ajoutArc(int j,int nbS,ChainonRue *prec)
{
 
	ChainonRue *c=(ChainonRue*)malloc(sizeof(ChainonRue));
 
	int numSom,poids;
 
	while(j<=nbS)
	{
 
		/*Creation du chainon*/
	       	fscanf(f,"%d",&poids);
	       	c->poids=poids;
	       	fscanf(f,"%d",&numSom);
		c->sommetSucc=&tabSommet[numSom];
		c->chainonRueSuivant=NULL;
		printf("chainon cree : %d %d \n",c->poids,numSom);
	      	if(j==1)
	       		prec=c;
		else
			prec->chainonRueSuivant=c;
	       	ajoutArc(j++,nbS,c);
	}	
}

Appel de ma fonction

Code :

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

ajoutArc(j,nbSucc,tabSommet[i].premiereRue);

**fearyourself** · 23/03/2006, 11h05

Ton code est largement trop dangereux pour qu'on donne une raison précise pour le segmentation fault, mais je vais tout de même tenter d'aider. Voici quelques remarques:

Code :

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

1
2
 
   ChainonRue *c=(ChainonRue*)malloc(sizeof(ChainonRue));

On ne cast plus le retour de malloc et on teste le retour pour vérifier qu'il est non NULL.

Code :

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

1
2
3
4
             fscanf(f,"%d",&poids);
             c->poids=poids;
             fscanf(f,"%d",&numSom);
      c->sommetSucc=&tabSommet[numSom];

Comment savoir si f est bien initialisé? Comment savoir si numSom ne vaut pas -2, 3241234? Il faut ajouter des tests et éviter les variables globales (ou au moins l'accès direct aux variables globales).

Code :

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

1
2
 
ajoutArc(j++,nbS,c);

Ne jamais mettre un j++ au milileu d'un appel comme celui-ci, au final tu fais cela:

Code :

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

1
2
ajoutArc(j,nbS,c); 
j++;

Est-ce vraiment ce que tu veux?

Code :

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

ajoutArc(j,nbSucc,tabSommet[i].premiereRue);

Comment savoir si j est mal initialisé?
Comment savoir si i est mal initialisé?
Comment savoir si le champs premiereRue est mal initialisé?

Donc il faut d'abord que tu ajoutes tout ces tests, que tu enlèves l'accès direct aux variables globales, que tu nous dises plus précisèment où se trouve le segmentation fault (au moins une indication serait bien), avant qu'on puisse vraiment pouvoir aider.

Sinon, cela revient à juste donner des indices comme j'ai fait,
Jc

**Trap D** · 23/03/2006, 11h06

En C les arguments sont passés par valeur, on peut les modifier dans la fonction, mais au sortir de celle-ci ils reprennent leur ancienne valeur.
Donc

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
void ajoutArc(int j,int nbS,ChainonRue *prec) 
{ 
 
   ChainonRue *c=(ChainonRue*)malloc(sizeof(ChainonRue)); 
 
  // en C, le cast (ChainonRue *) est inutile et parfois nuisible
  // Par contre, il FAUT tester le retopur du malloc
 
   int numSom,poids; 
 
   while(j<=nbS) 
   { 
 
      /*Creation du chainon*/ 
 
             // il vaut mieux ne pas utiliser scanf mais plutôt le couple
             // fgets / strtol :
             // fgets(temp, sizeof(temp), stdin);
             // poids = strtol(temp, NULL, 10); 
 
             fscanf(f,"%d",&poids); 
             c->poids=poids; 
 
             // idem ici pour scanf
             fscanf(f,"%d",&numSom); 
 
      c->sommetSucc=&tabSommet[numSom]; 
      c->chainonRueSuivant=NULL; 
      printf("chainon cree : %d %d \n",c->poids,numSom); 
            if(j==1) 
 
                prec=c;  // ici prec est modifié mais à la sortie de la fonction
                             // il reprend son ancienne valeur, c'est comme si
                             // tu n'avais rien fait.
                            // il faut espérer aussi que prec qui est un pointeur n'est pas NULL !
 
      else 
         prec->chainonRueSuivant=c; 
 
     ajoutArc(j++,nbS,c); 
   }    
}

Il faut donc revoir la conception de ta fonction récursive.
En génral les fonction récursive renvoie des noeuds, donc ici , ton prototype pourrait être

Code :

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

ChainonRue *ajoutArc(int j,int nbS,ChainonRue *prec)

[EDIT] moi c'est d'une seconde (????) que je suis grillé

**kidney** · 23/03/2006, 11h46

Bon j'ai remodifie ma fonction, mais j'ai toujours la meme erreur, en effet je ve modifier la valeur e mon pointeur prec, et que cette valeur reste quand je sors de ma fonction. Ou est-ce que ej me suis trompé pour ça?

Sinon, je sais que l'erreur de segmentation se trouve dans cette fonction, car si je commente mon appel de la fonction, mon programme marche.
La variable j est parfaitement initialisé, avant l appel de ma fonction.
La variable f est une variable globale pour mon fichier.

Mon erreur, c'est certainement, vouloir modifier mon pointeur et que ca reste

mais je trouve pas, c'est compliqué les pointeurs

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
/*Ajoute les arcs*/
void ajoutArc(int j,int nbS,ChainonRue *prec)
{
	int numSom=0,poids=0;
	ChainonRue *c=NULL;
	c=malloc(sizeof(ChainonRue));
	if(c!=NULL)
	{
 
 
		while(j<=nbS)
		{
 
			/*Creation du chainon*/
	       		fscanf(f,"%d",&poids);
	       		c->poids=poids;
	       		fscanf(f,"%d",&numSom);
			c->sommetSucc=&tabSommet[numSom];
			c->chainonRueSuivant=NULL;
			printf("chainon cree : %d %d \n",c->poids,numSom);
	      		if(j==1)
	       			prec=c;
			else
				prec->chainonRueSuivant=c;
			j++;
	       		ajoutArc(j,nbS,c);
		}	
	}
}

**fearyourself** · 23/03/2006, 12h02

Avant de penser à résoudre vraiment le problème, j'ai un problème avec ton algorthme. Ton appel récursif me semble très suspect.

Est-ce que tu peux donner un exemple de fichier texte (simple) contenant un graphe que tu veux modéliser?

Ou est-ce que ej me suis trompé pour ça?

Oui

Tu ne testes toujours pas la valeur de numSom avant de t'en servir pour le tableau tabSommet.

Finalement, il va falloir revoir tout ton algorithme de création du modèle et il y a un autre forum pour cela.

Jc

**Patriarch24** · 23/03/2006, 15h14

trouver l'algorithme dijistraka

Trouver l'algorithme de Dijkstra. Pauvre Edsger, il va se retourner dans sa tombe...

Ne jamais mettre un j++ au milileu d'un appel comme celui-ci, au final tu fais cela:

précision : il ne faut surtout pas faire cela, car le résultat est indéterminé.

Code :

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

1
2
3
4
5
 
while(j ...){
...
j++;
}

Réécrit donc cela en :

Code :

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

1
2
3
for(j=0;j...;++j){
....
}

Pour l'algo de Dijkstra, cf http://wikipedia.fr.

**Trap D** · 23/03/2006, 15h37

Le code

Code :

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

1
2
3
4
5
 
while(j ...){
...
j++;
}

est parfaitement correct, il n'y a abolument aucun problème à faire celà.

Faux est par contre

Code :

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

1
2
3
4
 
while(j++ < 10){
...
}

Quant à ceci, c'est fortement déconseillé mais parfaitement correct

Code :

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

1
2
3
4
5
 
while(++j < 10){
...
 
}

**Patriarch24** · 23/03/2006, 19h15

Le code est parfaitement correct, il n'y a abolument aucun problème à faire celà.

Je n'ai pas dit que c'était faux, mais il s'agit de suivre des idiomes (un while x avec un x++, c'est un for)... C'est pas obligatoire évidemment, mais plus un code est lisible mieux c'est (après c'est une question de philosophie...)

Quant à ceci, c'est fortement déconseillé mais parfaitement correct

D'ou l'utilité d'écrire un for a la place. Mais c'est OK bien sur.

**Lucky-94** · 25/03/2006, 03h47

Envoyé par Patriarch24

(...) (un while x avec un x++, c'est un for)... (...)

Il me semble que toutes instructions itératives peuvent être «*inter-changées*».
Ensuite, c'est à chacun de décider la boucle la mieux adapter pour chaque cas.
En algorithmique, un seul type de boucle est nécessaire et suffisant.
Il suffit de peu de modification pour changer de type de boucle.

Envoyé par Patriarch24

(...) plus un code est lisible mieux c'est (...)

Pour ma part, je trouve qu'utiliser un seul et même type de boucle permet de facilité la lecture et relecture du code (ou algorithme) et j'utilise donc systématiquement le même type de boucle.

**PRomu@ld** · 25/03/2006, 08h08

En C les arguments sont passés par valeur, on peut les modifier dans la fonction, mais au sortir de celle-ci ils reprennent leur ancienne valeur.

Si tu tiens réelement à modifier ton pointeur il faut faire ceci :

void ajoutArc(int j,int nbS,ChainonRue **prec)

Et dans ta fonction tu utilise *prec à la place de prec, du coup tu contournes le problème du passage de paramètres par valeur.

Sinon, je sais que l'erreur de segmentation se trouve dans cette fonction, car si je commente mon appel de la fonction, mon programme marche.

Au vu de ce que tu nous donnes, il nous est impossible de le debugger. Si tu as possibilité d'utiliser un debugger gdb ou ddd, tu peux identifier la ligne qui plante. (tu peux aussi mettre des fprintf(stderr, "coucou") partout mais c'est moins pro !)

En fait je n'ai pas regardé l'algo précisément mais il y a un trucs qui me chagrine: ton tabSommet, il est bien initialisé ?

[Debutante] Fonction recursive avec un pointeur

C

Discussions similaires

Partager

Partager