信息论与编码实验报告

1、信息论与编码实验报告学院：计算机与通信工程学院专业：计算机科学与技术班级：计1203班学号：姓名： 2014年12月29日实验一 唯一可译码判别准则实验目的：1.进一步熟悉唯一可译码判别准则；2.掌握C语言字符串处理程序的设计和调试技术。实验内容：1. 已知：信源符号数和码字集合C；2. 输入：任意的一个码，码字的个数和每个具体的码字在运行时从键盘输入；3. 输出：判决（是唯一可译码/不是唯一可译码）；循环（若继续判决则输入1循环判决，否则输入0结束运行）。实验原理：根据唯一可译码的判别方法，利用数据结构所学的知识，定义字符串数据类型并利用指针进行编程来实现算法。 算法：1、考察C 中所有的码

2、字，若Wi是 Wj的前缀，则将对应的后缀作为一个尾随后缀码放入集合Fi+1中；2、考察C和Fi俩个集合，若Wi C是 WjF的前缀或Wi F是 WjC的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1中；3、F=Fi即为码C的尾随后缀集合；4、若F中出现了C中的元素，算法终止，返回假（C不是唯一可译码）；否则若F中没有出现新的元素，则返回真。实验环境及实验文件存档名：1.实验环境：visual C+ 6.0 2.文件名 ：weiyikeyi.cpp实验结果及分析：1.源代码：#include<stdio.h> #include<string.h> char c1005

3、0; char f30050; int N,sum=0; /N为输入码字的个数，sum为尾随后缀集合中码字的个数int flag;/判断是否唯一可译标志位void patterson(char c,char d) /检测尾随后缀int i,j,k; for(i=0;i+) if(ci='0'&&di='0')/2字符串一样，跳出 break;if(ci='0') /d比c长，将d的尾随后缀放入f中 for(j=i;dj!='0'j+) fsumj-i=dj; fsumj-i='0' for(k=0;

4、k<sum;k+) if(strcmp(fsum,fk)=0) /查看当前生成的尾随后缀在f集合中是否存在 sum-;break; sum+; break; if(di='0') /c比d长，将c的尾随后缀放入f中 for(j=i;cj!='0'j+) fsumj-i=cj; fsumj-i='0' for(k=0;k<sum;k+) if(strcmp(fsum,fk)=0) /查看当前生成的尾随后缀在 f集合中是否存在 sum-;break; sum+; break; if(ci!=di)/字符不一样了也退出break; void

