将单词添加到特里

Question

我正在创建特里，在编译时遇到麻烦。

我得到的警告是：“从'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;
}

可能是什么原因造成的？我很确定我没有尝试访问无效的内存。也许这就是我设置节点和类的方式吗？

Answer 1

一个错误是您无法将Node初始化为默认值：

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。