The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 1056-IMMEDIATE DECODABILITY 解题报告

很久不做题目了 今天重新开始做 还颇费了一些时间 呵呵
原题链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1056




其实这道题 就是哈弗曼编码的问题 标准的做法是用树结构来模拟实现,与字典树的方法还有些神似。首先建立一个深度足够的满二叉树,然后按照长度由长到短的顺序,往里面添加路径(一边添加一边检查是不是前缀码),即0,往左走,1,往右走,把走过的所有位置都标记上,如果在走过的路径中有未标记过的点,那么它就肯定不是前缀码,否则是前缀码,判断完成后,输出相应的文字即可。


#include<iostream>
#include
<cmath>
#include
<cstring>
using namespace std;


struct node2
{
    
char data[100];
    
}
a[100];


int cmp(const void *a,const void *b)
{
    
struct node2 *c=(node2*)a;
    
struct node2 *d=(node2*)b;
    
return -(strlen(c->data)-strlen(d->data));
    
}





struct node 
{
    
bool flag;
    node 
*lchild;
    node 
*rchild;
}
;

void create(node *&p,int n)
{
    
if(n==0)
    
{
        p
=NULL;
        
return;
    }

    
else 
    
{
        
        p
=new node;
        p
->flag=false;
        p
->lchild=NULL;
        p
->rchild=NULL;
        create(p
->lchild,n-1);
        create(p
->rchild,n-1);
    }

}



bool search(char a[],node *tree)//返回true表示是前缀
{


    
int len=strlen(a);
    
int i;
    node 
*p=tree;
    
bool result=true;
    
for(i=0;i<len;i++)
    
{
        
if(a[i]-'0'==0)
        
{
            p
=p->lchild;
            
if(p->flag==false)
                result
=false;
            p
->flag=true;
        }

        
else if(a[i]-'0'==1)
        
{
            p
=p->rchild;
            
if(p->flag==false)
                result
=false;
            p
->flag=true;

        }

    }

    
return result;
}




int main()
{

    
int i;
    
int n;
    
int maxlen;
    
bool result=false;
    node 
*tree=NULL;
    
int casenum=0;
    
char temp[100];
    
while(scanf("%s",temp)!=EOF)
    
{
        casenum
++;
        tree
=NULL;
        maxlen
=0;
        n
=0;
        result
=false;
        
if(temp[0]!='9')
        
{
            strcpy(a[
1].data,temp);

            
if(strlen(a[1].data)>maxlen)
                maxlen
=strlen(a[1].data);
        }

        
for(i=2;;i++)
        
{


            scanf(
"%s",a[i].data);
            
if(a[i].data[0]=='9')
            
{
                n
=i-1;
                
break;
            }

            
if(strlen(a[i].data)>=maxlen)
                maxlen
=strlen(a[i].data);
        }

        qsort(a
+1,n,sizeof(a[0]),cmp);


        create(tree,maxlen
+1);
        
for(i=1;i<=n;i++)
        
{
            
if(search(a[i].data,tree)==true)
            
{
                result
=true;
            }

        }

        
if(result==true)
            printf(
"Set %d is not immediately decodable\n",casenum);
        
else 
            printf(
"Set %d is immediately decodable\n",casenum);
    }

    
return 0;

}








posted on 2009-07-06 13:42 abilitytao 阅读(996) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理