Добавление слов в три - PullRequest
Новая
       55

Добавление слов в три

0 голосов
/ 08 ноября 2019

Я создаю trie и у меня возникают проблемы во время компиляции.

Предупреждение, которое я получаю: «Чтение недопустимых данных из« currNode-> dict »: читаемый размер составляет 104 байта,но можно прочитать 388 байт. "

#pragma once
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

const int SIZE = 26;

struct Node {
bool isWord;
Node* dict[SIZE];
};

class Dictionary
{
public:
Dictionary();
Dictionary(string file);
void addWord(string word);

private:
Node *root;
int numWords;
};

Dictionary::Dictionary()
{
numWords = 0;
root = new Node;

for (int i = 0; i < SIZE; i++)
    root->dict[i] = nullptr;
}

Dictionary::Dictionary(string file)
{
numWords = 0;
root = new Node;

for (int i = 0; i < SIZE; i++)
    root->dict[i] = nullptr;

ifstream inFile;
string word;

inFile.open(file);

while (inFile >> word) {
    addWord(word);
    numWords++;
}
}

void Dictionary::addWord(string word)
{
int len = word.length(); // size of word
char letter;
int pos;

Node *currNode = root;

for (int i = 0; i < len; i++) {
    letter = word[i]; // takes character at position i
    pos = letter - 'a'; // finds the position of the character in the array (0 through 25)
                        // with 'a' being 0 and 'z' being 25

    if (!currNode->dict[pos]) {
        currNode->dict[pos] = new Node;

        currNode->isWord = false;
    }
    currNode = currNode->dict[pos];
}
currNode->isWord = true;
}

Что может быть причиной этого? Я почти уверен, что не пытаюсь получить доступ к неверной памяти. Возможно, так я настраиваю свой узел и класс?

1 Ответ

0 голосов
/ 08 ноября 2019

Одна ошибка в том, что вам не удалось инициализировать Node значениями по умолчанию. В вашем конструкторе Dictionary по умолчанию у вас есть код, который действительно должен быть частью того, что Node должен делать: 

root = new Node ;
for (int i = 0; i < SIZE; i++)
    root->dict[i] = nullptr;

Это должна быть работа Node, а не работа Dictionary.

Вместо этого у вас есть: 

struct Node {
    bool isWord;
    Node* dict[SIZE];
};

Поэтому каждый раз, когда вы делаете это: 

if (!currNode->dict[pos]) {
    currNode->dict[pos] = new Node;

Вы создаете неинициализированный Node объект. Весь этот массив Node::dict содержит неинициализированные указатели, к которым вы позже попытаетесь обратиться.

Самое простое решение - инициализация объекта Node нулем. 

if (!currNode->dict[pos]) {
    currNode->dict[pos] = new Node(); // <-- Note the parentheses

Это автоматически установитуказатели dict на nullptr.

Другой способ - убедиться, что Node объекты созданы со значениями по умолчанию: 

   #include <algorithm>

   struct Node {
        bool isWord;
        Node* dict[SIZE];
        Node() : isWord(false) { std::fill_n(dict, SIZE, nullptr); }
    };

При этом даже new Node; создаст инициализированные узлы.

...