哈夫曼编码译码器

1、 目录目录一、一、系统开发的背景系统开发的背景.1二、系统分析与设计二、系统分析与设计.1（一）（一）系统功能要求系统功能要求.1（二）（二）系统模块结构设计系统模块结构设计.2三、系统的设计与实现三、系统的设计与实现.2（一）（一）哈夫曼树的定义哈夫曼树的定义.2四、系统测试四、系统测试.3（一）（一）测试测试MAINMAIN_ _FORMFORM()()函数函数.3（二）（二）测试测试VOIDVOID HFMCODINGHFMCODING( (HFMTREEHFMTREE &HT,&HT,HFMCODEHFMCODE &HC,&HC,INTINT N N)

2、)函数，测试的结果函数，测试的结果.4（三）（三）测试编码函数，测试结果如下测试编码函数，测试结果如下.4（四）（四）测试译码函数，测试结果如下测试译码函数，测试结果如下.4（五）（五）测试退出函数，测试结果如下测试退出函数，测试结果如下.5五、总结（实验心得）五、总结（实验心得）.5六、附件（源代码）六、附件（源代码）.6 1哈夫曼编译码哈夫曼编译码一、一、 系统开发的系统开发的背景背景随着计算机的应用越来越普遍，它的应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。 为了确保能够更好的保存机密性文件、安全的传送某一个重要的东西，

3、利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码器。因此我为这样的信息收发站设计了一个简单的哈夫曼的编码/译码器。二、系统分析与设计二、系统分析与设计（一）（一） 系统功能要求系统功能要求一个完整的哈夫曼编码/译码器应具有以下功能：1、 初始化：从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树，并将它存于文件 hfmTree 中。2、 编码：利用以建好的哈夫曼树（如不在内存，则从文

4、件 hfmTree中读入） ，对文件 ToBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中。3、 译码：利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件 TextFile 中。4、 退出。 2（二）（二）系统模块结构设计系统模块结构设计通过对此功能的分析，哈夫曼编码/译码器的功能如图 1 所示。哈夫曼编码/译码器哈夫曼编码/译码器1.初始化1.初始化2.编码2.编码3.译码3.译码0.退出0.退出图 1 哈夫曼编码/译码器的功能图通过上图的功能分析，把整个系统划分为 4 个模块：1、初始化，该模块主要实现：哈夫曼二叉树的定义以及哈夫曼二叉树的

5、建立，借助函数 void hfmcoding（）来实现；2、编码，该模块主要实现：把输入的字符和代码以二进制的形式存储起来，借助函数 void hfmcoding（）来实现；3、译码，该模块主要实现：把以二进制形式存储起来的代码，转换成字符的形式并输出，借助函数来实现；4、退出。三、系统的设计三、系统的设计与实现与实现（一）（一） 哈夫曼树的定义哈夫曼树的定义1.哈夫曼树节点的数据类型定义为：typedef struct /赫夫曼树的结构体char ch;int weight; /权值int parent,lchild,rchild;htnode,*hfmtree;2.所实现的功能函数如下1）

6、 、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈 3夫曼树，处理 InputHuffman(Huffman Hfm)函数得到的数据，按照哈夫曼规则建立 2 叉树。此函数块调用了 Select（）函数。2)、void Select(hfmtree &HT,int a,int *p1,int *p2) /Select 函数，选出 HT 树到 a 为止，权值最小且 parent 为 0 的 2个节点3)、 int main()主函数： 利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.txt 中读入）对文件中的正文

7、进行编码，然后将结果存入文件 codefile.txt 中。如果正文中没有要编码的字符，则键盘读入并存储到 ToBeTran 文件中。读入 ToBeTran 中将要编码的内容，将编码好的哈夫曼编码存储到 CodeFile 中。4)、Encoding 编码功能：对输入字符进行编码5)、Decoding译码功能： 利用已建好的哈夫曼树将文件 codefile.txt 中的代码进行译码，结果存入文件 textfile.dat 中。6).主函数的简要说明，主函数主要设计的是一个分支语句，让用户挑选所实现的功能。使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功

8、能。四、系统测试四、系统测试（一）（一） 测试测试 main_form()main_form()函数函数测试该函数使用的测试方法，测试的具体步骤，测试用例的选取，测试的结果。图 1 哈夫曼编码/译码界面 4（二）（二） 测试测试 voidvoid hfmcoding(hfmtreehfmcoding(hfmtree &HT,hfmcode&HT,hfmcode &HC,int&HC,int n)n)函函数，测试的结果数，测试的结果图 2 哈夫曼树的初始化（一）（一） 测试编码函数，测试结果如下测试编码函数，测试结果如下图 3 哈夫曼的编码（二）（二） 测试译码函

