哈夫曼编码译码器系统

1、目录一、系统开发的背景(1)二、系统分析与设计(1)三、系统的设计与实现(2)(一)设计初始化(Initialization)(2)(二)设计编码(Encoding)(3)(三)设计译码(Decoding)(3)(四)设计印代码文件(Print)(4)(五)设计印哈夫曼树(TreePrinting)(4)四、系统测试(5)(一)测试main函数(5)(二)测试编码(Encoding)及译码(Decoding)函数(5)(三)测试印代码文件(Print)函数(6)(四)测试相关的根目录(6)五、总结(6)六、附件(代码、部分图表)(7)哈夫曼编/译码器系统一、系统开发的背景为了提高信道利用率，缩

2、短信息传输时间，降低传输成本，且在信息发送端通过一个编码系统对待传数据预先编码，在信息接收端将传来的数据进行译码（复原），因此设计哈夫曼编码/译码器系统。二、系统分析与设计（一）系统功能要求：【任务要求】I:初始化（Initialization）。从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。E：编码（Encoding）。利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行

3、译码，结果存入文件TextFile中。P:印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。T:印哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。【测试数据】利用教科书中的数据调试程序。用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THISPROGRAMISMYFAVORITE”。字符ABCDEFGHIJKLM频度1866413223210321154757

4、153220字符NOPQRSTUVWXYZ频度5763151485180238181161(二)系统模块结构设计通过对系统功能的分析，哈夫曼编码/译码器系统功能如图1所示哈夫曼编码/译码器系统图1哈夫曼编码/译码器系统功能图通过上图的功能分析，把整个系统划分为5个模块：1、初始化(Initialization),该模块主要实现：初始化要编辑的语句，然后语句里面有个调用输入编码的语句len=InputCode();2、编码(Encoding),该模块主要实现：voidEncoding。;3、译码(Incoding)，该模块主要实现:voidDecoding。;4、印代码文件(Print)，该模块

