哈夫曼编码译码器系统

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

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

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

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

5、模块主要实现：void Encoding(); 3、译码（Incoding）,该模块主要实现： void Decoding(); 4、印代码文件（Print），该模块主要实现：由函数void Code_printing()和函数void Code_printing1()实现。 5、印哈夫曼树（TreePrinting），该模块主要实现： coprint(p,HT);三、系统的设计与实现（一） 初始化（Initialization），该模块主要实现void Initialization() int a,k,flag,len; a=0; len=InputCode(); for(i=0;i<

6、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); printf("%d%dn",i,coui.count); for(i=0;i<=n;

7、i+) *(z+i)=coui.data; *(w+i)=coui.count; （二） 编码（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(

8、HCj,codefile); if(j>n) printf("字符错误，无法编码!n"); 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)

9、!='0'i+) i2=*(work+i);if(HTi3.lchild=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); do if(fgets(work5,51,txtfile)=NULL) prin

10、tf("不能读取文件n"); break; fputs(work5,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函数 （二）测试编

11、码（Encoding）及译码（Decoding）函数.（二）测试印代码文件（Print）函数（四）相关的根目录五、总结系统完成的功能：本程序完成的功能是可以在信息发送端通过一个编码系统对待传数据预先编码，在信息接收端将传来的数据进行译码（复原）。系统的不足：本次课程设计，我认为还有很多不足，比如说不能把一个随机输入的字符串中不同字符作为叶子结点元素，把其在该字符串中出现的次数作为权值构造一个赫夫曼树，并得到各个叶子结点的赫夫曼编码和整个输入的字符串的赫夫曼编码，还有不能够顺利按题目要求写出相应的文件，将编码存储在tex文件中。 我的收获是：通过本次实验，提高了自已调试程序的能力，充分体会到了在

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

13、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&&tj.parent=0) k=tj.we

14、ight,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; if(n<=

15、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

16、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' else cd-start='1' HCi=(char*)malloc(n-start)*sizeo

17、f(char); 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

18、strlen(str);void 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(&

19、quot;%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("下面将哈夫曼编码写入文件n.nn"); FILE *htmTree; char r=' ','0'

20、 if(htmTree=fopen("htmTree.txt","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("已将字符

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

22、不能打开文件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;

23、 printf("编码工作完成nn编码写入目录下的codefile.txt中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(&q

24、uot;codefile.txt","r")=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

25、+i); if(HTi3.lchild=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; *(work2+i4)='0' fputs(work2,txtfile); printf("译码完成n内容写入根目录下的文件txtfile.txt中nn"); free(work); free(work2); fclose(txtfile); fclose(codef);v

26、oid Code_printing() printf("下面打印根目录下文件CodePrin.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;

27、char *work3; work3=(char*)malloc(51*sizeof(char); 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("下面打

28、印根目录下文件txtfile.txt中译码字符n"); FILE * CodePrin1,* 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*s

29、izeof(char); do if(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("TreePrint.txt","a")=NULL) printf("创建文件失败n"); return; numb+; coprint(HT+start->rchild,HT);