Posted on 2010-11-05 17:12
李東亮 閱讀(1293)
評論(0) 編輯 收藏 引用 所屬分類:
acm
ZOJ 1808 Immediate
Decodability
這道題給出n個有1和0組成的字符串集合，然后要求判斷是否有某一個字符串是另一個字符串的前綴。是字典樹的典型應(yīng)用。
字典樹有靜態(tài)和動態(tài)之分，動態(tài)字典樹就是在插入時根據(jù)需要動態(tài)malloc節(jié)點，而靜態(tài)字典樹則是事先開辟一個較大的數(shù)組，然后設(shè)置一個變量index指向當(dāng)前數(shù)組中未被占用的節(jié)點下標(biāo)的最小值，即下一個可用節(jié)點的下標(biāo)。跟C語言中實現(xiàn)靜態(tài)鏈表類似。這兩種方法各有優(yōu)劣，動態(tài)字典樹理論上可以插入任意多個節(jié)點，但是每次的malloc及最后的free會消耗很多時間。而靜態(tài)字典樹省去了內(nèi)存的動態(tài)申請和釋放，節(jié)省了時間，但是可以插入節(jié)點數(shù)目受到事先開辟的數(shù)組大小限制，可擴展性較差。具體采用哪種實現(xiàn)方式根據(jù)需求而定。就本題而言時間要求1s，可以初步需要插入的判斷節(jié)點數(shù)目不會太多，因此為了提高運行速度采用了靜態(tài)字典樹。
參考代碼如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct dick
{
/*左右孩子指針，指向左右孩子在數(shù)組中的下標(biāo)，做孩子為0，右孩子為1*/
int child[2];
/*是否是字符串的最后一個字符*/
int leaf;
};
/*從該數(shù)組中分配節(jié)點*/
struct dick d[1000];
/*指向下個可用節(jié)點的下標(biāo)*/
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);
}
/*清理和初始化數(shù)據(jù)*/
flag = 1;
memset(d, 0, sizeof(d));
index = 0;
}
else if (flag == 1)
{
i = 0;
start = 0;
test = 1;
/*逐字符插入數(shù)據(jù)到字典樹中*/
while (buf[i] != '\0')
{
if (d[start].child[buf[i]-'0'] == 0)
{
if (d[start].leaf == 1)
{
break;/*發(fā)現(xiàn)已插入字符串是本字符串的前綴*/
}
/*分配新的節(jié)點*/
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;
}