我正在尝试自己实现Trie数据结构,而不考虑其他实现,所以简单地基于我对结构的概念性知识 . 我想避免使用向量,只是因为它们易于使用...我喜欢使用指针在我编程实践时为数组动态分配内存 . 也就是说,根据我目前的结构,我有一个Node类,它包含一个指向Node数组的指针,一个字母(bool)和一个标记(bool) . 我的Trie类有一个指向起始Node数组的指针 . 每个节点数组有26个元素来引用英文字母的每个字母,从“a”到“z”小写(我将每个单词转换为小写) . 当一个字母设置为'true'时,它的letterArray被分配新的内存 . Node有一个构造函数,用于将letter和marker设置为false,将letterArray设置为nullptr . 我可以插入第一个字母没问题,然后转到下一个letterArray(此时为nullptr),然后将内存分配给新数组 . 问题是,每个Node的下一个letterArray也分配了内存,但是没有对它们调用构造函数,导致它们的字母和标记包含垃圾,我想知道构造函数没有被调用的原因是什么?希望代码能够更清楚地说明这一点:

class Node {
private:
    bool letter;
    bool marker;
    Node* letterArray;

    void initNode();
public:
    Node();
    bool setLetter(bool set);
    bool setMarker(bool set);
    bool checkLetter();
    bool checkMarker();
    char getLetter();
    Node*& getNextLetterArray();
};

class Trie {
private:
    Node* start;
    int wordCount;
    int letterCount;

    const int totalLetters = 26;
    void destroyTrie();
    bool initBranch(Node*& nextBranch);
    void insertCharAndMove(Node*& ptr, int, int, int);

public:
    Trie();
    Trie(string firstWord);
    ~Trie();

    bool insertWord(string word);
    bool deleteWord(string word);
    bool getToLetter(char letter);
    string getLowerCase(string word);
    bool wordExists(string word);
};

insertWord:

bool Trie::insertWord(string word) {
    Node* ptr = start;
    string wordLower = getLowerCase(word);
    int wordLength = word.length();

    if (wordLength <= 0) return false;

    for (int i = 0; i < wordLength; i++) {
        int charIndex = (word[i] - 'a');
        insertCharAndMove(ptr, charIndex, wordLength, i);
    }
    wordCount++;
    return true;
}

void Trie::insertCharAndMove(Node*& ptr, int charIndex, int wordLength, int i) {
    if (ptr[charIndex].setLetter(true)) letterCount++;
    if (i < wordLength) {
        ptr = ptr[i].getNextLetterArray();
        initBranch(ptr);
    }
    else ptr[i].setMarker(true);
}

initBranch:

bool Trie::initBranch(Node*& nextBranch) {
    if (nextBranch != nullptr) return false;
    nextBranch = new Node[letterCount];
    return true;
}

Trie构造函数:

Trie::Trie() {
    start = new Node[totalLetters];

    wordCount = 0;
    letterCount = 0;
}

节点构造器:

Node::Node() {
    initNode();
}

void Node::initNode() {
    letter = false;
    marker = false;
    letterArray = nullptr;
}

getNextLetterArray:

Node*& Node::getNextLetterArray() {
    return letterArray;
}