Problème de segmentation - Forum C

Problème de segmentation Segmentation de la mémoire en assembleur » Articles Langage C - C/C++ Erreur de segmentation » Conseils pratiques - Langage C [Wine / Ubuntu 64 bit] Segmentation fault (Résolu) » Forum - Ubuntu [langage C] segmentation fault [Résolu] (Résolu) » Forum - C [Algo] Detecter deux segments qui se croisent [Résolu] (Résolu) » Forum - Programmation

span Audetee1216 2 réponses

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:

Forum

Problème de segmentation Segmentation de la mémoire en assembleur » Articles Langage C - C/C++ Erreur de segmentation » Conseils pratiques - Langage C [Wine / Ubuntu 64 bit] Segmentation fault (Résolu) » Forum - Ubuntu [langage C] segmentation fault [Résolu] (Résolu) » Forum - C [Algo] Detecter deux segments qui se croisent [Résolu] (Résolu) » Forum - Programmation

Web: www.shapebootstrap.net

2 réponses

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.

Reply
réponses:

Leave a Replay

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