英文:
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 forfopen()
failure, potentially causing a crash when you callfscanf()
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()
to1
, instead of only testingEOF
.
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
withstrncat(path, &board[x][y], 1);
but never backtrack on this, causingpath
to eventually overflow and cause undefined behavior (this is the most likely explanation).You should pass the number of characters in
path
as an argumentlen
and append the next one manually withpath[len] = board[x][y]; path[len + 1] = '\0';
and passlen + 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);
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论