本文共 2387 字，大约阅读时间需要 7 分钟。
大家都知道，Trie树（又称字典树）是一种树型数据结构，用于保存大量的字符串。它的优点是：利用字符串的公共前缀来节约存储空间。
相对来说，Trie树是一种比较简单的数据结构，比较易于理解。话说上帝是公平的，简单的东西是要付出相应的代价的！Trie树也有它的缺点，它的内存消耗非常大。下面介绍一个减小内存消耗的小技巧。
我们先看看这个题目：
看看这段程序：
#include#include #include typedef struct node { int flag; struct node *next[26]; }Node; int tmp; Node * NewNode() { int i; Node * p = (Node *)malloc(sizeof(Node)); p->flag =0; for(i =0; i <26; i++) p->next[i] =0; return p; } void insert(Node * root, char s[]) { int n = strlen(s); int i; Node * p; p = root; for(i =0; i < n; i++) { if(p->next[s[i] -'a'] == NULL) p->next[s[i] -'a'] = NewNode(); p = p->next[s[i] -'a']; } p->flag =1; } void search(Node * root, char s[]) { int len = strlen(s); int i; Node *p; p = root; for(i =0; i < len; i++) { if(p->next[s[i] -'a'] != NULL) p = p->next[s[i] -'a']; } if(p->flag) { p->flag =0; tmp--; } } void change(char s[]) { int len, i; len = strlen(s); for(i =0; i < len; i++) if(s[i] >='A'&& s[i] <='Z') s[i] +=32; } int main() { int n, m; char s[11]; Node *root; while(scanf("%d", &n),n) { tmp = n; scanf("%d", &m); root = NewNode(); while(n--) { scanf("%s", s); change(s); insert(root, s); } while(m--) { scanf("%s", s); change(s); search(root, s); } printf("%d\n", tmp); } return0; }
这是一个典型的Trie树程序，AC的结果是：
| 160138 | vongang | Accepted | 50376K | 312MS |
显然，memory很变态！
从上边程序可以看到。root 在while(scanf("%d", &n),n)里边初始化，当一次while(scanf("%d", &n),n)执行完以后，第二次又会给root重新分配空间。这样，原来分配的空间就没有用处了，于是，我们可以在一次程序执行完以后，将root的空间free掉。当然不是简单的free(root)，这里需要一个del（）函数，代码如下：
void del(Node * p) { int i; if(p) //p不为空 { for(i =0; i <26; i++) if(p->next[i]) del(p->next[i]); //递归删除每一个p->next[] } free(p); p = NULL; }
在while(scanf("%d", &n),n){}的最后调用del()函数可以大大减小内存消耗， AC结果：
| 160137 | vongang | Accepted | 12680K | 500MS |
memory从5W缩小到1W多，当然，时间有所增加，这也算是del()函数的一点缺陷吧。另为，此方法只适用于动态分配存储空间！
作者：VonGang
转载请注明：http://www.cnblogs.com/vongang/