5、主要实现：由函数voidCode_printing()和函数voidCode_printing1()实现。5、印哈夫曼树(TreePrinting)，该模块主要实现：coprint(p,HT);三、系统的设计与实现，该模块主要实现(1) 初始化(InitializationvoidInitialization()inta,k,flag,len;a=0;len=InputCode();for(i=0;i<len;i+)k=0;flag=1;coui-a.data=stri;coui-a.count=1;while(i>k)if(stri=strk)a+;flag=0;k+;if(fl

6、ag=0)break;if(flag)for(j=i+1;j<len;j+)if(stri=strj)+coui-a.count;n=len-a;for(i=0;i<n;i+)printf("%d%d",i,coui.data);printf("%d%dn",i,coui.count);for(i=0;i<=n;i+)*(z+i)=coui.data;*(w+i)=coui.count;(2) 编码(Encoding)，该模块主要实现voidEncoding()char*tran;i=99;tran=(char*)malloc(100*

7、sizeof(char);while(i=99)if(fgets(tran,100,tobetran)=NULL)printf("不能打开文件n");break;for(i=0;*(tran+i)!='0'i+)for(j=0;j<=n;j+)if(*(z+j-1)=*(tran+i)fputs(HCj,codefile);if(j>n)!n");printf("字符错误，无法编码break;(3) 译码(Decoding)，该模块主要实现voidDecoding()char*work,*work2,i2;inti4=0,i,

8、i3;unsignedlonglength=10000;work=(char*)malloc(length*sizeof(char);fgets(work,length,codef);work2=(char*)malloc(length*sizeof(char);i3=2*n-1;for(i=0;*(work+i-1)!='0'i+)i2=*(work+i);if(HTi3.lchild=0)*(work2+i4)=*(z+i3-1);i4+;i3=2*n-1;i-;elseif(i2='0')i3=HTi3.lchild;elseif(i2='1

9、9;)i3=HTi3.rchild;(4) 印代码文件(Print)，该模块主要实现voidCode_printing1()char*work5;work5=(char*)malloc(51*sizeof(char);doif(fgets(work5,51,txtfile)=NULL)printf("不能读取文件n");break;fputs(work5,CodePrin1);puts(work5);while(strlen(work5)=50);free(work5);(五)印哈夫曼树(TreePrinting)，该模块主要实现voidTree_printing(Huff

10、manTreeHT,intw)HuffmanTreep;p=HT+w;printf("下面打印哈夫曼树n");coprint(p,HT);printf("打印工作结束n");四、系统测试(一)测试main函数欢迎使用哈夫曼编码译码系统&初始化心、编码d、误码*卜加印代码t.印哈夫曼树外狼出*（二）测试编码（Encoding）及译码（Decoding）函数中的字符进行译码情先初始化哈夫曼链表.输入炉 d怔面对根目录下文件co def i译相完成的容写入根目录下的文件上乂 ti比请先初始化哈夫曼链表,输入r卜面对目录下文件obetran.txt 的字

11、符进行编码欢迎使用哈夫曼编码译码系统欢迎使用哈夫曼编码译码系统算第 JCMWMMMKMbMMMMMMMMMyWMNWMM* * * <* *（二）测试印代码文件（Print）函数*ix初始化、编码d、管码*P、E|3代招十*ER哈夫曼树y*退出*清先初始化哈夫曼链表,输入，卫下面打印根目录下文件CoMPrin.七n巾编码字符1000111061001101001011101000101111110003011110011010101081101081811001111101000100110011101100001110001101打印工作结束下面打印根目录下文件七Ktfile.txt中

12、译码字符THISPROGROMEISMYFAUORATE打印工作结束（四）相关的根目录CodaFrinl-记事本文件审）编辑旧格式©查看器助第ITHISPROGRAMEISMYFAVORATECvieFrin记事本文件UJ调辑也，格式旧直吞曲军助g|10001110010011010010111010001011111100000111100110101010011010010110011111010001001100111Q1W0001U0001101五、总结系统完成的功能：本程序完成的功能是可以在信息发送端通过一个编码系统对待传数据预先编码，在信息接收端将传来的数据进行译码（复原

13、）。系统的不足：本次课程设计，我认为还有很多不足，比如说不能把一个随机输入的字符串中不同字符作为叶子结点元素，把其在该字符串中出现的次数作为权值构造一个赫夫曼树，并得到各个叶子结点的赫夫曼编码和整个输入的字符串的赫夫曼编码，还有不能够顺利按题目要求写出相应的文件，将编码存储在tex文件中。我的收获是：通过本次实验，提高了自已调试程序的能力，充分体会到了在程序执行时的提示性输出的重要性，编写程序的时候，应先写出算法，再写程序,一段一段调试；此外，学编程一定要亲自动手，实践是检验真理正确性的唯一标准，不能眼高手低，还要学会归纳，发现编程的捷径，想着用更高效的方法去完成一个个任务。六、附件（代码、部

14、分图表）#include<stdio.h>#include<string.h>#include<malloc.h>#include<stdlib.h>constintUINT_MAX=1000;charstr50;typedefstructintweight,K;intparent,lchild,rchild;HTNode,*HuffmanTree;typedefchar*HuffmanCode;HuffmanTreeHT;HuffmanCodeHC;intw50,i,j,n;charz50;intflag=0;intnumb=0;structc

15、ouchardata;intcount;cou50;intmin(HuffmanTreet,inti)intj,flag;intk=UINT_MAX;for(j=1;j<=i;j+)if(tj.weight<k&&tj.parent=0)k=tj.weight,flag=j;tflag.parent=1;returnflag;voidselect(HuffmanTreet,inti,int&s1,int&s2)intj;s1=min(t,i);s2=min(t,i);if(s1>s2)j=s1;s1=s2;s2=j;voidHuffmanCod

16、ing(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)intm,i,s1,s2,start;intc,f;HuffmanTreep;char*cd;if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;i<=n;+i,+p,+w)p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;for(;i<=m;+i,+p)p->parent=0;for(

17、i=n+1;i<=m;+i)select(HT,i-1,s1,s2);HTs1.parent=HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(char);cdn-1='0'for(i=1;i<=n;i+)start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lch

18、ild=c)cd-start='0'elsecd-start='1'HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);intInputCode()FILE*tobetran;if(tobetran=fopen("tobetran.txt","w")=NULL)printf("不能打开文件n");return0;printf("请输入你想要编码的字符n");gets(str);fputs(

19、str,tobetran);printf("获取报文成功n");fclose(tobetran);returnstrlen(str);voidInitialization()inta,k,flag,len;a=0;len=InputCode();for(i=0;i<len;i+)k=0;flag=1;coui-a.data=stri;coui-a.count=1;while(i>k)if(stri=strk)a+;flag=0;k+;if(flag=0)break;if(flag)for(j=i+1;j<len;j+)if(stri=strj)+coui-

20、a.count;n=len-a;for(i=0;i<n;i+)printf("%d%d",i,coui.data);printf("%d%dn",i,coui.count);for(i=0;i<=n;i+)*(z+i)=coui.data;*(w+i)=coui.count;HuffmanCoding(HT,HC,w,n);printf("字符对应的编码为:n");for(i=1;i<=n;i+)puts(HCi);printf("下面将哈夫曼编码写入文件nnn");FILE*htmTree;ch

21、arr='','0'if(htmTree=fopen("htmTree.txt","w")=NULL)printf("cannotopenfilen");return;fputs(z,htmTree);for(i=0;i<n+1;i+)fprintf(htmTree,"%6d",*(w+i);fputs(r,htmTree);for(i=1;i<=n;i+)fputs(HCi,htmTree);fputs(r,htmTree);fclose(htmTree);printf

22、("已将字符与对应编码写入根目录下文件htmTree.txt中nn");voidEncoding()printf("下面对目录下文件tobetran.txt中的字符进行编码n");FILE*tobetran,*codefile;if(tobetran=fopen("tobetran.txt","rb")=NULL)printf("不能打开文件n");if(codefile=fopen("codefile.txt","wb")=NULL)printf(&qu

23、ot;不能打开文件n");char*tran;i=99;tran=(char*)malloc(100*sizeof(char);while(i=99)if(fgets(tran,100,tobetran)=NULL)printf("不能打开文件n");break;for(i=0;*(tran+i)!='0'i+)for(j=0;j<=n;j+)if(*(z+j-1)=*(tran+i)fputs(HCj,codefile);if(j>n)printf("字符错误，无法编码!n");break;printf("

24、;编码工作完成nn编码写入目录下的codefile.txt中nn");fclose(tobetran);fclose(codefile);free(tran);voidDecoding()printf("下面对根目录下文件codefile.txt中的字符进行译码n");FILE*codef,*txtfile;if(txtfile=fopen("txtfile.txt","w")=NULL)printf("不能打开文件n");if(codef=fopen("codefile.txt",&

25、quot;r")=NULL)printf("不能打开文件n");char*work,*work2,i2;inti4=0,i,i3;unsignedlonglength=10000;work=(char*)malloc(length*sizeof(char);fgets(work,length,codef);work2=(char*)malloc(length*sizeof(char);i3=2*n-1;for(i=0;*(work+i-1)!='0'i+)i2=*(work+i);if(HTi3.lchild=0)*(work2+i4)=*(z+i

26、3-1);i4+;i3=2*n-1;i-;elseif(i2='0')i3=HTi3.lchild;elseif(i2='1')i3=HTi3.rchild;*(work2+i4)='0'fputs(work2,txtfile);printf("译码完成n内容写入根目录下的文件txtfile.txt中nn");free(work);free(work2);fclose(txtfile);fclose(codef);voidCode_printing()printf("下面打印根目录下文件CodePrin.txt中编码

27、字符n");FILE*CodePrin,*codefile;if(CodePrin=fopen("CodePrin.txt","w")=NULL)printf("不能打开文件n");return;if(codefile=fopen("codefile.txt","r")=NULL)printf("不能打开文件n");return;char*work3;work3=(char*)malloc(51*sizeof(char);doif(fgets(work3,51,co

28、defile)=NULL)printf("不能读取文件n");break;fputs(work3,CodePrin);puts(work3);while(strlen(work3)=50);free(work3);printf("打印工作结束nn");fclose(CodePrin);fclose(codefile);voidCode_printing1()printf("下面打印根目录下文件txtfile.txt中译码字符n");FILE*CodePrin1,*txtfile;if(CodePrin1=fopen("Cod

29、ePrin1.txt","w")=NULL)printf("不能打开文件n");return;if(txtfile=fopen("txtfile.txt","r")=NULL)printf("不能打开文件n");return;char*work5;work5=(char*)malloc(51*sizeof(char);doif(fgets(work5,51,txtfile)=NULL)printf("不能读取文件n");break;fputs(work5,CodePrin1);puts(work5);while(strlen(work5)=50);free(work5);printf("打印工作结束");fclose(CodePrin1);fclose(txtfile);voidcoprint(HuffmanTreestart,HuffmanTreeHT)if(start!=HT)FILE*TreePrint;if(TreePrint=fopen("TreePrint.txt","a")=