000.c

判定一个码是否为唯一可译码 1. 已知：信源符号个数为q

//二维数组存放码字集，2表示空
int WetherFront(int C1[],int C2[],int n,int i,int j)//判定C1[i]是否C2[j]前缀，否输出0，是输出相应后缀起始位
{int k;
for(k=0;k<n&&C1[i*n+k]!=2&&C2[j*n+k]!=2;k++)
{if(C1[i*n+k]!=C2[j*n+k])break;};
if(C1[i*n+k]!=2)return 0;
else return k;}

int WetherInclud(int C1[],int C2[],int n)//判定C1、C2中是否有相同元素，有输出1，没有输出0
{int i,j;
for(i=0;i<n;i++)for(j=0;j<n;j++){for(k=0,k<n,k++)if(C1[i*n+k]!=C2[j*n+k])break;if(k==n)return 1;};
return 0;}

int Wether(int C[],int n)//判定是否唯一可译，是输出1，不是输出0
{int C1[n*n+n]={2},C2[n*n+n]={2},i,j,k=0,a,b,r,s=1,t,*A=C1,*B=C2;
for(i=0;i<n;i++)
{for(j=0;j<n;j++)
{if(i==j)continue;
a=WetherFront(C,C,n,i,j);
if(a){for(r=0;a<n;a++,r++)C1[k*n+r]=C[j*n+a];k++};
};};
do
{k=0;if(s%2){A=C1;B=C2;}else{A=C2;B=C1;};//执行次数奇偶性决定用于比较和用于存储的集合
if(WetherInclud(C,A,n))return 0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
a=WetherFront(C,A,n,i,j);b=WetherFront(A,C,n,j,i);
if(a){for(r=0,t=a;t<n;r++,t++)B[k*n+r]=C[i*n+t];k++}
else{if(b){for(r=0,t=a;t<n;r++,t++)B[k*n+r]=C[i*n+t];k++};};
};};
for(;k<n;k++)for(r=0,t=0;t<n;r++,t++)B[r*n+t]=2;
s++;
}while(B[0*n+0]!=2);//后缀码集合不为空
return 1;}

main()
{
int n,i,j,a;char ch;
scanf("%d",&n);
int C[n][n]={2};
for(i=0;i<n;i++)for(j=0;j<n;j++){scanf("%d",&C[i][j]);scanf("%c",&ch);if(ch=='\n')break;};
a=Wether(C,n);
if(a)printf("Yes\n");else printf("No\n");
}