哈夫曼编码译码器数据结构C语言

1、一、需求分析目前，进行快速远距离通信的主要手段是电报，即将需传送的文字转化成由二级制的字符组成的字符串。例如，假设需传送的电文为“ABACCDA”，它只有4种字符，只需两个字符的串，便可以分辨。假设A、B、C、D、的编码分别为00,01,10和11，则上述7个字符的电文便为“”，总长14位，对方接受时，可按二位一分进行译码。当然，在传送电文时，希望总长尽可能地短。如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。如果设计A、B、C、D的编码分别为0,00,1,01，则上述7个字符的电文可转换成总长为9的字符串“000011010”。但是

2、，这样的电文无法翻译，例如传送过去的字符串中前4个字符的字串“0000”就可以有很多种译法，或是“AAAA”或者“BB”，或者“ABA”等。因此，若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称作前缀编码。然而，如何进行前缀编码就是利用哈夫曼树来做，也就有了现在的哈夫曼编码和译码。二、概要设计利用哈夫曼树编/译码（一）、建立哈夫曼树（二）、对哈夫曼树进行编码（三）、输出对应字符的编码（四）、译码过程主要代码实现：struct code/结构体的定义char a;int w;int parent;int lchild;int rchild;void crea

3、tion(code *p,int n,int m);/建立哈夫曼树void coding(code *p,int n);/编码void display(code *p,int n,int m);/输出函数void translate(char *hc,code *p,int n);/译码三、 详细设计10序号：7653124（1） 、建立哈夫曼树ab*c*d*字符：*c646dbaab*c*10634321权值：33333ab*122112图3-2图3-3图3-1从叶子到根逆向求编码（2） 、对哈夫曼树进行编码主要代码实现：for(c=i,f=pi.parent;f!=0;c=f,f=pf.p

4、arent)1ab*c*d*if(pf.lchild=c)/左孩子编码为'0'10cd-start='0'01else/右孩子编码为'1'图3-4cd-start='1'（3） 、输出对应字符的码字符编码a110b111c10d表3-10（4） 、译码过程主要代码实现：if(strcmp(a,hci)=0)/比较两个字符串是否相等，相等则输出0for(c=2*n-1,j=0;aj!='0'j+)/从根出发，按字符'0'或'1'确定找左孩子或右孩子从跟到叶子顺向求字符if(aj=

5、9;0')/左孩子ab*c*d*10c=pc.lchild;10else10c=pc.rchild;/右孩子图3-5四、 调试分析（一）、数字的输入判断图4-1（二）、字母的输入判断图4-2（三）、程序是否继续进行的判断图4-3五、 用户手册（1） 、首先根据提示输入初始化数据，提示输入一个数字，请输入一个数a，0<a<9999；提示输入一个字母，则请输入一个字母（az)或者(AZ)中的一个字符；请勿在输入一个数字后再输入一个字符，或者在输入一个字符后再输入一个数字。（2） 在某一界面结束后，会有“请按回车继续下面操作”提示，请按提示进行操作，如输入其他数字则无效，知道输入

6、回车符界面才会跳转。（3） 对界面的操作可以自行选择，在询问是否译码的时候，请按要求进行选择，在一次译码结束后会询问是否继续译码，如需要则输入y或者Y，输入其他字符则退出程序。六、测试结果图6-1（一）、初始化（二）、建立哈夫曼树图6-2（三）、哈夫曼编码图6-3（四）、哈夫曼译码图6-4（五）、错误判定图6-5附录：源代码：#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>struct code/结构体的定义char a;int w;int parent

7、;int lchild;int rchild;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");while(scanf("%d",&

8、n)!=1|n<0|n>9999)printf("重新输入：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",&hti.a);while(!(hti.a>'a'|hti.a<'

9、;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>9999)printf("重新输入：n");fflush(stdin);/清空输入

10、缓冲区，往往是确保不影响后面数据的读取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();system("cls");display(ht,n,m);printf("请按回车进入编码对应界面n&q

11、uot;);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+;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(h

12、tj.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+)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的权值是找

13、到的两个值的权值之和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=(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=

14、c)/左孩子编码为'0'cd-start='0'else/右孩子编码为'1'cd-start='1'hci=(char*)malloc(n-start)*sizeof(char);/为第i个字符编码分配空间strcpy(hci,&cdstart);/从cd复制编码（串）到hc,&是取地址符，即取首地址，从start位置到'0'的编码为止。free(cd);/释放工作空间printf("n输出编码后的结果：n");printf("符号数码n");for(i=1;

15、i<=n;i+)printf("n%c%sn",pi.a,hci);printf("是否进行译码操作，是则译码，否则退出程序！n是（输入y/Y）否（输入其他字符）n");scanf("%d",&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(

16、"%s",a);/回车之后会自动生成'0'for(i=1;i<=n;i+)if(strcmp(a,hci)=0)/比较两个字符串是否相等，相等则输出0for(c=2*n-1,j=0;aj!='0'j+)/从根出发，按字符'0'或'1'确定找左孩子或右孩子if(aj='0')/左孩子c=pc.lchild;elsec=pc.rchild;/右孩子printf("字符是：n");printf("%cn",pc.a);break;if(i>n)pri

17、ntf("编码不存在对应的字符！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);设计体会通过这个课程设计，让我对数据结构这门课程有了更深一步