哈夫曼编码译码器

1、目录一、系统开发的背景 1二、系统分析与设计 1（一）系统功能要求 1（二）系统模块结构设计 2三、系统的设计与实现 2（一）哈夫曼树的定义 2四、系统测试 3（一）测试 MAIN_FORM（） 函数 3（二）测试 VOID HFMCODIN（GHFMTREE&HT,HFMCOD&EHC,INT N） 函数，测试的结果 4（三）测试编码函数，测试结果如下 4（四）测试译码函数，测试结果如下 4（五）测试退出函数，测试结果如下 5五、总结（实验心得） 5六、附件（源代码） 6哈夫曼编译码、 系统开发的背景随着计算机的应用越来越普遍，它的应用早已不局限于简单的数值运 算，而涉及到问题的分析、数据结

2、构框架的设计以及设计最短路线等复杂 的非数值处理和操作。为了确保能够更好的保存机密性文件、安全的传送某一个重要的东西， 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间， 降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先 编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以 双向传输信息的信道），每端都需要一个完整的编 / 译码器。因此我为这样 的信息收发站设计了一个简单的哈夫曼的编码 / 译码器。、系统分析与设计（一）系统功能要求一个完整的哈夫曼编码 / 译码器应具有以下功能：1、 初始化：从终端读入字符集大小n,以及n个字符和n个权值，建 立哈夫曼

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

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

5、初始化哈夫 曼树，处理InputHuffman(Huffman Hfm)函数得到的数据，按照哈夫 曼规则建立2叉树。此函数块调用了 Select ()函数。2) 、 void Select(hfmtree&HT,int a,int *p1,int *p2)/Select 函数，选出HT树到a为止，权值最小且pare nt为0的2 个节点3) 、int main()主函数：利用已建好的哈夫曼树(如不在内存，则从文件 hfmtree.txt中读入)对文件中的正文进行编码，然后将结果存入文件codefile.txt 中。如果正文中没有要编码的字符，则键盘读入并存储到ToBeTran文件中。读入ToB

6、eTran中将要编码的内容，将编码好的哈夫曼编码存储 到 CodeFile 中。4) 、Encoding编码功能：对输入字符进行编码5) 、Decoding译码功能：利用已建好的哈夫曼树将文件codefile.txt 中的代码进行译码，结果存入文件textfile.dat 中。6) .主函数的简要说明，主函数主要设计的是一个分支语句，让用户 挑选所实现的功能。使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫 曼函数，编码函数，译码函数来实现功能。四、系统测试(一) 测试 main_form()函数测试该函数使用的测试方法，测试的具体步骤，测试用例的选取，测试的结果图1哈夫曼编码/译码

7、界面(二)测试 void hfmcoding(hfmtree&HT,hfmcode &HC,int n)函数，测试的结果X MX XX XX赫夫臺编聊丿详码器 化1-2.X 昇:W X K X X X K K0.3負 X HE XM.K M：負 X MLJCMZiCXM：宾X烈e 103 d 32F 21i 57 n 5?尸48n D u n D 铀6息息息自心息息 -_1二星一皆r屋屈旨 辱壬HHH士千1 2 3 4 S 6你孝第暑第第第JAaaagaau10 4JFJTSF-kT4rr4ar43mrr 1 1 主冃士冃主冃-Hl冃土月QHI冃圭冃T :：llil1：0:ei：iis夫曼树已

8、经创建完毕，并且己经放入hfmTree. txtW 中(一)图2哈夫曼树的初始化测试编码函数，测试结果如下Wf耳咒X弭弭耳芹W豪M： 豪鼻1夫 赫:MWIK. fM X J X MMK耳3-CJX耳耗轉码码岀JH4C-4(-34-34#3KKXK 耳 33 耳请输入您宴操作的步辍：3條初为;friend谆码结東，字符已经存入Textfile-txt文件中!图4哈夫曼译码（三）测试退出函数，测试结果如下谙输入您要操作的步骤；0 Press any he/ to rontinuc图5哈夫曼编码/译码系统的退出五、总结（实验心得）系统完成了利用哈夫曼树对字符的编码和译码之间的转换，它能利用 哈夫曼编

9、码进行通信可以大大提高信道利用率，缩短信息传输时间，并且 降低传输成本的功能。此系统不能打印代码文件（Print），不能打印哈夫曼树（Tree Printing） 并且不能将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示 在终端上。我的收获是，通过今年对数据结构的学习和这次的课程设计，使 我了解到计算机的应用在人类的现实生活中已经越来越普遍，它的应用早 已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计 以及设计最短路线等复杂的非数值处理和操作。六、附件（源代码）#include#include#include#includetypedef struct /赫夫曼树的结构

10、体char ch;int weight; /权值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode; /代码函数，选出HT树到a为止,void Select(hfmtree &HT,int a,int *p1,int *p2) /Select 权值最小且 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

11、; / 选出最小的节点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;*p2=x;else*p1=x;*p2=y;n 个字符的void hfmcodi ng(hfmtree & HT,hfmcode & HC,i nt n) /构建赫夫曼树HT,并求出赫夫曼编码 HCint i,start,c,f,m,w; /w中存放的是权值int p1,p2;char *cd,z; /z 中存放的是需要编码的字符if(n=1)return;m=2*n-1; / 哈弗曼树中节点的个数

12、HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i=n;+i)/初始化 n 个叶子结点printf(”请输入第c字符信息和权值：”,i);scanf(%c%d,&z,&w);while(getchar()!=n)continue;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)/建

13、立赫夫曼树Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(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

14、-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);int main()char code100,h100,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);printf( *1

15、.初始化*n);printf( *2.编码*n);printf( *3.译码*n);printf( *0.退出*n);printf(*n);printf( *赫夫曼编码 / 译码器 *n);printf(*n);while(m!=0)/当choice的值不为q且不为Q时循环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=f

16、open(hfmTree,txt); if(fp=fopen(hfmTree,w)=NULL) printf(cant open file!n); return 1; fclose(fp); printf( 哈夫曼树已经创建完毕，并且已经放入 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

17、file!n);return 1;fputs(str,fp);fclose(fp);fp=fopen(CodeFile,w);if(fp=fopen(CodeFile,w)=NULL)printf(cant open file!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

18、.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 中的编码进行译码，将译出来的字符放入 Textfile.txt 中fp=fopen(CodeFile,w);if(fp=fopen(CodeFile,w)=NULL)printf(cant open file!n);return 1;fclose(fp);fp=fopen(Textfile,w);if(fp=fopen(Textfile,w)=NULL)printf(cant open file!n);return 1;k=0;while(hk!=0) / 先用编码中的前几个和字符的编码相比较，然后往后移for(i=1;i=n;i+)l=k;for(j=0;jstrlen(HCi);j+,l+) hlj=hl;hlj=0; if(strcmp(HCi,hl)=0) k