嗨:)有誰能告訴我爲什麼下面的代碼不起作用嗎？該程序在對應於'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中時出現分段錯誤

包括

回答

相關問題