trie树是一种字典树,用来保存单词或者数字,通常用来作为判断一组单词中是否存在有前缀单词的手段, 运用trie树关键在于初始化和清空原来的数据,如何做到省时是关键,技巧掌握好就行了。
题目 poj 1056 3630
3630代码:
//这个memset的作用是将前面(这个前面指的是前面的测试案例,不是指当前的测试案例)
//的地址清空。例如之前的案例中有个12345,目前要插入123,如果不清空3后面的地址,
//那么当前的字典树就会自动认为存在一个12345的电话号码。慢慢理解。。
memset(a[location-1].next,0,sizeof(a[location-1].next));
}
else if(temp_r->next[temp]->type==2)//这个字串已经出现过 并且是某个电话号码的结尾。那么
{ //之前的电话号码就是目前这个电话号码的前缀,也就是第2种
// 情况
return false;
}
temp_r=temp_r->next[temp];
s++;
}
if(flag) //这个电话号码不是别的电话号码的前缀或者有其他的是他的前缀
{
temp_r->type=2; //那么在保存他最后一个数字的地方标记为2.表示这里是某个电话号码的结尾
//这样做的目的就是为之后能判断是否存在第2种情况。
return true;
}
return false;
}
int main()
{
int t,n,i;
char phone_number[11]; //定义一个用于保存电话号码的字符串
bool flag;
scanf("%d",&t);
while(t--)
{
flag=true; //注意这个flag的作用,后面将说到
init(); //每组测试数据都需要先清空之前的链表
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",phone_number);
//flag的作用就是当还没有出现电话号码有前缀的情况就需要判断,如果
//已经存在了前缀的电话号码情况,那么后面所有的都不用判断了,因为已经
//无法呼叫到任何一个人了。这是所谓的"剪枝"
if(flag)
{
//在字典树插入这个电话号码并判断他是否是其他电话号码的前缀
//或者是之前有电话号码是他的前缀
if(!insert(phone_number))//进入插入并判断的函数体
flag=false;
}
}
if(flag)
puts("YES");
else
puts("NO");
}
return 0;
}