Trie 树内存消耗问题

全栈程序员-用户IM • 2021年5月25日下午12:00 • 未分类

大家都知道，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);

}

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;        

}