Trie树

Trie树入门
统计难题 ( hud-1251 )
指针多叉树

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define maxn 26
struct Trie
{
    int num;//到某一层字符数目
    struct Trie  *next[maxn];//每层最多多少种字符
};

struct Trie *root = (struct Trie*)malloc(sizeof(struct Trie));

void init()
{
    /*别忘了给root分配内存*/
    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';//转化为坐标
        if(p->next[pos] == NULL)//如果指向的结点为空，新建结点
        {
            //new一个新结点
            struct Trie *temp = (struct Trie*)malloc(sizeof(struct Trie));
            temp->num = 1;//这个地方是1说明添加了一个字符
            for(int j = 0 ; j < maxn ; ++j)
                temp->next[j] = NULL;
            p->next[pos] = temp;
            p = p->next[pos];
        }
        else
        {
            p = p->next[pos];//移动到一下层
            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对应的是new；free用来释放malloc出来动态内存
}
int main()
{
    char s[15];

    init();//初始化字典树，让根节点为空
    while(gets(s) && strlen(s))
        put(s);//每读取一条记录就加入字典树
    while(gets(s))
    {
        int ans = research(s);
        printf("%d\n",ans);
    }
    return 0;
}

数组多叉树

#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;
}