哈夫曼编码译码器

1、沈阳航空航天大学课课 程程 设设 计计 报报 告告课程设计名称：数据结构课程设计数据结构课程设计课程设计题目：哈夫曼编码哈夫曼编码/ /译码器译码器院（系）：计算机学院专 业：计算机科学与技术班 级：学 号：姓 名：指导教师：沈阳航空航天大学课程设计报告 I 目录目录沈阳航空航天大学沈阳航空航天大学.I第第 1 章章 概要设计概要设计.11.1 题目的内容与要求.11.2 总体结构.1第第 2 章章 算法分析算法分析.22.1 核心算法思想.22.2 算法结构定义.2第第 3 章章 详细设计详细设计.33.1 功能流程.3第第 4 章章 系统实现系统实现.54.1 错误分析.54.2 运行结果

2、.5参考文献参考文献.8附附 录录.9沈阳航空航天大学课程设计报告 1 第 1 章 概要设计1.1 题目的内容与要求题目的内容与要求内容：设计一个利用哈夫曼算法的编码和译码系统，可以接收从键盘输入的字符集大小、字符和权值信息，创建哈夫曼树生成哈夫曼编码并能对其进行解码。要求：1存储结构自定；2将生成的哈夫曼编码与等长编码进行比较，判断优劣；3给出动态演示过程（选作） 。1.2 总体结构总体结构本程序主要分为 3 个模块（功能模块图见图 1.1）：主模块，编码模块，译码模块。主模块：程序的主体部分，分别调用各个模块，实现各项功能。编码模块：对每个出现的字符进行编码。译码模块：将已有编码译成字符，

3、使之可以直接被读出。 哈哈夫夫曼曼编编码码/ /译译码码器器主主模模块块编编码码模模块块译译码码模模块块 图图 1.1 功能模块图功能模块图沈阳航空航天大学课程设计报告 2 沈阳航空航天大学课程设计报告 3 第 2 章 算法分析2.1 核心算法思想核心算法思想哈夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有 n 棵只含有根结点的二叉树。算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行 n1 次合并，所以共产生 n1 个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中一共有 2n1

4、 个结点，其中 n 个结点是初始森林的 n 个孤立结点。并且哈夫曼树中没有度数为 1 的分支结点。我们可以利用一个大小为 2n-1 的一维数组来存储哈夫曼树中的结点。哈夫曼编码是可变字长编码。编码时借助哈夫曼树，也即带权路径长度最小的二叉树，来建立编码。译码的基本思想是：读文件中编码，并与原先生成的赫夫曼编码表比较，遇到相等时，即取出其对应的字符存入一个新串中。2.2 算法结构定义算法结构定义结构体存储表示typedef struct int weight;int parent,lchild,rchild; Htnode,*Hfmtree; /动态分配数组存储哈夫曼树typedef char

5、*Hfmcode; /动态分配数组存储哈弗曼编码表沈阳航空航天大学课程设计报告 4 第 3 章 详细设计3.1 功能流程功能流程此流程图为构造哈夫曼树的过程，输入字符的次数为权值对每个结点赋值，构造哈夫曼树，如图 3.1 开开始始以以读读入入字字符符次次数数对对各各结结点点赋赋初初值值并并令令i=2n-1i i为为0 0找找出出根根结结点点权权值值最最小小和和次次小小树树s1,s2两两树树合合并并成成新新树树n+i结结束束i i减减1 1NY图图 3.1 流程图流程图沈阳航空航天大学课程设计报告 5 此流程图（图 3.2）为对字符进行哈夫曼编码的过程，将字符转化为哈夫曼编码。 开开始始i i

6、= =n n第第一一个个字字符符，i=1结结点点是是否否是是根根结结点点双双亲亲结结点点的的左左结结点点是是否否等等于于该该结结点点记记编编码码0 0记记编编码码1 1i i= =i i+ +1 1结结束束将将得得到到的的编编码码存存储储Y YY YY YN NN NN图图 3.2 字符编码模块流程图字符编码模块流程图沈阳航空航天大学课程设计报告 6 沈阳航空航天大学课程设计报告 7 第 4 章 系统实现4.1 错误分析错误分析在此程序调试过程中主要遇到以下几类问题：1、本程序运用了对文件进行操作，一定要注意在操作文件是文件的位置，我在做次程序是就是因为操作的文件位置错了导致程序无法正常运行。

7、2、在函数内部有时需要多定义参数，注意参数的作用域，而且注意传引用调用和传值调用的区别，不能不正确的修改实参的值，否则会导致程序运行的错误。3、本程序用到的外部函数较多，在调用时一定要注意传入的参数是否符合函数的定义，而且位置也不能错，这是引用函数要注意的一点。4、刚开始时清屏函数运用出错，导致操作界面消失，使用户无法操作，因此，在使用一些函数是一定要注意。4.2 运行结果运行结果运行程序首先出现界面图，如图 4.2 所示。 图图 4.1 界面图界面图选择操作 1 后，输入相应的字符大小，字符和权值，生成哈夫曼树。系统会显示每个字符的哈夫曼编码，如图 4.2 所示。沈阳航空航天大学课程设计报告

