Trie字典树模板及栗子

模板

Trie字典树大致可以分为两种实现方式，一种是数组，另一种是指针，那么我们就整理了两个模板：

数组的实现：

#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <map> using namespace std; const int N = 1000000; int ch[N][26],val[N],tot; //数组实现的话，总是拿不准ch数组的大小，我们不确定生成的节点会有多少 void Init() {     memset(ch[0],0,sizeof(ch[0]));     tot = 1;     memset(val,0,sizeof(val)); } void Insert(char *s,int x) {     int u = 0,len = strlen(s);     for(int i =0 ;i < len;i ++)     {         int v = s[i]-'a';         if(!ch[u][v])         {             memset(ch[tot],0,sizeof(ch[tot]));             val[tot] = 0;             ch[u][v] = tot ++;         }         u = ch[u][v];     }     val[u] = x;//结尾位置设置为权重，其余位置都设置为0 } int Find(char *s) {     int u = 0,len = strlen(s);     for(int i =0;i < len;i ++)     {         int v = s[i]-'a';         if(!ch[u][v]) return 0;         u = ch[u][v];     }     return val[u]; } void Del(char  *s) {     int  u = 0,len = strlen(s);     for(int i =0 ;i < len;i ++)     {         int v = s[i] - 'a';         if(!ch[u][v]) return ;         u = ch[u][v];     }     val[u] = 0;//删除时就是将最后一个位置的权值设置为0 }

指针实现

#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <map> using namespace std; //指针实现较为方便，并且也很容易理解 struct Trie { Trie *next[26]; int val; }; Trie *root; void Init() { root = (Trie *)malloc(sizeof(Trie)); for(int i = 0;i < 26;i ++) root->next[i] = NULL; root->val = 0; } void Insert(char *s) { Trie *p = root,*q; int len = strlen(s); for(int i = 0;i < len;i ++) { int v = s[i] - 'a'; if(p->next[v] == NULL) { q = (Trie *)malloc(sizeof(Trie)); q->val = 0; for(int j = 0;j < 26;j ++) q->next[j] = NULL; p->next[v] = q; } p = p->next[v]; } p->val = 1; } int Find(char *s) { int len = strlen(s); Trie *p = root; for(int i =0 ;i < len;i ++) { int v = s[i] - 'a'; p = p->next[v]; if(p == NULL) return -1; } return p->val; } void Del(Trie *s) { if(s == NULL) return ; for(int i =0;i < 26;i ++) if(s->next[i]) Del(s->next[i]); delete s; }

栗子

HDU 1251

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N = 1000000; int sz; int ch[N][26]; int val[N]; struct Trie { Trie(){ sz = 1;//这里要把0节点空出来，作为全部的根节点 memset(ch[0],0,sizeof(ch[0])); memset(val,0,sizeof(val)); } int idx(char c) { return c-'a'; } void Insert(char *s,int v) { int u = 0,len = strlen(s); for(int i =0 ;i < len;i ++) { int c = idx(s[i]); if(!ch[u][c])//表示这个节点重新作为一个新的节点，下面仍然还有26个子节点 { memset(ch[sz],0,sizeof(ch[sz])); val[sz] = 0; ch[u][c] = sz++; } u = ch[u][c]; val[u] ++; } } int Read(char *s) { int u = 0,len = strlen(s); for(int i = 0;i < len;i ++) { int c = idx(s[i]); if(!ch[u][c]) return -1; else u = ch[u][c]; } if(val[u] == 0) return 1; else return 2; } int Get_num(char *s) { int u = 0,len = strlen(s); for(int i = 0;i < len;i ++) { int c = idx(s[i]); if(!ch[u][c]) return 0; else u = ch[u][c]; } return val[u]; } }; int main() { Trie T; char s[15]; while(1) { gets(s); if(s[0] == '\0') break; T.Insert(s,1); } while(gets(s)) { printf("%d\n",T.Get_num(s)); } return 0; }

HUD 1075

#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <map> using namespace std; struct Trie { Trie *next[26]; char *val; }; Trie *root; void Init() { root = (Trie *)malloc(sizeof(Trie)); for(int i = 0;i < 26;i ++) root->next[i] = NULL; root->val = NULL; } void Insert(char *s,char *str) { Trie *p = root,*q; int len = strlen(s); for(int i = 0;i < len;i ++) { int v = s[i] - 'a'; if(p->next[v] == NULL) { q = (Trie *)malloc(sizeof(Trie)); q->val = NULL; for(int j = 0;j < 26;j ++) q->next[j] = NULL; p->next[v] = q; } p = p->next[v]; } p->val = new char[11]; strcpy(p->val,str); } void Find(char *s) { int len = strlen(s); Trie *p = root; for(int i =0 ;i < len;i ++) { int v = s[i] - 'a'; p = p->next[v]; if(p == NULL) {printf("%s",s);return ;} } if(p->val) printf("%s",p->val); else printf("%s",s); } void Del(Trie *s) { if(s == NULL) return ; for(int i =0 ;i < 26;i ++) { if(s->next[i]) Del(s->next[i]); } delete s->val; delete s; } int main() { char s[15],s1[15]; Init(); scanf("%s",s); while(scanf("%s %s\n",s,s1) && strcmp(s,"END")) { Insert(s1,s); } char str[3100],part[100]; while(gets(str) && strcmp(str,"END")) { int index = 0; int len = strlen(str); for(int i = 0;i < len;i ++) { if(islower(str[i])) part[index++] = str[i]; else { part[index] = '\0'; Find(part); index = 0; printf("%c",str[i]); } } puts(""); } }

参考博客

https://blog.csdn.net/hcbbt/article/details/39499325