哈夫曼编码译码器系统

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

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

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

4、以下报文的编 码和译码：“ THIS PROGRAM IS MY FAVORITE字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161(二)系统模块结构设计通过对系统功能的分析，哈夫曼编码/译码器系统功能如图1所示图1哈夫曼编码/译码器系统功能图通过上图的功能分析，把整个系统划分为5个模块：1、 初始化(Initialization)，该模块主要实现：初始化要编辑的语句，然 后语句里面有个调用输入编码的语句len=I nputCode();2、 编码(En codi ng)，该模

5、块主要实现：void En cod in g();3、译码(In codi ng)，该模块主要实现：void Decod in g();4、印代码文件(Print )，该模块主要实现：由函数 void Code_printing()5 、印哈夫曼树( TreePrinting )，该模块主要实现： coprint(p,HT);三、系统的设计与实现)，该模块主要实现(一) 初始化( Initialization void Initialization() int a,k,flag,len;a=0; len=InputCode(); for(i=0;i<len;i+) k=0;flag=1;

6、 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-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.c

7、ount;(二) 编码( Encoding )，该模块主要实现void Encoding()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)!n");printf(&q

8、uot; 字符错误，无法编码 break;(三) 译码( Decoding )，该模块主要实现void Decoding() char *work,*work2,i2;int i4=0,i,i3;unsigned long length=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.lchil

9、d=0) *(work2+i4)=*(z+i3-1);i4+;i3=2*n-1;i-;else if(i2='0')i3=HTi3.lchild;else if(i2='1')i3=HTi3.rchild;(四) 印代码文件( Print )，该模块主要实现void Code_printing1() char *work5; work5=(char*)malloc(51*sizeof(char); doif(fgets(work5,51,txtfile)=NULL)printf(" 不能读取文件 n"); break;fputs(work5,

10、CodePrin1); puts(work5);while(strlen(work5)=50); free(work5);(五) 印哈夫曼树( TreePrinting )，该模块主要实现void Tree_printing(HuffmanTree HT,int w)HuffmanTree p; p=HT+w;printf(" 下面打印哈夫曼树 n");coprint(p,HT);printf(" 打印工作结束 n");四、系统测试(一) 测试 main 函数（二）测试编码（Encoding ）及译码（Decoding）函数欢迎使用哈夫曼编码译码系统3&

11、#171;K>e3<XaT3<>t3<i<iMXKa<a<W：M：M3<：M：iM 3<X>EK：M NJCaiEMZJCKKXaCMiMXXatKXaCMiMKXK请先初始化哈夫曼错表“输入,"B纟遷呈皐丞玉文件中的字符进彳丁编码编码写入目录下的皿吐£ ile . txt科轉耳KK强島科科曲科料M科XX养拆耳养其當酬科斡弭利贰轉萍贰舄苑算用MX科用轉梵KK常詐 欢迎使用哈夫号编码铎码系统耳Kd吐田e?Me3（Jt JCJtJt JHMTt-Jt-lt-M JtTLMHiOHeiHHCM! JtJtJCXML

12、NJHX jcmjckbljc* i.初始化* 4印代福二霍哈夫曼番耳逋）fXWW 耳耳KFMKKi（賈：M覺：KMMKitFK爼耳i（麓托垃疋耳逋耳炖算賊址耳梵恒耳xxiticmc请先初始化哈夫曩铀表亠输A/十dK面对根目录下文件coil蛀ile . txt中的字符进行译码摆码完成丄，,內客写入根目录下的文件St晝i X -1M中（二）测试印代码文件（Print ）函数欢迎使用哈夫曼編码译码系统4E-KKM:躱着涯贰算耗算耳贰算洼贰耳科XXKX科X>t科）tx轉（科具耳常）tx弭（科具耳常具科弭请先初始化哈夫曼储表-输入,:r下面打印根目录下文件CodeFrin , t xt中编码字苻

13、10001110910011010310111010001011111130000111103110 pi019811319010L1991111L0L000100110011101103001110 0B11O1打印工作结束F面打印棍目录下文件txtPll. txt中译码字符THIS PROGFEME IS MV PAUORATE打印工作结束（四）相关的根目录MCodePi-ini -记事本文件阴 编辑（D 格式® 査看（V）帮助（H）THIS PROGRAME IS MY FAVORATE艮悴Fl （E）栏比（0）疋看划awocilOOOlllOOLOOlLOlOOlDinMOD

14、OlDLlLlllOOODOllLlOOllOlOLOlOOllOlOClOUOOLllLlOlOOCiajllOClllMlDOOOllLOOairi五、总结系统完成的功能：本程序完成的功能是可以在信息发送端通过一个编码系统对待传数据预先编码，在信息接收端将传来的数据进行译码（复原）。系统的不足：本次课程设计，我认为还有很多不足，比如说不能把一个随机 输入的字符串中不同字符作为叶子结点元素，把其在该字符串中出现的次数作为权值构造一个赫夫曼树，并得到各个叶子结点的赫夫曼编码和整个输入的字符串 的赫夫曼编码，还有不能够顺利按题目要求写出相应的文件，将编码存储在tex文件中。我的收获是：通过本次实

15、验，提高了自已调试程序的能力，充分体会到了在程序执行时的提示性输出的重要性，编写程序的时候，应先写出算法，再写程序,一段一段调试；此外，学编程一定要亲自动手，实践是检验真理正确性的唯一标准，不能眼高手低，还要学会归纳，发现编程的捷径，想着用更高效的方法去完 成一个个任务。六、附件(代码、部分图表)#include<stdio.h>#include <string.h>#include <malloc.h>#include <stdlib.h> const int UINT_MAX=1000;char str50; typedef structin

16、t weight,K;int parent,lchild,rchild;HTNode,* HuffmanTree; typedef char *HuffmanCode;HuffmanTree HT; HuffmanCode HC;int w50,i,j,n; char z50;int flag=0;int numb=0; struct cou char data;int count;cou50;int min(HuffmanTree t,int i)int j,flag;int k=UINT_MAX; for(j=1;j<=i;j+) if(tj.weight<k&&

17、;tj.parent=0) k=tj.weight,flag=j;tflag.parent=1; return flag;void select(HuffmanTree t,int i,int &s1,int &s2) int j; s1=min(t,i);s2=min(t,i);if(s1>s2)j=s1;s1=s2;s2=j;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)int m,i,s1,s2,start;int c,f;HuffmanTree p;char *cd;

