代码之家 › 专栏 › 技术社区 › user3243499

DFS中的分段错误

c99 graph c

user3243499 · 技术社区 · 8 年前

我已经为DFS编写了一个简单的递归过程。

#include <stdbool.h>

void mydfs(int ROWS, int COLS,char **A,int row, int col, bool **visited){
    static int rowAdjacencyParams[4] = {-1,0,1,0};
    static int colAdjacencyParams[4] = {0,1,0,-1};

    *(*(visited+col)+row) = true;
    //visited[row][col] = true;
    int i,newR,newC;
    for(i = 0;i<4;i++){
        newR = row + rowAdjacencyParams[i];
        newC = col + colAdjacencyParams[i];

        if(((newR >=0) && (newR < ROWS)) && ((newC>=0) && (newC < COLS))){
            /*if((A[newR][newC] == 'X') && !visited[newR][newC]){
                mydfs(ROWS,COLS,A,newR,newC,visited);
            }*/
        }
    }
}

int black(char** A, int n1) {
    int i,j,count = 0; 
    int cols = strlen(A[0]);
    bool visited[n1][cols];

    memset(visited,0,sizeof(visited));


    for(i = 0;i<n1;i++){
        for(j = 0;j<cols;j++){
            if((A[i][j] == 'X') && !visited[i][j]){
                count++;
                mydfs(n1,cols,A,i,j,visited);
            }
        }
    }


    return count;
}
int main(){
    int ROWS = 3;
    int COLS = 7;

    char P[ROWS][COLS]= {"OOOXOOO","OOXXOXO","OXOOOXO"};

    printf("Number of islands = %d",black(P,COLS));
    return 0;
}

更新了主功能

然而,当我运行这个时,它给了我一个 segmentation fault 用于线路 visited[row][col] = true; .然后我试图将其更改为 *(*(visited+col)+row) = true; 但仍有相同的分割错误。请解释我为什么会出现此错误。

1 回复 | 直到 8 年前

PaulMcKenzie 8 年前

除了注释指出的超出数组缓冲区的字符数据之外,还有一个错误是:

int black(char** A, int n1) {
//...
for(i = 0;i<n1;i++){
    for(j = 0;j<cols;j++){
        if((A[i][j] == 'X') && !visited[i][j]){  /* A[i] is out of bounds */

这个 n1 作为列数传入,即7。但是,如果返回 main ,您有这个:

int ROWS = 3;
int COLS = 7;

char P[ROWS][COLS]= {"OOOXOOO","OOXXOXO","OXOOOXO"};
printf("Number of islands = %d",black(P,COLS));

这个 P 数组只有3行。所以当 black 调用函数时,假设P有7行,而不是3行。这将导致 A 数组访问 A[0] , A[1] , A[2] ,(很好),但之后 A[3] 等,这是未定义的行为(在您的情况下,是崩溃)。

因此,您需要纠正列/行逻辑。

我会告诉你一个秘密。由于您最初将问题标记为C++,我花了一些时间将这些双星改为 std::vector ,并使用 at() 函数查找问题。我知道您现在已经将您的问题标记为C99,但我只想知道为什么标记很重要。我不知道C99是否具有这种自动检测边界条件的功能。