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
", tmp);
    }
    return0;
}

   

    这是一个典型的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/