大家好，欢迎来到IT知识分享网。
目录
一.字典树概述
1.定义
字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
字典树与字典很相似，当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。
2.例子
比如我们创建一个字典树包含下列单词：
inn, int, at, age, adv, ant …
inn, int, at, age, adv, ant …
字典树算法的核心思想就是每层存入单词的字符，顺着树节点依次往下排布，用bool judge变量来标记此字符处是否构成单词（某个单词的结尾字符），还可以用一个int counter变量来累计某个前缀出现的次数。
二.算法实现
1.指针申请空间法
使用指针方便快捷，但是要注意释放空间，否则容易出错。
struct Node//首节点是不存东西的！ { int counter;//出现次数 bool judge;//标记是否构成单词 Node *next[26];//分支(26个字母) Node():counter(0),judge(false) {}; }; Node *Root; void Creattree(Node *&root) { root=new Node(); memset(root->next,0,sizeof(root->next));//申请空间 } void inserttree(char *s,Node *&root) { Node *p=root; for(int i=0; i<strlen(s); i++) { int id=s[i]-'a'; if(p->next[id]==NULL)//如果为空则申请 Creattree(p->next[id]); p=p->next[id];//顺着树枝往下构造 p->counter++;//更新次数 } p->judge=true;//最终地方构成单词 }2.结构体数组实现法
struct Node { int counter; int next[26]; bool judge; }tree[maxn]; int n,m,top; bool sign; int Creat()//申请树，此处用top序号来表示树 { memset(tree[top].next,-1,sizeof(tree[top].next)); tree[top].judge=false; tree[top].counter=0; return top++; } void Increat(char *s) //插入单词 { int rt=0,len=strlen(s); for(int i=0;i<len;i++) { int c=s[i]-'a'; if(tree[rt].next[c]==-1) { tree[rt].next[c]=Creat();//赋予序号来表示开辟了节点！ } rt=tree[rt].next[c];//顺次往下 tree[rt].counter++; } tree[rt].judge=true; }三.算法例题
1.字典树
数据保证所有的单词都是有小写字母组成，并且长度不超过10。若存在则输出Yes，不存在输出No 。
3 2 aab aa ad ac ad No Yes
（1）结构体实现
#include <iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=; struct Node { int counter; int next[26]; bool judge; }tree[maxn]; int n,m,top; int Creat() { memset(tree[top].next,-1,sizeof(tree[top].next)); tree[top].judge=false; tree[top].counter=0; return top++; } void Increat(char *s) { int rt=0,len=strlen(s); for(int i=0;i<len;i++) { int c=s[i]-'a'; if(tree[rt].next[c]==-1) { tree[rt].next[c]=Creat(); } rt=tree[rt].next[c]; tree[rt].counter++; } tree[rt].judge=true; } void findtree(char *s) { int rt=0,len=strlen(s); for(int i=0;i<len;i++) { int c=s[i]-'a'; if(tree[rt].next[c]==-1) { return false; } rt=tree[rt].next[c]; } return tree[rt].judge; } int main() { while(cin>>n>>m&&(n||m)) { top=0; Creat(); char name[10]; for(int i=0;i<n;i++) { cin>>name; Increat(name); } for(int j=0;j<m;j++) { cin>>name; if(findtree(name)) cout<<"No"<<endl; else cout<<"Yes"<<endl; } } return 0; }（2）指针实现
#include <iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=1000; bool sign; struct Node { int counter; bool judge; Node *next[26]; Node():counter(0),judge(false) {}; }; Node *Root; void Creattree(Node *&root) { root=new Node(); memset(root->next,0,sizeof(root->next)); } void inserttree(char *s,Node *&root) { Node *p=root; for(int i=0; i<strlen(s); i++) { int id=s[i]-'a'; if(p->next[id]==NULL) Creattree(p->next[id]); p=p->next[id]; p->counter++; } p->judge=true; } void release(Node *root) { if(root==NULL) return; for(int i=0;i<26;i++) { if(root->next[i]!=NULL) release(root->next[i]); } delete(root); } bool findtree(char *s) { Node *root=Root; int i; for(i=0; i<strlen(s); i++) { int id=s[i]-'a'; if(root->next[id]==NULL) { sign=false; break; } else root=root->next[id]; } if(root->judge!=true) sign=false; } int main() { int n,m; while(cin>>n>>m&&(n||m)) { getchar(); Creattree(Root); char name[10]; for(int i=0; i<n; i++) { cin>>name; inserttree(name,Root); } for(int j=0; j<m; j++) { sign=true; cin>>name; findtree(name); if(sign) cout<<"Yes"<<endl; else cout<<"No"<<endl; } release(Root); } return 0; }2.迷之好奇
FF得到了一个有n个数字的集合。不要问我为什么，有钱，任性。FF很好奇的想知道，对于数字x，集合中有多少个数字可以在x前面添加任意数字得到。如，x = 123，则在x前面添加数字可以得到4123，5123等
本题有多组输入。对于每组数据，首先输入n(1<= n <= )。接下来n行。每行一个数字y(1 <= y <= )代表集合中的元素。接下来一行输入m(1 <= m <= ),代表有m次询问。接下来的m行。每行一个正整数x(1 <= x <= )。对于每组数据，输出一个数字代表答案。
3 12345 66666 12356 3 45 12345 356 1 0 1
#include <iostream>//字典树最好用数组，结构体指针会产生内存泄漏。而二叉树和搜索树常用指针！ #include<cstdio> #include<cstring> using namespace std; const int maxn=; int top; struct Node { int next[10]; int counter; bool judge; }tree[maxn]; int Creat() { memset(tree[top].next,-1,sizeof(tree[top].next)); tree[top].counter=0; tree[top].judge=false; return top++; } void Increat(char *s) { int rt=0,len=strlen(s); for(int i=len-1;i>=0;i--) { int c=s[i]-'0'; if(tree[rt].next[c]==-1) { tree[rt].next[c]=Creat(); } tree[rt].counter++; rt=tree[rt].next[c];//注意这里的顺序，如果是求某个前缀的话，现在这个顺序输出都是字符串后面第一个字符的出现次数，而若倒过来输出的是最后一个字符的次数！！！ } tree[rt].judge=true; } int findtree(char *s) { int rt=0,len=strlen(s); for(int i=len-1;i>=0;i--) { int c=s[i]-'0'; if(tree[rt].next[c]==-1) { return 0; } rt=tree[rt].next[c]; } return tree[rt].counter; } int main() { int n,m; while(cin>>n) { top=0; Creat(); char name[10]; for(int i=0;i<n;i++) { cin>>name; Increat(name); } cin>>m; for(int j=0;j<m;j++) { cin>>name; int sum=findtree(name); cout<<sum<<endl; } } return 0; }免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/111963.html
