哈夫曼树编码译码试验报告

1、数据结构课程设计设计题目：哈夫曼树编码译码课题名称哈夫曼树编码译码院系年级专业学号姓名成绩1、课题设计目的：在当今信息爆炸时代,如何釆用有效的数据压缩技术节省数据文 件的存储空间和计算机网络的传送时间己越來越引起人们的重视, 哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术.哈夫曼 编码是一种编码方式,以哈夫曼树一即最优二义树,带权路径长度 最小的二叉树,经常应用于数据压缩.哈弗曼编码使用一张特殊的 编码表将源字符例如某文件中的一个符号进行编码.这张编码 表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立 起来的.课题设计目的与设计意义2、课题设计意义：哈夫曼编码的应用很广泛,利用哈

2、夫曼树求得的用于通信的二进 制编码称为哈夫曼编码.树中从根到每个叶子都有一条路径,对路 径上的各分支约定：指向左子树的分支表示“0码,指向右子树的 分支表示“1码,取每条路径上的“0或“1的序列作为和各个 叶子对应的字符的编码,这就是哈夫曼编码.哈弗曼译码输入字符 串可以把它编译成二进制代码,输入二进制代码时可以编译成字符 串.指导教师:第一章需求分析 1第二章设计要求第三章概要设计1其主要流程图如图1T所示.32设计包含的几个方面4第四章详细设计41哈夫曼树的存储结构描述为：42哈弗曼编码53哈弗曼译码74主函数85显示局部源程序： 8第五章调试结果10第六章心得体会12第七章参考文献12附

3、录：12第一章需求分析在当今信息爆炸时代,如何釆用有效的数据压缩技术节省数据文件的存储空 间和计算机网络的传送时间己越來越引起人们的重视,哈夫曼编码正是一种应用 广泛且非常有效的数据压缩技术.哈夫曼编码是一种编码方式,以哈夫曼树一即 最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩.哈弗曼编码使 用一张特殊的编码表将源字符例如某文件中的一个符号进行编码.这张编码 表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起來的出现 概率高的字符使用较短的编码,反之出现概率低的那么使用较长的编码,这便使编 码之后的字符串的平均期望长度降低,从而到达无损压缩数据的目的.哈夫曼 编码的应用很

4、广泛,利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编 码.树中从根到每个叶子都有一条路径,对路径上的各分支约定：指向左子树的 分支表示“0码,指向右子树的分支表示“1码,取每条路径上的“0或“1 的序列作为和各个叶子对应的字符的编码,这就是哈夫曼编码.哈弗曼译码输入 字符串可以把它编译成二进制代码,输入二进制代码时可以编译成字符串.第二章设计要求对输入的一串电文字符实现哈夫曼编码,再对哈夫曼编码生成的代码串进行 译码,输出电文字符串.通常我们把数据压缩的过程称为编码,解压缩的过程称 为解码.电报通信是传递文字的二进制码形式的字符串.但在信息传递时,总希 望总长度能尽可能短,即釆用最短码.假

5、设每种字符在电文中出现的次数为Wi, 编码长度为Li,电文中有n种字符,那么电文编码总长度为ZWiLio假设将此对应 到二叉树上,Wi为叶结点的权,Li为根结点到叶结点的路径长度.那么,LWiLi 恰好为二叉树上带权路径长度.因此,设计电文总长最短的二进制前缀编码, 就是以n种字符出现的频率作权,构造一棵哈夫曼树,此构造过程称为哈夫曼编 码.设计实现的功能：1哈夫曼树的建立；2哈夫曼编码的生成；3编 码文件的译码.9第三章概要设计哈夫曼编译码器的主要功能是先建立哈夫曼树,然后利用建好的哈夫曼树 生成哈夫曼编码后进行译码.在数据通信中,经常需要将传送的文字转换成由二进制字符0、1组成的二 进制串

6、,称之为编码.构造一棵哈夫曼树,规定哈夫曼树中的左分之代表0,右 分支代表1,那么从根节点到每个叶子节点所经过的路径分支组成的0和1的序列 便为该节点对应字符的编码,称之为哈夫曼编码.最简单的二进制编码方式是等长编码.假设采用不等长编码,让出现频率高的 字符具有较短的编码,让出现频率低的字符具有较长的编码,这样可能缩短传送 电文的总长度.哈夫曼树课用于构造使电文的编码总长最短的编码方案.(1)其主要流程图如图1-1所示.结束2设计包含的几个方面：哈夫曼树的建立哈夫曼树的建立由哈夫曼算法的定义可知,初始森林中共有n棵只含有根结点的 二叉树.算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树

