尝试在文件上实施 Prim 算法时出现分段错误

Question

我只从我的代码中得到 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

Answer 1

正如@kaylum 上面所说。当您看到 Segmentation Fault 时，您应该使用调试器。对我来说，当我看到这个错误时，我总是尝试用 valgrind 运行程序。使用valgrind（首先编译代码时使用-g）你可以看到内存错误的位置。

对于您的程序，它计算出这一行 *n = nsz;。所以看看变量n和nsz。

顺便说一句，您必须分配 2 个变量 n 和 stv 而不是将它们分配给 0。

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

Answer 2

我认为您对 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]);
    }
}

非常简要地解释您的错误：

n 是指向 int 的指针，您将其分配给 0 (n=0)。所以它指向 "zero" 内存地址。（Rq：太长了，无法解释 "zero" 内存地址的含义，这就是我使用 "" 的原因）。之后，当你写 *n=nsz 时，你尝试在这个 "zero" 被禁止的内存地址写入 nsz 值。如果要使用指针，则必须按照 Hitokiri 的建议分配内存来存储值。

尝试在文件上实施 Prim 算法时出现分段错误

Segmentation fault trying to implement Prim's algorithm on file

c

prims-algorithm