Ошибка сегментации при попытке реализовать алгоритм Прима в файле - PullRequest
Новая
       25

Ошибка сегментации при попытке реализовать алгоритм Прима в файле

0 голосов
/ 07 апреля 2020

Я получаю только Segmentation Fault из своего кода, но он не говорит мне, где. Я предполагаю, что это связано с файлом, но я не совсем уверен. Это единственное, что удерживает меня от тестирования и отладки остальной части кода (если эта реализация Prim действительно работает и файл читается правильно). Не стесняйтесь задавать вопросы. Заранее спасибо!

Вот мой код: 

#include <limits.h>
#include <stdbool.h>
#include <stdio.h>

#define N 10
#define INF INT_MAX
int spanning[N][N];

int main(int argc, char **argv) {
    int prims(int amtrx[][N], int *n);
    void printpaths(int *n);

    if (argc < 2) {
        printf("Missing Filename.\n");
        return(1);
    } else if (argc > 2) {
        printf("Too many arguments.\n");
        return(1);
    }
    FILE* f = fopen(argv[1], "r");

    int *n, *stv, i, j, nsz, nedg, fr, to, vtx, wt;
    vtx = 1111;
    nedg = 999;
    nsz = 100;
    stv = 0;
    n = 0;

    if(f) {
        fscanf(f, "%d %d %d", &nsz, &nedg, &vtx);
        int amtrx[nsz][N];

        for(i = 0; i < nsz; i++){
                for(j = 0; j < nsz; j++){
                        amtrx[i][j] = INF;
                }
        }
        for(i = 0; i < nedg; i++){
            fscanf(f, "%d %d %d", &fr, &to, &wt);
            amtrx[fr][to] = wt;
            amtrx[to][fr] = wt;
        }
        *n = nsz;
        *stv = vtx;

        int total_cost = prims(amtrx, n);
        printpaths(n);
        printf("\n\nTotal cost of spanning tree: %d", total_cost);
    } else {
        printf("Failed to open the file\n");
    }
    fclose(f);
    return 0;
}

int prims(int amtrx[][N], int *n) {
    int cost[N][N];
    int u, v, min_distance, distance[N], from[N];
    int visited[N], no_of_edges, i, min_cost, j;

    for(i = 0; i < *n; i++)
        for(j = 0; j < *n; j++) {
            if(amtrx[i][j] == 0)
                cost[i][j] = INF;
            else {
                cost[i][j] = amtrx[i][j];
                spanning[i][j] = 0;
            }
        }

    distance[0] = 0;
    visited[0] = 1;

    for(i = 1; i < *n; i++) {
        distance[i] = cost[0][i];
        from[i] = 0;
        visited[i] = 0;
    }
    min_cost = 0;
    no_of_edges = *n - 1;

    while(no_of_edges > 0) {
        min_distance = INF;
        for(i = 1; i < *n ; i++)
            if(visited[i] == 0 && distance[i] < min_distance) {
                v = i;
                min_distance = distance[i];
            }

        u = from[v];

        spanning[u][v] = distance[v];
        spanning[v][u] = distance[v];
        no_of_edges--;
        visited[v] = 1;

        for(i = 1; i < *n; i++)
            if(visited[i] == 0 && cost[i][v] < distance[i]) {
                distance[i] = cost[i][v];
                from[i] = v;
            }
        min_cost = min_cost + cost[u][v];
    }
    return min_cost;
}

void printpaths(int *n) {
    int i, j;
    for(i = 0; i < *n; i++) {
        printf("\n");
        for(j = 0; j < *n; j++)
            printf("%d\t", spanning[i][j]);
    }
}

Вот что находится во входном файле: 

6 10 0 <-- size, edges, start
0 1 16 <-- from, to, weight
0 5 21
0 4 19
1 2 5
1 3 6
1 5 11
2 3 10
3 4 18
3 5 14
4 5 33

Ответы [ 2 ]

2 голосов
/ 07 апреля 2020

Как сказал @kaylum выше. Вы должны использовать отладчик, когда видите Segmentation Fault. Для меня, я всегда пытаюсь запустить программу с valgrind, когда я вижу эту ошибку. С помощью valgrind (сначала используйте -g, когда вы компилируете код), вы можете увидеть, где ошибка памяти.

Для вашей программы она вычисляет эту строку *n = nsz;. Посмотрите на переменные n и nsz.

Кстати, вам нужно выделить 2 вариабеля n и stv вместо назначения их 0. 0. 1014 * 

stv = malloc(sizeof(int));
n = malloc(sizeof(int));

Результат после выделения: 

0   16  0   0   0   0   
16  0   5   6   0   11  
0   5   0   0   0   0   
0   6   0   0   18  0   
0   0   0   18  0   0   
0   11  0   0   0   0   

Total cost of spanning tree: 56
1 голос
/ 07 апреля 2020

Я думаю, что у вас проблемы с пониманием указателя и параметров в функции C. Я предполагаю, что вы объявляете n как указатель на int, потому что вы используете int * в прототипе вашей функции.

Первое решение, объявите n и stv как int, используйте их как целые числа и передайте их адрес в вызове функции. 

...
int n, stv, i, j, nsz, nedg, fr, to, vtx, wt;
...
n = nsz;
stv = vtx;

int total_cost = prims(amtrx, &n);
printpaths(&n);

Но в функциях prims и printpaths вы не меняете значение n, поэтому вам не нужен указатель на n. 

...
int n, stv, i, j, nsz, nedg, fr, to, vtx, wt;
...
n = nsz;
stv = vtx;

int total_cost = prims(amtrx, n);
printpaths(n);

...
int prims(int amtrx[][N], int n) {
    int cost[N][N];
    int u, v, min_distance, distance[N], from[N];
    int visited[N], no_of_edges, i, min_cost, j;

    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++) {
            if(amtrx[i][j] == 0)
                cost[i][j] = INF;
            else {
                cost[i][j] = amtrx[i][j];
                spanning[i][j] = 0;
            }
        }

    distance[0] = 0;
    visited[0] = 1;

    for(i = 1; i < n; i++) {
        distance[i] = cost[0][i];
        from[i] = 0;
        visited[i] = 0;
    }
    min_cost = 0;
    no_of_edges = n - 1;

    while(no_of_edges > 0) {
        min_distance = INF;
        for(i = 1; i < n ; i++)
            if(visited[i] == 0 && distance[i] < min_distance) {
                v = i;
                min_distance = distance[i];
            }

        u = from[v];

        spanning[u][v] = distance[v];
        spanning[v][u] = distance[v];
        no_of_edges--;
        visited[v] = 1;

        for(i = 1; i < n; i++)
            if(visited[i] == 0 && cost[i][v] < distance[i]) {
                distance[i] = cost[i][v];
                from[i] = v;
            }
        min_cost = min_cost + cost[u][v];
    }
    return min_cost;
}

void printpaths(int n) {
    int i, j;
    for(i = 0; i < n; i++) {
        printf("\n");
        for(j = 0; j < n; j++)
            printf("%d\t", spanning[i][j]);
    }
}

To очень кратко объясните свою ошибку:

n - это указатель на int, и вы присваиваете ему 0 (n=0). Так что это указывает на «нулевой» адрес памяти. (Rq: слишком долго, чтобы объяснить, что означает «нулевой» адрес памяти, поэтому я использую «»). После, когда вы пишете *n=nsz, вы пытаетесь записать значение nsz по этому «нулевому» адресу памяти, который запрещен. Если вы хотите использовать указатель, вы должны выделить память для хранения значения, как предложил Хитокири.

...