Huffman编码实验报告

1、实 验 报 告 书课程名称： 信息论与编码实验 实验名称： 哈夫曼编译码 一、实验目的掌握树的操作实现算法。掌握二叉树的建立，遍历，输出等算法。掌握哈夫曼树的构造算法。二、实验要求（1）实验前编写源程序、准备测试数据。（2）在Turbo C下完成程序的编辑、编译、运行，获得程序结果。如果结果有误，应找出原因，并设法更正之。三、实验算法基本思想描述 根据给定的字符和其中每个字符的频度构造哈夫馒树并输出字符集中每个字符的哈夫曼编码将给定的字符串根据其哈夫曼编码进行编码并进行相应的译码四、实验流程1、初始化，统计文本文件中各字符的个数作为权值,生成哈夫曼树；2、根据符号概率的大小按由大到小顺序对符号

2、进行排序； 3、把概率最小的两个符号组成一个节点；4、重复步骤（2）（3），直到概率和为1；5、从根节点开始到相应于每个符号的“树叶”，概率大的标“0”，概率小的标“1”；6、从根节点开始，对符号进行编码；7、译码时流程逆向进行，从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。五、实验内容编程实现任给n个权值，构造出哈夫曼树，并对各个字符编码。编码：#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>typedef struct /结构体的定义char

3、a; /变量的定义int w;int parent;int lchild;int rchild;code;void creation(code *p,int n,int m); /建立哈夫曼树void coding(code *p,int n);/编码void translate(char *hc,code *p,int n); /译码void display(code *p,int n,int m);/输出函数/主函数void main()int i,n,m;code *ht;printf("字符的数量:n(请输入一个大于0的数字,输入多个数字则按第一个数字运行)n");

4、while(scanf("%d",&n)!=1|n<0|n>9999) /输入的字符的范围是az或AZprintf("重新输入：n");fflush(stdin);m=2*n-1;/哈夫曼树中没有度为1的结点，故含有m=2n-1个结点ht=(code*)malloc(m+1)*sizeof(code);/动态申请内存for(i=1;i<=n;i+)/对1n的数进行初始化printf("输入编码中的字符(请输入一个字母):n");fflush(stdin);scanf("%c",&h

5、ti.a);while(!(hti.a>'a'|hti.a<'z'|hti.a>'A'|hti.a<'Z')printf("重新输入：n");fflush(stdin);scanf("%c",&hti.a);/清空输入缓冲区，往往是确保不影响后面数据的读取printf("输入字符的权值(请输入一个数字):n");while(scanf("%d",&hti.w)!=1|hti.w<0|hti.w>999

6、9) /输入的数字范围09999printf("重新输入：n");fflush(stdin);/清空输入缓冲区，往往是确保不影响后面数据的读取hti.lchild=0;hti.rchild=0;hti.parent=0;for(i=n+1;i<=m;i+)/对n+12n-1的数进行初始化hti.a='*'hti.w=0;hti.lchild=0;hti.rchild=0;hti.parent=0;creation(ht,n,m);printf("请按回车进入哈夫曼树对应界面n");getchar(); /获取字符串getchar()

7、;system("cls");display(ht,n,m);printf("请按回车进入编码对应界面n");getchar();system("cls");coding(ht,n);getchar();void creation(code *ht,int n,int m)int i,j,m1,m2,t1,t2;for(i=n+1;i<=m;i+) /将第一个没有双亲的结点依次和表中的其它值作比较找出第一个最小的数j=1; /找到第一个最小值（双亲不为0）while(htj.parent!=0) /找到表中第一个没有双亲的结点j

8、+;t1=htj.w;m1=j;for(j=m1+1;j<=m;j+)if(htj.parent=0&&htj.w!=0)/条件(htj.w!=0)是因为n2n-1的权值初始值为0if(htj.w<t1) /依次找出比第一个没有双亲结点的值小的数，进行比较交换t1=htj.w;m1=j;htm1.parent=i;/第一个值的双亲为htihti.lchild=m1;/hi的的左孩子是最小值的序号j=1;/剩余中找到第二个最小值（双亲不为0）while(htj.parent!=0)j+;t2=htj.w;m2=j;for(j=m2+1;j<=m;j+) /进行第

9、二次比较，在m2+1m中找出第二个最小值if(htj.parent=0&&htj.w!=0)if(htj.w<t2)t2=htj.w;m2=j;htm2.parent=i;/第二个值的双亲为htihti.rchild=m2;/hi的的左孩子是最小值的序号hti.w=t1+t2;/hi的权值是找到的两个值的权值之和void coding(code *p,int n)int i,c,f;char *hc;/指针的指针char *cd;char ch;int start;hc=(char*)malloc(n+1)*sizeof(char *);/分配n个字符编码的头指针向量cd

10、=(char*)malloc(n*sizeof(char);/分配求编码的工作空间cdn-1='0'/编码结束符for(i=1;i<=n;i+)start=n-1;for(c=i,f=pi.parent;f!=0;c=f,f=pf.parent)/从叶子到根逆向求对应数的编码if(pf.lchild=c)/左孩子编码为'0'cd-start='0'else/右孩子编码为'1'cd-start='1'hci=(char*)malloc(n-start)*sizeof(char);/为第i个字符编码分配空间str

11、cpy(hci,&cdstart);/从cd复制编码（串）到hc,&是取地址符，即取首地址，从start位置到'0'的编码为止。free(cd);/释放工作空间printf("n输出编码后的结果：n");printf("符号数码n");for(i=1;i<=n;i+)printf("n%c%sn",pi.a,hci);译码： printf("是否进行译码操作，是则译码，否则退出程序！n是（输入y/Y）否（输入其他字符）n");scanf("%c",&

12、ch);if(ch='y'|ch='Y')translate(hc,p,n);elseexit(0);void translate(char *hc,code *p,int n)char a10,ch;int i,j,c;doprintf("nnn请输入编码：n");scanf("%s",a);/回车之后会自动生成'0'for(i=1;i<=n;i+)if(strcmp(a,hci)=0)/比较两个字符串是否相等，相等则输出0for(c=2*n-1,j=0;aj!='0'j+)/从根出

13、发，按字符'0'或'1'确定找左孩子或右孩子if(aj='0')/左孩子c=pc.lchild;elsec=pc.rchild;/右孩子printf("字符是：n");printf("%cn",pc.a);break;if(i>n)printf("编码不存在对应的字符！n");printf("是否继续输入?是（输入y或者Y）否(其他）n");fflush(stdin);scanf("%c",&ch);while(ch='y'|ch='Y');void display(code *p,int n,int m)int i;printf("n序号码值权值双亲左孩子右孩子n");for(i=1;i<=m;i+)printf("%d%c%d%d%d%dn",i,pi.a,pi.w,pi.parent,pi.lchild,pi.rchild);六、实验数据记录及分析（包括源程序清单及运行结果）：1、输入界面：2、哈夫曼编码对应界面：3、编码对应界面：4、译码结果：六、实验心得体会 通过本次