7、,合并 成一棵新的二叉树；每合并一次,森林中就减少一棵树,产生一个新结点.显然 要进行n1次合并,所以共产生n1个新结点,它们都是具有两个孩子的分支 结点.由此可知,最终求得的哈夫曼树中一共有2nl个结点,其中n个结点是 初始森林的n个孤立结点.并且哈夫曼树中没有度数为1的分支结点.我们可以 利用一个大小为211-1的一维数组來存储哈夫曼树中的结点. 哈夫曼编码要求电文的哈夫曼编码,必须先定义哈夫曼编码类型,根据设计要求和实际需要 定义的类型如下：tvpedet stmct char ch; /存放编码的字符charbitsN+l;/存放编码位串mt len; /编码的长度CodeNode;

8、/编码结构体类型 代码文件的译码译码的根本思想是：读文件中编码,并与原先生成的哈夫曼编码表比拟,遇到相 等时,即取出其对应的字符存入一个新串中.第四章详细设计1哈夫曼树的存储结构描述为：define N 50 /叶子结点数define M 2 *N-1 哈夫曼树中结点总数tvpedef stmct mt weight; 叶子结点的权值mt lcluld, rchild, parent; /左右孩子及双亲指针HTNode; /树中结点类型tvpedef HTNode HuffiiianTieeM+1 ;哈弗曼树的算法void CreateHTHTNode ht,iiit n调用输入的数组 ht,

9、和节点数 nmt iklnodgmode;mt inuihniin2;for (i=0;i<2*n-l;i+)hti .paient=hti .lcliild=hti .rchild=-l;/所有结点的相关域置初值-1for (i=n;i<2*n-l;i+)min 1 =min2=32767; lnode=rnode=-l;for (k=0:k<=i-l;k+)if (htk.parent=-l)if (htk. weight<niHi 1)构造哈夫曼树/mt 的范怜I 是-3276832767/Inode和inode记录最小权值的两个结点位置/只在尚未构造二叉树的结点

10、中查找假设权值小于最小的左节点的权值niiii2=niuil ;rnode=lnode;min 1 =htk .weight;hiode=k;else if (htk.weight<niui2)niiii2=htk .weight;rnode=k;htliiode .paient=i;htrnode .paient=i;hti .weight=htliiode .weight+htrnode .weight;为两个最小节点权值之和hti .lcliild=lnode 4iti .rchild=mode;(2)哈弗曼编码void CreateHCode(HTNode ht,HCode hc

11、d,int n)两个最小节点的父节点是i两个最小节点的父节点权值父节点的左节点和右节点HCode he;for (i=0;i<n;i+)/根据哈夫曼树求哈夫曼编码hc.stail=n;c=i; f=hti .parent:循序直到树根结点结束循环if (htf.lchild=c)hc.cdhc start-=O;elsehc.cdhc.start='r；c=f;f=htf.paient;hc.stait+；hcdi=hc;void DispHCode(HTNode ht,HCode hcdjnt n)mt i,k;输出哈夫曼编码:n)；for (i=0;i<n;i+)pri

