DFS 中的分段错误

Question

我已经为 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;
}

已更新主函数

但是，当我运行这样做时，它为第 visited[row][col] = true; 行提供了 segmentation fault。然后我尝试将其更改为 *(*(visited+col)+row) = true; 但仍然有相同的分段错误。请解释为什么我会收到此错误。

Answer 1

除了评论指出的超出数组缓冲区的字符数据之外，还有一个错误是：

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有没有这种自动检测边界条件的功能

DFS 中的分段错误

Segmentation error in DFS

c

graph

c99