Trieツリーを実行中にエラーが発生しました

Question

私は文字列を挿入し、トライデータ構造を使用して検索を行います。これはポインタを使用した私の最初の実装で、コードで間違っていると混乱します。それをデバッグするのに役立ちますし、私のポインタロジックで何が間違っているか教えてください。

typedef struct trie { 
    unordered_multimap<char, struct trie> child; 
    bool isEnd; 
} trie; 
trie* newtrienode() 
{ 
    trie* newnode = (trie*)malloc(sizeof(trie)); 
    newnode->isEnd = false; 
    return newnode; 
} 
trie* root = newtrienode(); 
void insert(string word) 
{ 
    trie* current = root; 
    for (int i = 0; i < word.length(); i++) { 
     char ch = word[i]; 
     trie* node = current->child[ch]; 
     if (node == NULL) { 
      trie* node = newtrienode(); 
      current->child.insert(pair<char, trie>(ch, node)); 
     } 
     current = node; 
    } 
    current->isEnd = true; 
} 
bool search(string word) 
{ 
    trie* current = root; 
    for (int i = 0; i < word.length(); i++) { 
     char ch = word[i]; 
     trie* node = current->child[ch]; 
     if (node == NULL) { 
      return false; 
     } 
     current = node; 
    } 
    return true; 
} 

Answer 1

コメントとは別に、コードにいくつかの問題があります。

trie* newnode = (trie*)malloc(sizeof(trie)); 

これはタイプtrieのオブジェクトを作成できません、それだけtrieのサイズのメモリのブロックを割り当て、変数newnodeにそれへのポインタを割り当てます。特に、unordered_multimapのコンストラクタは呼び出されません。そのポインタを介してchildメンバにアクセスすると、未定義の動作が発生します。それに、あなたは決してその記憶を解放しない。 2番目のテンプレートパラメータとして不完全型trieでunordered_multimapデータメンバを宣言された第2ラインで

typedef struct trie { 
    unordered_multimap<char, struct trie> child; 
    bool isEnd; 
} trie; 

。コンパイラの中にはそれが許されているものもありますが、標準ではそれらを必要としません。一方、shared_ptrは、テンプレートパラメータとして不完全な型で使用可能であることが要求されます。また、ノードは文字ごとに1つのサブツリーしか持てないので、マルチマップは必要ありません。マップで十分です。だから私はunordered_map<char, shared_ptr<trie>>を使用し、​​のすべての出現をshared_ptr<trie>に置き換えることを提案します。一度rootがリリースされると、オブジェクトの削除も処理されます。

newtrienode()関数は次のようになります。キーが存在しないとき

shared_ptr<trie> newtrienode() 
{ 
    shared_ptr<trie> newnode (new trie()); 
    newnode->isEnd = false; 
    return newnode; 
} 

3.

trie* node = current->child[ch]; 
if (node == NULL) { 

operator[]はNULLを返しません。デフォルトで構築されたオブジェクトをコンテナに挿入し、そのコンテナへの参照を返します。キーが存在するかどうかを確認するには、findまたはcountを使用します。

4.

trie* node = current->child[ch]; 
if (node == NULL) { 
    trie* node = newtrienode(); 
    current->child.insert(pair<char, trie>(ch, node)); 
} 
current = node; 

3行目には、新しい変数を宣言していることに注意してください。最初の行で宣言された変数nodeは変更されません。