《Huffman二叉树实验报告--数据结构(C语言)》由会员分享，可在线阅读，更多相关《Huffman二叉树实验报告--数据结构(C语言)（9页珍藏版）》请在金锄头文库上搜索。
1、江海强 07092007数据结构作业报告Huffman二叉树实验报告姓名：江海强班级：070921班学号：07092007上机时间：2010-10-22报告时间：2010-10-26摘要1.实验目的本实验是为了让我们深入了解Huffman二叉树，学会使用Huffman编码对数据进行无损压缩，最终能够灵活运用Huffman二叉树。2.实验方法利用递归的方法创建Huffman二叉树，且利用了二叉树的性质对字符串进行编码和译码。3.实验结果此程序是在C+环境中运行的。由后面的运行出来的结果且由验证解码的结果可以得知，此程序是正确无误的。由此我们还可以看出利用Huffman编码可以大大节省空间复杂度。
2、内容一问题重述设计一个程序，首先读入一个ASCII文件，统计文档中字符出现的频度，并根据频度对每个字符生成Huffman编码。需要打印出原始数据、每个字符对应的Huffman编码以及原文档的Huffman编码。还要按照Huffman树对编码后的数据进行解码且验证解码的结果。最后输出一些统计数据，如总编码长度、编码效率等。二算法描述本程序除了运用一些条件语句，判断语句之外，主要是运用了二叉树的性质来设计程序的。本程序利用二叉树来设计二进制的前缀编码。约定了左分支表示字符0，右分支表示字符1，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。假设每种字符在输入的字符串中
3、出现的次数为，其编码长度为，字符串中只有n种字符，则字符串总长为（即二叉树上带权路径的长度）：WPL =当输入字符串jiang_hai_qiang时，即可建立Huffman树，如下面两表所示，根据此表可以建立如右图的Huffman二叉树的结构图例如n的频率为2，q的频率为1，这两个结点的共同parent结点的频率为图2+1=3。编码表：编码频率：编码长度：编码表：编码频率：编码长度：j:111014g:10023i:11033_:10123a:0032h:111114n:01023q:01113表1numweightparentlchildrchild119002312003313004210
4、005211006211007190081100092121710313481141456125142913615310149151112151501314表2由此可以算出WPL=23+3(3+2+2+2+1)+4(1+1)=42。开始输入一串字符数组，用m来记录字符串个数，n来记录字符串中不同字符的个数。用for语句把不同字符赋值给数组b。结束调用函数Calculate()，计算不同字符的个数，并把结果赋值给A。最后调用HuffmanDecoding()，对输入的二进制编码进行解码。调用HuffmanCoding()，构造Huffman二叉树HT，并求出Huffman编码HC。首先对前n个结
5、点初始化，也对n+1到2n-1个结点初始化。调用Select()构建Huffman二叉树；还读出ASCII1文件，并且求出了每个字符的Huffman编码。调用SC_HuffmanCoding()，输出Huffman编码调用函数ASCII2()，读出ASCII2文件三变量说明全局变量A是用来存储字符的权值的。weight代表的是该结点的权值。程序中有m=2*n-1，是为Huffman二叉树开辟2n-1个结点。在主函数中，m是用来记录输入字符串的个数的；n是用来记录有多少种字符的；a则是完整地记录输入的字符串；而b是记录输入字符串中的不同字符。HT表示Huffman树；而HC表示Huffman编码
6、。其中还要说明的一些C+语句：如coutHCj+1a代表的输入语句；outfileHTi.parenta来替换上述的语句了，虽然不能存储空格字符，但是只要不在中间输入空格，运行结果是正确的，此程序还是挺好的。八附录#include#include#include #include#include#includeusing namespace std; int A100;typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode, *HuffmanTree;typedef char *HuffmanC
7、ode;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.weight=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;el
8、se 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; for(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 outfi
