实验三哈夫编码.doc

《实验三哈夫编码.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构实验报告1．实验要求1实验目的Ø掌握二叉树基本操作的实现方法Ø了解赫夫曼树的思想和相关概念Ø学习使用二叉树解决实际问题的能力利用二叉树结构实现赫夫曼编/解码器。基本要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、打印

2、(Print)：以直观的方式打印赫夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据：IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.2.程序分析2.1存储结构用二叉树的结构建立哈夫曼树，每个节点的结构是structHNode{intweight;intparent;intlch;intrch;stringcode;chardata;};weightparentlchrchcodedata哈夫曼树的特点：只有度为2的结点

3、和叶子结点，所以具有n个叶子结点的哈夫曼树的结点总数为2n-1顺序存储结构：设置一个的HTree[2*n-1]数组2.2关键算法分析建立哈夫曼树编码解码关键算法一：初始化伪代码：1.将存字符串权值的数组a赋0值，字符种类n赋0值2.获取输入字符串3.遍历输入的字符串，若某个字符出现一次，则在a[i]++，i为该字符ascii码4.遍历a数组，在a[i]有值的地方给HTree[i].weight赋值为a[i],HTree[i].data赋值为ascii码为i的字符源代码:voidHuffman::Init()//初始化{for(intm=0;m<256;++m

4、)a[m]=0;cout<<"请输入想要编码的字符"<

5、ree[j].data=char(k);j++;}}}时间复杂度：若输入的字符串长度为n，则时间复杂度为O(n)关键算法二：编码：思想（不等长编码）使用频率高的字符，编码长度短；使用频率低的字符，编码长度长；利用不等长编码，可以使报文总长度较短，这也是文件压缩技术的核心。1．取当前结点=叶结点2．取当前结点的父结点2.1如果叶结点是左孩子，编码0否则，编码12.2当前结点=父结点反复执行，直到当前结点是根结点。生成哈夫曼编码源代码：voidHuffman::Encode()//编码{cout<<"各字符编码，总编码分别为："<

6、;i

7、code);}inti=0;while(!HTree[i].code.empty()){cout<

8、读取编码串2．从根结点开始,如果是0,则选择左支;如