哈夫曼(huffman)编译码器课程设计报告书

1、下载可编辑商学院陇桥学院工学系课程设计报告设计题目：哈夫曼 （huffman）编译码器系别：专业 ( 方向 ) ：年级、班：学生姓名：学生学号：指导教师：年月日.专业 .整理 .下载可编辑目录哈夫曼 (huffman )编译码器3一、 编译码器开发的背景3二、系统的分析与设计3（一）系统功能要求3（二）系统模块结构设计4三、系统的设计与实现6（一） main()6（二）运算71.权值运算 quanzhi()72.印二叉树函数 huffmantree( )73. 编译码运算 huffmancode()94.输出运算 shuchu()9四、系统测试10（一）测试主函数10（二）测试印二叉树函数10

2、（三） 测试译码运算函数11五、总结12六、附件（代码、部分图表）13.专业 .整理 .下载可编辑哈夫曼 (huffman )编译码器一、 编译码器开发的背景利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。 但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/ 译码系统。二、系统的分析与设计（一）系统功能要求一个完整的系统应具有以下功能：1) I ：初始化（ Initialization）。从终端读入字符集大小n，以及 n 个字符和n 个权值，建立哈夫曼树，

3、并将它存于文件hfmTree 中。2) E：编码（ Encoding ）。利用以建好的哈夫曼树（如不在存，则从文件 hfmTree 中读入），对文件 ToBeTran中的正文进行编码，然后将结果存入文件 CodeFile 中。3) D：译码（Decoding）。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件 TextFile 中。.专业 .整理 .下载可编辑4) P：印代码文件（ Print ）。将文件 CodeFile 以紧凑格式显示在终端上，每行50 个代码。同时将此字符形式的编码文件写入文件 CodePrin 中。5) T：印哈夫曼树（ Tree Print

4、ing）。将已在存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。（二）系统模块结构设计通过对系统功能的分析，哈夫曼（ huffman ）编译码器功能如图（1）所示。哈夫曼（ huffman ）编译码器选择操作初输编输出出始二译叉代化树码码图（ 1）哈夫曼（ huffman) 编译码器功能图通过上图的功能分析，把整个系统分为四个模块：1. 初始化模块， 该模块主要实现：输入二叉树的结点数，以及要加密的句子，建立哈夫曼树。.专业 .整理 .下载可编辑2. 输出二叉树模块， 该运算模块主要实现： 将输入的字符串中每个字符出现的次数当作

5、权值，建立二叉树，将二叉树的parent,weight,lchild,rchild输出。3. 译码模块，该操作主要实现：对编码后的代码进行译码，然后输出。4. 输出模块，该操作主要进行表头的输出。开始用户选择是否y=1否y=2输入叶子节点数y=3对输入的句输入句子子进行编码建立二叉树， 输输出每个字符退出系统出二叉树的编码结束图流程图.专业 .整理 .下载可编辑三、系统的设计与实现（一） main()输出 1. 输出二叉树操作2. 进行输出二叉树操作3. 退出编译码操作系统，并让用户选择所进行的操作，对其调用。该模块的具体代码如下所示：void main()int i,n,s=1;hnodet

6、ype huffnodemaxnode;while(s)shuchu();scanf("%d",&i);switch(i)case 1:haffmantree(huffnode,&n);break;case 2:haffmancode();break;case 3:s=0;break;分析：首先输出一个主菜单，方便用户进行操作，用switch语句调用函数使用户对其进行选择要执行的操作（1. 输出二叉树操作，2. 进行编译码操作，3. 退出程序） 。.专业 .整理 .下载可编辑（二）运算该模块的具体代码如下所示：1. 权值运算 quanzhi()分析：此函数用

