Trie树

发表于 更新于 分类于 阅读次数：

字典树用于单词统计，查询，非常有用。现在就Trie树给出C语言实现。

题目来源：http://hihocoder.com/problemset/problem/1014

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <stdio.h>
#include <malloc.h>

#define MAXN  26

struct Trie{
	int count;   //单词计数
	int flag;    // 1表示是单词，0表示不是单词
	struct Trie *next[MAXN];
};

struct Trie *rt;

//初始化Trie树
void trie_init(){
	int i;
	rt = (struct Trie*)malloc(sizeof(struct Trie));

	rt->count = 0;
	rt->flag = 0;
	for(i=0; i<MAXN; ++i)
		rt->next[i] = NULL;
}

//插入单词
void trie_insert(char *s){
	int i;
	struct Trie *tmp = rt;

	for(s; *s!='\0'; ++s){
		if(tmp->next[*s -'a'] == NULL){
             struct Trie *cur = (struct Trie*)malloc(sizeof(struct Trie));
             cur->count = 0;
             cur->flag = 0;
             for(i=0; i<MAXN; ++i)
		         cur->next[i] = NULL;
		     tmp->next[*s -'a'] = cur;
		}
		tmp->count++;
		tmp = tmp->next[*s -'a'];
	}
	tmp->flag = 1;
	tmp->count++;
}

//查询给定字符串前缀的单词数目
int trie_search(char *s){

	struct Trie *tmp = rt;
	for(s; *s!='\0'; ++s){
		if(tmp->next[*s -'a'] == NULL)
			return 0;
	    tmp = tmp->next[*s -'a'];
	}
	return tmp->count;
}

//删除整个Trie树
void trie_del(struct Trie *root){
    int i;
    for(i=0; i<MAXN; ++i){
       if(root->next[i] != NULL)
       	trie_del(root->next[i]);
    }
    free(root);
}

int main(){
  	int i, n, m;
	  char ch[15];

    FILE *fin;
    fin = fopen("input.txt", "r");

 while(fscanf(fin, "%d", &n) != EOF){
       trie_init();
       for(i=0; i<n; ++i){
       	   fscanf(fin, "%s", ch);   	  
       	   trie_insert(ch);
       }
       fscanf(fin, "%d", &m);
       for(i=0; i<m; ++i){
		   fscanf(fin, "%s", ch);
       	   printf("%d\n", trie_search(ch));
       }
       trie_del(rt);
	 }  

	return 0;
}