0

我有一些代码应该递归地覆盖boggle板上的所有位置。但是由于某种原因，它在只找到 2 个单词后会引发分段错误？任何想法为什么会发生？

该代码可能会引发错误：

//++++++++++++ Find Word ++++++++++++++//
void findword(vector<vector<tile> > board, unsigned int row, unsigned int col, set<string> &results, unsigned int board_width, string word, set<string> dictionary)
{               
    if(checkbound(row, col, board_width) == false)          // If tile is outside of the boundary than do nothing
        return;
    if(board[row][col].getused() == true)               // If tile has already been used than do nothing
        return;
    word = word + board[row][col].getvalue();           // Adds letter to word

    //Check Prefixes
    set<string>::iterator pos;
    pos = dictionary.lower_bound(word);             // Creates an iterator at position
    if(pos== dictionary.end())                  // If it reaches the end without finding word than do nothing
    {
        return;

    }
    else if(word == pos->substr(0,word.length()))
    {
        cout<<"word: " <<word<<endl;
        cout<<"dict: " <<*pos<<endl;
        if(word == *pos)                    // If word = word at prefix
        {       
            cout<< word<<" word inserted"<<endl;    
            results.insert(word);               // Add words to results set
        }
    }
    else
        return;

    //set to used
    board[row][col].setused(true);                  // set tile to used




    findword(board, row-1, col-1, results, board_width, word, dictionary);  // Checks all tiles around every tile
    findword(board, row-1, col, results, board_width, word, dictionary);
    findword(board, row-1, col+1, results, board_width, word, dictionary);
    findword(board, row, col-1, results, board_width, word, dictionary);
    findword(board, row, col+1, results, board_width, word, dictionary);
    findword(board, row+1, col-1, results, board_width, word, dictionary);
    findword(board, row+1, col, results, board_width, word, dictionary);
    findword(board, row+1, col+1, results, board_width, word, dictionary);

    board[row][col].setused(false);                 // set tile to not-used
}

给出的错误：

word: r
dict: riot
word: ro
dict: robot
word: rob
dict: robot
word: robo
dict: robot
word: robot
dict: robot
robot word inserted
word: roo
dict: root
word: root
dict: root
root word inserted
Segmentation fault (core dumped)

Valgrind的主要错误代码：

==4629== Invalid read of size 1
==4629==    at 0x407C2E: tile::getused() (tile.cpp:33)
==4629==    by 0x401ACE: findword(std::vector<std::vector<tile, std::allocator<tile> >, std::allocator<std::vector<tile, std::allocator<tile> > > >, unsigned int, unsigned int, std::set<std::string, std::less<std::string>, std::allocator<std::string> >&, unsigned int, std::string, std::set<std::string, std::less<std::string>, std::allocator<std::string> >) (main.cpp:58)
==4629==    by 0x4020EC: findword(std::vector<std::vector<tile, std::allocator<tile> >, std::allocator<std::vector<tile, std::allocator<tile> > > >, unsigned int, unsigned int, std::set<std::string, std::less<std::string>, std::allocator<std::string> >&, unsigned int, std::string, std::set<std::string, std::less<std::string>, std::allocator<std::string> >) (main.cpp:93)
==4629==    by 0x4020EC: findword(std::vector<std::vector<tile, std::allocator<tile> >, std::allocator<std::vector<tile, std::allocator<tile> > > >, unsigned int, unsigned int, std::set<std::string, std::less<std::string>, std::allocator<std::string> >&, unsigned int, std::string, std::set<std::string, std::less<std::string>, std::allocator<std::string> >) (main.cpp:93)
==4629==    by 0x401F78: findword(std::vector<std::vector<tile, std::allocator<tile> >, std::allocator<std::vector<tile, std::allocator<tile> > > >, unsigned int, unsigned int, std::set<std::string, std::less<std::string>, std::allocator<std::string> >&, unsigned int, std::string, std::set<std::string, std::less<std::string>, std::allocator<std::string> >) (main.cpp:91)
==4629==    by 0x402264: findword(std::vector<std::vector<tile, std::allocator<tile> >, std::allocator<std::vector<tile, std::allocator<tile> > > >, unsigned int, unsigned int, std::set<std::string, std::less<std::string>, std::allocator<std::string> >&, unsigned int, std::string, std::set<std::string, std::less<std::string>, std::allocator<std::string> >) (main.cpp:95)
==4629==    by 0x402BF0: main (main.cpp:185)
==4629==  Address 0x4c3b178 is 8 bytes after a block of size 48 alloc'd

Checkbound 函数：

//+++++++++++ Check Bounds ++++++++++++//
bool checkbound(unsigned int row, unsigned int col, unsigned int board_width)
{
    if(row < 0 || row > board_width || col < 0 || col > board_width)
        return false;
    else
        return true;
}

木板：

r b o
o i t
r o h
4

2 回答 2

2

board_width 的值是多少？如果这是 3，那么您忘记了从 0 开始的索引并且最大可用索引是 2，因此 checkbound 函数中的条件必须是：

    if(row < 0 || row >= board_width || col < 0 || col >= board_width)
于 2013-07-10T06:04:25.397 回答
1

我的猜测是您的问题出在您的检查绑定函数中。您执行以下操作：

row > board_width

我不确定你是如何计算宽度的，但我相信你的问题就在这里。大小为 3 的向量将是索引：myVec[0]、myVec[1]、myVec[2]。

如果在此示例中，您说 board_width 为 3，这将导致您的段错误。

于 2013-07-10T06:13:53.087 回答