5、 yima() int i,j; printf(" *唯一可译码判别*n");printf("请输入码字的个数:");/输入码得个数scanf("%d",&N); while(N>100) printf("输入码字个数过大，请输入小于100的数n"); printf("请输入码字的个数:"); scanf("%d",&N); flag=0; printf("请分别输入码字:n"); for(i=0;i<N;i+) scanf(&

6、quot;%s",&ci); for(i=0;i<N-1;i+)/判断如果码本身是否重复for(j=i+1;j<N;j+) if(strcmp(ci,cj)=0) flag=1;break; if(flag=1)/如果码本身有重复，就可以断定它不是唯一可译码 printf("这不是唯一可译码。n"); else for(i=0;i<N-1;i+) /此处是根据原始编码生成的尾随后缀集合s1放 入f中 for(j=i+1;j<N;j+) patterson(ci,cj); for(i=0;i+) /根据原始码与si生成si+1也放入f

7、i int s=0; for(j=0;j<N;j+)/判断si+1中的字符串是否与si中一样 ， 重复的则不再添加 if(i=sum) s=1;break; else patterson(fi,cj); if(s=1)break; for(i=0;i<sum;i+) /判断p里的字符串是否与s 中重复， 重复则不是唯一的 for(j=0;j<N;j+) if(strcmp(fi,cj)=0) flag=1; break; if(flag=1) printf("这不是唯一可译码！n"); else printf("这是唯一可译码！n");

8、 void main()int flag=1;while(flag)yima();printf("是否继续判别？1/0n");scanf("%d",&flag);2. 运行结果（1） 输入0,01,001时：（2） 继续执行，输入1,01,10,1010（3） 结束执行实验二 霍夫曼编码实验目的：1. 进一步熟悉Huffman编码过程；2. 掌握C语言递归程序的设计和调试技术。实验内容：1. 输入：信源符号个数r、信源的概率分布P；2. 输出：每个信源符号对应的Huffman编码的码字。实验原理：1. 将q个信源符合按概率大小递减排列;2. 用“

9、0,1”码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含q-1个符号的新信源，称为缩减信源；3. 把缩减信源的符号仍按概率大小递减次序排列，再将其最后两个概率最小的信源符号分别用“0”和“1”码符号表示，并且合并成一个符号，这样又形成了q-2个信源符号的缩减信源；4. 依次继续下去，直至信源符号最后只剩下两个信源符号为止，将这最后两个信源符号分别用二元码符号“0”和“1”表示；5. 然后从最后一级缩减信源开始，进行回溯，就得到各信源符号所对应的码符号序列，即对应的码字。实验环境及实验文件存档名：1.实验环境：visual C+ 6.0 2.文件名 ：

10、Huffman.cpp实验结果及分析：1. 程序源代码：#include<stdio.h>#define N 50 #define maxval 10000.0#define maxsize 100 typedef struct char ch; float weight; int lchild,rchild,parent;hufmtree;typedef struct char bitsN; /位串 int start; /编码在位串中的起始位置 char ch; /字符codetype;void huffman(hufmtree tree);/建立哈夫曼树void huffma

11、ncode(codetype code,hufmtree tree);/根据哈夫曼树求出哈夫曼编码int n;int m;void main() printf("输入信源符号个数n");scanf("%d",&n);getchar();m = 2*n-1; printf(" *霍夫曼哈夫曼编码*n"); printf("总共有%d个字符n",n); hufmtree tree2*N-1; codetype codeN; int i,j;/循环变量 huffman(tree);/建立哈夫曼树 huffmanc

12、ode(code,tree);/根据哈夫曼树求出哈夫曼编码 printf("输出每个字符的哈夫曼编码n"); for(i=0;i<n;i+) printf("%c: ",codei.ch); for(j=codei.start;j<n;j+) printf("%c ",codei.bitsj); printf("n"); void huffman(hufmtree tree)/建立哈夫曼树 int i,j,p1,p2;/p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标 float small

13、1,small2,f; char c; for(i=0;i<m;i+) /初始化 treei.parent=0; treei.lchild=-1; treei.rchild=-1; treei.weight=0.0; printf("依次读入前%d个结点的字符及权值(中间用空格隔开)n",n); for(i=0;i<n;i+) /读入前n个结点的字符及权值 printf("输入第%d个字符为和权值",i+1); scanf("%c %f",&c,&f); getchar(); treei.ch=c; tre

14、ei.weight=f; for(i=n;i<m;i+) /进行n-1次合并，产生n-1个新结点 p1=0;p2=0; small1=maxval;small2=maxval; /maxval是float类型的最大值 for(j=0;j<i;j+) /选出两个权值最小的根结点 if(treej.parent=0) if(treej.weight<small1) small2=small1; /改变最小权、次小权及对应的位置 small1=treej.weight; p2=p1; p1=j; else if(treej.weight<small2) small2=tree

15、j.weight; /改变次小权及位置 p2=j; treep1.parent=i; treep2.parent=i; treei.lchild=p1; /最小权根结点是新结点的左孩子 treei.rchild=p2; /次小权根结点是新结点的右孩子 treei.weight=treep1.weight+treep2.weight; /huffmanvoid huffmancode(codetype code,hufmtree tree)/根据哈夫曼树求出哈夫曼编码/codetype code为求出的哈夫曼编码/hufmtree tree为已知的哈夫曼树 int i,c,p; codetype cd; /缓冲变量 for(i=0;i<n;i+) cd.start=n; cd.ch=treei.ch; c=i; /从叶结点出发向上回溯 p=tre