字典树模板【经测试，几个函数都好用】

  1 /*
  2 自己来写字典树
  3 */
  4 #include <stdio.h>
  5 #include <malloc.h>
  6 #include <string.h>
  7 struct node
  8 {
  9     int size;                       //该结点上的前缀单词的个数
 10     struct node *child[26];         //下一个单词的结点
 11 }a;
 12 typedef struct node NODE;
 13 NODE *root;                        //表示根节点。（根节点里面什么也不包含）
 14 void insert(char word[])
 15 {
 16     int l=strlen(word);
 17     int i,j;
 18     int temp;
 19     NODE *s=root;
 20     for(i=0;i<l;++i)
 21     {
 22         temp=word[i]-'a';
 23         if(s->child[temp]==NULL)    //如果未出现，则建立一个。
 24         {
 25             NODE *t=(NODE *)malloc(sizeof(a));
 26             s->child[temp]=t;
 27             t->size=1;
 28             for(j=0;j<26;++j)
 29             {
 30                 t->child[j]=NULL;
 31             }
 32             s=t;                    //更换结点
 33         }
 34         else                        //如果出现了，则
 35         {
 36             s=s->child[temp];
 37             s->size++;
 38         }
 39     }
 40     return ;
 41 }
 42 void init(NODE *tem)               //重定义字典树
 43 {
 44     int i;
 45     for(i=0;i<26;++i)
 46     {
 47         if(tem->child[i]!=NULL)    //如果子节点不为空
 48         {
 49             init(tem->child[i]);
 50             free(tem->child[i]);
 51         }
 52     }
 53     return ;
 54 }
 55 int check(char word[])              //字符串的查找
 56 {
 57     int l=strlen(word);             //计算字符串的长度
 58     int i;
 59     int temp;
 60     int res;
 61     NODE *p=root;
 62     for(i=0;i<l;++i)
 63     {
 64         temp=word[i]-'a';
 65         if(p->child[temp]!=NULL)
 66         {
 67             p=p->child[temp];
 68             res=p->size;
 69         }
 70         else
 71         {
 72             return 0;
 73         }
 74     }
 75     return res;
 76 }
 77 int main()
 78 {
 79     char temp[15];
 80     int res;
 81     int i;
 82     int t,n,m;
 83     root=(NODE *)malloc(sizeof(a));
 84     scanf("%d",&t);
 85     {
 86         while(t--)
 87         {
 88             for(i=0;i<26;++i)
 89             {
 90                 root->child[i]=NULL;
 91             }
 92             scanf("%d%d",&n,&m);
 93             while(n--)
 94             {
 95                 //gets(temp);
 96                 scanf("%s",temp);
 97                 getchar();
 98                 insert(temp);
 99             }
100             while(m--)
101             {
102                 //gets(temp);
103                 scanf("%s",temp);
104                 getchar();
105                 res=check(temp);
106                 printf("%d\n",res);
107             }
108             init(root);
109         }
110     }
111     return 0;
112 }