哈夫曼(huffman)编译码器课程设计.doc

兰州商学院陇桥学院 工学系课程设计报告设 计 题 目：哈夫曼（huffman）编译码器 系 别： 专 业 (方 向)： 年 级、 班： 学 生 姓 名： 学 生 学 号： 指 导 教 师： 年 月日 目 录哈夫曼(huffman )编译码器3一、 编译码器开发的背景3二、系统的分析与设计3（一）系统功能要求3（二）系统模块结构设计4三、系统的设计与实现6（一）main()6（二）运算71. 权值运算quanzhi()72. 印二叉树函数huffmantree( )73.编译码运算huffmancode()94. 输出运算 shuchu()9四、系统测试10（一）测试主函数10（二）测试印二叉树函数10（三） 测试译码运算函数11五、总结12六、附件（代码、部分图表）13哈夫曼(huffman )编译码器1、 编译码器开发的背景 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。二、系统的分析与设计（一）系统功能要求一个完整的系统应具有以下功能：1) I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。2) E：编码（Encoding）。利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。3) D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。4) P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。5) T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。（二）系统模块结构设计通过对系统功能的分析，哈夫曼（huffman）编译码器功能如图（1）所示。哈夫曼（huffman ）编译码器初 始 化输出二叉树编 译 码输出 代码选 择 操 作 图（1）哈夫曼（huffman)编译码器功能图通过上图的功能分析，把整个系统分为四个模块：1.初始化模块，该模块主要实现：输入二叉树的结点数，以及要加密的句子，建立哈夫曼树。2.输出二叉树模块，该运算模块主要实现：将输入的字符串中每个字符出现的次数当作权值，建立二叉树，将二叉树的parent,weight,lchild,rchild输出。3.译码模块，该操作主要实现：对编码后的代码进行译码，然后输出。4.输出模块，该操作主要进行表头的输出。开始是 用户选择否y=1否y=2 输入叶子节点数y=3对输入的句子进行编码 输入句子 退出系统输出每个字符的编码建立二叉树，输出二叉树 结束 图流程图三、系统的设计与实现（一）main()输出1.输出二叉树操作2.进行输出二叉树操作3.退出编译码操作系统，并让用户选择所进行的操作，对其调用。 该模块的具体代码如下所示：void main()int i,n,s=1; hnodetype 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() 分析：此函数用于对一串字符进行求权值运算，利用循环将一串字符中每个字符的个数设定为权值。void quanzhi(int tmaxleaf,char smaxleaf,int n)/求权值函数，将句子中的字符出现的个数当作权值int i,j,h;for(i=0;in;i+)for(j=0;jn;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(输入叶子结点个数：);scanf(%d,&n);for(i=0;i2*n-1;i+)/数组huffnode初始化huffnodei.weight=0; huffnodei.parent=-1;huffnodei.lchild=-1;huffnodei.rchild=-1;printf(输入要编译的句子的n); for(i=0;in;i+) printf(第%d个结点,i+1);scanf(%d,&huffnodei.weight);getchar();printf(印二叉树：n); for(i=0;in;i+)quanzhi(t,s,n); k=huffnodei.weight;for(i=0;in-1;i+)/构造哈夫曼树m1=m2=maxvalue; x1=x2=0;for(j=0;jn+i;j+)/选取最小和次小两个权值if(huffnodej.parent=-1&huffnodej.weightm1)m2=m1;x2=x1;m1=huffnodej.weight;x1=j;elseif(huffnodej.parent=-1&huffnodej.weightm2)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;i2*n-1;i+)printf( %4d,k); printf( %4d,huffnodei.lchild);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;in;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=huffnodec.parent;for(j=cd.start+1;jn;j+)huffcodei.bitj=cd.bitj;huffcodei.start=cd.start;for(i=0;in;i+)printf(第%d个译码为：,i+1);for(j=huffcodei.start+1;jn;j+)printf(%4d,huffcodei.bitj);printf(n);4. 输出运算 shuchu()void shuchu()printf(*n);printf(* |* 哈夫曼树的编译码 * | *n);printf(* |* 1.输出二叉树操作 * | *n);printf(* |* 2.进行编译码操作 * | *n);printf(* |* 3.退出编译码操作系统* | *n);printf(*n); printf(请选择要进行的操作:);四、系统测试（一）测试主函数main（）函数该测试主要进行对主函数调用以及输出的测试，测试的结果：（二）测试印二叉树函数 测试选择1，选择1操作首先输入叶子节点数，然后输入要编译的句子，分别输入第n+1个节点，然后系统会将输入字符的个数当作权值进行编译输出二叉树，测试结果为：（3） 测试译码运算函数测试选择2，输入要选择的操作2，然后按要求依次输入需要的值，系统会根据输入的数据进行译码操作，最后输出译码。输出结果为： （4） 测试退出函数 测试选择3进行退出，测试结果为:五、总结系统功能：系统完成了将一段字符串进行哈夫曼加密，用户将自己的选择输入程序，然后按照程序的提示进行输入，系统将根据输入进行编码、译码操作，然后印出编译的二叉树，以及每个字符的译码。不足：系统没有将印哈夫曼树操作完成，系统没有将字符的权值根据大小将左孩子设为最小权值，将次小权值设为右孩子，导致加密有许多种，哈夫曼树也创建了许多种，输出的译码不唯一。收获：通过一学期数据结构的学习，我发现数据结构比较难，没有完整的自己独立完成一个程序。但也学到了许多东西，学会了以前不会的函数调用，在编程时，有许多小问题还是不能够及时的发现，老是被一点小问题卡住导致程序不执行或输出死循环，一些程序的指针还不太熟悉。 通过这次程序设计，我发现了许多自己的不足，对一些算法还不能熟练运用，不能将所学的运用到程序中，一些语句还是不太懂；同时，也有一些收获，对函数调用能够熟练运用，也明白了结构体的作用，掌握了最优二叉树的建立和原理，对哈夫曼树有了更深一步的了解。六、附件（代码、部分图表） /*哈弗曼树*/#include #define maxvalue 1000/定义最大权值#define maxleaf 50/定义哈夫曼树中叶子结点个数#define maxnode maxleaf*2-1/定义哈夫曼树中结点个数整数常量maxnode#define maxbit 100/定义哈夫曼树的最大长度整数常量typedef struct/定义结构体int weight;int parent;int lchild;int rchild;hnodetype;typedef structint bitmaxbit;int start;hcodetype; /求权值函数void quanzhi(int tmaxleaf,char smaxleaf,int n)/求权值函数，将句子中的字符出现的个数当作权值int i,j,h;for(i=0;in;i+)for(j=0;jn;j+)if(si=sj)h+;ti=h; /印二叉树函数void haffmantree(hnodetype huffnodemaxnode,int *m)int i,j,n,k;int m1,m2,x1,x2;char smaxleaf,tmaxleaf; printf(输入叶子结点个数：);scanf(%d,&n);for(i=0;i2*n-1;i+)/数组huffnode初始化huffnodei.weight=0; huffnodei.parent=-1;huffnodei.lchild=-1;huffnodei.rchild=-1;printf(输入要编译的句子的n); for(i=0;in;i+) printf(第%d个结点,i+1);scanf(%d,&huffnodei.weight);getchar();printf(印二叉树：n); for(i=0;in;i+)quanzhi(t,s,n); k=huffnodei.weight;for(i=0;in-1;i+)/构造哈夫曼树m1=m2=maxvalue; x1=x2=0;for(j=0;jn+i;j+)/选取最小和次小两个权值if(huffnodej.parent=-1&huffnodej.weightm1)m2=m1;x2=x1;m1=huffnodej.weight;x1=j;elseif(huffnodej.parent=-1&huffnodej.weightm2)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;i2*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;in;i+)cd.start=n-1;c=i;p=huffnodec.parent;while(p!=-1)if(huffnodep