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

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

阅读量：5040 次

发布时间：2019-06-12

本文共 2676 字，大约阅读时间需要 8 分钟。

1 /*  2 自己来写字典树  3 */  4 #include 
        
           5 #include 
         
            6 #include 
          
             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
           
            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
            
             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 }