数据结构课程设计电文编码译码哈夫曼编码

1、福建农林大学计算机与信息学院数据结构课程设计设计：哈夫曼编译码器姓名：韦邦权专业： 2013 级计算机科学与技术学号： 13224624班级： 13052316完成日期： 2013.12.2819哈夫曼编译码器一、需求分析在当今信息爆炸时代， 如何采用有效的数据压缩技术节省数据文 件的存储空间和计算机网络的传送时间已越来越引起人们的重视， 哈 夫曼编码正是一种应用广泛且非常有效的数据压缩技术。 哈夫曼编码 是一种编码方式， 以哈夫曼树即最优二叉树， 带权路径长度最小的 二叉树，经常应用于数据压缩。 哈夫曼编码使用一张特殊的编码表将 源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之

2、处在于，它是根据每一个源字符出现的估算概率而建立起来的 （出现 概率高的字符使用较短的编码，反之出现概率低的则使用较长的编 码，这便使编码之后的字符串的平均期望长度降低， 从而达到无损压 缩数据的目的）。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用 于通信的二进制编码称为哈夫曼编码。 树中从根到每个叶子都有一条 路径，对路径上的各分支约定：指向左子树的分支表示“ 0”码，指 向右子树的分支表示“ 1”码，取每条路径上的“ 0”或“ 1”的序列 作为和各个叶子对应的字符的编码， 这就是哈夫曼编码。 哈夫曼译码 输入字符串可以把它编译成二进制代码， 输入二进制代码时可以编译 成字符串。二、设计要求

3、对输入的一串电文字符实现哈夫曼编码， 再对哈夫曼编码生成的 代码串进行译码， 输出电文字符串。 通常我们把数据压缩的过程称为 编码，解压缩的过程称为解码。 电报通信是传递文字的二进制码形式 的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短 码。假设每种字符在电文中出现的次数为 Wi,编码长度为Li，电文 中有n种字符，则电文编码总长度为刀 WiLi。若将此对应到二叉树上， Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，刀 WiLi 恰好为二叉树上带权路径长度。因此 ,设计电文总长最短的二进制 前缀编码,就是以 n 种字符出现的频率作权,构造一棵哈夫曼树,此 构造过程称为哈

4、夫曼编码。 设计实现的功能： (1) 哈夫曼树的建立； (2) 哈夫曼编码的生成； (3) 编码文件的译码。三、概要设计哈夫曼编 译码器的主要功能是先建立哈夫曼树,然后利用建好 的哈夫曼树生成哈夫曼编码后进行译码 。在数据通信中,经常需要将传送的文字转换成由二进制字符0、1 组成的二进制串,称之为编码。构造一棵哈夫曼树,规定哈夫曼树 中的左分之代表 0,右分支代表 1,则从根节点到每个叶子节点所经 过的路径分支组成的 0 和 1的序列便为该节点对应字符的编码, 称之 为哈夫曼编码。最简单的二进制编码方式是等长编码。 若采用不等长编码, 让出 现频率高的字符具有较短的编码, 让出现频率低的字符具

5、有较长的编 码,这样可能缩短传送电文的总长度。 哈夫曼树课用于构造使电文的 编码总长最短的编码方案。设计包含的几个方面： 哈夫曼树的建立赫夫曼树的建立由赫夫曼算法的定义可知， 初始森林中共有 n 棵只含 有根结点的二叉树。 算法的第二步是： 将当前森林中的两棵根结点权 值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减 少一棵树，产生一个新结点。显然要进行 n 1 次合并，所以共产生 n 1 个新结点，它们都是具有两个孩子的分支结点。由此可知，最 终求得的哈夫曼树中一共有 2n1 个结点，其中 n 个结点是初始森林 的 n 个孤立结点。 并且哈夫曼树中没有度数为 1 的分支结点。 我

6、们可 以利用一个大小为 2n-1 的一维数组来存储赫夫曼树中的结点。定义 的结构体类型如下： typedef structchar data;/ 结点字符int weight; int parent; int lchild; int rchild;/权值/双亲结点 /左孩子结点 /右孩子结点HTNode; 哈夫曼编码要求电文的哈夫曼编码， 必须先定义哈夫曼编码类型， 根据设计要求 和实际需要定义的类型如下：typedet struct char cdN; / 存放编码的数组int start; / 从 start 开始读 cd 中的哈夫曼编码 Hcode; / 编码结构体类型 代码文件的译码译