18、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(i=n+1;i<=m;+i) select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; H

19、Ti.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.lchild=c)cd-start='0'elsecd-start='1'HCi=(char*)malloc(n-start)*sizeof(char);

20、 strcpy(HCi,&cdstart);free(cd);int InputCode()FILE *tobetran;if(tobetran=fopen("tobetran.txt","w")=NULL)printf(" 不能打开文件 n");return 0;printf(" 请输入你想要编码的字符 n");gets(str);fputs(str,tobetran);printf(" 获取报文成功 n");fclose(tobetran);return strlen(str);vo

21、id Initialization() int a,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-a.count;n=len-a;for(i=0;i<n;i+)printf("%d%d ",i,coui.data); pri

22、ntf("%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;char r=' ','0'if(htmTree=fopen("htmTree.txt"

23、;,"w")=NULL)printf("can not open filen");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(" 已将字符与对应编码写入根目录下文件htmTree.txt 中 nn");void Encodi

24、ng()printf(" 下面对目录下文件 tobetran.txt 中的字符进行编码 n");FILE *tobetran,*codefile; if(tobetran=fopen("tobetran.txt","rb")=NULL) printf(" 不能打开文件 n"); if(codefile=fopen("codefile.txt","wb")=NULL)printf(" 不能打开文件 n");char *tran;i=99; tran=(cha

25、r*)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(" 编码工作完成 nn 编码写入目录下的 codefile.tx

26、t 中 nn"); fclose(tobetran); fclose(codefile); free(tran);void Decoding()printf(" 下面对根目录下文件 codefile.txt 中的字符进行译码 n");FILE *codef,*txtfile; if(txtfile=fopen("txtfile.txt","w")=NULL) printf(" 不能打开文件 n");if (codef=fopen("codefile.txt","r"

27、)=NULL)printf(" 不能打开文件 n");char *work,*work2,i2;int i4=0,i,i3;unsigned long length=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

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

29、Prin.txt 中编码字符 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

30、); do if(fgets(work3,51,codefile)=NULL) printf(" 不能读取文件 n");break; fputs(work3,CodePrin);puts(work3); while(strlen(work3)=50); free(work3);printf(" 打印工作结束 nn");fclose(CodePrin); fclose(codefile);void Code_printing1()printf(" 下面打印根目录下文件 txtfile.txt 中译码字符 n"); FILE * Code

31、Prin1,* txtfile; if(CodePrin1=fopen("CodePrin1.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);void coprint(HuffmanTree start,HuffmanTree HT)if(start!=HT)FILE * TreePrint;if(TreePrint=fopen(&q