ZOJ 1808 Immediate Decodability

Posted on 2010-11-05 17:12 李东亮 阅读(1272) 评论(0)  编辑 收藏 引用 所属分类: acm
 

ZOJ 1808 Immediate Decodability

       这道题给出n个有10组成的字符串集合,然后要求判断是否有某一个字符串是另一个字符串的前缀。是字典树的典型应用。

       字典树有静态和动态之分,动态字典树就是在插入时根据需要动态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, 
0sizeof(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, 
0sizeof(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;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


posts - 12, comments - 1, trackbacks - 0, articles - 1

Copyright © 李东亮