Huffman二叉树实验报告

1、数据结构作业报告Huffman 二叉树实验报告姓名：江海强班级：070921班学号：07092007上机时间：2010-10-22报告时间：2010-10-26摘要实验目的本实验是为了让我们深入了解Huffman二叉树，学会使用Huffman编码对数据 进行无损压缩，最终能够灵活运用 Huffman 二叉树。实验方法利用递归的方法创建Huffman二叉树，且利用了二叉树的性质对字符串进行编 码和译码。实验结果此程序是在C+环境中运行的。由后面的运行出来的结果且由验证解码的结果 可以得知，此程序是正确无误的。由此我们还可以看出利用Huffman编码可以大大 节省空间复杂度。内容内容一问题重述设计

2、一个程序，首先读入一个ASCII文件，统计文档中字符出现的频度，并根 据频度对每个字符生成Huffman编码。需要打印出原始数据、每个字符对应的 Huffman编码以及原文档的Huffman编码。还要按照Huffman树对编码后的数据进 行解码且验证解码的结果。最后输出一些统计数据，如总编码长度、编码效率等。二算法描述本程序除了运用一些条件语句，判断语句之外，主要是运用了二叉树的性质来 设计程序的。本程序利用二叉树来设计二进制的前缀编码。约定了左分支表示字符0，右分 支表示字符T，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该 叶子结点字符的编码。假设每种字符在输入的字符串中出现的

3、次数为wi，其编码长度为Z.,字符串zI中只有n种字符，则字符串总长为（即二叉树上带权路径的长度）：WPL =图11i = 1 当输入字符串jiang_hai_qiang时， 即可建立Huffman树，如下面两表所示， 根据此表可以建立如右图的Huffman 二叉树的结构图图11例如n的频率为2，q的频率为1, 这两个结点的共同parent结点的频率为 2+1=3。编码表：编码频率：编码长度：编码表：编码频率：编码长度：j：111014g10023i:1103310123a:0032h111114n:01023q01113numweightparentlchildrchild119002312

4、003313004210005211006211007190081100092121710313481141456125142913615310149151112151501314表2由此可以算出 WPL=2X3+3X (3+2+2+2+l)+4X (1+1)=42。三变量说明全局变量A是用来存储字符的权值的。weight 代表的是该结点的权值。程序中有m=2*n-l,是为Huffman二叉树开辟2n-1个结点。在主函数中，m是用来记录输入字符串的个数的；n是用来记录有多少种字符 的；a则是完整地记录输入的字符串；而b是记录输入字符串中的不同字符。HT 表示 Huffman 树；而 HC 表示

5、 Huffman 编码。其中还要说明的一些C+语句：如coutHCj+la代表的输入语句；outfileHTi.parentt则是代表写入文件的语 句。四函数与思路说明此程序有1个主函数和7个子函数。其中子函数分别为Calculate(), Select(), ASCII1()，ASCII2()，HuffmanCoding()，SC_HuffmanCoding()，HuffmanDecoding()。 子函数Calculate ()是用来计算权值的。子函数Select()的作用是在HT1,2, i-1选择parent为0且weight最小的 两个结点，其序号分别为 s1 和 s2。子函数ASC

6、II1()和ASCII2()分别是用来写入ASCII1和ASCII2文件的，这两 个文件中分别存储Huffman二叉树的结构表和Huffman编码表。子函数HuffmanCoding()主要是为赫夫曼二叉树编码，构造赫夫曼二叉树HT, 并求出n个字符的赫夫曼编码HC。其中此函数本身调用了子函数Select()和子函 数ASCII1()。在这个程序中，此子函数HuffmanCoding ()为最重要的子函数。它不 但分配了 Huffman 二叉树结点的空间，且记录好每个结点的内容。它还从叶子到根 逆向求每个字符的赫夫曼编码。SC_HuffmanCoding()这个子函数是用来输出字符串的赫夫曼编

7、码的。而最后的HuffmanDecoding ()这个子函数，则是对编码后的数据进行解码。五程序执行结果请任意输入一组字符: jiang_hai_qiangHuffman二叉树的结构:numweightparentlchildrchild119002312003313004210005211006211007190081100092121710313481141456125142913615310149151112151501314Huffman各字符的编码如下: 编码表:编码频度: TOC o 1-5 h z j:11101i:1103a:003n:0102g:1002_:1012h:111

