Segmentation fault in C: Adjacency structure representing graph

Question

Segmentation fault in C: Adjacency structure representing graph

Navigation

#1 by (2 votes)
#2 by (1 votes)

2

I need to create a program to read a graph and represent it in an adjacency structure, however, my compiler is accusing segmentation fault and I can not figure out what might be causing this. Can you help me?

#include <stdio.h>
#include <stdlib.h>

FILE *ent;
FILE *saida;
int V, E;
int **matriz;
struct adj{
    int w, v;
    struct adj *prox;
};
typedef
struct adj grafo;
grafo **G;

void Estrutura (int V);
void M_Adj (int **matriz, int V);
void ZerarMatriz (int **matriz);
void printMatriz (int **matriz, int V);
void printEstrutura (grafo **G, int V);

int main()//(int argc, char *argv[])
    {
    //declarações e abertura de arquivos
    ent = fopen("ent.txt", "r");
    saida = fopen("sai.txt", "w");

    //ler arquivo de entrada e declarações
    int i,v, w, Vi;
    fscanf(ent, "%d %d", &V, &E);

    //alocar matriz
    matriz = malloc(V * sizeof(int*));
    for (i = 0; i < V; i++)
        matriz[i] = (int*)malloc(V * sizeof(int));

    //alocar vetor cabeça do grafo
    G = (grafo **) malloc(sizeof(V*sizeof(grafo)));

    //int matriz[V][V];
    fprintf (saida, "Arquivo de entrada \n \n");
    fprintf(saida, "%d %d \n", V, E);
    for(i = 0; i < V; i++){
        fscanf(ent, "%d", &v);
        fprintf(saida, "%d ", v);
        fscanf(ent, "%d", &w);
        if (w != 0) fscanf(ent, "%d", &Vi);
        while (w != 0){
        fprintf(saida,"%d %d ", w, Vi);
        fscanf(ent, "%d", &w);
        if (w != 0) fscanf(ent, "%d", &Vi);
    }
    fprintf(saida, "\n");
    }
    ZerarMatriz(matriz);
    M_Adj(matriz, V);
    Estrutura(V);
    fclose(ent);
    fclose(saida);
    free(matriz);
    return 0;
}

void Estrutura (int V){
    ent = fopen("ent.txt", "r");
    int i, Vi, w, v, VV, EE;
    fscanf(ent, "%d", &VV);
    fscanf(ent, "%d", &EE);
    printf("Tam: %d %d \n", VV, EE);
    for (i = 0; i < V; i++)
        (G[i]->prox) = NULL; -- O ERRO É ACUSADO AQUI
    struct adj *aux = malloc(sizeof(struct adj));
    for(i = 0; i < V; i++){
        fscanf(ent, "%d %d", &Vi, &w);
        printf("\n %d %d \n", Vi,w);
        while (w != 0){
            fscanf(ent, "%d", &v);
            aux->prox = NULL;
            aux->v = v;
            aux->w = w;
            if (&(G[i]->prox) == NULL){  -- SE EU NÃO COLOCAR O & COMERCIAL TAMBÉM É ACUSADO AQUI
                G[i]->prox = aux;}
            else
            {
                grafo *aux2 = G[i];
                while(&(aux2->prox) != NULL) -- SE EU NÃO COLOCAR O & COMERCIAL TAMBÉM É ACUSADO AQUI
                    aux2 = (grafo *) (aux2->prox); -- ISSO TAMBÉM NÃO PARECE FUNCIONAR
                (aux2->prox) = aux;
                aux2 = NULL;
            }
            fscanf(ent, "%d", &w);
        }
    }
    aux = NULL;
    fprintf(saida," \n Estrutura de Adjacência: \n");
    printEstrutura(G, V);
}

I know it's a bit redundant, but it's for didactic purposes. Thank you.

------------------------------------ Update ---------- ------------------

Victor, thank you very much for the answer but even with these changes there were still some problems, so I decided to add the new vertices at the beginning of the list, with the changes the code looks like this:

void Estrutura (int V){
    ent = fopen("ent.txt", "r");
    int i, Vi, w, v, VV, EE;
    fscanf(ent, "%d", &VV);
    fscanf(ent, "%d", &EE);
    printf("Tam: %d %d \n", VV, EE);
    struct adj *aux = malloc(sizeof(struct adj));
    for(i = 0; i < V; i++){
        fscanf(ent, "%d %d", &Vi, &w);
        printf("\n %d %d ", Vi,w);
        while (w != 0){
            fscanf(ent, "%d", &v);
            printf(" %d %d ", w, v);
            aux->prox = NULL;
            aux->v = v;
            aux->w = w;
            if (G[i] == NULL){
                G[i] = aux;
            }
            else{
                aux->prox = G[i];
                G[i] = aux;
            }
            fscanf(ent, "%d", &w);
        }
    }
    aux = NULL;
    printEstrutura(G, V);
}

