Инициализация дерева три - PullRequest
Новая
       10

Инициализация дерева три

0 голосов
/ 12 октября 2018

Я использую C ++ для построения дерева слов с кучей слов в словаре.Вот как я определил свой TrieNode и построил дерево: 

struct TrieNode {
    TrieNode *children[26];
    bool isWord;
    TrieNode(): isWord(false) {}  /* to be deleted */
};

void buildTree(TrieNode *root, string word) {
    TrieNode *cur = root;
    for (char c : word) {
        if (!cur->children[c-'a'])
            cur->children[c-'a'] = new TrieNode();
        cur = cur->children[c-'a'];
    }
    cur->isWord = true;
}

Это отлично работает на некоторых компиляторах, но на других это дает некоторые странные результаты.Например, однажды я обнаружил, что isWord был инициализирован как 152, и вся программа потерпела крах.Я попытался удалить строку, отмеченную выше в коде, все снова получилось.Что здесь происходит?

Кроме того, в чем разница между "новым TrieNode ()" и "новым TrieNode"?Иногда я обнаруживал, что они тоже дают разные результаты.

1 Ответ

0 голосов
/ 12 октября 2018

Проблема с вашим кодом в том, что вы предполагаете, что члены инициализируются.К сожалению, это не так .Таким образом, указатели на children не обязательно инициализируются на nullptr, что заставляет ваш код разыменовывать недопустимые указатели, что вызывает неопределенное поведение (UB) (например, повреждение памяти, сбои и т. Д.).

Простое решение:

Добавьте инициализатор по умолчанию для вашего массива в классе: 

       TrieNode *children[26]{};

Демо

Мои советы:

  • используйте векторы вместо собственных массивов.Их конструктор по умолчанию гарантирует, что они пусты.
  • прочитайте эту статью о инициализации
  • сделайте некоторую проверку границ, потому что если в ваших данных будут потеряны некоторые заглавные буквы, вы выйдете за пределы диапазона, и снова UB,
...