[Debutante] Fonction recursive avec un pointeur

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:

---

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:

---

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:

---

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

---

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:

---

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:

---

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:

---

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:

---

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

---

Est-ce vraiment ce que tu veux?

Code:

---

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

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:

---

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:

---

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

---

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

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:

---

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); } } }

---

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?

Citation:

---

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

Citation:

---

trouver l'algorithme dijistraka

---

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

Citation:

---

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

Citation:

---

Code:

---

1 2 3 4 5

while(j ...){ ... j++; }

---

---

Réécrit donc cela en :

Code:

---

1 2 3

for(j=0;j...;++j){ .... }

---

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

Le code

Code:

---

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:

---

1 2 3 4

while(j++ < 10){ ... }

---

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

Code:

---

1 2 3 4 5

while(++j < 10){ ...   }

---

Citation:

---

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...)

Citation:

---

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.

Citation:

---

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.

Citation:

---

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.

Citation:

---

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 :

Citation:

---

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.

Citation:

---

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