void printEstrutura (grafo **G, int V){
    int i;
    struct adj *aux;
    fprintf(saida, "/n PRINTANDO ESTRUTURA :DDDDD");
    for(i = 0; i < V; i++){
        aux = G[i];
        while (aux != NULL){
             fprintf(saida, "%d %d", aux->w, aux->v);
             aux = aux->prox;
        }
    }
}

But with the changes, my code is looped in the print function. I've been working for a long time and this is messing up my income, I'm going to get some sleep to avoid slips like the last one. Thank you.

c grafo

asked by anonymous 24.01.2015 / 15:58

2 answers

1

Victor, I was a little silly to develop the code, whenever I changed the aux it was still pointing to the same position, then it generated the infinite loop in the print. Thanks a lot for the help.

The corrected version looks like this:

for(i = 0; i < V; i++){
    fscanf(ent, "%d %d", &Vi, &w);
    printf("\n %d ", Vi,w);
    while (w != 0){
        aux = malloc(sizeof(struct adj));
        fscanf(ent, "%d ", &v);
        aux->v = v;
        aux->w = w;
        printf("%d %d ", aux->w, aux->v);
        aux->prox = G[Vi];
        G[Vi] = aux;
        fscanf(ent, "%d", &w);
        aux = NULL;
    }
}

25.01.2015 / 14:54

Pass php session value to Ajax Problem with Seed Relationship between Category and Sub-Category in Laravel 4

score 2 · Accepted Answer

I think your main problem is here:

G = (grafo **) malloc(sizeof(V*sizeof(grafo)));

You missed the parentheses! And as a result it will allocate a much smaller amount of memory than it should, which will cause segmentation to fail when you access the pointer some position beyond the one that was allocated.

What you wanted is this from here:

G = (grafo **) malloc(V * sizeof(grafo*));

However, you should always keep in mind that this will create an array of pointers to adjacencies and not an array of adjacencies.

Attention, at this time this memory region will contain garbage, which means you will have an array of invalid pointers.

So, it's a good idea to initialize the array:

G = (grafo **) malloc(V * sizeof(grafo*));
for (i = 0; i < V; i++) {
    G[i] = NULL;
}

More forward, this will go wrong:

for (i = 0; i < V; i++)
    (G[i]->prox) = NULL; // O ERRO É ACUSADO AQUI

Because G[i] is null! And if you have not put that for loop I suggested before, then it will be even worse, because G[i] will be a pointer filled with garbage. The solution is to simply remove this loop from the program, you do not need it.

In the for loop of the Estrutura function, you set nothing to any of the G array positions. So whenever you try to access G[i] , something bad will happen. Somewhere you should do this:

G[i] = alguma_coisa;

Finally, this is not what you want:

if (&(G[i]->prox) == NULL)
...
while(&(aux2->prox) != NULL)

Well, if G[i] is a valid pointer, then &(G[i]->prox) will never be null, since the pointer will always have an address in this case. And if G[i] is an invalid pointer, this will give segmentation failure. The same applies to aux2 . Therefore, with & , or a segmentation fault occurs, or if will never enter and while will never exit.

What you want is not to know if the pointer address is null, but whether the pointer itself is null. Then, remove & .

Incidentally, the address of any variable in the program will never be null, since any variable in which you can use the address operator exists, and if it exists, then it is in some address somewhere in memory. If it does not exist, you're going to have a segmentation fault while trying to access a variable that does not exist. Therefore, the & operator will never give you null as a response *.

*: Except if you are programming some critical part of the operating system or BIOS kernel that needs to manipulate some value in the zero memory position, which you will probably never do.

UPDATE:

I do not see anything wrong with your update code. Make sure that the G array was properly initialized with NULL in all positions. If not, I suggest putting some printf whenever you add some adjacency to the graph and then try to find where and how it can generate something incorrect in the graph that makes printEstrutura loop infinite.

In addition, your new code simplifies this:

        aux->prox = NULL;
        aux->v = v;
        aux->w = w;
        if (G[i] == NULL){
            G[i] = aux;
        }
        else{
            aux->prox = G[i];
            G[i] = aux;
        }

And turn it into this:

        aux->prox = G[i];
        aux->v = v;
        aux->w = w;
        G[i] = aux;