7、于对一串字符进行求权值运算， 利用循环将一串字符中每个字符的个数设定为权值。void quanzhi(int tmaxleaf,charsmaxleaf,int n)/求权值函数，将句子中的字符出现的个数当作权值int i,j,h;for(i=0;i<n;i+)for(j=0;j<n;j+)if(si=sj)h+;ti=h;2. 印二叉树函数huffmantree( )void haffmantree(hnodetype huffnodemaxnode,int *m)int i,j,n,k;int m1,m2,x1,x2;char smaxleaf,tmaxleaf;printf(

8、"输入叶子结点个数：");scanf("%d",&n);for(i=0;i<2*n-1;i+)/数组 huffnode初始化huffnodei.weight=0;huffnodei.parent=-1;huffnodei.lchild=-1;huffnodei.rchild=-1;printf("输入要编译的句子的n");.专业 .整理 .下载可编辑for(i=0;i<n;i+)printf("第%d个结点 ",i+1);scanf("%d",&huffnodei.w

9、eight);getchar();printf("印二叉树： n");for(i=0;i<n;i+)quanzhi(t,s,n);k=huffnodei.weight;for(i=0;i<n-1;i+)/构造哈夫曼树m1=m2=maxvalue;x1=x2=0;for(j=0;j<n+i;j+)/选取最小和次小两个权值if(huffnodej.parent=-1&&huffnodej.weight<m1)m2=m1;x2=x1;m1=huffnodej.weight;x1=j;elseif(huffnodej.parent=-1&am

10、p;&huffnodej.weight<m2)m2=huffnodej.weight;x2=j;/将找出的两棵子树合并为一颗子树huffnodex1.parent=n+i;huffnodex2.parent=n+i;huffnoden+i.weight=huffnodex1.weight+huffnodex2.weight;huffnoden+i.lchild=x1;huffnoden+i.rchild=x2;for(i=0;i<2*n-1;i+)printf("%4d",k);printf("%4d",huffnodei.lchil

11、d);printf("%4d",huffnodei.rchild);.专业 .整理 .下载可编辑printf("%4dn",huffnodei.parent);*m=n;3. 编译码运算huffmancode()void haffmancode()hnodetype huffnodemaxnode;hcodetype huffcodemaxleaf,cd;int i,j,c,p,n=0;haffmantree(huffnode,&n);for(i=0;i<n;i+)cd.start=n-1;c=i;p=huffnodec.parent;wh

