字典树的基本模板

字典树的基本功能是用来查询某个单词（前缀）在所有单词中出现次数的一种数据结构 
1、统计一组字符串中某前缀出现次数（字典树第一类应用）
2、一组字符串中是否有一个字符串是另一个字符串的前缀（字典树第二类应用） 
理解上面两种功能有利于理解字典树的数据结构的设置

 int count;//记录该字符在该位置出现次数(即前缀出现次数)
 struct node *next[Max];//定义26个分节点，数字的话则10个

1）定义结点 

#define Max 26
struct node
{
    int count;//记录该字符在该位置出现次数
    struct node *next[Max];//定义26个分节点
};

2）建立一个结点

struct node *build()//建立节点
{
    struct node *p;
    p=(struct node *)malloc(sizeof(struct node));
    for(int i=0;i<26;i++)
    {
        p->next[i]=NULL;//令其指向0；
    }
        p->count=1;/*如果出现这个站点，那么它的次数肯定是大于等于1的。
        但是我们刚开始建立不必考虑后续问题*/
    return p;//返回新建立的节点
}

3、存储结点，（对于一个字符串）不断把上面的字符结点插入组成一棵字典树
     通过不断输入字符串构建字典树

void save(char *s)//储存字母
{
    int len=strlen (s);
    if(len==0)return ;
    struct node *p;
    p=root;
    for(int i=0;i<len;i++)
        if(p->next[s[i]-'a']!=NULL)
            /*如果这个节点之前就已经存在呃，我们只需要把统计次数加上1.*/
        {
            p=p->next[s[i]-'a'];
            p->count=p->count+1;
        }
        else//如果不存在的话，我们就建立一个新的节点
        {
            p->next[s[i]-'a']=build();
            p=p->next[s[i]-'a'];
        }
}

4、查询前缀次数（输入一个前缀，统计出现次数）

int search (char *s)//这个函数来查询数据
{
    struct node *p;
    int len=strlen(s);
    if(len==0)
        return 0;
    p=root;//此处小心,root是不存储任何字符，所以下面p->next[]比较是否为NULL;root在main()创建
    for(int i=0;i<len ;i++)
    {
        if(p->next[s[i]-'a']!=NULL)//说明还有下个节点，继续查询
            p=p->next[s[i]-'a'];//执行i=0之后，p=p0，直接指向当前字符
        else
            return 0;
        /*如果没有指向下个节点，说明这个要查询的字符串根本不存在，直接返回0*/
    }
    return p->count;//直接返回以这个字符结尾的前缀次数
}