很久不做題目了 今天重新開始做 還頗費了一些時間 呵呵
原題鏈接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1056
其實這道題 就是哈弗曼編碼的問題 標(biāo)準(zhǔn)的做法是用樹結(jié)構(gòu)來模擬實現(xiàn)，與字典樹的方法還有些神似。首先建立一個深度足夠的滿二叉樹，然后按照長度由長到短的順序，往里面添加路徑（一邊添加一邊檢查是不是前綴碼），即0，往左走，1，往右走，把走過的所有位置都標(biāo)記上，如果在走過的路徑中有未標(biāo)記過的點，那么它就肯定不是前綴碼，否則是前綴碼，判斷完成后，輸出相應(yīng)的文字即可。
#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;
}