为什么在这个Boggle搜索程序中出现分段错误？

huangapple
go评论77阅读模式
英文:

Why do I get a segmentation fault in this Boggle Search program?

问题

我在搜索`main`函数中的`searchBoggle`时遇到了分段错误。我认为这可能与字符串路径有关。我应该在每次迭代时为其创建一个新的空字符串或空路径来实现我想要的效果，但我无法做到。当我递归到棋盘时，路径应该是一个字符串，我会添加更多的字符，当我从一个新的点开始时，路径应该再次为空字符串。
英文:

I am having a segmentation fault on the searchboggle for what I look up it something to do with the string path I think in the main function. I should make a new empty string or empty path for each iteration to do what I want but I cant do it. It should path should be a string when I am recursing to the board I add more chars and when I start on a new point should be a empty string again.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "hash.h"

#define MAX_WORD_LENGTH 30

int wordcount = 0;
int row[] = { -1, -1, -1, 0, 1, 0, 1, 1 };
int col[] = { -1, 1, 0, -1, -1, 1, 0, 1 };

HashTable readwords(HashTable H, char *filename) {
    char word[50] = "";
    FILE *f = fopen(filename, "r");
    while (fscanf(f, " %s", word) != EOF)
        Insert(word, H);
    fclose(f);
    return H;
}

void readboard(char *filename, char board[][4]) {
    FILE *file;
    char line[12];
    // Open the file
    file = fopen(filename, "r");
    if (file == NULL) {
        printf("Error opening the file.\n");
        return;
    }
    int x = 0;
    // Read the file and populate the board dynamically
    while (fgets(line, sizeof(line), file) != NULL && x < 4) {
        board[x][0] = line[0];
        board[x][1] = line[2];
        board[x][2] = line[4];
        board[x][3] = line[6];
        x++;
    }
    // Close the file
    fclose(file);
}

bool isSafe(int x, int y, bool processed[][4]) {
    return (x >= 0 && x < 4) && (y >= 0 && y < 4) && !processed[x][y];
}

void searchBoggle(char board[][4], HashTable words, char answer[200][30],
                  bool processed[][4], int x, int y, char *path,
                  int wordX[30], int wordY[30]) {

    // marca o nó atual como processado
    processed[x][y] = true;
 
    // atualiza o caminho com o caractere atual e o insere no conjunto
    strncat(path, &board[x][y], 1);
 
    // verifica se o caminho está presente no conjunto de entrada
    if (Find(path, words)) {
        wordcount++;
        int sz = strlen(path);
        for (int j = 0; j < sz; j++) {
            answer[wordcount][j] = path[j];
        }
    }
    
    // verifica todos os oito movimentos possíveis da célula atual
    for (int k = 0; k < 8; k++) {
        // pula se uma célula é inválida ou já foi processada
        if (isSafe(x + row[k], y + col[k], processed)) {
            searchBoggle(board, words, answer, processed,
                         x + row[k], y + col[k], path, wordX, wordY);
        }
    }
    
    // backtrack: marca o nó atual como não processado
    processed[x][y] = false;
}

int main() {
    char path[30] = "";
    char filename[] = "corncob_caps_2023.txt";
    char filename2[] = "boggle0.txt"; 
    int tableSize = 60000; 
    char answer[200][30];
    bool processed[4][4];
    int wordX[30];
    int wordY[30];
    char board[4][4];
    HashTable words = InitializeTable(tableSize);
    words = readwords(words, filename);
    
    readboard(filename2, board);
    for (int x = 0; x < 4; x++) {
        for (int y = 0; y < 4; y++) {
            // considera cada caractere como um ponto de partida e executa o DFS
            searchBoggle(board, words, answer, processed, x, y, path, wordX, wordY);
        }
    }
    return 0;
}

If needed anything more just let me know so I could add it.

Seeing the all the answers i change the code and know it look like this, i run it on debug and it acctualy run just fin just take some time but then when i run it normaly it just gives me segmentation fault again.


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "hash.h"

#define MAX_WORD_LENGTH 30
int wordcount=0;
int row[] = { -1, -1, -1, 0, 1, 0, 1, 1 };
int col[] = { -1, 1, 0, -1, -1, 1, 0, 1 };

HashTable readwords(HashTable H,char *filename){
    char word[50]="";
    FILE* f = fopen(filename, "r");
    while(fscanf(f, " %s", word) != EOF)
        Insert(word, H);
    fclose(f);
    return H;
}