12、ile(p!=-1)if(huffnodep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=huffnodec.parent;for(j=cd.start+1;j<n;j+)huffcodei.bitj=cd.bitj;huffcodei.start=cd.start;for(i=0;i<n;i+)printf("第%d个译码为： ",i+1);for(j=huffcodei.start+1;j<n;j+)printf("%4d",huffcodei.bit

13、j);printf("n");4. 输出运算 shuchu()void shuchu().专业 .整理 .下载可编辑printf("* *n");printf("*|*哈夫曼树的编译码* |*n");printf("*|* 1.输出二叉树操作* |*n");printf("*|* 2.进行编译码操作* |*n");printf("*|* 3.退出编译码操作系统* |*n");printf("*n");printf("请选择要进行的操作:"

14、;);四、系统测试（一）测试主函数main（）函数该测试主要进行对主函数调用以及输出的测试，测试的结果：（二）测试印二叉树函数测试选择 1，选择 1 操作首先输入叶子节点数，然后输入要编译的句子，分别输入第 n+1 个节点，然后系统会将输入字符的个数当作权值进行编译输出二叉树，测试结果为：.专业 .整理 .下载可编辑（三）测试译码运算函数测试选择 2，输入要选择的操作2，然后按要求依次输入需要的值，系统会根据输入的数据进行译码操作，最后输出译码。输出结果为：（四）测试退出函数测试选择 3 进行退出，测试结果为:.专业 .整理 .下载可编辑五、总结系统功能 ：系统完成了将一段字符串进行哈夫曼加密

15、， 用户将自己的选择输入程序， 然后按照程序的提示进行输入， 系统将根据输入进行编码、译码操作，然后印出编译的二叉树， 以及每个字符的译码。不足：系统没有将印哈夫曼树操作完成， 系统没有将字符的权值根据大小将左孩子设为最小权值， 将次小权值设为右孩子， 导致加密有许多种，哈夫曼树也创建了许多种，输出的译码不唯一。收获：通过一学期数据结构的学习， 我发现数据结构比较难，没有完整的自己独立完成一个程序。 但也学到了许多东西， 学会了以前不会的函数调用，在编程时，有许多小问题还是不能够及时的发现，老是被一点小问题卡住导致程序不执行或输出死循环， 一些程序的指针还不太熟悉。通过这次程序设计，我发现了许

16、多自己的不足，对一些算法还不能熟练运用，不能将所学的运用到程序中，一些语句还是不太懂；同时，也有一些收获，对函数调用能够熟练运用，也明白了结构体的作用，掌握了最优二叉树的建立和原理， 对哈夫曼树有了更深一步的.专业 .整理 .下载可编辑了解。六、附件（代码、部分图表）/*哈弗曼树 */#include <stdio.h>#define maxvalue 1000/定义最大权值#define maxleaf 50/定义哈夫曼树中叶子结点个数#define maxnode maxleaf*2-1/定义哈夫曼树中结点个数整数常量maxnode#define maxbit 100/定义哈夫

17、曼树的最大长度整数常量typedef struct/定义结构体int weight;int parent;int lchild;int rchild;hnodetype;typedef structint bitmaxbit;int start;hcodetype;/求权值函数void quanzhi(int tmaxleaf,charsmaxleaf,int n)/求权值函数，将句子中的字符出现的个数当作权值int i,j,h;for(i=0;i<n;i+)for(j=0;j<n;j+)if(si=sj)h+;ti=h;/印二叉树函数void haffmantree(hnodet

18、ype huffnodemaxnode,int *m)int i,j,n,k;.专业 .整理 .下载可编辑int m1,m2,x1,x2;char smaxleaf,tmaxleaf;printf("输入叶子结点个数：");scanf("%d",&n);for(i=0;i<2*n-1;i+)/数组 huffnode初始化huffnodei.weight=0;huffnodei.parent=-1;huffnodei.lchild=-1;huffnodei.rchild=-1;printf("输入要编译的句子的n");fo

19、r(i=0;i<n;i+)printf("第%d个结点 ",i+1);scanf("%d",&huffnodei.weight);getchar();printf("印二叉树： n");for(i=0;i<n;i+)quanzhi(t,s,n);k=huffnodei.weight;for(i=0;i<n-1;i+)/构造哈夫曼树m1=m2=maxvalue;x1=x2=0;for(j=0;j<n+i;j+)/选取最小和次小两个权值if(huffnodej.parent=-1&&huff

20、nodej.weight<m1)m2=m1;x2=x1;m1=huffnodej.weight;x1=j;elseif(huffnodej.parent=-1&&huffnodej.weight<m2)m2=huffnodej.weight;x2=j;.专业 .整理 .下载可编辑/将找出的两棵子树合并为一颗子树huffnodex1.parent=n+i;huffnodex2.parent=n+i;huffnoden+i.weight=huffnodex1.weight+huffnodex2.weight;huffnoden+i.lchild=x1;huffnoden

21、+i.rchild=x2;for(i=0;i<2*n-1;i+)printf("%4d",k);printf("%4d",huffnodei.lchild);printf("%4d",huffnodei.rchild);printf("%4dn",huffnodei.parent);*m=n;/编译码函数void haffmancode()hnodetype huffnodemaxnode;hcodetype huffcodemaxleaf,cd;int i,j,c,p,n=0;haffmantree(huffnode,&n);for(i=0;i<n;i+)cd.start=n-1;c=i;p=huffnodec.parent;while(p!=-1)if(huffnodep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=huffnode