使用 class C++ 的 Trie 数据结构

Question

我正在尝试使用 class 在 C++ 中实现 trie 数据结构。在 TrieNode class 我有一个 TrieNode *children[26]; 数组和一个 isEndOfWord 布尔值来确定它是否是结束词。在同一个 class 中，我还有其他适合像 getters 和 setters 这样的函数，另外还有插入和搜索。

每当我尝试添加一个新词时，它也会通过将 isEndOfWord 设置为 true 来将每个词末尾的 bool 值设置为 true。但是在搜索功能中，它并不能确定单词的结尾。请指导我，因为我是这个数据结构的新手，请评论我编写代码的方式以及编写代码的合适方式（如果有兴趣，以专业方式）。谢谢！

#include<cstdio>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

using namespace std;
class TrieNode{

    private:

        TrieNode *children[26];
        bool isEndOfWord;
    public:

        TrieNode(){
            for(int i = 0; i < 26; i++){

                children[i] = NULL;
            }
            isEndOfWord = false;
        }

        bool checkNull(char temp){
            cout<<"\nIncheckNULL "<<temp<<" "<<(temp - 'a')<<" \n";
            if(children[temp - 'a'] == NULL){

                return true;
            }
            else{

                return false;
            }
        }

        void setNode(char temp){
            cout<<"Setting node \n";
            children[temp - 'a'] = new TrieNode();
        }

        TrieNode *getNode(char temp){

            return children[temp - 'a'];
        }

        void setEndWord(){

            this->isEndOfWord = true;
        }

        bool getEndWord(){

            return this->isEndOfWord;
        }

        void insert(TrieNode*, string);
        bool search(TrieNode*, string);

};

void TrieNode::insert(TrieNode *root, string key){

    TrieNode *crawl = root;
    //cout<<"key is "<<key<<endl;
    int length = sizeof(key)/sizeof(key[0]);
    //cout<<"find length\n";
    for(int i = 0; key[i] != '[=11=]'; i++){
        cout<<"TEST null check key is "<<key[i]<<endl;
        if(crawl->checkNull(key[i])){
            cout<<"null check key is "<<key[i]<<endl;
            crawl->setNode(key[i]);
            crawl = crawl->getNode(key[i]);

            if(key[i + 1] == '[=11=]'){
                cout<<"In setting end word\n";
                if(crawl->getEndWord()){

                    cout<<"Word already exists";
                }
                else{

                    crawl->setEndWord();
                    cout<<"End word setted "<<crawl->getEndWord()<<endl;
                }
            }
        }
        else{

            if(key[i + 1] == '[=11=]'){
                cout<<"In setting end word\n";
                if(crawl->getEndWord()){

                    cout<<"Word already exists";
                }
                else{

                    crawl->setEndWord();
                    cout<<"End word setted\n";
                }
            }
            else{

                crawl = crawl->getNode(key[i]); 
            }
        }
    }
}

bool TrieNode::search(TrieNode *root, string key){

    TrieNode *crawl = root;
    cout<<"key is "<<key<<endl;
    cout<<"\n In search\n";
    int length = sizeof(key)/sizeof(key[0]);
    for(int i = 0; key[i] != '[=11=]'; i++){

        if(crawl->checkNull(key[i])){
            cout<<"INside search checknull"<<endl;
            cout<<"Word does not exists"<<"sorry"<<endl;
            break;
        }
        else{
            cout<<"IN each character getting getEndWord "<<crawl->getEndWord()<<endl;
            if(key[i + 1] == '[=11=]'){

                if(crawl->getEndWord()){

                    cout<<"Word Exists";
                }
                else{

                    cout<<"Word does not exists"<<"sorry"<<endl;
                    break;
                }
            }
            else{

                crawl = crawl->getNode(key[i]); 
            }
        }
    }

}

int main(){

    TrieNode *root = new TrieNode();
    cout<<"starting"<<endl;
    root->insert(root, "hello");
    cout<<"first added"<<endl;
    root->insert(root, "anna");
    root->insert(root, "anni");
    cout<<"words added"<<endl;
    root->search(root, "hello");
    root->search(root, "anny");

}

Answer 1

我会就很多事情向您提供反馈，但这不是代码审查网站，它是针对特定问题的。不过，我会简要指出一些我注意到的事情：

1) 不包括 C headers;改用c++。

2) 字符串是什么类型？

3) 你计算了长度（不正确，假设问题 2 的答案是 "the standard c++ string class"），但你没有使用它。

4) search() return 是一个布尔值，但你 return 什么都没有。当你找到一个单词的结尾时，你应该从函数中return。

5) search() 在 for 循环的顶部调用 checkNull() 而不确保它不为空。在此之后：crawl = crawl->getNode(key[i]); 它可能为 null，但随后您循环并遍历指针而不对其进行测试。