HashTable readCharsWords(HashTable H,char *filename){
    char word[50]="";
    int sz;
    FILE* f = fopen(filename, "r");
    while(fscanf(f, " %s", word) != EOF){
        char d[30];
        sz = strlen(word);
        memset(d, 0, sizeof(d));
        for (int j = 0; j < sz-1; j++) {
            d[j]=word[j];
            d[j+1]='

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "hash.h"
#define MAX_WORD_LENGTH 30
int wordcount=0;
int row[] = { -1, -1, -1, 0, 1, 0, 1, 1 };
int col[] = { -1, 1, 0, -1, -1, 1, 0, 1 };
HashTable readwords(HashTable H,char *filename){
char word[50]="";
FILE* f = fopen(filename, "r");
while(fscanf(f, " %s", word) != EOF)
Insert(word, H);
fclose(f);
return H;
}
HashTable readCharsWords(HashTable H,char *filename){
char word[50]="";
int sz;
FILE* f = fopen(filename, "r");
while(fscanf(f, " %s", word) != EOF){
char d[30];
sz = strlen(word);
memset(d, 0, sizeof(d));
for (int j = 0; j < sz-1; j++) {
d[j]=word[j];
d[j+1]='\0';
if(!Find(d,H)){
Insert(d,H);
}    
}
}
fclose(f);
return H;
}
void readboard(char *filename,char board[][4]) {
FILE *file;
char line[12];
// Open the file
file = fopen(filename, "r");
if (file == NULL) {
printf("Error opening the file.\n");
return;
}
int x=0;
// Read the file and populate the board dynamically
while (fgets(line, sizeof(line), file) != NULL&&x<4) {
board[x][0] = line[0];
board[x][1] = line[2];
board[x][2] = line[4];
board[x][3] = line[6];
x++;
}
// Close the file
fclose(file);
}
bool isSafe(int x, int y, bool processed[][4]) {
return (x >= 0 && x < 4) && (y >= 0 && y < 4) &&
!processed[x][y];
}
void searchBoggle(char board[][4], HashTable halfwords, HashTable words, char answer[200][30], bool processed[][4], int x, int y, char *path, int wordX[30], int wordY[30],int len){
// marca o nó atual como processado
processed[x][y] = true;
// atualiza o caminho com o caractere atual e o insere no conjunto
path[len] = board[x][y]; path[len + 1] = '\0';
// verifica se o caminho está presente no conjunto de entrada
if (Find(path, words) && wordcount < 200) {
strcpy(answer[wordcount++], path);
}
if(!Find(path, halfwords)){
return;
}
// verifica todos os oito movimentos possíveis da célula atual
for (int k = 0; k < 8; k++)
{
// pula se uma célula é inválida ou já foi processada
if (isSafe(x + row[k], y + col[k], processed)) {
searchBoggle(board, halfwords, words, answer, processed, x + row[k], y + col[k], path,wordX,wordY,len + 1);
}
}
// backtrack: marca o nó atual como não processado
processed[x][y] = false;
}
int main(){
char path[30]="";
char filename[] = "corncob_caps_2023.txt";
char filename2[] = "boggle0.txt"; 
int tableSize = 60000; 
HashTable H = InitializeTable(200000);
H=readCharsWords(H,filename);
char answer[200][30];
bool processed[4][4];
int wordX[30];
int wordY[30];
char board[4][4];
HashTable words = InitializeTable(tableSize);
words = readwords(words, filename);
readboard(filename2, board);
for (int x = 0; x < 4; x++){
for (int y = 0; y < 4; y++) {
// considera cada caractere como um ponto de partida e executa o DFS
searchBoggle(board,H,words,answer,processed, x,y, path,wordX,wordY,0);
}
}
return 0;
}

';
            if(!Find(d,H)){
                Insert(d,H);
            }    
        }
        
    }
    fclose(f);
    return H;
}

void readboard(char *filename,char board[][4]) {
    FILE *file;
    char line[12];
    // Open the file
    file = fopen(filename, "r");
    if (file == NULL) {
        printf("Error opening the file.\n");
        return;
    }
    int x=0;
    // Read the file and populate the board dynamically
    while (fgets(line, sizeof(line), file) != NULL&&x<4) {
        board[x][0] = line[0];
        board[x][1] = line[2];
        board[x][2] = line[4];
        board[x][3] = line[6];
        x++;

    }
    // Close the file
    fclose(file);

    
}
bool isSafe(int x, int y, bool processed[][4]) {
    return (x >= 0 && x < 4) && (y >= 0 && y < 4) &&
        !processed[x][y];
}

