Posted on 2010-11-05 17:12
李東亮 閱讀(1295)
評論(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;
}