7、码的基本思想是： 读文件中编码， 并与原先生成的哈夫曼编码表比 较，遇到相等时，即取出其对应的字符存入一个新串中。四、详细设计字符统计int jsq(char *s,int cnt,char str)char *p;int i,j,k;for(i=1;i<=256;i+)cnti=0;for(p=s;*p!='0'p+)k=*p; cntk+;j=0;for(i=1,j=0;i<=256;i+) if(cnti!=0) j+;return j;哈夫曼树的算法void CreateHT(HTNode ht,int n,char str,int cn) for(int

8、input=1;input<=256;input+) strinput=input;int l=0;for(int output=1;output<=256;output+) if(cnoutput !=0)htl.data=stroutput;的字母依次存入数组 hthtl.weight=cnoutput;l+;/创建哈夫曼树函数/按字母顺序将出现int i,k,lnode,rnode;int min1,min2;for (i=0;i<2*n-1;i+)hti.parent=hti.lchild=hti.rchild=0;for (i=n;i<2*n-1;i+)/ 所

9、有结点的相关域置初值 0 /构造哈夫曼树min1=min2=MAX;lnode=rnode=0;for (k=0;k<=i-1;k+)/int 的范围是 -32768-32767if (htk.parent=0)if (htk.weight<min1)min2=min1;rnode=lnode;min1=htk.weight;lnode=k;else if (htk.weight<min2)min2=htk.weight;rnode=k;htlnode.parent=i;htrnode.parent=i;/只在尚未构造二叉树的结点中查找/ 比 min1 小时/比 min1 大

10、，比 min2 小/ 两个最小节点的父节点是 ihti.weight=htlnode.weight+htrnode.weight; 为两个最小节点权值之和/两个最小节点的父节点权值hti.lchild=lnode;hti.rchild=rnode;哈夫曼编码/父节点的左节点和右节点void CreateHCode(HTNode ht,HCode hcd,int n) hc.start=n; c=i;/初始位置/从叶子结点 hti 开始上溯int i,p,c;HCode hc;for (i=0;i<n;i+)/根据哈夫曼树求哈夫曼编码p=hti.parent;while (p!=0) /

