嗨:)有谁能告诉我为什么下面的代码不起作用吗？该程序在对应于'B'的节点中的if(children[word[letter_no] - 'A'] == nullptr)行处崩溃。但节点是创建的，当我尝试在构造函数中调用children[1]时，它起作用。但是，当它被称为在insert()功能，它不...试图插入一个单词到trie中时出现分段错误

包括

#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; 
}

来源

2017-02-10 Jecke

请注意，字母不授权是在一个连续范围相同的数字。如果例如系统使用了EBCDIC（可以），那么这将不起作用。 – NathanOliver

偏离主题，但空行和括号是免费的！ – peval27

启用编译器警告！

你有未定义行为由于评价的未指定的顺序：
```
children[word[letter_no] - 'A']->insert(word, ++letter_no); 
```
警告：未测序的修改和访问letter_no [-Wunsequenced]
你在这里也有潜在危险的比较：
```
letter_no < word.length 
```
警告：符号和无符号整数之间的比较表达式

on wandbox

而且，你不应该在现代C++代码中使用new和delete。根据您需要的所有权语义，使用std::unique_ptr或std::shared_ptr。

从评论：

Jecke：这就是真实的，但它没有一个是什么导致了问题。我简化了我的代码，使其在一个问题中更具可读性。在我最初的代码中，我试图使用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'

on wandbox

来源

2017-02-10 13:41:38

如果OP消除代码重复问题将消失 – Slava

这都是事实，但没有一个是造成问题的原因。我简化了我的代码，使其在一个问题中更具可读性。在我最初的代码中，我试图使用shared_ptr，但结果是一样的。看，http：// pastebin。com/MFZdrp22不能正常工作（仍然存在分段错误） – Jecke

@Jecke：仔细阅读第18和第19行。你正在访问'nullptr'！你可能想要的是'children [word [letter_no] - 'A'] - > insert（word，letter_no + 1）;' –

维托里奥已经回答了有关原因几句话大约风格：

，你只能有一个方法：

void insert(const string &word, size_t letter_no = 0);

那么你不需要重写，你可以使用std::unique_ptr，你不需要循环在你的ctor中， d，如果你消除重复代码：

if (letter_no < word.length()) { 
     auto &child = children[word[letter_no] - 'A']; 
     if (!child) 
      child = std::make_unique<Node>(); 
     child->insert(word, ++letter_no); 
    }

，它不仅使你的代码更易读，但让竟被你的问题消失

来源

2017-02-10 13:50:26 Slava

Vittorio Romeo's answer是正确的。你应该总是清理你的警告。

但在给你一个完整的解释的意图：

考虑当你1 ^ST递归，letter_no是0。 word包含'A'，'B','C'和'\0'。所以letter_no索引'A'。

验证该letter_no是一个有效的索引word后：letter_no < word.length()你增量letter_no：children[word[letter_no] - 'A']->insert(word, ++letter_no);

letter_no递增因为该线路上1 ^ST操作，因此它实际上具有价值1，索引'B'。然后通过'A'减去1的索引，这是一个未分配的元素。

至于解决办法，你不关心维护letter_no的价值，所以才这样做：children[word[letter_no] - 'A']->insert(word, letter_no + 1);

来源

2017-02-10 14:03:30

试图插入一个单词到trie中时出现分段错误

包括

回答

相关问题