TrieTree

文章目录

• 前言
• 直接上代码
• 总结

---

前言

最近在b站刷左神的教学视频的时候，谈到TrieTree的C++实现，发现内存泄露在是个C++实现的很麻烦的问题，左神使用Hash_set记录要释放的Node，最后统一释放。

本文使用C++11的智能指针来处理该问题并重写TieTree的C++实现，仅供参考，欢迎提问和纠正。

直接上代码

/**
 * @file trietree.cpp
 * @author Stephen Ding ([email protected])
 * @brief Method to Implement TrieTree With CPP
 * @version 0.1
 * @date 2022-04-05
 * 
 * @copyright Copyright (c) 2022
 * 
 */

#include 
#include 
#include 
#include 
using namespace std;

#define MAX_PATH 26
// 26个字母，也可以换作其他分类
// 例如颜色，可以使用HashMap类型的TrieNode::nexts

struct TrieNode{
    TrieNode(){
        pass = 0;
        end = 0;
        nexts.fill(nullptr);
    }
    int pass; // 经过的次数，端点也算经过
    int end; // 作为终端的次数
    array<shared_ptr<TrieNode>,MAX_PATH> nexts; // 默认为nullptr
    // 每个节点都有26个通路可以走 
    // 下标是标记为a->z的路,如果有实际值,则表示走了这条路到达这个节点
    // 使用智能指针是为了解决内存泄露问题
};
        
class TrieTree{
    private:
        shared_ptr<TrieNode> root;
    public:
        TrieTree(){
            root = make_shared<TrieNode>();
        }

        // 增
        void Insert(string word){
            if(word.empty()){
                return;
            }
            shared_ptr<TrieNode> node = root;
            node->pass++;
            int index_path = 0; // "a"-"a",名叫a的路,对应下标为0
            for (int ele=0; ele < word.size(); ++ele){
                index_path = word[ele] - 'a';
                if(node->nexts[index_path] == nullptr){
                    node->nexts[index_path] = make_shared<TrieNode>(); // 创建走该条路的一个节点
                }
                node = node->nexts[index_path];
                node->pass++;
            }
            node->end++;

        }

        // 查
        inline int Find(string word){
            if(word.empty()){
                return 0;
            }
            shared_ptr<TrieNode> node = root;
            int index_path = 0;
            for (int ele=0; ele < word.size(); ++ele){
                index_path = word[ele] - 'a';
                if(node->nexts[index_path] == nullptr){
                    return 0;
                }
                node = node->nexts[index_path];
            }
            return node->end;
        }

        // 删
        void Delete(string word){
            if(Find(word) == 0) {
                cout << "Attention:This word not exits!!!" << endl;
                return;
            }
            shared_ptr<TrieNode> node = root;
            root->pass--;
            int index_path = 0;
            for(int ele=0; ele < word.size(); ++ele){
                index_path = word[ele] - 'a';
                if(--(node->nexts[index_path]->pass) == 0){
                    node->nexts[index_path] = nullptr; //如果是普通指针，这里导致原来的内存被泄漏！！！
                    return; 
                }
                node = node->nexts[index_path];
            }
            node->end--;
        }

        // 找: 以pre开头的字符串的个数
        int PrefixNumber(string pre){
            if(pre.empty()){
                return 0;
            }
            shared_ptr<TrieNode> node = root;
            int index_path = 0;
            for(int ele=0; ele < pre.size(); ++ele){
                index_path = pre[ele] - 'a';
                if(node->nexts[index_path] == nullptr){
                    return 0;
                }
                node = node->nexts[index_path];   
            }
            return node->pass;
        }

        // 字符串的数量
        int Size(){
            return root->pass;
        }

        
};


int main(int arc, char** arv){

    TrieTree test;
    string s;
    s = "wang";
    test.Insert(s);
    s = "bao";
    test.Insert(s);    
    s = "qiang";
    test.Insert(s);
    s = "wang";
    test.Insert(s);

    cout<< "Find wang1: " << test.Find("wang") << endl;
    cout<< "Find qiang: " << test.Find("qiang") << endl;
    cout<< "Find marong: " << test.Find("marong") << endl;

    test.Delete("wang");
    cout<< "Find wang2: " << test.Find("wang") << endl;

    cout<< "Per as ba1: " << test.PrefixNumber("ba") << endl;
    s = "baba";
    test.Insert(s);
    cout<< "Per as ba2: " << test.PrefixNumber("ba") << endl;

    cout << "Size: " << test.Size() << endl;

    return 0;
}

总结

shared_ptr类型的指针在被重赋值或者执行结束被释放，原来指向的内存也自动释放。

代码可以直接编译执行。