哈夫曼编码译码器

《哈夫曼编码译码器》由会员分享，可在线阅读，更多相关《哈夫曼编码译码器（25页珍藏版）》请在装配图网上搜索。

1、沈阳航空航天大学课程设计报告课程设计名称： 数据结构课程设计课程设计题目： 哈夫曼编码 / 译码器院（系）：计算机学院专业：计算机科学与技术班级：学号：姓名：指导教师：沈阳航空航天大学课程设计报告目录沈阳航空航天大学.I第1章 概要设计11.1题目的内容与要求11.2总体结构1第2章 算法分析22.1核心算法思想22.2算法结构定义2第3章 详细设计33.1功能流程3第4章 系统实现54.1错误分析54.2运行结果5参考文献8附录9I沈阳航空航天大学课程设计报告第 1章 概要设计1.1 题目的内容与要求内容：设计一个利用哈夫曼算法的编码和译码系统，可以接收从键盘输入的字符集大小、字符和权值信息

2、， 创建哈夫曼树生成哈夫曼编码并能对其进行解码。要求：1存储结构自定；2将生成的哈夫曼编码与等长编码进行比较，判断优劣；3给出动态演示过程（选作） 。1.2 总体结构本程序主要分为3 个模块（功能模块图见图1.1 ）：主模块，编码模块，译码模块。主模块：程序的主体部分，分别调用各个模块，实现各项功能。编码模块：对每个出现的字符进行编码。译码模块：将已有编码译成字符，使之可以直接被读出。哈夫曼编码 / 译码器主编译码码模模模块块块图 1.1 功能模块图1沈阳航空航天大学课程设计报告第2章算法分析2.1 核心算法思想哈夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有 n 棵只含有根结点的二叉树。

3、算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行 n 1 次合并，所以共产生 n 1 个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中一共有 2n1 个结点，其中 n 个结点是初始森林的 n 个孤立结点。并且哈夫曼树中没有度数为 1 的分支结点。我们可以利用一个大小为 2n-1 的一维数组来存储哈夫曼树中的结点。哈夫曼编码是可变字长编码。编码时借助哈夫曼树，也即带权路径长度最小的二叉树，来建立编码。译码的基本思想是：读文件中编码，并与原先生成的赫夫曼编码表比较，遇到相等时，即取出其

4、对应的字符存入一个新串中。2.2 算法结构定义结构体存储表示typedef structint weight;int parent,lchild,rchild;Htnode,*Hfmtree;/动态分配数组存储哈夫曼树typedef char *Hfmcode;/动态分配数组存储哈弗曼编码表2沈阳航空航天大学课程设计报告第 3章 详细设计3.1 功能流程此流程图为构造哈夫曼树的过程，输入字符的次数为权值对每个结点赋值，构造哈夫曼树，如图3.1开始以读入字符次数对各结点赋初值并令i=2n-1Yi 为 0N找出根结点权值最小和次小树s1,s2两树合并成新树n+ii 减 1结束图 3.1 流程图3沈

5、阳航空航天大学课程设计报告此流程图（图 3.2）为对字符进行哈夫曼编码的过程，将字符转化为哈夫曼编码。开始第一个字符，i=1Ni=nYN结点是否是根结点Y双亲结点的左结点是否等于该结点N将得到的编码存储Y记编码0记编码1i=i+1结束图 3.2 字符编码模块流程图4沈阳航空航天大学课程设计报告第 4章 系统实现4.1 错误分析在此程序调试过程中主要遇到以下几类问题：1、本程序运用了对文件进行操作，一定要注意在操作文件是文件的位置，我在做次程序是就是因为操作的文件位置错了导致程序无法正常运行。2、在函数内部有时需要多定义参数，注意参数的作用域， 而且注意传引用调用和传值调用的区别， 不能不正确的

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

