很久不做题目了 今天重新开始做 还颇费了一些时间 呵呵
原题链接: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;
}