trieツリーの表現方法と実現
6233 ワード
#include <vector>
#include<cstring>
#include<iostream>
#include <set>
#include <algorithm>
using namespace std;
#define INF 1000000;
// , , , ;
typedef struct node{
char c;
node *firstchild,*nextsibling;
node():c('\0'),firstchild(NULL),nextsibling(NULL){}
}node,*pointer;
/* , ;
26*strlen(str);
;
*/
struct Trie{
pointer root;
Trie(){root=new node();}
void insert(char* s,int i,int n,pointer& root){
if(i==n) return ;
pointer u=root; // , root ;
if(u!=NULL) while(u->nextsibling!=NULL&&u->c!=s[i]) u=u->nextsibling;
if(u==NULL||u->nextsibling==NULL&&u->c!=s[i]){
pointer& v = (u==NULL ? root:u->nextsibling);//NULL root, ;
v=new node();
v->c=s[i];
insert(s,i+1,n,v->firstchild);
}
else insert(s,i+1,n,u->firstchild);
}
void Insert(char* s){
int n=strlen(s);
insert(s,0,n,root);
}
bool find(char* s,int i,int n,pointer& root){
if(i==n) return true;
pointer u=root;
if(u==NULL) return false;
while(u->nextsibling!=NULL&&u->c!=s[i]) u=u->nextsibling;
if(u->nextsibling==NULL&&u->c!=s[i]) return false;
return find(s,i+1,n,u->firstchild);
}
bool Find(char* s,int n){
return find(s,0,n,root);
}
};
int main()
{
char str[1000];
Trie trie;
while(gets(str)!=NULL&&str[0]!='#'){
trie.Insert(str);
}
while(gets(str)!=NULL){
if(trie.Find(str,strlen(str))) printf("find
");
else printf("not find
");
}
return 0;
}
上述插入和建树用的是递归的方式;
而循环版本并不好写(每到一个结点都是站在结点的孩子头上,而不是父亲指针那里,所以写起来很麻烦),因为同s[i] -- > s[i+1] 下一次要用的指针必须为某个特定指针,只能通过递归传引用
void insert(char* s,int n){pointer& Root=root;for(int i=0;i<n;i++){ pointer u=Root; if(u!=NULL)while(u->nextsibling!=NULL&&u->c!=s[i]) u=u->nextsibling; if(u==NULL||u->nextsibling==NULL&&u->c!=s[i]){ pointer& v=(u==NULL ? Root:u->nextsibling); v=new node(); v->c=s[i]; Root=v->firstchild; } else Root=u->firstchild;(这样的写法错误,因为Root为根结点的引用,对它的修改即修改了根结点)}}
每次都站在父节点上考虑,就好写多,下面为指针--循环版;
#include <cstdio> #include <cstring> #include <iostream> using namespace std; typedef struct node{ char c; node *firstchild,*nextsibling; node():c('\0'),firstchild(NULL),nextsibling(NULL){} }node,*pointer; struct Trie{ pointer root; Trie(){root=new node();} void insert(char* s,int n){ pointer u=root; for(int i=0;i<n;i++){ pointer v=u->firstchild; if(v!=NULL) while(v->nextsibling!=NULL&&v->c!=s[i]) v=v->nextsibling; if(v==NULL||v->nextsibling==NULL&&v->c!=s[i]){ pointer& p=(v==NULL ? u->firstchild:v->nextsibling); p=new node(); p->c=s[i]; u=p; } else u=v; } } bool find(char* s,int n){ pointer u=root; for(int i=0;i<n;i++){ pointer v=u->firstchild; if(v==NULL) return false; while(v->nextsibling!=NULL&&v->c!=s[i]) v=v->nextsibling; if(v->nextsibling==NULL&&v->c!=s[i]) return false; u=v; } return true; } }; int main() { char str[1000]; Trie trie; while(gets(str)!=NULL&&str[0]!='#'){ trie.insert(str,strlen(str)); } while(gets(str)!=NULL){ if(trie.find(str,strlen(str))) printf("find
"); else printf("not find
"); } return 0; }
pointer p=p1;ポインタpの指向はp 1と同じである(pでは変化を指し、p 1では同じメモリ領域を指すポインタが1つ増えている).
pointer& p=p1;p 1には使える名前が1つ増えました.3つ目は、変化が起こる状況が異なることです.
次は左の子、右の兄弟の配列の表示方法です#include <cstdio> #include <cstring> #include <iostream> using namespace std; struct Trie{ static const int maxn = 100001; Trie():tot(2){ memset(firstchild,0,sizeof(firstchild)); memset(nextsibling,0,sizeof(nextsibling)); memset(c,0,sizeof(c)); } char c[maxn]; int firstchild[maxn],nextsibling[maxn],tot; void insert(char* s,int n){ int u=1; for(int i=0;i<n;i++){ int v=firstchild[u]; if(v!=0) while(nextsibling[v]!=0&&c[v]!=s[i]) v=nextsibling[v]; if(!v||nextsibling[v]==0&&c[v]!=s[i]){ int& p=(v==0 ? firstchild[u]:nextsibling[v]); p=tot; c[tot]=s[i]; u=tot++; } else u=v; } } bool find(char* s,int n){ int u=1; for(int i=0;i<n;i++){ int v=firstchild[u]; if(!v) return false; while(nextsibling[v]!=0&&c[v]!=s[i]) v=nextsibling[v]; if(nextsibling[v]==0&&c[v]!=s[i]) return false; else u=v; } return true; } }; int main() { char str[1000]; Trie trie; while(gets(str)!=NULL&&str[0]!='#'){ trie.insert(str,strlen(str)); } while(gets(str)!=NULL){ if(trie.find(str,strlen(str))) printf("find
"); else printf("not find
"); } return 0; }
以下は子供配列で実装されたバージョンです#include <cstdio> #include <cstring> #include <iostream> using namespace std; /* ( , , ) (maxn) ; , o(strlen(str)) ; */ struct Trie{ static const int maxn = 10000; static const int sigma_size = 27; int tot,c[maxn],son[maxn][sigma_size]; Trie():tot(2){memset(son,-1,sizeof(son));} void insert(char* s,int n){ int u=1; for(int i=0;i<n;i++){ int word=s[i]-'a'; if(son[u][word]==-1){ son[u][word]=tot; u=tot++; } else u=son[u][word]; } } bool find(char* s,int n){ int u=1; for(int i=0;i<n;i++){ int word=s[i]-'a'; if(son[u][word]==-1) return false; u=son[u][word]; } return true; } }; int main() { char str[1000]; Trie trie; while(gets(str)!=NULL&&str[0]!='#'){ trie.insert(str,strlen(str)); } while(gets(str)!=NULL){ if(trie.find(str,strlen(str))) printf("find
"); else printf("not find
"); } return 0; }