9、数，测试结果如下测试译码函数，测试结果如下 5图 4 哈夫曼译码（三）（三） 测试退出函数，测试结果如下测试退出函数，测试结果如下图 5 哈夫曼编码/译码系统的退出五、总结五、总结（实验心得）（实验心得）系统完成了利用哈夫曼树对字符的编码和译码之间的转换，它能利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，并且降低传输成本的功能。此系统不能打印代码文件（Print） ，不能打印哈夫曼树（Tree Printing） 。并且不能将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上。我的收获是，通过今年对数据结构的学习和这次的课程设计，使我了解到计算机的应用在人类的现实

10、生活中已经越来越普遍，它的应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。 6六、附件（源代码）六、附件（源代码）#include#include#include#include typedef struct /赫夫曼树的结构体char ch;int weight; /权值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode; /代码void Select(hfmtree &HT,int a,int *p1,int *p2) /Select 函数，选出

11、 HT 树到 a 为止，权值最小且 parent 为 0 的 2 个节点int i,j,x,y;for(j=1;j=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=i; /选出最小的节点for(j=1;j=a;+j)if(HTj.parent=0&x!=j)y=j;break;for(i=j+1;i=a;+i)if(HTi.weighty)*p1=y; 7*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &

12、HT,hfmcode &HC,int n) /构建赫夫曼树 HT，并求出 n 个字符的赫夫曼编码 HCint i,start,c,f,m,w; /w 中存放的是权值int p1,p2;char *cd,z; /z 中存放的是需要编码的字符if(n=1)return;m=2*n-1; /哈弗曼树中节点的个数HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i=n;+i) /初始化 n 个叶子结点printf(请输入第%d 字符信息和权值：,i);scanf(%c%d,&z,&w);while(getchar()!=n)conti

13、nue;HTi.ch=z; HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的结点HTi.ch=0;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;+i) /建立赫夫曼树 8Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC

14、=(hfmcode)malloc(n+1)*sizeof(char *); /cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i) /给 n 个字符编码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);strcpy(HCi,&cdstart);free(cd);int main()char code100,h1

15、00,hl100;int n,i,j,k,l,m; /m 中存放选择序号，n 中存放char str100;hfmtree HT;hfmcode HC; /HC 中存放的是哈弗曼代码FILE *fp;FILE *htmTree;FILE *ToBeTran;FILE *CodeFile;FILE *Textfile;printf(n); 9while(m!=0) /当 choice 的值不为 q 且不为 Q 时循环printf( *n);printf( * 赫夫曼编码/译码器 *n); printf( * 1.初始化 *n);printf( * 2.编码 *n);printf( * 3.译码

16、*n);printf( * 0.退出 *n);printf( *n);printf(n); printf(请输入您要操作的步骤：);scanf(%d,&m); if(m=1) /初始化赫夫曼树printf(请输入字符个数：);scanf(%d,&n);hfmcoding(HT,HC,n);for(i=1;i=n;+i)printf(%c:,HTi);puts(HCi);fp=fopen(hfmTree,txt);if(fp=fopen(hfmTree,w)=NULL)printf(cant open file!n);return 1;fclose(fp);printf(哈夫曼树

17、已经创建完毕，并且已经放入 hfmTree.txt 文件中!n); else if(m=2) /进行编码，并将字符放入 ToBeTran.txt，码值放入CodeFile.txt 中printf(请输入字符：);scanf(%s,str);fp=fopen(ToBeTran,w);if(fp=fopen(ToBeTran,w)=NULL)printf(cant open file!n);return 1;fputs(str,fp);fclose(fp);fp=fopen(CodeFile,w); 10if(fp=fopen(CodeFile,w)=NULL)printf(cant open f

18、ile!n);return 1;for(i=0;istrlen(str);i+)for(j=0;j=n;+j)if(HTj.ch=stri)fputs(str,htmTree);break;fclose(fp);printf(n);printf(编码完毕，并且已经存入 CodeFile.txt 文件！n);fp=fopen(CodeFile,r); /从 CodeFile.txt 中读入编码，输出在终端if(fp=fopen(CodeFile,r)=NULL)printf(cant open file!n);return 1;printf(编码码值为：%d,HTj);fclose(fp); else if(m=3) /读入 CodeFile.txt 中的编码进行译码，将译出来的字符放