7、下界面（图 4.3 ）供用户选择。图 4.3 程序运行截图选择操作 3 后，系统会显示用哈夫曼编码翻译成的字符，显示以下界面（图4.4 ）供用户选择图 4.4 程序运行截图选择操作 4 后，退出系统，显示以下界面（图4.5 ）6沈阳航空航天大学课程设计报告图 4.5 程序运行截图7沈阳航空航天大学课程设计报告参考文献1 严蔚敏 . 数据结构 (C 语言版 ). 清华大学出版社， 20072 谭浩强 .C 语言程序设计教程 . 高等教育出版社， 20063 苏仕华 . 数据结构课程设计 . 机械工业出版社， 20078沈阳航空航天大学课程设计报告附录源程序如下：#include#include#

8、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) /Select 函数，选出 HT 树到 a 为止，权值最小且 parent为 0 的 2 个节点int i,j,x,y;for(j=1;j=a;+j)if(HTj.parent=0)x=

9、j;break;for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=i;/选出最小的节点9沈阳航空航天大学课程设计报告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;void Hfmcoding(Hfmtree &HT,Hfmcode &HC,int n) /构建赫夫曼树HT，并求出 n10沈阳航空航天大学课程设计报告个字符的赫夫曼编码HCint i,start,c,f,

10、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)continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i)/ 初始化其余的结点HTi.ch=0;11沈阳航空航天大学课程设计报告HTi.

11、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.weight+HTp2.weight;HC=(Hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0;/- 从叶子到根逆向给出每个字符的哈夫曼编码-for(i=1;ich

12、oice;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沈阳航空航天大学课程设计报告for(i=1;i=n;i+)output_file(HTi.chHCi);output_file.close();printf( 赫夫曼树已经创建完毕，并且已经放入 hfmTree.txt 文件中 !n);else if(choice=2)/进行编码，并将字符

13、放入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(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)15沈阳航空航天大学课程设计报告output_fileHCj;br

14、eak;output_file.close();coutn;printf( 编码完毕，并且已经存入B.txt 文件！ n);input_file.open(B.txt);/ 从 B.txt 中读入编码，输出在终端if(!input_file)coutcant oen file!code;cout编码码值为： codeendl;input_file.close();else if(choice=3) /读入 B.txt 中的编码进行译码，将译出来的字符放入 Textfile.txt 中input_file.open(B.txt);if(!input_file)coutcant oen file!

15、h;input_file.close();output_file.open(Textfile.txt);if(!output_file)16沈阳航空航天大学课程设计报告coutcant oen file!endl;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)output_fileHTi.ch;k=k+strlen(HCi);break;output_file.close();input_file.op

16、en(Textfile.txt);if(!input_file)coutcant oen file!h;couthendl;17沈阳航空航天大学课程设计报告input_file.close();printf( 译码结束，字符已经存入Textfile.txt 文件中 !n);else if(choice=4)exit(0);else/如果选了选项之外的就让用户重新选择printf( 您没有输入正确的步骤，请重新输入！);18沈阳航空航天大学课程设计报告课程设计总结：通过近两周的课程设计使我对哈夫曼树以及哈夫曼编码译码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。在

17、做课设的过程中我也遇到了很多问题： 开始的时候，代码中有许多的错误，特别是有一个“无法找到文件”的错误让我束手无策， 最后还是屏蔽了定义的四个头文件然后慢慢地改正错误才让我又看到了希望。然后在实现文章的读入时，由于对文件不是太熟悉，只好翻开 C语言和 C+语言书本仿照其模式编写，但后来进入了死循环，最后的解决方式是在 main 函数里有一个控制语句使用不正确。我们遇到问题很正常， 说明我们掌握的知识还是太少不灵活， 并且这些错误也让我明白了一个道理- 细节决定成败。同时，对于编程者而言，思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。请教老师和同学也很重要， 毕竟对待同一问题我们会有不同的理解和分析，相互之间的交流也是一种学习方法的沟通。通过这次课程设计， 我看清楚了自己的编程功底和动手能力还不如人意， 这主要是平时实践太少的缘故。我想， 在即将到来的寒假中，我会努力尝试编写一些程序，争取提高自己的编程水平。我相信通过我的不断努力，我一定能收获更多果实。指导教师评语：指导教师 (签字)：年月日课程设计成绩19沈阳航空航天大学课程设计报告20