Posted on 2010-11-05 17:12
李东亮 阅读(1282)
评论(0) 编辑 收藏 引用 所属分类:
acm
ZOJ 1808 Immediate
Decodability
这道题给出n个有1和0组成的字符串集合，然后要求判断是否有某一个字符串是另一个字符串的前缀。是字典树的典型应用。
字典树有静态和动态之分，动态字典树就是在插入时根据需要动态malloc节点，而静态字典树则是事先开辟一个较大的数组，然后设置一个变量index指向当前数组中未被占用的节点下标的最小值，即下一个可用节点的下标。跟C语言中实现静态链表类似。这两种方法各有优劣，动态字典树理论上可以插入任意多个节点，但是每次的malloc及最后的free会消耗很多时间。而静态字典树省去了内存的动态申请和释放，节省了时间，但是可以插入节点数目受到事先开辟的数组大小限制，可扩展性较差。具体采用哪种实现方式根据需求而定。就本题而言时间要求1s，可以初步需要插入的判断节点数目不会太多，因此为了提高运行速度采用了静态字典树。
参考代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct dick
{
/*左右孩子指针，指向左右孩子在数组中的下标，做孩子为0，右孩子为1*/
int child[2];
/*是否是字符串的最后一个字符*/
int leaf;
};
/*从该数组中分配节点*/
struct dick d[1000];
/*指向下个可用节点的下标*/
int index;
int main(void)
{
char buf[100];
int no = 0;
int flag = 1;
int i;
index = 0;
int start;
int tmp;
int test;
memset(d, 0, sizeof(d));
freopen("in.txt", "r", stdin);
while (gets(buf) != NULL)
{
if (buf[0] == '9' && buf[1] == '\0')
{
++no;
if (flag == 1)
{
printf("Set %d is immediately decodable\n", no);
}
else
{
printf("Set %d is not immediately decodable\n", no);
}
/*清理和初始化数据*/
flag = 1;
memset(d, 0, sizeof(d));
index = 0;
}
else if (flag == 1)
{
i = 0;
start = 0;
test = 1;
/*逐字符插入数据到字典树中*/
while (buf[i] != '\0')
{
if (d[start].child[buf[i]-'0'] == 0)
{
if (d[start].leaf == 1)
{
break;/*发现已插入字符串是本字符串的前缀*/
}
/*分配新的节点*/
d[start].child[buf[i]-'0'] = ++index;
test = 0;
}
tmp = d[start].child[buf[i]-'0'];
if (buf[i+1] == '\0')
{
d[tmp].leaf = 1;
}
start = tmp;
++i;
}
if (test == 1)
{
flag = 0;
}
}
}
return 0;
}