实验报告学院：专业：班级：姓名：学号：实验日期：实验名称：实验一：唯一可译码判别准则的代码实现实验二：霍夫曼编码的代码实现实验目的：实验一：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<stdio.h>#include<string.h>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<sum;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<sum;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<N;i++){scanf("%s",&c[i]);}for(i=0;i<N-1;i++)for(j=i+1;j<N;j++){if(strcmp(c[i],c[j])==0){flag=1;break;}}if(flag==1){printf(" 这不是唯一可译码。
\n");}else{for(i=0;i<N-1;i++){for(j=i+1;j<N;j++){patterson(c[i],c[j]);}}for(i=0;;i++){int s=0;for(j=0;j<N;j++){if(i==sum){ s=1;break;}elsepatterson(f[i],c[j]);}if(s==1)break;}for(i=0;i<sum;i++){for(j=0;j<N;j++){if(strcmp(f[i],c[j])==0){flag=1;break;}}}if(flag==1){printf(" 这不是唯一可译码！\n");}elseprintf(" 这是唯一可译码！\n");}}void main(){int flag=1;while(flag){yima();printf(" 是否继续判别？1/0\n");scanf("%d",&flag);}}实验二源代码：#include<stdio.h>#include<stdlib.h>#define N 50#define maxval 10000.0#define maxsize 100typedef struct{char ch;float weight;int lchild,rchild,parent;}hufmtree;typedef struct{char bits[N]; //位串int start; //编码在位串中的起始位置char ch; //字符}codetype;void huffman(hufmtree tree[]);void huffmancode(codetype code[],hufmtree tree[]); int n;int m;void main(){int i,j;printf(" 输入信源符号个数\n");scanf("%d",&n);getchar();m = 2*n-1;hufmtree tree[2*N-1];codetype code[N];huffman(tree);huffmancode(code,tree);printf(" 输出每个字符的哈夫曼编码\n");for(i=0;i<n;i++){printf("%c: ",code[i].ch);for(j=code[i].start;j<n;j++)printf("%c ",code[i].bits[j]);printf("\n");}system("pause");}void huffman(hufmtree tree[]){int i,j,p1,p2;float small1,small2,f;char c;for(i=0;i<m;i++){tree[i].parent=0;tree[i].lchild=-1;tree[i].rchild=-1;tree[i].weight=0.0;}printf(" 依次读入前%d 个结点的字符及权值(空格隔开)\n",n);for(i=0;i<n;i++){printf(" 输入第%d 个字符为和权值",i+1);scanf("%c %f",&c,&f);getchar();tree[i].ch=c;tree[i].weight=f;}for(i=n;i<m;i++){p1=0;p2=0;small1=maxval;small2=maxval;for(j=0;j<i;j++)if(tree[j].parent==0)if(tree[j].weight<small1){small2=small1;small1=tree[j].weight;p2=p1;p1=j;}elseif(tree[j].weight<small2){small2=tree[j].weight;p2=j;}tree[p1].parent=i;tree[p2].parent=i;tree[i].lchild=p1;tree[i].rchild=p2;tree[i].weight=tree[p1].weight+tree[p2].weight;}}void huffmancode(codetype code[],hufmtree tree[]){int i,c,p;codetype cd;for(i=0;i<n;i++){cd.start=n;cd.ch=tree[i].ch;c=i;p=tree[i].parent;while(p!=0){cd.start--;if(tree[p].lchild==c)cd.bits[cd.start]='0';elsecd.bits[cd.start]='1';c=p;p=tree[p].parent;}code[i]=cd;}}实验一运行结果图：实验二运行结果图：实验结果与分析：实验一：由运行结果可知完成了对唯一可译码判别准则的实现实验二：由运行结果可知完成了对霍夫曼编码的实现。