11、循序直到树根结点结束循环hc.cdhc.start-=(htp.lchild)=c?'0':'1'/ 左孩子记为 0，右孩子记为 1c=p;p=htp.parent; hc.start+; hcdi=hc;/与上句 c=i;p=hti.parent 同义，促进循环/start 指向哈夫曼编码 hc.cd 中最开始字符/lnode 和 rnode 记录最小权值的两个结点位置 /选出每次外层循环最小权值的两个结点 哈夫曼译码void deHCode(HTNode ht,HCode hcd,int n,char str)/ 译码函数printf(" 输出译码

12、结果为 :n");int i,j,k,x,m=0;char codeMAX;for (i=0;i<MAX;i+)for (j=0;j<n;j+)if(stri=htj.data) / 循环查找与输入字符相同的编号，相同的就 输出这个字符的编码for (k=hcdj.start;k<=n;k+)codem=hcdj.cdk;/ 将输出的编码赋值到数组中m+;break;/ 输出完成后跳出当前 for 循环codem='#'/把要进行译码的字符串存入 code 数组中while(code0!='#')for (i=0;i<n;i+)

13、m=0;for (k=hcdi.start,j=0;k<=n;k+,j+)if(codej=hcdi.cdk) m+;if(m=j) 串个数相等时则输出这个的 data 数据printf("%c",hti.data); for(x=0;codex-j!='#'x+) 删除codex=codex+j;/m 为想同编码个数的计数器/j 为记录所存储这个字符的编码个数/当有相同编码时 m 值加 1/当输入的字符串与所存储的编码字符/ 把已经使用过的 code 数组里的字符串删除j个数，往前移动j位printf("n"); 主函数void

14、main()char stMAX,sstMAX;int cn257;int n,i;printf(" 请输入字符串 (任意字符 ):n"); gets(st);n=jsq(st,cn,sst);/99for(i=0;i<99;i+)ssti=sti;/HTNode htM;HCode hcdN;CreateHT(ht,n,st,cn);CreateHCode(ht,hcd,n); outputHCode(ht,hcd,n); editHCode(ht,hcd,n,sst); deHCode(ht,hcd,n,sst);五、调试输出哈夫曼编码输入字符串（任意字符兴Not

15、hingis inpocsible t输岀哈夫曼编码二11r11100hl11101b11110emuSTh63011110I6010n6011n610001011P0101s100t1010输出编码结果输出译码结果THIS PROGRAM I£ MV FRAUORITE输岀編码结果为：1011010100100101011110901101110010110010111110001011100101011111190001101110111 01100910001110001111011100001113110101 0110110110111101111*111100011300

16、1111106091 110011110001B101101111010输出编译结果为：THIS PROGRAM IS ttV FflAUOEITEPress： any key to cont inueM附录源程序#i nclude <stdio.h> #in elude <stri ng.h> #defi ne N 256 #define M 2*N-1 #defi ne MAX 32767/gets ()函数需要/义用N表示50叶节点数/用M表示节点总数当叶节点数位n时总节点数为2n-1typedef structchar data; int weight; int

17、 pare nt; int lchild; int rchild;HTNode;/结点字符/权值/双亲结点左孩子结点/右孩子结点typedef structchar cdN;/存放哈夫曼码int start;/从 start 开始读 cd 中的哈夫曼码HCode;/int jsq(char *s,int cnt,char str)char *p;int i,j,k;for(i=1;i<=256;i+)cnti=0;for(p=s;*p!='0'p+)k=*p;cntk+;j=0;for(i=1,j=0;i<=256;i+)if(cnti!=0)j+;return j

18、;/void CreateHT(HTNode ht,int n,char str,int cn)/ 创建哈夫曼树函数for(int input=1;input<=256;input+)strinput=input;int l=0;for(int output=1;output<=256;output+)if(cnoutput !=0)htl.data=stroutput;/按字母顺序将出现的字母依次存入数组 hthtl.weight=cnoutput;l+;int i,k,lnode,rnode;int min1,min2;for (i=0;i<2*n-1;i+)hti.pa

19、rent=hti.lchild=hti.rchild=0;/ 所有结点的相关域置初值 0for (i=n;i<2*n-1;i+)min1=min2=MAX;/构造哈夫曼树/int 的范围是 -32768-32767lnode=rnode=0;for (k=0;k<=i-1;k+)/lnode 和 rnode 记录最小权值的两个结点位置/选出每次外层循环最小权值的两个结点if (htk.parent=0)if (htk.weight<min1)min2=min1;rnode=lnode;min1=htk.weight;lnode=k;else if (htk.weight<

20、;min2)min2=htk.weight;rnode=k;/只在尚未构造二叉树的结点中查找/ 比 min1 小时/比 min1 大，比 min2 小htlnode.parent=i;htrnode.parent=i;hti.weight=htlnode.weight+htrnode.weight;为两个最小节点权值之和/ 两个最小节点的父节点是 i/两个最小节点的父节点权值hti.lchild=lnode;hti.rchild=rnode;/父节点的左节点和右节点void CreateHCode(HTNode ht,HCode hcd,int n)int i,p,c;HCode hc;for

21、 (i=0;i<n;i+) hc.start=n; c=i; p=hti.parent; while (p!=0) /根据哈夫曼树求哈夫曼编码/初始位置/从叶子结点 hti 开始上溯/ 循序直到树根结点结束循环hc.cdhc.start-=(htp.lchild)=c?'0':'1' 子记为 1/ 左孩子记为 0，右孩c=p; p=htp.parent;hc.start+;hcdi=hc;/与上句 c=i;p=hti.parent 同义，促进循环/start 指向哈夫曼编码 hc.cd 中最开始字符/void outputHCode(HTNode ht,H

22、Code hcd,int n) int i,k;printf(" 输出哈夫曼编码 :n");for (i=0;i<n;i+)printf(" %c:t",hti.data);for (k=hcdi.start;k<=n;k+)printf("%c",hcdi.cdk);printf("n");/void editHCode(HTNode ht,HCode hcd,int n,char str) int i,j,k;printf("n 输出编码结果 :n"); for (i=0;i&l

23、t;MAX;i+) for (j=0;j<n;j+) if(stri=htj.data) 输出这个字符的编码/输出哈夫曼编码的列表/输出 data 中的所有数据，/输出所有 data 中数据的编码/从初最开始的字符起输出/编码函数/循环查找与输入字符相同的编号，相同的就for (k=hcdj.start;k<=n;k+)printf("%c",hcdj.cdk);/ 输出完成后跳出当前 for 循环 break;printf("n");/译码函数void deHCode(HTNode ht,HCode hcd,int n,char str) printf(" 输出译码结果为 :n");int i,j,k,x,m=0; char codeMAX;for (i=0;i<MAX;i+)for (j=0;j<n;j+)if(stri=htj.data