哈夫曼编码实验报告.doc

《哈夫曼编码实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、北京邮电大学信息与通信工程学院数据结构实验报告1．实验要求利用二叉树结构实现哈夫曼编/解码器。基本要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。5、打印(Print)：以直观的方式打印哈夫曼树（选作）计算输入的字符串编码前和

2、编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。并用IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.进行测试。2.程序分析哈夫曼树结点的存储结构包括双亲域parent，左子树lchild，右子树rchild，还有字符word，权重weight，编码code对用户输入的信息进行统计，将每个字符作为哈夫曼树的叶子结点。统计每个字符出现的次数作为叶子的权重，统计次数可以根据每个字符不同的ASCII码，根据叶子结点的权重建立一个哈夫曼树。建立每个叶子的编码从根结点开始，规定

3、通往左子树路径记为0，通往右子树路径记为1。由于编码要求从根结点开始，所以需要前序遍历哈夫曼树，故编码过程是以前序遍历二叉树为基础的。同时注意递归函数中能否直接对结点的编码域进行操作。编码信息只要遍历字符串中每个字符，从哈夫曼树中找到相应的叶子结点，取得相应的编码。最后再将所有找到的编码连接起来即可。译码则是将编码串从左到右逐位判别，直到确定一个字符。这就是哈夫曼树的逆过程。遍历编码串，从哈夫曼树中找到相应的叶子结点，取得相应的字符再将找到的字符连接起来即可。2.1存储结构哈夫曼树结点存储结构parentlchildrchildwordweightcode

4、2.2关键算法分析第5页北京邮电大学信息与通信工程学院1.统计字符频度自然语言描述：（1）取出字符串中的一个字符（2）遍历所有初始化的哈夫曼树结点（3）如果结点中有记录代表的字符且字符等于取出的字符，说明该字符的叶子存在，则将该结点的权值加1（4）如果所有结点记录的字符均没有与取出的字符一致，说明该字符的叶子不存在，则将结点的字符记为取出字符，并将权重设为1（5）重复以上步骤，直至字符串中所有字符全部遍历伪代码描述：1.for(inti=0;i

5、==HuffTree[j].word)//若字符已被统计，则增加权值即可1.1.1.1权重++;1.1.1.2break;1.1.2elseif(!HuffTree[j].word)//否则需要一个新结点储存这个字符1.1.2.1HuffTree[j].word=WordStr[i];1.1.2.2HuffTree[j].weight=1;1.1.2.3叶子结点个数++;1.1.2.4break;时间复杂度O(n2)，空间复杂度S(0)2.构造哈夫曼树自然语言描述：（1）选出权值最小的两个结点，其权值和作为其根结点的权值，最小的结点作为左子树，次小的作为右

6、子树，不断将两棵子树合并为一棵树。（2）重复上述过程，直至所有结点全被遍历完伪代码描述：1.intleaves=n;2.for(intj=n;j<2*n-1;j++)2.1intj1=0;intj2=0;2.2Select(HuffTree,leaves,j,j1,j2);//选出两个权值最小结点2.3HuffTree[j1].parent=j;HuffTree[j2].parent=j;2.4HuffTree[j].weight=HuffTree[j1].weight+HuffTree[j2].weight;//根结点权值等于两个结点权值和第5页北京邮电

7、大学信息与通信工程学院2.5HuffTree[j].lchild=j1;HuffTree[j].rchild=j2;//左子树为权值最小，右子树权值次小2.6叶子数--;时间复杂度O(n)，空间复杂度S(2)3.为每个叶子结点编码自然语言描述：（1）初始化一个字符数组Code暂存每个叶子结点的编码。（2）前序遍历哈夫曼树（3）若结点左右子树都为-1，则将code复制到编码的code串，准备返回上一层，编码相应少一位，code长度减1，返回（4）否则按照从左到右的顺序前序遍历根结点的所有子树（5）若访问左子树，则进入下一层，编码相应多一位，code长度加1并

8、将最后一位赋0；访问右子树，进入下一层，code长度加1并将最后一