Huffman二叉树实验报告--数据结构(C语言)

《Huffman二叉树实验报告--数据结构(C语言)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、江海强07092007数　据　结　构　作　业　报　告　　——Huffman二叉树实验报告姓名：江海强班级：070921班学号：07092007上机时间：2010-10-22报告时间：2010-10-26摘要1.实验目的本实验是为了让我们深入了解Huffman二叉树，学会使用Huffman编码对数据进行无损压缩，最终能够灵活运用Huffman二叉树。2.实验方法　　利用递归的方法创建Huffman二叉树，且利用了二叉树的性质对字符串进行编码和译码。3.实验结果此程序是在C++环境中运行的。由后面的运行出来的结果且由验证解码的

2、结果可以得知，此程序是正确无误的。由此我们还可以看出利用Huffman编码可以大大节省空间复杂度。11江海强07092007内容一．问题重述设计一个程序，首先读入一个ASCII文件，统计文档中字符出现的频度，并根据频度对每个字符生成Huffman编码。需要打印出原始数据、每个字符对应的Huffman编码以及原文档的Huffman编码。还要按照Huffman树对编码后的数据进行解码且验证解码的结果。最后输出一些统计数据，如总编码长度、编码效率等。二．算法描述本程序除了运用一些条件语句，判断语句之外，主要是运用了二叉树的性质来

3、设计程序的。本程序利用二叉树来设计二进制的前缀编码。约定了左分支表示字符'0'，右分支表示字符'1'，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。假设每种字符在输入的字符串中出现的次数为，其编码长度为，字符串中只有n种字符，则字符串总长为（即二叉树上带权路径的长度）：WPL=当输入字符串jiang_hai_qiang时，即可建立Huffman树，如下面两表所示，根据此３表可以建立如右图①的Huffman二叉树的结构图３２２２１例如n的频率为2，q的频率为1，这两个结点的共同parent结点

4、的频率为图①１１2+1=3。编码表：编码频率：编码长度：编码表：编码频率：编码长度：j:111014g:10023i:11033_:10123a:0032h:111114n:01023q:01113表111江海强07092007numweightparentlchildrchild119002312003313004210005211006211007190081100092121710313481141456125142913615310149151112151501314表2由此可以算出WPL=2×3+3×(3+2+2

5、+2+1)+4×(1+1)=42。开始输入一串字符数组，用m来记录字符串个数，n来记录字符串中不同字符的个数。用for语句把不同字符赋值给数组b[]。结束调用函数Calculate()，计算不同字符的个数，并把结果赋值给A[]。最后调用HuffmanDecoding()，对输入的二进制编码进行解码。调用HuffmanCoding()，构造Huffman二叉树HT，并求出Huffman编码HC。首先对前n个结点初始化，也对n+1到2n-1个结点初始化。调用Select()构建Huffman二叉树；还读出ASCII1文件，并且

6、求出了每个字符的Huffman编码。调用SC_HuffmanCoding()，输出Huffman编码调用函数ASCII2()，读出ASCII2文件11江海强07092007三．变量说明全局变量A[]是用来存储字符的权值的。weight代表的是该结点的权值。程序中有m=2*n-1，是为Huffman二叉树开辟2n-1个结点。在主函数中，m是用来记录输入字符串的个数的；n是用来记录有多少种字符的；a[]则是完整地记录输入的字符串；而b[]是记录输入字符串中的不同字符。HT表示Huffman树；而HC表示Huffman编码。其中

7、还要说明的一些C++语句：如cout<>a代表的输入语句；outfile<

8、1,2,…i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2。子函数ASCII1()和ASCII2()分别是用来写入ASCII1和ASCII2文件的，这两个文件中分别存储Huffman二叉树的结构表和Huffman编码表。子函数HuffmanCoding()主要是为赫夫曼二