尝试将单词插入trie时出现分段错误

Question

嗨:)有谁能告诉我为什么以下代码不起作用？程序if(children[word[letter_no] - 'A'] == nullptr)在对应的节点中的行崩溃'B'.但节点被创建,当我尝试调用children[1]构造函数,它的工作原理.但是当它在insert()函数中调用时,它不会......

包括

#include <memory> //shared_ptr
#include <string>    
using namespace std;    
const int ALPHABET = 26;

class Node {
public:
    shared_ptr<Node> children[ALPHABET];

    Node() { for (int i = 0; i < ALPHABET; ++i) children[i] = nullptr;}
    void insert(const string &word, unsigned letter_no) {
        if (letter_no < word.length()) {
            if (children[word[letter_no] - 'A'] == nullptr) 
                children[word[letter_no] - 'A'] = make_shared<Node>();
            children[word[letter_no] - 'A']->insert(word, letter_no+1);
        }
    }
};

int main() {
    Node trie{};
    trie.insert("ABC", 0);
    return 0;
}

Answer 1

启用编译器警告!

• 由于未指定的评估顺序,您有未定义的行为:

  children[word[letter_no] - 'A']->insert(word, ++letter_no);
  

  警告:letter_no无序修改和访问[-Wunsequenced]

• 您还有一个潜在的危险比较:

  letter_no < word.length
  

  警告:有符号和无符号整数表达式之间的比较

在wandbox上

此外,您不应该在现代C++代码中使用new和delete.使用std::unique_ptr或std::shared_ptr取决于您需要的所有权语义.

来自评论:

杰克:这都是事实,但没有一个是造成这个问题的原因.我简化了我的代码,因此在一个问题中它更具可读性.在我的原始代码中,我正在尝试使用shared_ptr,但结果是一样的.看,pastebin.com/MFZdrp22效果不好(仍然是分段错误)

仔细看看这些线:

if (letter_no < word.length()) 
{
    if (children[word[letter_no] - 'A'] == nullptr)
    {
        children[word[letter_no] - 'A'] = make_shared<Node>();
    }

    ++letter_no;                                              // (0)
    children[word[letter_no] - 'A']->insert(word, letter_no); // (1)
}

• word是"ABC".

• word[letter_no] - 'A'是0.

• 在(0),你增加letter_no.

• 在(1),word[letter_no] - 'A'是1.

• children[1]是nullptr.繁荣!

再次,编译器是你的朋友.编译,-fsanitize=undefined您将收到以下错误消息:

runtime error: member call on null pointer of type 'Node'
runtime error: member access within null pointer of type 'Node'

在wandbox上