北邮哈夫曼树实验报告.doc

第 PAGE 4页 北京邮电大学电信工程学院 第 PAGE 1页 数据结构实验报告 实验名称： 实验三——树 学生姓名： 班 级： 2011211114 班内序号： 14 学 号： 2011210400 日 期： 2012年11月29日 1．实验要求 （1） 实验目的 掌握二叉树基本操作的实现方法 了解赫夫曼树的思想和相关概念 学习使用二叉树解决实际问题的能力 （2） 实验内容 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树 建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。 打印(Print)：以直观的方式打印赫夫曼树（选作） 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。 测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 2. 程序分析 2.1 存储结构 该程序使用哈夫曼树结构存储数据，并利用哈夫曼树进行编码得到每个字符的编码从而减少数据的存储空间，哈夫曼树是二叉树，以各频度作为叶子结点组成哈夫曼树，而每个结点存储的有其频度，其双亲结点，其左孩子和右孩子，并且哈夫曼树有一个相应的编码表存储各叶子结点的编码。 哈夫曼树的存储结构如图： ED E D B A C 2.2 关键算法分析 1．关键算法 哈夫曼树解码和译码问题的实质就是把已知的一段字符串，统计每个字符的频度，并按照频度建立哈夫曼树，每个叶子结点都为一个频度，然后利用建好的哈夫曼树建立编码表，从而得到每个字符的编码，这样每输入一段字符都可以去编码表找对应的字符从而编码成一段二进制码，这样的编码存储更节省存储空间，从而达到压缩效果。 关键算法如下： 1：把输入的一段字符串转化为每个字符的频度，并对应一个字符数组存储字符： 利用ASCII码有128个并对应着的整形，用一个整形数组存储每个字符出现的次数，数组的下标为每个字符的ASCII码对应整数。 用赋好值的整形数组每个元素除以总的元素并对应存入一个double类型的数组（元素为0的不存），并建立一个字符数组存储每个字符对应double数组的每一个元素（频度）。 2：利用建好的double数组建立哈夫曼树： ①建立一个含2*k-1个结点的树，并把k个频度对应存入0--k-1个结点的weight域，并令这些结点的左孩子，右孩子，和双亲都为-1。 ②找出0——k-1个结点频度最小的两个结点，并令第k个结点的频度等于两节点频度之和，一个结点为其左孩子，一个结点为其右孩子。 ③循环步骤2，使建好的树每个结点的域都填充好（每次比较除去已经提取出来的结点，并加入新建好的结点）。 3：利用建好的哈夫曼树建立编码表: ①编码表data域存字符，code域存每个字符的编码。 ②找到叶子结点的双亲，判断如果该结点是双亲的左孩子则存编码0，右孩子存编码1，然后再找其双亲的双亲，判断双亲是祖父结点的左孩子还是右孩子，重复上述步骤直到根结点。 ③把每个字符的编码倒置并输出每个字符的编码。 4：译码函数: 如果是第一个字符是0则找根结点的左孩子，如果是1则找右孩子。 继续令找到的结点作为双亲并找下一个字符重复步骤（1）（2）直到叶子结点。 重复(1)(2)直到遍历字符数组。 5：编码函数： 把字符数组的第一个字符与叶子结点的字符比较，找到相同的字符，把其编码并入一个字符数组存储起来。 字符下标加1，重复步骤（1）直到遍历整个字符数组。 2. 代码详细分析: （1）把输入的一段字符串转化为每个字符的频度，并对应一个字符数组存储字符： ①利用ASCII码有128个并对应着的整形，用一个整形数组存储每个字符出现的次数，数组的下标为每个字符的ASCII码对应整数; while(p[i]) { a[p[i]]++; i++; } ②用赋好值的整形数组每个元素除以总的元素并对应存入一个double类型的数组（元素为0的不存），并建立一个字符数组存储每个字符对应double数组的每一 个元素（频度）： for(int j=0;j128;j++) { if(a[j]) { b[k]=(double)a[j]/i; c[k]=(char)j; k++;