Ошибка выполнения Trie Tree

Question

Я хочу вставить строку и выполнить поиск opeartion с помощью структуры данных trie. Это моя первая реализация с использованием указателей, поэтому я действительно смущен тем, что я делаю неправильно в коде, Это дает ошибку компиляции. пожалуйста, помогите отладить его и, пожалуйста, скажите мне, что не так в моей логике указателя.

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

Помимо упоминаний в комментариях, я вижу несколько проблем с кодом.

1.

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

Это не создает объект типа trie, он выделяет только блок памяти размером trie и присваивает указатель на него в переменной newnode. В частности, он не вызывает конструктор unordered_multimap. Любой доступ к члену child через этот указатель вызывает неопределенное поведение. Кроме того, вы никогда не освобождаете эту память.

2.

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

На второй строке вы объявляющий элемент в unordered_multimap данных с неполным типом trie в качестве второго параметра шаблона. Некоторые компиляторы допускают это, но стандарт их не требует. shared_ptr, с другой стороны, необходимо использовать с неполным типом в качестве параметра шаблона. Кроме того, узел может иметь только одно поддерево для каждого символа, поэтому вам не нужно многомарочное; карты будет достаточно. Поэтому я бы предложил использовать unordered_map<char, shared_ptr<trie>> и заменить все вхождения 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; 

Обратите внимание, что в третьей строке вы объявляете новую переменную. Переменная node, объявленная в первой строке, не изменяется.