实验报告
学院：专业：班级：
姓名：学号：实验日期：
实验名称：
实验一：唯一可译码判别准则的代码实现
实验二：霍夫曼编码的代码实现
实验目的：
实验一：
1.进一步熟悉唯一可译码判别准则；
2.掌握C 语言字符串处理程序的设计和调试技术。
实验二：
1.进一步熟悉Huffman 编码过程；
2.掌握C 语言递归程序的设计和调试技术。
实验仪器：
装有visual studio 2010 的电脑一台
实验原理：
实验一：
根据唯一可译码的判别方法，利用数据结构所学的知识，定义字符串数据类型并利用指针进行编程来实现算法。
算法：1、考察 C 中所有的码字，若Wi 是Wj 的前缀，则将对应的后缀作为一个尾随后缀码放入集合Fi+1 中；
2、考察C 和Fi 俩个集合，若Wi ∈C 是Wj∈F 的前缀或Wi ∈F 是Wj∈C 的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1 中；
3、F=∪Fi 即为码C 的尾随后缀集合；
4、若F 中出现了C 中的元素，算法终止，返回假（C 不是唯一可译码）；否
则若F 中没有出现新的元素，则返回真。
实验二：
1.将q 个信源符合按概率大小递减排列;
2.用“0,1”码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含q-1 个符号的新信源，称为缩减信源s 1；
3.把缩减信源s1的符号仍按概率大小递减次序排列，再将其最后两个概率最小的信源符号分别用“0”和“1”码符号表示，并且合并成一个符号，这样又形成了q-2 个信源符号的缩减信源s 2；
4.依次继续下去，直至信源符号最后只剩下两个信源符号为止，将这最后两个信源符号分别用二元码符号“0”和“1”表示；
5.然后从最后一级缩减信源开始，进行回溯，就得到各信源符号所对应的码符号序列，即对应的码字。
实验内容与步骤：
实验一：
1.已知：信源符号数和码字集合C；
2.输入：任意的一个码，码字的个数和每个具体的码字在运行时从键盘输入；
3.输出：判决（是唯一可译码/不是唯一可译码）；循环（若继续判决则输入1 循环判决，否则输入0 结束运行）。
实验二：
1. 输入：信源符号个数r、信源的概率分布P；
2. 输出：每个信源符号对应的Huffman 编码的码字。
实验数据：
实验一源代码：
#include
#include
char c[100][50];
char f[300][50];
int N,sum=0;
int flag;
void patterson(char c[],char d[])
{
int i,j,k;
for(i=0;;i++)
{
if(c[i]=='\0'&&d[i]=='\0')
break;
if(c[i]=='\0')
{
for(j=i;d[j]!='\0';j++) f[sum][j-i]=d[j];
f[sum][j-i]='\0';
for(k=0;k{
if(strcmp(f[sum],f[k])==0)
{
sum--;break;
}
}
sum++;
break;
}
if(d[i]=='\0')
{
for(j=i;c[j]!='\0';j++) f[sum][j-i]=c[j];
f[sum][j-i]='\0';
for(k=0;k{
if(strcmp(f[sum],f[k])==0)
{
sum--;break;
}
}
sum++;
break;
}
if(c[i]!=d[i])
break;
}
}
void yima()
{
int i,j;
printf(" 请输入码字的个数:");
scanf("%d",&N);
flag=0;
printf(" 请分别输入码字:\n");
for(i=0;i{
scanf("%s",&c[i]);
}
for(i=0;ifor(j=i+1;j{
if(strcmp(c[i],c[j])==0)
{flag=1;break;}
}
if(flag==1)
{
printf(" 这不是唯一可译码。\n");
}
else
{
for(i=0;i{
for(j=i+1;j{
patterson(c[i],c[j]);
}
}
for(i=0;;i++)
{
int s=0;
for(j=0;j{
if(i==sum)
{ s=1;break;}
else
patterson(f[i],c[j]);
}
if(s==1)break;
}
for(i=0;i{
for(j=0;j{
if(strcmp(f[i],c[j])==0)
{
flag=1;
break;
}
}
}