6) setNode 是一个 public 函数，无条件地覆盖给定变量的槽中的任何内容。如果有人用相同的字符两次调用它并泄漏（并且可能会丢失树中的数据），您可以破坏现有的 child。

7) 搜索不需要是 TrieNode 的成员。事实上，它不会通过 "this" 访问任何数据。您可能根本不希望 TrieNode 是 public，而是 Trie 的内部实现细节，这是搜索功能应该存在的地方，根应该存储和管理的地方。

8) 在 C++ 中使用 nullptr 而不是 NULL

9) 看起来你需要调试 search()，因为当你检查词尾时它不在最后一个字母上。

10) 你需要一个析构函数并且需要释放你的节点。或者将它们存储在 unique_ptr<> 中，以便在 object 超出范围时自动删除。

11) 不要在 headers 中 "using namespace std;"。将您的 headers 包含在我的代码中会使您变得有毒。

Answer 2

您的插入和搜索功能可以稍微简化一下。

考虑一下。（阅读下面代码中的注释，它们说明了代码的作用）

void TrieNode::insert(TrieNode *root, string key){

    TrieNode *crawl = root;
    if (!crawl) {
        crawl = new TrieNode();
    } 
    cout << "Adding " << key << " to the trie" << endl;
    for (int index = 0, auto str_iterator = str.begin(); str_iterator < str.end(); ++str_iterator, ++index) {
        char key_char = *str_iterator;
        if(crawl -> checkNull(key_char)){
            // If a node representing the char does not exist then make it 
            crawl -> setNode(key_char);
        }
        crawl = crawl -> getNode(key_char);
        if (index == key.length() - 1) {
            // We are at the last character, time to mark an end of word
            crawl -> setEndWord();
        }
    }
}

bool TrieNode::search(TrieNode *root, string key){

    TrieNode *crawl = root;
    if (!crawl) {
        cout << "Trie is empty!" << endl;
        return false;
    } 
    cout << "Searching for " << key << " in the trie" << endl;
    for (int index = 0, auto str_iterator = str.begin(); str_iterator < str.end(); ++str_iterator, ++index) {
        char key_char = *str_iterator;
        if(crawl -> checkNull(key_char)){
            cout << "Key is not in the trie" << endl;
            return false;
        }
        crawl = crawl -> getNode(key_char);
        if (index == key.length() - 1) {
            if (!(crawl -> getEndWord())) {
                cout << "Word is physically present in trie, but not present as a distinct word" << endl;
                return false;
            } else {
                return true;
            }
        }
    }
    cout << "Code should not reach here" << endl; // IMO throw an exception I guess
    return false;
}

利用 C++ 的强大功能std::string

而且你的整个 temp - 'a' 逻辑对我来说有点不确定。除非我需要

，否则我不会过多地使用 ASCII 值

为什么要包含一大堆 C headers？只需 iostream 就足以完成 cstdio 所做的事情。

if(!ptr) 是一种更自然的检查 NULL 的方法。

在生产中不要使用 using namespace std;，而只是在 cout 和 endl 之类的东西前加上 std::。这样做的原因是为了避免污染标准命名空间。

读一本很好的 CPP OOP 书 :)。对你有很大帮助。

我也喜欢 anna 和 anni。你的 anna 和 anni 一定很自豪能进入你的 trie :D

Answer 3

insert 和 search 函数一团糟。他们使用相当人为的方法来检查字符串的结尾，不必要地重复并且在其中一个分支中存在错误。

这里有更简单的版本。他们使用字符串size作为循环边界，循环结束时需要的动作在循环之后进行，这样更自然。

void TrieNode::insert(TrieNode *root, string key){
    TrieNode *crawl = root;
    for(int i = 0; i < (int) (key.size()); i++){
        if(crawl->checkNull(key[i])){
            crawl->setNode(key[i]);
        }
        crawl = crawl->getNode(key[i]);
    }
    crawl->setEndWord();
}

bool TrieNode::search(TrieNode *root, string key){
    TrieNode *crawl = root;
    for(int i = 0; i < (int) (key.size()); i++){
        if(crawl->checkNull(key[i])){
            return false;
        }
        crawl = crawl->getNode(key[i]);
    }
    return crawl->getEndWord();
}

我使用了相同的样式，但为了便于阅读省略了调试输出。

此外，代码实际上并没有使用 search 作为函数，它没有 return 一个值。相反，它依靠调试输出来显示结果。现在已更正。 main 补充这些的功能如下。

int main(){
    TrieNode *root = new TrieNode();
    cout<<"starting"<<endl;
    root->insert(root, "hello");
    cout<<"first added"<<endl;
    root->insert(root, "anna");
    root->insert(root, "anni");
    cout<<"words added"<<endl;
    cout << root->search(root, "hello") << endl;  // 1
    cout << root->search(root, "anny") << endl;  // 0
}

使用 class C++ 的 Trie 数据结构

Trie data structure using class C++

c++

search

trie

data-structures