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