void searchBoggle(char board[][4], HashTable halfwords, HashTable words, char answer[200][30], bool processed[][4], int x, int y, char *path, int wordX[30], int wordY[30],int len){
    // marca o nó atual como processado
    processed[x][y] = true;
 
    // atualiza o caminho com o caractere atual e o insere no conjunto
    path[len] = board[x][y]; path[len + 1] = '

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "hash.h"
#define MAX_WORD_LENGTH 30
int wordcount=0;
int row[] = { -1, -1, -1, 0, 1, 0, 1, 1 };
int col[] = { -1, 1, 0, -1, -1, 1, 0, 1 };
HashTable readwords(HashTable H,char *filename){
char word[50]="";
FILE* f = fopen(filename, "r");
while(fscanf(f, " %s", word) != EOF)
Insert(word, H);
fclose(f);
return H;
}
HashTable readCharsWords(HashTable H,char *filename){
char word[50]="";
int sz;
FILE* f = fopen(filename, "r");
while(fscanf(f, " %s", word) != EOF){
char d[30];
sz = strlen(word);
memset(d, 0, sizeof(d));
for (int j = 0; j < sz-1; j++) {
d[j]=word[j];
d[j+1]='\0';
if(!Find(d,H)){
Insert(d,H);
}    
}
}
fclose(f);
return H;
}
void readboard(char *filename,char board[][4]) {
FILE *file;
char line[12];
// Open the file
file = fopen(filename, "r");
if (file == NULL) {
printf("Error opening the file.\n");
return;
}
int x=0;
// Read the file and populate the board dynamically
while (fgets(line, sizeof(line), file) != NULL&&x<4) {
board[x][0] = line[0];
board[x][1] = line[2];
board[x][2] = line[4];
board[x][3] = line[6];
x++;
}
// Close the file
fclose(file);
}
bool isSafe(int x, int y, bool processed[][4]) {
return (x >= 0 && x < 4) && (y >= 0 && y < 4) &&
!processed[x][y];
}
void searchBoggle(char board[][4], HashTable halfwords, HashTable words, char answer[200][30], bool processed[][4], int x, int y, char *path, int wordX[30], int wordY[30],int len){
// marca o nó atual como processado
processed[x][y] = true;
// atualiza o caminho com o caractere atual e o insere no conjunto
path[len] = board[x][y]; path[len + 1] = '\0';
// verifica se o caminho está presente no conjunto de entrada
if (Find(path, words) && wordcount < 200) {
strcpy(answer[wordcount++], path);
}
if(!Find(path, halfwords)){
return;
}
// verifica todos os oito movimentos possíveis da célula atual
for (int k = 0; k < 8; k++)
{
// pula se uma célula é inválida ou já foi processada
if (isSafe(x + row[k], y + col[k], processed)) {
searchBoggle(board, halfwords, words, answer, processed, x + row[k], y + col[k], path,wordX,wordY,len + 1);
}
}
// backtrack: marca o nó atual como não processado
processed[x][y] = false;
}
int main(){
char path[30]="";
char filename[] = "corncob_caps_2023.txt";
char filename2[] = "boggle0.txt"; 
int tableSize = 60000; 
HashTable H = InitializeTable(200000);
H=readCharsWords(H,filename);
char answer[200][30];
bool processed[4][4];
int wordX[30];
int wordY[30];
char board[4][4];
HashTable words = InitializeTable(tableSize);
words = readwords(words, filename);
readboard(filename2, board);
for (int x = 0; x < 4; x++){
for (int y = 0; y < 4; y++) {
// considera cada caractere como um ponto de partida e executa o DFS
searchBoggle(board,H,words,answer,processed, x,y, path,wordX,wordY,0);
}
}
return 0;
}

';
 
    // verifica se o caminho está presente no conjunto de entrada
    if (Find(path, words) && wordcount < 200) {
        strcpy(answer[wordcount++], path);
    }
    
    if(!Find(path, halfwords)){
        return;
    }
    
    // verifica todos os oito movimentos possíveis da célula atual
    for (int k = 0; k < 8; k++)
    {
        // pula se uma célula é inválida ou já foi processada
        if (isSafe(x + row[k], y + col[k], processed)) {
            searchBoggle(board, halfwords, words, answer, processed, x + row[k], y + col[k], path,wordX,wordY,len + 1);
        }
    }
    
    // backtrack: marca o nó atual como não processado
    processed[x][y] = false;
}

