目录
1.字典树
2.字典树的实现方式
（1）使用二维数组实现
①字典树的插入
（2）使用链表实现
①定义数据结构
②插入字典树中
③搜索前缀，判断字符串是否存在
④查找前缀数
⑤释放节点
⑥主函数
3.字典树的应用
（1）字符串检索
（2）前缀统计
（3）最长公共前缀
（4）排序
（5）作为其他数据结构与算法的辅助结构
1.字典树
2.字典树的实现方式 （1）使用二维数组实现 ①字典树的插入字典树，又称为Trie树，单词查找树，是一种树形结构，也是哈希的一种变种，主要用于统计，排序和存储大量的字符串（不限于字符串）。经常被用于搜索引擎引擎系统用于文本词频统计。
字典树特点：主要利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
将一个字符串插入到字典树中，这里使用二维数组来存储。
初始化工作：
#include
#include
#include
using namespace std;
const int maxn=32;
//二维数组存储字典树
int trie[maxn][26];
//字符串的结束标记
bool end[maxn];
//字符数和索引
int n,index;
void init(){
memset(trie,0,sizeof(trie));
memset(end,false,sizeof(end));
index=1;
} 比如我们现在插入一个字符串“dream”，因为这里是使用数组存储的，所以需要将字符转换为数字（str[i]-'a'）；这里的trie[1][0]从下标为1开始；首先第一个字符在trie[1][‘d’-'a’];第二个字符在trie[2][‘r’-'a’]；第三个字符在trie[3][‘e’-'a']；第四个字符在trie[4][‘a’-'a']；第五个字符在trie[1][‘m’-'a'].字典树的结构如下：
再插入一个字符串：“draw”,第一个字符在 trie[1][‘d’-'a’]；第二个字符在trie[2][‘r’-'a’]；第是三个字符trie[3][‘a’-'a’]；第四个字符在trie[2][‘w’-'a’]；
字符串插入 *** 作：
//插入字符串
void insert(string str){
int p=1;
for(int i=0;i字符串的查找 *** 作：
查找一个字符串是否存在于字典树中，需要将字符串转换为数字，若查找的位置trie[p]['x'-'a']为0，那么则表示没有存储字符串，也就是不存在该字符串。如果查找到最后的结束标志并且字符串也遍历完毕，则表示查找成功。
//搜索当前字符串是否存在
bool search(string str){
int p=1;
for(int i=0;i查找一个字符串是否为其他字符串的前缀：
//判断当前字符是否为其他字符的前缀
bool prefix(string str){
int p=1;
for(int i=0;i遍历字符串：
//深度遍历字典树
void dfs(int p){
for(int i=0;i<26;i++){
if(trie[p][i]){
cout<统计一个字符串所有前缀单词的个数，只需要从根到叶子单词出现的个数，也可以判断一个单词是否为其他单词的前缀。
方法：只需要记录从根到叶子节点由多少个结束标记。
//判断一个字符串串有多少个前缀
int Scount(string st){
int p=1;
//记录前缀
int cnt=0;
for(int i=0;i主程序：
int main(){
init();
while(1){
int flag;
string st;
string str;
string fix;
int cnt=0;
menu();
cout<<"请输入操作: ";
cin>>flag;
switch (flag){
case 1:
cout<<"请输入要输入的字符串数: "<>n;
while(n--){
cout<<"请输入字符串: "<>str;
insert(str);
}
break;
case 2:
cout<<"请输入要查找的字符串: "<>st;
if(search(st)){
cout<<"查询成功"<>fix;
if(prefix(fix)){
cout<<"YES"<>st;
cnt=Scount(st);
cout<<"该字符前缀数: "< 结果测试：
（2）使用链表实现 ①定义数据结构
#include
#include
#include
#include void menu(){
cout<<"----------------------------------"<next[id]==NULL){
p->next[id]=new Trie();
}
p=p->next[id];
//使用p->v记录前缀数量
p->v++;
}
p->v=-1;
}
int search(string s){
Trie *p=root;
for(int i=0;inext[id];
if(p==NULL){//表示不存在该字符
return 0;
}else if(p->v==-1&&(iv==-1){
return 1;
}else{
//表示为其他字符串的前缀
return 2;
}
} int Find(string s){ //返回以字符串word为前缀的单词的数量
Trie *p = root;
for(int i=0;inext[idx]==NULL){
return 0;
}
p = p->next[idx];
}
return p->v;
} void release(Trie*p){
if(p==NULL){
return ;
}else{
for(int j=0;j<26;j++){
if(p->next[j]!=NULL){
release(p->next[j]);
}
}
}
delete p;
}int main(){
string s;
root=new Trie();
while(1){
int flag=0;
int n;
int num;
menu();
cout<<"请输入操作: ";
cin>>flag;
switch(flag){
case 1:
cout<<"请输入插入字符串数: ";
cin>>n;
while(n--){
cout<<"请输入插入的字符串: ";
cin>>s;
insert(s);
cout<<"插入字典树中成功!"<>s;
flag=search(s);
if(flag==1||flag==2){
cout<<"存在字典树中"<>s;
flag=search(s);
if(flag==2){
cout<<"该字符串为其他字符串的前缀!"<>s;
num=Find(s);
cout<<"前缀数: "<
3.字典树的应用 （1）字符串检索
（2）前缀统计事先将字符串存储到字典树Trie中，查找字符串，出现的频率和搜索引擎的热门查询
（3）最长公共前缀统计一个字符串所有前缀单词的个数，只需要从根到叶子单词出现的个数，也可以判断一个单词是否为其他单词的前缀。
（4）排序两个字符串的最长公共前缀的长度就是它们所在节点最近公共祖先到根的长度。
（5）作为其他数据结构与算法的辅助结构利用字典树进行串排序，对字典树先序遍历，输出相应的字符串便是按字典排序的结果。
如后缀树和AC自动机。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）