Trie 树缩小内存消耗的小技巧
大家都知道，Trie树（又称字典树）是一种树型数据结构，用于保存大量的字符串。它的优点是：利用字符串的公共前缀来节约存储空间。
相对来说，Trie树是一种比较简单的数据结构，比较易于理解。话说上帝是公平的，简单的东西是要付出相应的代价的！Trie树也有它的缺点，它的内存消耗非常大。下面介绍一个减小内存消耗的小技巧。
我们先看看这个题目：http://acm.sdut.edu.cn/judgeonline/showproblem?problem_id=1500
先看看这段程序：
#include <stdio.h>
#include <string.h>
#include <malloc.h>
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);
}
return 0;
}
这是一个典型的Trie树程序，AC的结果是：
| 160138 | vongang | 1500 | Accepted | 50376K | 312MS | GCC |
显然，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 | 1500 | Accepted | 12680K | 500MS | GCC |
memory从5W缩小到1W多，当然，时间有所增加，这也算是del()函数的一点缺陷吧。另为，此方法只适用于动态分配存储空间！
作者：VonGang
转载请注明：http://www.cnblogs.com/vongang/
推荐.NET配套的通用数据层ORM框架：CYQ.Data 通用数据层框架
"