首页 > 代码库 > Trie树 模板

Trie树 模板

2024-07-15 22:11:40   227人阅读

typedef struct node{    int count;    struct node *next[MAX];}Trie;Trie *Newnode()//建立结点&初始化a{    int i;    Trie *T;    T = (Trie *)malloc(sizeof(Trie));    T->count = 0;    for(i=0;i<MAX;i++)        T->next[i] = NULL;    return T;}
void creatTrie(Trie *root, char *str)//创建{    int i;    int len = strlen(str);    int id;    Trie *p = root;    for(i=0;i<len;i++)    {        id = str[i]-‘a‘;        if(p->next[id] == NULL)            p->next[id] = Newnode();        p->next[id]->count++;        p = p->next[id];    }}
void findTrie(Trie *root, char *str)//查找{    int i;    int len = strlen(str);    int id;    Trie *p = root;    for(i=0;i<len;i++)    {        id = str[i]-‘a‘;        if(p->next[id] == NULL)            return ;        if(p->next[id]->count == 1){            //操作            return ;        }        if(p->next[id] > 1)        //操作        p = p->next[id];    }}
void delTrie(Trie *T)//删除字典树{    int i;    for(i=0;i<MAX;i++)        if(T->next[i] != NULL)            delTrie(T->next[i]);    free(T);}

 http://hihocoder.com/problemset/problem/1014

题解：

 1 #include <cstdio> 2 #include <cstring> 3 #include <string.h> 4 #include <queue> 5 #define MAX 27 6  7 using namespace std; 8  9 struct node10 {11     int v;12     struct node *next[MAX];13 };14 15 node *Newnode()16 {17     int i;18     node *T;19 20     T = new node();21     for(i=0;i<MAX;i++)22         T->next[i] = NULL;23     T->v = 0;24     return T;25 }26 27 void CreatTrie(node *root, char *str)28 {29     int i;30     int id;31     int len = strlen(str);32     node *T = root;33 34     for(i=0;i<len;i++)35     {36         id = str[i]-‘a‘;37         if(T->next[id] == NULL)38             T->next[id] = Newnode();39         T->next[id]->v++;40         T = T->next[id];41     }42 }43 44 void FindTrie(node *root, char *str)45 {46     int i;47     int id;48     int len = strlen(str);49     node *T = root;50     int ans;51 52     for(i=0;i<len;i++)53     {54         id = str[i]-‘a‘;55         if(T->next[id] == NULL){56             ans = 0;57             break;58         }59         ans = T->next[id]->v;60         T = T->next[id];61     }62     printf("%d\n",ans);63 }64 65 void DeleTrie(node *T)66 {67     int i;68 69     for(i=0;i<MAX;i++)70         if(T->next[i] != NULL)71             DeleTrie(T->next[i]);72     delete(T);73 }74 75 int main()76 {77     int n, m;78     char str[27];79     node *root;80 81     root = Newnode();82     scanf("%d",&n);83     while(n--){84         scanf("%s",str);85         CreatTrie(root, str);86     }87     scanf("%d",&m);88     while(m--){89         scanf("%s",str);90         FindTrie(root, str);91     }92     DeleTrie(root);93     return 0;94 }

 


联系
我们