简单路径查找代码中的分段错误

Question

我一直在尝试调试这段代码，但现在真的需要帮助。这是在网格中查找字符串的代码，但由于某种原因，我正在分段 fault.Any 非常感谢您的指点

#include <stdio.h>

char grid[5][5] = {
    {'t', 'z', 'x', 'c', 'd'},
    {'a', 'h', 'n', 'z', 'x'},
    {'h', 'w', 'o', 'i', 'o'},
    {'o', 'r', 'n', 'r', 'n'},
    {'a', 'b', 'r', 'i', 'n'},
};
int n = 5;
int found = 0; // flag indicating if string has been found


void find(int i, int j, char *search) {
    if (i >= n || j >= n || i < 0 || j < 0) {
        return ;
    }

    if (!search) {
        found = 1;
        return ;
    }

    if (grid[i][j] == search[0]) {

        find (i+1, j, search+1); 
        find (i, j+1, search+1);
        find (i+1, j+1, search+1);
        find (i-1, j, search+1);
        find (i, j-1, search+1);
        find (i-1, j-1, search+1);
    }
    else {
        find (i+1, j, search); 
        find (i, j+1, search);
        find (i+1, j+1, search);
        find (i-1, j, search);
        find (i, j-1, search);
        find (i-1, j-1, search);
    }
}


int main() {
    char s[] = {'h', 'o', 'r', 'i', 'z', 'o', 'n', '[=10=]'}; // String to be searched
    find(0, 0, s);
    printf("%s\n", found ? "Found": "Not Found");    
    return 0;
}

Answer 1

你的问题是堆栈溢出。

如果你运行你的程序在调试器下，你会看到这样的东西：

Program received signal SIGSEGV, Segmentation fault.
0x00000000004006d5 in find (i=3, j=4, search=0x7fffffffdd44 "zon") at t.c:34
34          find (i+1, j, search);
(gdb) bt 10
#0  0x00000000004006d5 in find (i=3, j=4, search=0x7fffffffdd44 "zon") at t.c:34
#1  0x0000000000400720 in find (i=4, j=4, search=0x7fffffffdd44 "zon") at t.c:37
#2  0x00000000004006da in find (i=3, j=4, search=0x7fffffffdd44 "zon") at t.c:34
#3  0x0000000000400720 in find (i=4, j=4, search=0x7fffffffdd44 "zon") at t.c:37
#4  0x00000000004006da in find (i=3, j=4, search=0x7fffffffdd44 "zon") at t.c:34
#5  0x0000000000400720 in find (i=4, j=4, search=0x7fffffffdd44 "zon") at t.c:37
#6  0x00000000004006da in find (i=3, j=4, search=0x7fffffffdd44 "zon") at t.c:34
#7  0x0000000000400720 in find (i=4, j=4, search=0x7fffffffdd44 "zon") at t.c:37
#8  0x00000000004006da in find (i=3, j=4, search=0x7fffffffdd44 "zon") at t.c:34
#9  0x0000000000400720 in find (i=4, j=4, search=0x7fffffffdd44 "zon") at t.c:37
#10 0x00000000004006da in find (i=3, j=4, search=0x7fffffffdd44 "zon") at t.c:34
(More stack frames follow...)

请注意，索引是重复的，您没有取得进展。还有这个：

(gdb) bt -10
#261985 0x0000000000400720 in find (i=4, j=4, search=0x7fffffffdd44 "zon") at t.c:37
#261986 0x0000000000400651 in find (i=4, j=3, search=0x7fffffffdd43 "izon") at t.c:27
#261987 0x0000000000400651 in find (i=4, j=2, search=0x7fffffffdd42 "rizon") at t.c:27
#261988 0x00000000004006f0 in find (i=4, j=1, search=0x7fffffffdd42 "rizon") at t.c:35
#261989 0x00000000004006f0 in find (i=4, j=0, search=0x7fffffffdd42 "rizon") at t.c:35
#261990 0x0000000000400637 in find (i=3, j=0, search=0x7fffffffdd41 "orizon") at t.c:26
#261991 0x0000000000400637 in find (i=2, j=0, search=0x7fffffffdd40 "horizon") at t.c:26
#261992 0x00000000004006da in find (i=1, j=0, search=0x7fffffffdd40 "horizon") at t.c:34
#261993 0x00000000004006da in find (i=0, j=0, search=0x7fffffffdd40 "horizon") at t.c:34
#261994 0x000000000040079f in main () at t.c:46

告诉您在程序因堆栈耗尽而崩溃之前，它成功地（递归地）调用了 find 260,000 多次。

Answer 2

你的实现的问题是你没有正确编写递归。对于连续路径搜索，如果字符不匹配，你不应该看邻居。

您犯的第二个错误是期望 search 在字符串结束时变为 NULL。事实上你需要检查是否 search[0] =='[=12=]'.

由于您不查看邻居（通过删除 else），因此您需要查看所有起点。

考虑以下代码。

#include <stdio.h>

char grid[5][5] = {
    {'t', 'z', 'x', 'c', 'd'},
    {'a', 'h', 'n', 'z', 'x'},
    {'h', 'w', 'o', 'i', 'o'},
    {'o', 'r', 'n', 'r', 'n'},
    {'a', 'b', 'r', 'i', 'n'},
};
int n = 5;
int found = 0; // flag indicating if string has been found
void find(int i, int j, char *search) {
     if (i >= n || j >= n || i < 0 || j < 0) {
         return ;
     }

     if (search[0]=='[=10=]') {
         found = 1;
         return ;
     }

     if (grid[i][j] == search[0]) {
         find (i+1, j, search+1); 
         find (i, j+1, search+1);
         find (i+1, j+1, search+1);
         find (i-1, j, search+1);
         find (i, j-1, search+1);
         find (i-1, j-1, search+1);
     }
}


int main() {
     char s[] = {'h', 'o', 'r', 'i', 'z', 'o', 'n', '[=10=]'}; // String to be searched
     int i, j;
     for(i = 0; i<n && !found;i++)
         for(j = 0; j<n && !found;j++){
             find(i, j, s);
         }
     printf("%s\n", found ? "Found": "Not Found");    
     return 0;
}

这可以正常工作并打印 Found。

此处演示：https://ideone.com/l3ohwr

简单路径查找代码中的分段错误

Segmentation fault in simple path finding Code

c

debugging

path

backtracking

segmentation-fault