12、ntf(M%c:t'hti.data);for (k=hcdi.start;k<=n;k+)prmtf(H%c'hcdi.cdk);prmtf(n)；void editHCode(HTNode ht,HCode hcd.iiit n)char stnngMAXSIZE;mt i,j,k;scanf(s",stnng);pnntf(Hn输出编码结果:n");for (i=0;stimgi !='#,;i+)处理左孩子结点处理右孩子结点/stall指向哈夫曼编码hc.cd中最开始字符输出哈夫曼编码的列表输出data中的所有数据,即A-Z/输岀所有d

13、ata中数据的编码编码函数/把要进行编码的字符串存入suing数组中/#为终止标志for (j=0j<nj+)if(strmgi=htj .data)就输出这个字符的编码for (k=hcd j .start;k<=n;k+) pimtf("%c",hcdj.cdk); break;(3)哈弗曼译码void deHCode(HTNode ht,HCode hcd,iiit n)char codeMAXSIZE;int ij 丄k 皿x；scanf(s,code);while(code0 !=护)for (i=0;i<n;i+)m=0:for (k=hcdi

14、. start j=0 ;k<=n;k+,j+) if(codej=hcdi.cdk)m卄；if(m=j)串个数相等时那么输出这个的data数据/循环查找与输入字符相同的编号,相同的输出完成后跳出当前for循坏译码函数把要进行译码的字符串存入code数组中/m为想同编码个数的计数器/J为记录所存储这个字符的编码个数当有相同编码时m值加1当输入的字符串与所存储的编码字符prmtf(H%cH,hti.data);for(x=0;codex-l!='#*;x-H-)把已经使用过的code数组里的字符串删除13codex=codex4j;(4)主函数void main()iiit n=2

15、6j;chai orz5back,flag= 1;chai sU=AB,CT>T7F,GBT/r：KT?vr,OP,Q,R,STV；V7W,；XrY,；Z,;/初始化intfhum=186,64,13,22,32,103,21,15,47,57丄2,32,20,57,63)5 丄4&51,80,23,8,18,1,16;/初始化HTNode htM;HCode hcdN;for (i=0;i<n;i+)建立结构体建立结构体把初始化的数据存入ht结构体中hti.data=stii;hti .weight=fiiumi;while (flag)菜单函数,当flag为0时跳出循环

