Problème de segmentation

1 réponse

Bonjour,
je souhaite réaliser un programme pour trouver le plus court chemin avec un parcours en largeur, mais je ne parviens pas à trouver ce qui fait que lors des tests je trouve une erreur de segmentation.
Une piste ? Un conseil?
Merci bcp !

void Initial_parcours_largeur(int** matrix, int s, int t, int n){   int i;   int** predecesseurs = (int**) malloc(n*sizeof(int*));   for(i = 0; i < n; i++) {     int* ligne = (int*) malloc(n * sizeof(int));     predecesseurs[i] = ligne;}      int** V = (int**) malloc(n*sizeof(int*));   for(i = 0; i < n; i++) {     int* vi = (int*) malloc(n * sizeof(int));     V[i] = vi;}      int* couleur = (int*) malloc (n * sizeof(int));   couleur[s]='N';   for(i=0 ; i<n ; i++){     couleur[i]='B';}   int u=0;   int c=1;   int d=0;   int b;      if (s==t){     printf("%d\n",s+1);   }    else{     for (b=0; b<n; b++){       if (matrix[s][b]==1){  if(couleur[b]=='B'){    couleur[b]='N';    c++;    V[d][u]=b;    predecesseurs[d-1][u]=s;    u++;}}}           if (b==t){        printf("%d\n",s);        printf("%d\n",t);      }   else{     d++;     while (c!=n){       u=0;       int m;       int a;       for (a=0;a<n;a++){  for (m=0;m<n;m++){    if (matrix[V[d-1][a]][m]==1){      if (couleur[m]=='B'){        couleur[m]='N';        c++;        V[d][u]=m;        predecesseurs[d-1][u]=V[d-1][a];}}    if (b==t){      printf("%d\n",s);      printf("%d\n",t);      int* A = (int*) malloc (n*sizeof(int));      A[0]=predecesseurs[d-1][t];      int dep=d;      int x=1;      while (dep!=1){        A[x]=predecesseurs[dep][A[x-1]];        dep--;        x++;}      printf("%d\n",s);      int z;      for (z=d;z>0;z--){        printf("%d\n",A[z]);}  }  }     }     d++;}}}   free(couleur);   if (c>=n && n!=1){printf("not connected");}    for(i = 0; i < n; i++) {     free(predecesseurs[i]);}   }  int main() {     int i,j;     int n, s, t;     scanf("%d",&n);     int** matrix = (int**) malloc(n*sizeof(int*));      for(i = 0; i < n; i++) {         int* line = (int*) malloc(n * sizeof(int));         matrix[i] = line;         for(j = 0; j < n; j++) {             scanf("%d", &line[j]);      }     }            scanf("%d", &s);     scanf("%d", &t);     s--;     t--;     Initial_parcours_largeur(matrix,s,t,n);        for(i = 0; i < n; i++) {   free(matrix[i]);  }       free(matrix);     return EXIT_SUCCESS; }

Tag:

A voir également:

Forum

A voir également:Problème de segmentationErreur de segmentation c - Conseils pratiques - Langage C Segmentation fault (core dumped) ✓ - Forum - Programmation Le segment d'enregistrement de fichier est illisible - Forum - Matériel informatique Segment tcp - Articles Mise en forme segment excel - Articles

Web: www.shapebootstrap.net

1 réponse

Marsh

NOVEMBER 9, 2013 AT 9:15 PM

Bonjour,

En outre ta fonction de calcul de chemin devrait idéalement ne rien allouer. Elle devrait simplement prendre en paramètre :

le graphe et les poids installés sur ses arcs, ou directement la matrice des poids
le sommet source s
le vecteur (pré-alloué) qui a chaque sommet t associe le poids du (d'un) plus court chemin de s à t
le vecteur (pré-alloué) qui a chaque sommet t associe son (ou l'un de ses) prédécesseurs au sens des plus courts chemins de s à t
Pour information, tu pourrais (comme boost) passer en paramètre l'algèbre de plus court chemin impliquée (dans ton cas (N, min, +) car les poids sont des entiers positifs, on prend les chemins de poids minimaux, et la longueur d'un chemin est obtenue en sommant les poids des arcs). En effet, les mathématiciens ont montré que l'algorithme de Dijkstra était valide dans tout semi anneau (par exemple ([0,1], max, x) ou (N, max, min)). Mais bon, pour le moment, oublions la généralisation de l'algorithme de Dijkstra et tenons-nous en à sa version de base.

Plusieurs conseils :

Tant que tu débogues, hardcode le contenu de ta matrice, et commente la partie où tu saisis tout en attendant. En l'occurrence pour savoir comment déclencher ton erreur de segmentation, il faudrait nous dire quelle est ta matrice de poids, le sommet source, etc...
Ça me paraît très compliqué comme implémentation. Voici le pseudo code que tu pourrais utiliser :

http://www.boost.org/doc/libs/1_41_0/libs/graph/doc/dijkstra_shortest_paths.html

Indique avec des
```
printf
```
ce que l'utilisateur doit saisir (nombre de sommets, poids entre le sommet i et le sommet j, etc.) et les valeurs valides (valeurs positives, valeurs entre 0 et n, etc.) Idéalement contrôle la saisie, et utilise des poids qui garantissent que cette saisie est correcte (par exemple le nombre de sommet devrait être un
```
unsigned int
```
ou un
```
size_t
```
).
Vérifie que pour chaque
```
malloc
```
, tu fais d'ici la fin du programme le
```
free
```
correspondant. Attention à les faire dans le bon ordre. Par exemple si tu désalloues ta matrice, il faut d'abord désallouer les lignes, et ensuite le tableau de lignes.
Essaye de localiser l'erreur de segmentation avec un débogueur (par exemple sous linux on utiliserait
```
gdb
```
), et le cas échéant en mettant des
```
printf
```
un peu partout dans ton code.
Aère ton code (espace autour des opérateurs =, ==, <=) et indente-le (accolades fermante sur une ligne vide et en dessous de la primitive correspondant).

Exemple :

for (i = 0; i < 10; ++i) {   printf("%d\n", i); }

Ensuite il y a au moins une chose qui ne va pas dans ton programme. Si l'utilisateur saisit s=0 et/ou t=0, comme tu décrémentes s, tu peux arriver en dehors de matrix.

réponses:

auteur on Modifié le 1 mars 2018 à 13:30

par exemple sous linux on utiliserait gdb

Oui, gdb avec le core dump produit par l'erreur de segmentation et en utilisant les fonctionnalités de backtrace :

http://www.linux-france.org/article/devl/gdb_howto.html

Sous Linux, on dispose aussi du magnifique Valgrind, pour détecter les fuites mémoire et faire d'autres choses très sympas :

http://valgrind.org/
https://openclassrooms.com/courses/debuguer-facilement-avec-valgrind

Dal

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed

Name *

Email *

URL

Message *