信息论与编码实习报告
实验一 唯一可译码判决准则
一、 实验内容
编程实现唯一可译码的判决准则―――Sardinas－Patterson算法 二、实验环境
1. 计算机
2. Windows 2000 或以上 3. VC++ 6.0 三、实验目的
1. 进一步熟悉唯一可译码判决准则； 2. 掌握VC开发环境的使用；
3. 掌握C语言编程（尤其是字符串处理）； 四、实验要求
1. 提前预习实验，认真阅读实验原理。
2. 认真高效的完成实验，实验过程中服从实验室管理人员以及实验指导老
师的管理。 3. 认真填写实验报告。 五、实验原理
1. 唯一可译码判决准则的原理参考书1的153页。 其原理可简介如下：
将源码组C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，便可判断此码C为唯一可译变长码。
2. 算法流程
输入码字集合X W，W∈X for 所有if 码字W是码字W 的前缀， 即将相应的后缀作为一个尾随后缀放入新集合X end if end for for 所有W∈X for 所有W∈ X if W是W 的前缀， 即将相应的后缀作为一个尾随后缀放入新集合X中 else if W是W的前缀， 即将相应的后缀作为一个尾随后缀放入新集合X中 end if end for end for 构造尾随后缀集合X←Xif 有码字W∈X，W∈X，则非唯一可译码 0ji0i j1i0jn－1i jnjini i0i六、实验设计 1、数据结构
本实验所需设计的程序中，码字可用如下结构表示： char c[100][50] 尾随后缀用如下结构表示: char f[300][50]
2、关键算法
本程序的关键算法是用来求尾随后缀的Sardinas－Patterson算法。
其算法流程图如下：
如果 c[i]=d[i]= ’ Y ’/0 N Y
如果c[i]=’/0’,将d的剩余部分放入尾随后缀集合 开始 输入两个要计算尾随后缀的字符i=0 比较c[i]、d[i] N Y
如果d[i]=’/0’,将c的剩余部分放入尾随后缀集合 N 如果 c[i]=d[i] N Y
void patterson(char c[],char d[]) //检测尾随后缀
{
int i,j,k;
for(i=0;;i++)
i++； break {
if(c[i]=='\\0'&&d[i]=='\\0')//2字符串一样，跳出 break;
if(c[i]=='\\0') //d比c长，将d的尾随后缀放入f中 {
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) /*查看当前生成的尾随后缀在f集 合中是否存在*/ { sum--;break; } } sum++; break; } if(d[i]=='\\0') //c比d长，将c的尾随后缀放入f中 { 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) /*查看当前生成的尾随后缀在 f集合中是否存在*/ { sum--;break; } } sum++; break; } if(c[i]!=d[i])//字符不一样了也退出 break; } } 3、函数调用关系图 Main()函数调用void patterson(char c[],char d[])函数。 八、用户手册及总结