数据结构 基于哈夫曼树的知识进行编码和译码 课程设计 实验报告.doc

数 据 结 构 课 程 设 计设计题目： 基于哈夫曼树的知识进行编码和译码- 17 -课题名称基于哈夫曼树的知识进行编码和译码院 系年级专业学 号姓 名成 绩课题设计目的与设计意义1、课题设计目的：在当今这个科技飞速发展的时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码的应用和广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定，指向左子树的分支表示为0码，指向右子树的分支表示为1码。取每条路径上的0或1所排成的序列作为和各个对应字符的编码，称为哈夫曼编码。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码或译码。电报通信时传递文字的二进制码形式的字符串。但在传递信息时总希望总长度尽可能最短，即采用最短码。2、课题设计意义：作为学计算机专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试计算程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见。同时，师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。指导教师：年 月 日目 录一：课程设计的目的及意义- 1 -二：需求分析- 1 -三：项目设计- 2 -（1）设计思路及方案：- 2 -（2）模块的设计及介绍- 3 -（3）模块图及流程图- 6 -四：系统实现- 7 -（1）主调函数- 7 -（2）建立哈夫曼树- 7 -（3）对哈夫曼树进行编码- 9 -(4) 对哈夫曼树进行译码- 10 -五：系统调试- 11 -(1) 进入主界面- 11 -（2）建立哈夫曼树- 11 -（3）对哈夫曼树进行编码- 12 -（4）对哈夫曼树进行译码- 12 -六：实验总结- 13 -附录 源程序- 14 -参考文献：- 18 -一：课程设计的目的及意义1、课题设计目的：在当今这个科技飞速发展的时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码的应用和广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定，指向左子树的分支表示为0码，指向右子树的分支表示为1码。取每条路径上的0或1所排成的序列作为和各个对应字符的编码，称为哈夫曼编码。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码或译码。电报通信时传递文字的二进制码形式的字符串。但在传递信息时总希望总长度尽可能最短，即采用最短码。2、课题设计意义：作为学计算机专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试计算程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见。同时，师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。二：需求分析问题描述：假设用于通讯的电文仅由“a,b,c,d,e,f,g,h”8个字母组成，字母在电文中出现的频率分别为：7,19,2,6,32,3,21,10。试为这8个字母构造哈夫曼树进行哈夫曼编码并在编码成功后进行译码。测试数据：例如输入字符字符串的个数：8输入8字符串：abcdefgh输入对应字符出现的次数：7 19 2 6 32 3 21 10则显示效果如下：a 7.00 -1 -1 10b 19.00 -1 -1 12c 2.00 -1 -1 8d 6.00 -1 -1 9e 32.00 -1 -1 13f 3.00 -1 -1 8g 21.00 -1 -1 12h 10.00 -1 -1 10 5.00 2 5 9 11.00 8 3 11 17.00 0 10 11 28.00 9 7 13 40.00 1 6 14 60.00 11 4 14 100.00 12 13 -1对字符串进行编码得：a：1010b：00c：10000d：1001e：11f：10001g：01h：1011对字符串进行译码：输入二进制编码：11您输入的编码对应的字符为：e按0退出Press any key to continue三：项目设计（1）设计思路及方案：本课题是用最优二叉树即哈夫曼树来实现哈夫曼编码译码的功能。假设每种字符出现在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为（W1*L1）+（W2*W2）+（Wi*Li）。若将此对应到二叉树上，Wi为叶子结点，Li为叶子结点到根结点的路径长度。那么，（W1*L1）+（W2*W2）+（Wi*Li）恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一颗哈夫曼树，此构造过程称为哈夫曼编码。该项目设计将实现以下几项功能：1：构造哈夫曼树2：对哈夫曼树进行编码 3：对哈夫曼树进行译码。（2）模块的设计及介绍#includetypedef struct结构体定义；hufmtree;hufmtree tree20;typedef struct初始化；codetype;codetype code20;void HUFMTREE(int n)类型定义；for(循环)scanf(接收数据);printf(提示语:);for(循环)scanf(接收数据);for(循环)定义左右孩子及其双亲；for(循环)初始化；接收命令；for(循环) 处理命令；选出两个最小权值及保存次小权值；构造最小二叉树；printf(提示语);for(循环)输出哈夫曼数；提示：构造哈夫曼树HUFMCODE(参数)结点定义；printf(提示语);for(循环)定义类型；while(循环)初始化； 左子树用0标记； 右子树用1标记； 接收数据；for(循环)处理命令； 输出结果；提示：哈夫曼编码DECODE(参数)类型定义；printf(提示语);scanf(接收数据);for(循环)接受命令；printf(提示语:);printf(接收数据”);处理命令；提示：哈夫曼译码void main()定义类型；while(循环)界面友好化； scanf(接收数据);switch(传参数)接受命令；处理命令；printf(界面友好化);退出程序；（3）模块图及流程图哈夫曼树建立哈夫曼树哈夫曼编码哈夫曼译码结束统计字符串出现频率字符串个数建立哈夫曼树哈夫曼编码哈夫曼译码是否继续？操？程序作程序开始否是四：系统实现（1）主调函数void main()int n,m,j=1;while(j)printf(*n*哈夫曼树*n*n*构造哈弗曼树请按-1n*对哈弗曼树编码请按-2n*对哈弗曼树译码请按-3n); /*生成菜单*/ scanf(%d,&m);switch(m)case 1:printf(请输入字符的个数:); /*接收数据*/ scanf(%d,&n); HUFMTREE(n);break; /*建立哈夫曼树*/ case 2:HUFMCODE(tree,n);break; /*对哈夫曼树进行编码*/case 3:DECODE(tree,n); /*对哈夫曼树进行译码*/printf(*继续请按-1n*退出请按-0n);scanf(%d,&j); /*主函数*/（2）建立哈夫曼树hufmtree tree20;typedef structchar bits10; /*结构体定义*/int start;codetype;codetype code20;void HUFMTREE(int n)int i,j,p1,p2;float m1,m2; printf(请输入%d个字符:,n);getchar();for(i=0;in;i+)scanf(%c,&treei.ch); /*读入前n个结点的权值*/printf(请输入对应字符出现的次数:);for(i=0;in;i+)scanf(%f,&treei.weight);for(j=0;j2*n-1;j+)treej.lchild=-1;treej.rchild=-1; /*初始化*/treej.parent=-1;for(j=n;j2*n-1;j+) /*进行n-1次合并，产生n-1个新结点*/m1=1000;m2=1000;p1=p2=-1; for(i=0;ij;i+)if(treei.parent=-1)if(treei.weightm1) /*选出两个权值最小的根结点*/m2=m1; /*改变最小权、次小权及对应位置*/p2=p1;m1=treei.weight;p1=i; elseif(treei.weightm2)m2=treei.weight; /*改变次小权及位置*/p2=i;treej.weight=m1+m2;treej.lchild=p1; /*最小权根结点是新结点的左孩子*/treej.rchild=p2; /*次小权根结点是新结点的右孩子*/treep1.parent=j; treep2.parent=j;printf(您输入的字符构造的哈弗曼树为:n);for(i=0;i2*n-1;i+)printf(%ct%.2ft%dt%dt%dn,treei.ch,treei.weight,treei.lchild,treei.rchild,treei.parent);（3）对哈夫曼树进行编码HUFMCODE(hufmtree tree,int n)int i,c,p;codetype cd; /*定义结点类型*/printf(您输入的字符对应的编码为:n);for(i=0;in;i+)cd.start=n-1;c=i; /*从叶结点出发向上回溯*/p=treei.parent; while(p!=-1)cd.start-;if(treep.lchild=c)cd.bitscd.start=0; /*左子树生成代码为0*/elsecd.bitscd.start=1; /*右子树生成代码为1*/ c=p;p=treep.parent;codei=cd; /*第i+1个字符的编码存入codei*/ printf(%c:,treei.ch);for(;cd.startn-1;cd.start+)printf(%c,codei.bitscd.start);printf(n);(4)对哈夫曼树进行译码DECODE(hufmtree tree,int n)int i,j=0;char b10; /*结点定义*/i=2*n-2;printf(请输入二进制编码n);scanf(%s,b); /*接收输入数据 */for(j=0;bj!=0;j+)if(bj=0)i=treei.lchild; /*如是左子树则译码为0*/elsei=treei.rchild;if(treei.lchild=-1) /*如是右子树则译码为1*/printf(您输入的编码对应的字符为:);printf(%cn,treei.ch); /*如输出译码对应的字符*/if(treei.lchild!=-1) printf(输入有误!n); /*结束程序*/五：系统调试(1)进入主界面图5.1进入主界面（2）建立哈夫曼树图5.2建立哈夫曼树的结果（3）对哈夫曼树进行编码图5.3对哈夫曼树进行编码的结果（4）对哈夫曼树进行译码图5.4对哈夫曼树进行译码的结果六：实验总结程序分析： 本次哈夫曼编码译码器的课程实验做得还算成功，不仅仅在于程序能够正常运行，实现应有的功能，关键在于过程，在于小组成员的分工合作和一起纠错排错的过程，在完成程序的过程中才能真正理解面向对象和模块化设计的思想，关键在于这些函数代表的是一个个功能模块，任何一个模块出现问题或者模块之间的衔接出现问题都将导致程序运行的失败。哈夫曼编码译码器课程实验我完成了建立哈夫曼树，及对哈夫曼数的编码和译码功能结构体和类型的定义，以及void函数，HUFMCODE函数，DECODE函数的实现。在初始设计的时候，我体会到书写流程图的重要性，只有又一个清晰的设计思路才能事半功倍，分工明确，避免无效劳动或者在错误的编程方向上走弯路，也让大家明白自己在程序设计中的位置和职责。初始的创建是哈夫曼编码译码系统成功的关键，输出接点字符或者权重信息，作为检验，对验证和纠错起到了非常大的作用。在适当的地方调用它们，运行时可以看到验证编写程序的正确性； 实验心得：通过这段时间的课程设计使我对哈夫曼树以及哈夫曼编码和译码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。首先我谈谈我在设计期间我遇到的难点。开始的时候，代码中有许多的错误，特别是有一个“无法找到文件”的错误让我束手无策，最后还是屏蔽了定义的四个头文件然后慢慢地改正错误才让我又看到了希望。然后在实现文章的读入时，由于对文件不是太熟悉，只好翻开C语言书本仿照其模式编写，但后来进入了死循环，最后的解决方式是把main函数里的一个dowhile循环去掉。许多的错误让我明白了一个道理-细心是非常重要的。同时，对于编程者而言，思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。请教老师也很重要，因为毕竟我们是新手，对于某些问题很难弄清楚。而且，某些错误对于我们来说有时候想半天都弄不来，但老师几下下就搞好了，这样就更加有效地节约了时间。这次课程设计不但让我学得了一些编程知识，还学会了系统的做一份课程设计报告，学会了如何截图，学会了如何更好的画流程图，明白了做事情只有认真，才能真正做得更好！这段时间里，可谓是酸甜苦辣都尝过。有时，为了一个错误而焦头烂额；有时，编程熬夜到凌晨两点；有时，连吃饭都是匆匆了事；但一旦程序运行成功，总会让我兴奋不已。通过这次课程设计，我看清楚了自己的编程功底和动手能力还不如人意，这主要是平时实践太少的缘故。我想，在未来的暑假中，我会努力尝试编写一些程序。虽然我们信息管理专业的学生，但现在编程的能力太差了，毕竟多精通一门技术总是好事。在这个程序中，还有许多地方值得完善。比如，读出文本只能是大写的文档，空格和小写不能识别，更不用说是任意的ASC码字符了。由于时间问题，暂时不能实现了。我想在暑假里好好研究这个问题。附录 源程序 #includetypedef structfloat weight;int lchild,rchild,parent;char ch;hufmtree;hufmtree tree20;typedef structchar bits10;int start;codetype;codetype code20;void HUFMTREE(int n)int i,j,p1,p2;float m1,m2; printf(请输入%d个字符:,n);getchar();for(i=0;in;i+)scanf(%c,&treei.ch);printf(请输入对应字符出现的次数:);for(i=0;in;i+)scanf(%f,&treei.weight);for(j=0;j2*n-1;j+)treej.lchild=-1;treej.rchild=-1;treej.parent=-1;for(j=n;j2*n-1;j+)m1=1000;m2=1000;p1=p2=-1;for(i=0;ij;i+)if(treei.parent=-1)if(treei.weightm1)m2=m1;p2=p1;m1=treei.weight;p1=i;elseif(treei.weightm2)m2=treei.weight;p2=i;treej.weight=m1+m2;treej.lchild=p1;treej.rchild=p2;treep1.parent=j;treep2.parent=j;printf(您输入的字符构造的哈弗曼树为:n);for(i=0;i2*n-1;i+)printf(%ct%.2ft%dt%dt%dn,treei.ch,treei.weight,treei.lchild,treei.rchild,treei.parent);HUFMCODE(hufmtree tree,int n)int i,c,p;codetype cd;printf(您输入的字符对应的编码为:n);for(i=0