16、(5)显示局部源程序：pnntfC'iT); pnntfp pnntfp'u pnntfp'u pnntfp'u pnntfp'u pnntfp pnntffE)； pnntfp*)* 1显示编码*");*2进行编码*")；* 3进行译码*n);* 4退出* *»请输入选择的编号鋼；scanf(c",&orz);switch(orz)case Acase 'A*:svstem(nclsH);清屏函数CreateHT(ht.n);CreateHCode(htJicd.n);DispHCode(htJi

17、cd.n);pnntf("n按任意键返回.)； getchQ;system(HclsH);break;case b:case Bisystem(HclsH);pnntf(请输入要进行编码的字符串(以特结束):n)；editHCode(htJicd,n);pnntf("n按任意键返回.)； getchQ;system(HclsH);break;case *c*:case 9C:system(HclsH);DispHCode(htJicd.n);pnntfC*请输入编码(以#结束):n)；deHCode(htJicd.n);pnntf("n按任意键返回.)； getc

18、hQ;system(HclsH);break;case'd*:caseflag=O;break;default:system(HclsH);第五章调试结果进入主菜单:Progra> Fileslicrosoft Visual StudioMyPro ject sdf saDebugdf sa.-*A显示编码*B进行编码*C进行诺箱*D退岀*请输入选择的编号:选A时的显示结果选择B时的显示结果I:0001J:0111K：011001000L：011001011M：10111N：1100100：1000P：1001Q：011011R：011001001S：0010T：0011U：11

19、01U：00001W：0110011X：110001V：011001010Z：110000幘输入编码以诞吉東:1111010#AB按任意键返回*C: Progra> Fileslicrosoft Visual StudioMyProjectsdf saDebugdf sa.荫输入要进行编码的字符串以#结東:VUDtt出编码结果：011001010110100000按任意键返回选C时的显示结果11第六章心得体会通过这次课程设计,让我对一个程序的数据结构有更全面更进一步的熟悉, 根据不同的需求,采用不同的数据存储方式,不一定要用栈,二叉树等高级类型, 有时用根本的一维数组,只要运用得当,也能

20、到达相同的效果,其至更佳,就如 这次的课程设计,通过用for的多重循环,舍弃多余的循环,提升了程序的运行 效率.在编写这个程序的过程中,我复习了之前学的根本语法,哈弗曼树最小路 径的求取,哈弗曼编码及译码的应用范围,程序结构算法等一系列的问题它使我 对数据结构改变了看法.在这次设计过程中,表达出自己单独设计模具的水平以 及综合运用知识的水平,体会了学以致用、突出自己劳动成果的喜悦心情,也从 中发现自己平时学习的缺乏和薄弱环节,从而加以弥补.第七章参考文献11徐孝凯编著,?数据结构课程实验?,清华大学出版2002年第一版2 张乃笑编著,?数据结构与算法?,电子工业出版社2004年10月附录： 源

21、程序如下：#include <stdio.h>#include <stdlib.h># iiiclude<conio.h>#include <stnng.h>define N 50#define M 2*N-13 严蔚敏?数据结构?C语言版清华大学出版社要用system函数要调用的头文件用getchQ要调用的头文件义用N表示50叶节点数用M表示节点总数 当叶节点数位n时总节点数为2n-ldefine MAXSIZE 100tvpedef stmctchar data; mt weight; mt parent; mt lcluld; mt rcl

22、uld;HTNode;/结点值权值双亲结点左孩子结点右孩子结点tvpedef stmctchar cdN;mt start;HCode;存放哈夫曼码从start开始读cd中的哈夫曼码void CreateHT(HTNode ht,mt n) mt i,k、lnode、mode;mt innihniin2;调用输入的数组ht口和节点数n构造哈夫曼树/mt 的范閑是-3276832767/Inode和inode记录最小权值的两个结点位置/只在尚未构造二叉树的结点中查找假设权值小于最小的左节点的权值两个最小节点的父节点是1两个最小节点的父节点权值父节点的左节点和右节点for (i=0;i<2*

23、n-l;i+)hti .parent=hti .lcliild=hti .rchild=-l;所有结点的相关域置初值 1for (i=n;i<2*n-l;i+)min 1 =min2=32767; lnode=rnode=-l;for (k=0;k<=i-l;k+)if (htk.parent=-l)if (htk. weight<niHi 1)niiii2=niuil ;rnode=lnode; min 1 =htk .weight;hiode=k;else if (htk.weight<niui2)niiii2=htk .weight;rnode=k;htliiod

24、e .parent=i;htrnode .parent=i;hti .weight=htliiode .weight+htrnode .weight;为两个最小节点权值之和hti.lcliild=lnodeiti.rchild=mode;19void CreateHCode(HTNode ht,HCode hcd,mt n)iiit i,f,c;HCode he;for (i=0;i<n;i+)hc.stail=n;c=i;f=hti .parent;wliileif (htf.lcluld=c)hc.cd he. start-=*0,;elsehc.cdhc.startr；c=f;f=

25、htf.paient;hc.stait+；hcdi=hc;void DispHCode(HTNode ht,HCode hcdjnt n)mt i,k;pimtfC 输出哈夫曼编码:n)；for (i=0;i<n;i+)printf(%c:t",hti.data);for (k=hcdi.start;k<=n;k+)根据哈夫曼树求哈夫曼编码循序直到树根结点结束循环处理左孩子结点/处理右孩子结点/start指向哈夫曼编码hc.cd中最开始字符输出哈夫曼编码的列表输出data中的所有数据,即A-Z/输出所有data中数据的编码pimtf("%c",hcdi

26、.cdk);prmtf(n)；void editHCode(HTNode ht,HCode hcd.iiit n) 编码函数char string MAXSIZE;int i,j,k;scanfV%s,stnng);printf(n输出编码结果:n");for (i=0;stimgi ?='#'i+)for (j=Oj<nj+)if(stringi=htj .data)就输出这个字符的编码for (k=hcd j. start ;k<=n;k+) printfC%c",hcdjcdk);break;把要进行编码的字符串存入suing数组中/#为终

27、止标志/循环查找与输入字符相同的编号,相同的/输出完成后跳出当前for循坏void deHCode(HTNode ht,HCode hcd,iiit n) char codeMAXSIZE;intscanfC%s,code);while(code0 !=的for (i=0;i<n;i+)m=0:for (k=hcdi. startj=O ;k<=n;k+,j+)译码函数把要进行译码的字符串存入code数组中/m为想同编码个数的计数器/J为记录所存储这个字符的编码个数if(code j=hcdi.cdk)当有相同编码时m值加1m+；if(m=j)当输入的字符串与所存储的编码字符串个数相等时那么输出这个的data数据pimtf("%c",hti.data);for(x=0;codex-l!='#*;x-H-)把已经使用过的code数组里的字符串删除codex=codex-Fj;void main()iiit n=26j;chai orz5back,fla