8、 8 图图 4.2 程序运行截图程序运行截图选择操作 2 后，输入字符串，系统会显示对字符串进行哈弗曼编码得到的哈弗曼编码，显示以下界面（图 4.3）供用户选择。 图图 4.3 程序运行截图程序运行截图选择操作 3 后，系统会显示用哈夫曼编码翻译成的字符，显示以下界面（图4.4）供用户选择 图图 4.44.4 程序运行截图程序运行截图选择操作 4 后，退出系统，显示以下界面（图 4.5）沈阳航空航天大学课程设计报告 9 图图 4.5 程序运行截图程序运行截图沈阳航空航天大学课程设计报告 10 参考文献1 严蔚敏.数据结构(C 语言版).清华大学出版社，20072 谭浩强.C 语言程序设计教程.

9、高等教育出版社，20063 苏仕华.数据结构课程设计.机械工业出版社，2007沈阳航空航天大学课程设计报告 11 附 录源程序如下：#include#include#include#include#includetypedef struct /赫夫曼树的结构体char ch;int weight; /权值int parent,lchild,rchild;Htnode,*Hfmtree; /动态分配数组存储赫夫曼树typedef char *Hfmcode; /动态分配数组存储赫夫曼编码表void Select(Hfmtree &HT,int a,int *s1,int *s2) /Se

10、lect 函数，选出 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; /选出最小的节点沈阳航空航天大学课程设计报告 12 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)*s1=y;*s2=x;else*s1=x;*s2=y;vo

11、id Hfmcoding(Hfmtree &HT,Hfmcode &HC,int n) /构建赫夫曼树 HT，并求出 n沈阳航空航天大学课程设计报告 13 个字符的赫夫曼编码 HCint i,start,c,f,m,w;int p1,p2;char *cd,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)c

12、ontinue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的结点HTi.ch=0;沈阳航空航天大学课程设计报告 14 HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;+i) /建立赫夫曼树Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.we

13、ight+HTp2.weight;HC=(Hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0; /-从叶子到根逆向给出每个字符的哈夫曼编码-for(i=1;ichoice; if(choice=1) /初始化赫夫曼树coutn;Hfmcoding(HT,HC,n);for(i=1;i=n;+i)coutHTi.ch:HCiendl;output_file.open(hfmTree.txt);if(!output_file)coutcant oen file!endl; 沈阳航空航天大学课程设计报

14、告 17 for(i=1;i=n;i+)output_file(HTi.chHCi);output_file.close();printf(赫夫曼树已经创建完毕，并且已经放入 hfmTree.txt 文件中!n); else if(choice=2) /进行编码，并将字符放入A.txt，码值放入 B.txt 中printf(请输入字符：);gets(str);output_file.open(A.txt);if(!output_file)coutcant oen file!endl;output_filestrendl;output_file.close();output_file.open(

15、B.txt);if(!output_file)coutcant oen file!endl;for(i=0;istrlen(str);i+)for(j=0;j=n;+j)if(HTj.ch=stri)沈阳航空航天大学课程设计报告 18 output_fileHCj;break;output_file.close();coutn;printf(编码完毕，并且已经存入 B.txt 文件！n);input_file.open(B.txt); /从 B.txt 中读入编码，输出在终端if(!input_file)coutcant oen file!code;cout编码码值为：codeendl;inp

16、ut_file.close(); else if(choice=3) /读入 B.txt 中的编码进行译码，将译出来的字符放入 Textfile.txt 中input_file.open(B.txt);if(!input_file)coutcant oen file!h;input_file.close();output_file.open(Textfile.txt);if(!output_file)沈阳航空航天大学课程设计报告 19 coutcant oen file!endl;k=0;while(hk!=0) /先用编码中的前几个和字符的编码相比较，然后往后移for(i=1;i=n;i+)

17、l=k;for(j=0;jstrlen(HCi);j+,l+)hlj=hl;hlj=0;if(strcmp(HCi,hl)=0)output_fileHTi.ch;k=k+strlen(HCi);break;output_file.close();input_file.open(Textfile.txt);if(!input_file)coutcant oen file!h; couthendl;沈阳航空航天大学课程设计报告 20 input_file.close();printf(译码结束，字符已经存入 Textfile.txt 文件中!n); else if(choice=4) exit(

18、0); else /如果选了选项之外的就让用户重新选择printf(您没有输入正确的步骤，请重新输入！);沈阳航空航天大学课程设计报告 21 课程设计总结：课程设计总结：通过近两周的课程设计使我对哈夫曼树以及哈夫曼编码译码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。在做课设的过程中我也遇到了很多问题：开始的时候，代码中有许多的错误，特别是有一个“无法找到文件”的错误让我束手无策，最后还是屏蔽了定义的四个头文件然后慢慢地改正错误才让我又看到了希望。然后在实现文章的读入时，由于对文件不是太熟悉，只好翻开 C 语言和 C+语言书本仿照其模式编写，但后来进入了死循环，最后的解决方式是在 main 函数里有一个控制语句使用不正确。我们遇到问题很正常，说明我们掌握的知