哈夫曼树编码译码实验资料报告材料

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

2、夫曼树求得的用于通信的二进 制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路 径上的各分支约定：指向左子树的分支表示“ 0”码，指向右子树的 分支表示“ 1”码，取每条路径上的“ 0”或“ 1”的序列作为和各个 叶子对应的字符的编码，这就是哈夫曼编码。哈弗曼译码输入字符 串可以把它编译成二进制代码，输入二进制代码时可以编译成字符 串。指导教师:目录第一章需求分析 1.第二章设计要求 1.第三章概要设计 2.(1) 其主要流程图如图 1-1 所示。 3.(2) 设计包含的几个方面 4.第四章 详细设计 4.(1)哈夫曼树的存储结构描述为： 4( 2)哈弗曼编码 5.( 3)哈弗曼译码

3、7.( 4)主函数 8.( 5 )显示部分源程序： 8.第五章调试结果 1.0.第六章心得体会 1.2.第七章参考文献 1.2.附录： 1.2.第一章 需求分析在当今信息爆炸时代， 如何采用有效的数据压缩技术节省数据文件的存储空 间和计算机网络的传送时间已越来越引起人们的重视， 哈夫曼编码正是一种应用 广泛且非常有效的数据压缩技术。 哈夫曼编码是一种编码方式， 以哈夫曼树即 最优二叉树， 带权路径长度最小的二叉树， 经常应用于数据压缩。 哈弗曼编码使 用一特殊的编码表将源字符 (例如某文件中的一个符号) 进行编码。 这编码表的 特殊之处在于， 它是根据每一个源字符出现的估算概率而建立起来的 (

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

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

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

7、夫曼树课用于构造使电文的编码总长最短的编码方案。(1)其主要流程图如图1-1所示否是否为根结点?是左子是否为空?否否是否为空是结点数是否大于1是l<2*N?开始/X”输出根结点和权值输出两子结点和已构造的结点双亲结点为两子结点之和将data和权值赋给ht此时编码为0调用SELECT函数编码为1计算根结点函数结束(2)设计包含的几个方面： 哈夫曼树的建立 哈夫曼树的建立由哈夫曼算法的定义可知， 初始森林中共有 n 棵只含有根结点的 二叉树。算法的第二步是： 将当前森林中的两棵根结点权值最小的二叉树， 合并 成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然 要进行 n1

8、 次合并，所以共产生 n1 个新结点，它们都是具有两个孩子的分支 结点。由此可知，最终求得的哈夫曼树中一共有2n1个结点，其中n个结点是 初始森林的 n 个孤立结点。 并且哈夫曼树中没有度数为 1 的分支结点。 我们可以 利用一个大小为 2n-1 的一维数组来存储哈夫曼树中的结点。 哈夫曼编码要求电文的哈夫曼编码， 必须先定义哈夫曼编码类型， 根据设计要求和实际需要 定义的类型如下： typedet struct char ch; / 存放编码的字符 char bitsN 1; / 存放编码位串 int len; / 编码的长度 CodeNode; / 编码结构体类型 代码文件的译码译码的基本

9、思想是： 读文件中编码， 并与原先生成的哈夫曼编码表比较， 遇到相 等时，即取出其对应的字符存入一个新串中。第四章 详细设计(1)哈夫曼树的存储结构描述为：#define N 50 / 叶子结点数#define M 2*N-1 / 哈夫曼树中结点总数typedef struct int weight; / 叶子结点的权值int lchild, rchild, parent; / 左右孩子及双亲指针HTNode; / 树中结点类型 typedef HTNode HuffmanTreeM+1;哈弗曼树的算法void CreateHT(HTNode ht,int n)/调用输入的数组 ht, 和节点

10、数 nint i,k,lnode,rnode;int min1,min2;/ 所有结点的相关域置初值 -1for (i=n;i<2*n-1;i+)min1=min2=32767;lnode=rnode=-1;/构造哈夫曼树/int 的围是 -32768 32767/lnode 和 rnode 记录最小权值的两个结点位置for (i=0;i<2*n-1;i+)hti.parent=hti.lchild=hti.rchild=-1;for (k=0;k<=i-1;k+)if (htk.parent=-1)if (htk.weight<min1)/只在尚未构造二叉树的结点中查

11、找/若权值小于最小的左节点的权值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;/ 两个最小节点的父节点是 ihti.weight=htlnode.weight+htrnode.weight; 为两个最小节点权值之和/两个最小节点的父节点权值hti.lchild=lnode;hti.rchild=rnode;(2)哈弗曼编码void CreateHCode(HTNode ht,HC

12、ode hcd,int n)/父节点的左节点和右节点int i,f,c;HCode hc;for (i=0;i<n;i+)/根据哈夫曼树求哈夫曼编码hc.start=n;c=i; f=hti.parent;while (f!=-1)if (htf.lchild=c)hc.cdhc.start-='0'elsehc.cdhc.start-='1'c=f;f=htf.parent;hc.start+; hcdi=hc;void DispHCode(HTNode ht,HCode hcd,int n) int i,k;printf(" 输出哈夫曼编码

13、: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 stringMAXSIZE;int i,j,k;scanf("%s",string); printf("n 输出编码结果 :n");for (i=0;stringi!=&#

14、39;#'i+)/循序直到树根结点结束循环/处理左孩子结点/处理右孩子结点/start 指向哈夫曼编码 hc.cd 中最开始字符/输出哈夫曼编码的列表/输出 data 中的所有数据，即 A-Z/输出所有 data 中数据的编码/编码函数/ 把要进行编码的字符串存入 string 数组中/#为终止标志for (j=0;j<n;j+)if(stringi=htj.data)就输出这个字符的编码for (k=hcdj.start;k<=n;k+)printf("%c",hcdj.cdk);break;(3)哈弗曼译码void deHCode(HTNode ht

15、,HCode hcd,int n)char codeMAXSIZE;int i,j,l,k,m,x;scanf("%s",code);while(code0!='#')for (i=0;i<n;i+)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-1!='#'x+)/循环查找与输入字符相同的编号， 相同的/ 输出完成后跳

16、出当前 for 循环/译码函数/把要进行译码的字符串存入code数组中/m 为想同编码个数的计数器/j 为记录所存储这个字符的编码个数/当有相同编码时m值加1/当输入的字符串与所存储的编码字符/把已经使用过的code数组里的字符串删除codex=codex+j;(4)主函数void main()int n=26,i;char orz,back,flag=1;char str='A','B','C','D','E','F','G','H','I',

17、9;J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' /初始化int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16;/建立结构体/建立结构

18、体/ 把初始化的数据存入 ht 结构体中/菜单函数，当 flag 为 0 时跳出循环/初始化HTNode htM;HCode hcdN;for (i=0;i<n;i+)hti.data=stri;hti.weight=fnumi;while (flag)(5)显示部分源程序：printf("n");printf("*");printf("n* 1显示编码*");printf("n* 2进行编码*");printf("n* 3进行译码*");printf("n* 4退出*n&quo

19、t;);printf("* *");printf("n");printf("请输入选择的编号:");scanf("%c",&orz);switch(orz)case 'a':case 'A':system("cls");CreateHT(ht,n);CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n); printf("n 按任意键返回 ."); getch();system("cls"

20、);break;case 'b':case 'B':system("cls");printf(" 请输入要进行编码的字符串 editHCode(ht,hcd,n);printf("n 按任意键返回 ."); getch();system("cls");break;case 'c':case 'C':system("cls");DispHCode(ht,hcd,n);printf(" 请输入编码 (以#结束 ):n"); d

21、eHCode(ht,hcd,n);printf("n 按任意键返回 ."); getch();system("cls");break;case 'd':case 'D':flag=0;break;default:/清屏函数（以#结束）:n"）;system("cls");第五章调试结果进入主菜单X 一 一 - ft B c DX二 X 二 一-马马马 T编译 片ZI仃出*显r一二-* 二 二y "C; Fro£iaa 7iLesXIicio»ort Visual

22、StudiDXVyPLOjeclsXdf saXDelmcVfifsa* -选A时的显示结果| - - *c；Frogia>FiLesMiciosort Visual StudioBjrProjeclsdfsaXPebucdfsa. |输出哈夫曼编码：白:111D-士 丄00 =011000D =0B0S0E =10110F；010G-1109丄丄H：匹丄丄010J :MUM1J：BillK：011301006L：011001 (MlM：loinH：1100100：1000P：1001Q：n：H11RR1 mi£ =saleT =QBHu =1101u =0&&

23、91V-01X0011X：刖d选择B时的显示结果选C时的显示结果、"c ； Pl ugiu Files Mice osQtt Ti?ual StudiDWyPLOjec-isXdrsxeVucdrsz.k:P；Q：V-请输入編码CM结束X misieit舉任意键返叵.0801 Bill 011081003 尬 1.丄 901011 10111 113S10 1009 ieai e>i丄e>丄丄 unutntM0811 1101 09091 0113011 110901 811301018 1 10P»fW第六章 心得体会 通过这次课程设计，让我对一个程序的数据结

24、构有更全面更进一步的认识， 根据不同的需求， 采用不同的数据存储方式， 不一定要用栈，二叉树等高级类型， 有时用基本的一维数组，只要运用得当，也能达到相同的效果，甚至更佳，就如 这次的课程设计，通过用 for 的多重循环，舍弃多余的循环，提高了程序的运行 效率。在编写这个程序的过程中， 我复习了之前学的基本语法， 哈弗曼树最小路 径的求取， 哈弗曼编码及译码的应用围， 程序结构算法等一系列的问题它使我对 数据结构改变了看法。 在这次设计过程中， 体现出自己单独设计模具的能力以及 综合运用知识的能力， 体会了学以致用、 突出自己劳动成果的喜悦心情， 也从中 发现自己平时学习的不足和薄弱环节，从而

25、加以弥补。第七章 参考文献1 徐孝凯编著，数据结构课程实验 ，清华大学出版 2002 年第一版2 乃笑编著，数据结构与算法，电子工业 2004 年 10 月3 严蔚敏 数据结构(C语言版)清华大学附录：源程序如下：#include <stdio.h>#include <stdlib.h>/ 要用 system 函数要调用的头文件#include<conio.h>/用 getch() 要调用的头文件#include <string.h>#define N 50/义用 N 表示 50 叶节点数#define M 2*N-1/ 用 M 表示节点总数 当

26、叶节点数位 n 时总节点数为 2n-1#define MAXSIZE 100typedef structchar data; int weight; int parent; int lchild; int rchild;/结点值/权值/双亲结点 /左孩子结点 /右孩子结点HTNode;typedef structvoid CreateHT(HTNode ht,int n) int i,k,lnode,rnode;/调用输入的数组 ht, 和节点数 nchar cdN;/存放哈夫曼码int start; HCode;/从 start 开始读 cd 中的哈夫曼码int min1,min2;for

27、(i=0;i<2*n-1;i+)hti.parent=hti.lchild=hti.rchild=-1;/ 所有结点的相关域置初值 -1for (i=n;i<2*n-1;i+)min1=min2=32767;lnode=rnode=-1;for (k=0;k<=i-1;k+)if (htk.parent=-1)if (htk.weight<min1)/构造哈夫曼树/int 的围是 -32768 32767/lnode 和 rnode 记录最小权值的两个结点位置/只在尚未构造二叉树的结点中查找/若权值小于最小的左节点的权值min2=min1;rnode=lnode;min

28、1=htk.weight;lnode=k;else if (htk.weight<min2)min2=htk.weight;rnode=k;/ 两个最小节点的父节点是 i/两个最小节点的父节点权值htlnode.parent=i;htrnode.parent=i;hti.weight=htlnode.weight+htrnode.weight;为两个最小节点权值之和hti.lchild=lnode;hti.rchild=rnode;/父节点的左节点和右节点void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c;HCode hc;for

29、(i=0;i<n;i+)hc.start=n;c=i; f=hti.parent;while (f!=-1)if (htf.lchild=c) hc.cdhc.start-='0'elsehc.cdhc.start-='1'c=f;f=htf.parent;hc.start+; hcdi=hc;void DispHCode(HTNode ht,HCode hcd,int n) /根据哈夫曼树求哈夫曼编码/循序直到树根结点结束循环/处理左孩子结点/处理右孩子结点/start 指向哈夫曼编码 hc.cd 中最开始字符/输出哈夫曼编码的列表int i,k;pri

30、ntf(" 输出哈夫曼编码 :n");for (i=0;i<n;i+)/输出 data 中的所有数据，即 A-Zprintf(" %c:t",hti.data);for (k=hcdi.start;k<=n;k+)/输出所有 data 中数据的编码printf("%c",hcdi.cdk);printf("n");void editHCode(HTNode ht,HCode hcd,int n) /编码函数/ 把要进行编码的字符串存入 string 数组中/#为终止标志/循环查找与输入字符相同的编号，

31、相同的/ 输出完成后跳出当前 for 循环char stringMAXSIZE;int i,j,k;scanf("%s",string);printf("n 输出编码结果 :n");for (i=0;stringi!='#'i+)for (j=0;j<n;j+)if(stringi=htj.data)就输出这个字符的编码for (k=hcdj.start;k<=n;k+)printf("%c",hcdj.cdk);break;void deHCode(HTNode ht,HCode hcd,int n) c

32、har codeMAXSIZE;int i,j,l,k,m,x;scanf("%s",code);while(code0!='#')for (i=0;i<n;i+)m=0;for (k=hcdi.start,j=0;k<=n;k+,j+)/译码函数/把要进行译码的字符串存入code数组中/m 为想同编码个数的计数器/j 为记录所存储这个字符的编码个数if(codej=hcdi.cdk)/当有相同编码时m 值加 1m+;/当输入的字符串与所存储的编码字符if(m=j) 串个数相等时则输出这个的 data 数据/把已经使用过的 code 数组里的字符

33、串printf("%c",hti.data); for(x=0;codex-1!='#'x+) 删除codex=codex+j;void main()int n=26,i;char orz,back,flag=1;char str='A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'/初始化int fnum=18