文章目录
动态前缀树的实现
动态前缀树实现的关键在于利用指针的动态分配,但这也带来了一个问题,内存的释放问题。所以我们采用将每一个申请的内存空间通过vector进行存储,最后方便释放。
Trie_dyn.h
//
// Created by Alone on 2021/8/3.
//
#ifndef MY_TINY_STL_TRIE_DYN_H
#define MY_TINY_STL_TRIE_DYN_H
#include <cstring>
#include <string>
#include <vector>
using namespace std;
struct Trie{
bool f;
Trie* children[26];
Trie():f(false){
memset(children,0,sizeof(children));
}
};
class Trie_dyn {
private:
vector<Trie*>pool;
Trie* searchPrefix(const string s);
public:
Trie_dyn():pool(1){
pool[0] = new Trie;
}
~Trie_dyn();
void insert(string word);
bool search(string word);
bool startWith(string prefix);
};
#endif //MY_TINY_STL_TRIE_DYN_H
Trie_dyn.cpp
//
// Created by Alone on 2021/8/3.
//
#include "Trie_dyn.h"
//每次入新的表需要把它们加入到内存池,方便最后析构函数的清理
void Trie_dyn::insert(string word) {
Trie* node = pool[0];
for(auto&&t:word){
if(!(node->children[t-'a'])){
node->children[t-'a'] = new Trie;
pool.emplace_back(node->children[t-'a']);
}
node = node->children[t-'a'];
}
node->f = true;
}
Trie * Trie_dyn::searchPrefix(const string s) {
Trie* node = pool[0];
for(auto&&t:s){
if(!(node->children[t-'a']))
return nullptr;
node = node->children[t-'a'];
}
return node;
}
bool Trie_dyn::search(string word) {
Trie* t = searchPrefix(word);
return t!= nullptr&&t->f;
}
bool Trie_dyn::startWith(string prefix) {
return searchPrefix(prefix)== nullptr?false:true;
}
Trie_dyn::~Trie_dyn() {
for(auto t:pool){
delete t;
}
}
静态前缀树的实现
静态前缀树有很多好处,最大的一条就是不需要进行内存释放,坏处在于申请的内存空间有限,没有堆上那么大的内存申请。还有一个好处在于平时很好写。而且效率相对动态的实现方式要高。
需要注意的地方:静态实现方式利用二维数组,其中第一个下标代表一个结点,第二个下标代表这个结点的表。其中下标0默认为根节点。还需要利用 tot 指针对结点进行正确的连接。
Trie_static.h
//
// Created by Alone on 2021/8/3.
//
//静态字典树(前缀树)用二维数组来实现,第一维度表示结点,第二维度表示当前结点的表表指针。
#ifndef MY_TINY_STL_TRIE_STATIC_H
#define MY_TINY_STL_TRIE_STATIC_H
#include <cstring>
#include <string>
#define maxn 10000
using namespace std;
class Trie_static {
private:
int tot;
bool isEnd[maxn];
int son[maxn][26];
int searchPrifix(string word);
public:
Trie_static(){
tot = 0;
memset(isEnd,0,sizeof(isEnd));
memset(son,0,sizeof(son));
}
void insert(string word);
bool search(string word);
bool startWith(string word);
};
#endif //MY_TINY_STL_TRIE_STATIC_H
Trie_static.cpp
//
// Created by Alone on 2021/8/3.
//
#include "Trie_static.h"
void Trie_static::insert(string word) {
int p = 0;
for(auto&&t:word){
int&& ch = t-'a';
if(!son[p][ch]){
son[p][ch] = ++tot;
}
p = son[p][ch];
}
//标记单词结尾的结点
isEnd[p] = true;
}
int Trie_static::searchPrifix(const string word) {
int p = 0;
for(auto && t:word){
int&& ch = t-'a';
if(!son[p][ch])
return 0;
p = son[p][ch];
}
return p;
}
bool Trie_static::search(string word) {
int&& t = searchPrifix(word);
return t&&isEnd[t];
}
bool Trie_static::startWith(string word) {
return searchPrifix(word);
}
前缀树的好处
- 前缀树,就是通过已有的单词构建出的一颗单词查找树,能较快的查找出是否存在某个前缀。