int main(){
    char path[30]="";
    char filename[] = "corncob_caps_2023.txt";
    char filename2[] = "boggle0.txt"; 
    int tableSize = 60000; 
    HashTable H = InitializeTable(200000);
    H=readCharsWords(H,filename);
    char answer[200][30];
    bool processed[4][4];
    int wordX[30];
    int wordY[30];
    char board[4][4];
    HashTable words = InitializeTable(tableSize);
    words = readwords(words, filename);
    
    readboard(filename2, board);
    for (int x = 0; x < 4; x++){
        for (int y = 0; y < 4; y++) {
            // considera cada caractere como um ponto de partida e executa o DFS
            searchBoggle(board,H,words,answer,processed, x,y, path,wordX,wordY,0);
            
        }
    }
    
    return 0;
}

答案1

得分: 2

以下是已经翻译好的部分：

在代码中有一些可能导致未定义行为的问题：

  • 在 readwords 函数中，您没有检查 fopen() 的失败情况，可能导致在调用 fscanf() 时出现空指针而导致崩溃。

  • 如果字典中的任何单词超过 49 个字符，fscanf(f, " %s", word) 可能会导致缓冲区溢出。

  • 此外，您应该将 fscanf() 的返回值与 1 进行比较，而不仅仅是测试 EOF。

以下是修改后的版本：

#include <errno.h>

HashTable readwords(HashTable H, char *filename) {
    char word[50] = "";
    FILE *f = fopen(filename, "r");
    if (f == NULL) {
        fprintf(stderr, "无法打开 %s: %s\n", filename, strerror(errno));
        exit(1);
    }
    while (fscanf(f, "%49s", word) == 1) {
        Insert(word, H);
    }
    fclose(f);
    return H;
}

  • 您总是使用 strncat(path, &board[x][y], 1); 将下一个字符附加到 path，但从不进行回溯，导致 path 最终溢出并导致未定义行为（这是最有可能的解释）。

    您应该将 path 中的字符数作为参数 len 传递，并使用 path[len] = board[x][y]; path[len + 1] = '\0'; 手动附加下一个字符，并将 len + 1 传递给递归调用。

  • 当复制从字典中找到的单词时，您忘记在目标数组中设置空终止符。您应该只写：

    // 检查路径是否在输入集中
    if (Find(path, words) && wordcount < 200) {
        strcpy(answer[wordcount++], path);
    }
英文:

Here are some problems in the code that may produce undefined behavior:

  • in readwords, you do not check for fopen() failure, potentially causing a crash when you call fscanf() with null pointer.

  • fscanf(f, " %s", word) may cause a buffer overflow if any word from the dictionary is longer than 49 letters.

  • furhtermore, you should compare the return value of fscanf() to 1, instead of only testing EOF.

Here is a modified version:

#include <errno.h>

HashTable readwords(HashTable H, char *filename) {
    char word[50] = "";
    FILE *f = fopen(filename, "r");
    if (f == NULL) {
        fprintf(stderr, "cannot open %s: %s\n", filename, strerror(errno));
        exit(1);
    }
    while (fscanf(f, "%49s", word) == 1) {
        Insert(word, H);
    }
    fclose(f);
    return H;
}

  • you always append the next character to path with strncat(path, &board[x][y], 1); but never backtrack on this, causing path to eventually overflow and cause undefined behavior (this is the most likely explanation).

    You should pass the number of characters in path as an argument len and append the next one manually with path[len] = board[x][y]; path[len + 1] = '\0'; and pass len + 1 to the recursive calls.

  • when you copy a word found in the dictionary, you forget to set the null terminator in the destination array. You should just write:

    // verifica se o caminho está presente no conjunto de entrada
    if (Find(path, words) && wordcount < 200) {
        strcpy(answer[wordcount++], path);
    }

huangapple
  • 本文由 发表于 2023年6月22日 04:18:35
  • 转载请务必保留本文链接：https://go.coder-hub.com/76526850.html
  • c
  • debugging
  • segmentation-fault
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定