HDU 1671 简单字典树+内存清理

先说一下题意  给你一些电话号码  如果有电话号的前缀和其他电话号码相同输出NO   否则输出YES   此题输入数据为T组  每组n个电话  你《=10000   

按正常字典树做会超内存      所以得用内存清理函数

int clear(node *s)
{
for(int i=0;i<=9;i++)
if(s->next[i]!=NULL)
{
clear(s->next[i]);
}
free(s);
return 0;
}

s传进来是根的地址

 

贴一下AC的代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
using namespace std;


struct node
{
struct node *next[10];
int tt;
};
struct node *root;
int flash;
int add(char str[])
{
struct node *s,*ne;
//printf("%s\n",str);
int i,j;
s=root;
int len=strlen(str);
for(i=0;i<len;i++)
{
if(s->next[str[i]-'0']!=NULL)
{
s=s->next[str[i]-'0'];
}
else
{
ne=(struct node*)malloc(sizeof(struct node));
memset(ne,NULL,sizeof(struct node));
s->next[str[i]-'0']=ne;
s=ne;
}
}
s->tt=1;
return 0;
}
int find(char str[],int a)
{
int len=strlen(str),i,j;
struct node *s;
s=root;
for(i=0;i<len;i++)
{
if(s->next[str[i]-'0']!=NULL)
{
s=s->next[str[i]-'0'];
}
else return 0;
}
if(a) flash=1;
if(s->tt==1) flash=1;
return 0;
}
int clear(node *s)
{
for(int i=0;i<=9;i++)
if(s->next[i]!=NULL)
{
clear(s->next[i]);
}
free(s);
return 0;
}
int main()
{
int T,i,j,n;
char str[10010][15];
scanf("%d",&T);
while(T--)
{
root=(struct node*)malloc(sizeof(struct node));
memset(root,NULL,sizeof(struct node));
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%s",str[i]);
}
//for(i=1;i<=n;i++)
//printf("%s\n",str[i]);
flash=0;
int len;
char str1[12];
for(i=1;i<=n;i++)
{
if(flash) break;
len=strlen(str[i]);
for(j=0;j<len;j++)
{
str1[j]=str[i][j];
str1[j+1]='\0';
if(j!=len-1) find(str1,0);
else find(str1,1);
}
add(str[i]);
}
if(flash) printf("NO\n");
else printf("YES\n");
clear(root);
}
return 0;
}