簡單路徑查找中的分段錯誤代碼

Question

我一直在嘗試調試此代碼，但現在真的需要幫助。它是將高度讚賞

#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', '\0'}; // String to be searched 
    find(0, 0, s); 
    printf("%s\n", found ? "Found": "Not Found");  
    return 0; 
} 

Answer 1

你的實現的問題是你沒有正確寫入遞歸。對於連續路徑搜索，如果字符不匹配，則不應該查看鄰居。

另外你犯的錯誤是期望search在字符串結束時變爲NULL。事實上，你需要檢查是否search[0] =='\0'。

既然你不看鄰居（通過刪除其他），你需要看看所有的起點。

請考慮以下代碼。

#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]=='\0') { 
     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', '\0'}; // 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

Answer 2

您的問題是堆棧溢出在網格中查找字符串，但由於某些原因，我越來越細分fault.Any指針的代碼。

如果您在調試器下運行程序，你會看到這樣的事情：

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+倍。