8、11q:0111输入的字符串的Huffman编码：1110 110 00 010 100 101 1111 00 110 101 011 110 00 010 100请输入一串编码:1110 110 00 010 100 101 1111 00 110 101 011 110 00 010 100所得译码为:jiang_hai_qiang六结论由程序的运行结果和前面的讨论得知，运用Huffman树来编码解码是非常节约 空间，减少复杂度的。通过这次编程，可以让我们深入了解Huffman树，学会灵活 运用 Huffman 树，也可以让我们深刻地认识到 Huffman 树的优点和作用。七编程中遇到的

9、问题以及解决方法在编程过程中，运用C语言不会读入ASCII文件，后来运用C+语言成功写入 和读出文件。刚刚开始编程是打算连空格也作为字符来存储在Huffman树节点中的，即在主 函数中也定义了数组c100,用gets(c)输入一串字符，再利用for语句把字符串 分为一个一个字符存储在数组a100中的，可是这样子的运行结果会有乱码。后来 就直接用C+语句cina来替换上述的语句了，虽然不能存储空格字符，但是只要 不在中间输入空格，运行结果是正确的，此程序还是挺好的。八附录#include#include#include#include#include #include using namespa

10、ce std;int A100;typedef structunsigned int weight;unsigned int parent,lchild,rchild;HTNode, *HuffmanTree;typedef char *HuffmanCode;void Calculate(char a,char b,int m,int n,int*w)/计算权值 int i,j; for(i=0;in;i+)for(j=0;jm;j+) if(bi=aj)Ai+1=wi+1+;void Select(HuffmanTree HT,int n,int &s1,int &s2)HT0.weigh

11、t=100;/输入权值一般不能超过次数 s1=0;s2=0;for(int i=1;i=n;+i) if(HTi.parent=0) if(HTi.weightHTs2.weight) if(HTs2.weightHTs1.weight) s1=s2; s2=i;else if(HTi.weightHTs1.weight) s1=s2;s2=i;void ASCII1(HuffmanTree HT,int m)int i;ofstream outfile(ASCII1.txt);写入 ASCII1 文件 outfilenum weight parent lchild rchildendl; f

12、or(i=1;i=m;i+)outfileit; outfileHTi.weightt; outfileHTi.parentt; outfileHTi.lchildt; outfileHTi.rchildendl;void ASCII2(char b,HuffmanCode HC,int n)int i;ofstream outfile(ASCII2.txt);写入 ASCII2 文件 outfilevv编码表:vvtvv编码频度vvendl; for(i=1;iweight=wi;p-parent=0;p-lchild=0;p-rchild=0;for(;iv=m;+i,+p)/对从第n+1

13、个顶点到第2n-1个顶点初始化p-weight=0;p-parent=0;p-lchild=0;p-rchild=0;for(i=n+1;iv=m;+i)构建赫夫曼树Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;ASCII1(HT,m);printf(nHuffman 二叉树的结构:n); printf(num weight parent lchild rchildn);for(i=1;i=m;i+)printf(%d

14、t,i); printf(%dt,HTi.weight);printf(%dt,HTi.parent); printf(%dt,HTi.lchild);printf(%dn,HTi.rchild);/- 从叶子到根逆向求每个字符的赫夫曼编码 - HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(char);分配求编码的工作空间 cdn-l=O;编码结束符for(i=l;iv=n;i+)逐个字符求赫夫曼编码start=n-1;编码结束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf

15、.parent)从叶子到根逆向求编码 if(HTf.lchild=c) cd-start=0;else cd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);为第 i 个字符编码分配空间 strcpy(HCi,&cdstart);从 cd 复制编码串到 HCfree(cd);/释放工作空间void SC_HuffmanCoding(char a,char b,int m,int n,HuffmanCode HC)/输出 huffman 编码 int i,j;printf(输入的字符串的Huffman编码:n); for(i=0;im;i+)for

16、(j=0;jn;j+) if(ai=bj)coutHCj+1c; printf(n 所得译码为:n);while(c=O)ll(c=T)判断是否是合法字符if(c=0)i=HTi.lchild; 继续向左查找else i=HTi.rchild; 继续向右查找if(HTi.lchild=O)直到分支的末端printf(”c,bi-l);/输出对应的符号 i=m;重新开始查找下一个cinc;printf(n);void main()HuffmanTree HT;HuffmanCode HC;char al00,bl00;int i=0,j=0,m=0,n=0,*w;printf(请任意输入一组字符:n); cina;while(ai)m+;i+;用m来记录a中字符串个数for(i=0;im;i+)for(j=0;ji;j+) if(im)&(aj=ai)i+;j=-l;if(im) bn=ai;n+; w=(int*)m