Trie樹入門
統(tǒng)計(jì)難題 ( hud-1251 )
指針多叉樹
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define maxn 26
struct Trie
{
int num;//到某一層字符數(shù)目
struct Trie *next[maxn];//每層最多多少種字符
};
struct Trie *root = (struct Trie*)malloc(sizeof(struct Trie));
void init()
{
/*別忘了給root分配內(nèi)存*/
root->num = 0;
for(int i = 0 ; i < maxn ; ++i)
root->next[i] = NULL;
}
void put(char *str)//插入字典樹
{
int len = strlen(str);
struct Trie *p = root;//先由p指向字典樹的根符匾，從而找到這棵字典樹
//把字符加入字典樹
for(int i = 0 ; i < len ; ++i)
{
int pos = str[i] - 'a';//轉(zhuǎn)化為坐標(biāo)
if(p->next[pos] == NULL)//如果指向的結(jié)點(diǎn)為空轿偎，新建結(jié)點(diǎn)
{
//new一個(gè)新結(jié)點(diǎn)
struct Trie *temp = (struct Trie*)malloc(sizeof(struct Trie));
temp->num = 1;//這個(gè)地方是1說(shuō)明添加了一個(gè)字符
for(int j = 0 ; j < maxn ; ++j)
temp->next[j] = NULL;
p->next[pos] = temp;
p = p->next[pos];
}
else
{
p = p->next[pos];//移動(dòng)到一下層
p->num++;
}
}
}
int research(char *str)
{
struct Trie *p = root;
int len = strlen(str);
for(int i = 0 ; i < len ; ++i)
{
int pos = str[i] - 'a';
p = p->next[pos];
if(p == NULL)
return 0;
}
return p->num;
}
void del(Trie *p)
{
if(p==NULL) return;
for(int i=0;i<maxn;i++)
{
if(p->next[i]!=NULL)
del(p->next[i]);
}
if(p!=root) free(p);//delete對(duì)應(yīng)的是new吞加；free用來(lái)釋放malloc出來(lái)動(dòng)態(tài)內(nèi)存
}
int main()
{
char s[15];
init();//初始化字典樹钙态，讓根節(jié)點(diǎn)為空
while(gets(s) && strlen(s))
put(s);//每讀取一條記錄就加入字典樹
while(gets(s))
{
int ans = research(s);
printf("%d\n",ans);
}
return 0;
}
數(shù)組多叉樹
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<map>
#include<string>
using namespace std;
const int MAXN=4000010;
struct Node
{
int sum;
int next[26];
};
Node trie[MAXN];
int trie_s;
void insert(char *str)
{
int len=strlen(str);
int p=0;
for(int i=0;i<len;i++)
{
int pos=str[i]-'a';
if(!trie[p].next[pos])
{
trie[p].next[pos]=trie_s++;
}
trie[trie[p].next[pos]].sum++;
p=trie[p].next[pos];
}
}
int query(char *str)
{
int len=strlen(str);
int p=0;
for(int i=0;i<len;i++)
{
int pos=str[i]-'a';
if(!trie[p].next[pos]) return 0;
p=trie[p].next[pos];
}
return trie[p].sum;
}
int main()
{
char s[15];
trie_s=1;
char c;
while(true)
{
int index=0;
c=getchar();
if(c=='\n') break;
s[index++]=c;
while(true)
{
c=getchar();
if(c=='\n')
{
s[index++]=0;
break;
}
s[index++]=c;
}
insert(s);
}
while(scanf("%s",s)!=EOF)
{
printf("%d\n",query(s));
}
return 0;
}
左兒子右兄弟樹
#include <stdio.h>
#include <string.h>
using namespace std;
#define maxn 4000010
struct node
{
char y;
int son;
int right;
int sum;
}trie[maxn];
char str[15];
int trie_s ;
long long sum ;
void init()
{
trie[0].son = trie[0].right = -1;
trie[0].sum = 0;
sum = 0;
trie_s = 1;
}
void put()
{
int i , v , k = strlen(str);
int u = 0;
bool flag;
for(i = 0;i<k;i++)
{
flag = false;
for(v = trie[u].son ; v!= -1 ; v = trie[v].right)
{
if(trie[v].y == str[i])
{
trie[v].sum++;
flag = true;
break;
}
}
if(!flag)
{
v = trie_s++;
trie[v].right = trie[u].son;
trie[v].y = str[i];
trie[u].son = v;
trie[v].sum = 1;
trie[v].son = -1;
}
u = v;
}
}
int research()
{
int i , v , k = strlen(str);
int u = 0;
bool flag;
for(i = 0; i <k ; i++)
{
flag = false;
for(v = trie[u].son ; v!= -1 ; v = trie[v].right)
{
if(trie[v].y == str[i])
{
flag = true;
break;
}
}
if(!flag)
{
return 0;
}
u = v;
}
return trie[u].sum;
}
int main()
{
init();
while(gets(str) && strlen(str))
put();
while(gets(str))
{
int ans = research();
printf("%d\n",ans);
}
return 0;
}
