哈夫曼树的实现及应用报告

《哈夫曼树的实现及应用报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、设计思想哈夫曼树实现及应用。第一步，统计字母及频数。输入我们想要编码的字母。字母输入后存入数组zimu中，计算出字母的种类n和每类字母出现的次数，依次存入数组Z和数组W中。并将字母出现的次数作为该字母的权值。第二步，构建哈夫曼树。初始化2n-l各结点，然后构建n棵只有根结点的二叉树，并给每个节点赋权值。在所有n个结点中找两个权值最小的结点il和i2,并til和i2没有父结点，将两个结点合并，则他们的父结点k的权值力il和i2两个结点的权值之和。其中父结点k的左子为il和i2中较小的il,右子为i2。之后进入循环，不断地寻找il

2、和i2,不断地将两棵树合并。直到只剩下一棵二叉树。第四步，打印树形哈夫曼树。用递归的方法先序遍历哈夫曼树，并用C记录当前层级。然后用switch语句判断当前层次，并根据层数来输出各行应填充的字符。最终输岀树形哈夫曼树。第五步，根据哈夫曼树进行编码。定义一个用于存放哈夫曼编码的二维数组bianmao选取一个叶子结点，判断是否有父结点，若有则判断是否为父结点的左子，若是则叫数组屮输入0,反之则输入1。依次循环，直到父结点不存在。当所有的叶子结点都记录了哈夫曼编码后，循环结束。第六步，输出哈夫曼编码。按顺序输出数组Z巾的元素，并找到元素

3、在二维数组bianma中对应的哈夫曼编码，然后逆向输出数组中的编码，直到数组Z中元素都输出来。然后输出zimu数组中元素对应的哈夫曼编码。图I哈夫曼树丈现及应用算法流程图三、源代码下妞给岀的是用哈夫曼树实现及应用算法实现的程序的源代码:#ifndefHuffmanTree_H#defineHuffmanTree_HclassHuffmantreeIpublic:intweight，m，g;intparentJchild,rchild,flog;charnode;charZ[26];intW[26];voidSum(charzifu

4、[]);voidHuffmanTree(HuffmantreehuffTree[J);voidBianMa(HuffmantreehuffTree

5、],charzimu

6、

7、);};#cndif#include#include#include"HuffmanTree.h"usingnamespacestd;voidHuffmantree::Sum(charzifu[J)//计算字符串中字符种类的个数及其出现次数(inti，j，k;i=j=0;whilc(zifu[i]){for(k=0;k

8、k++)if(Z

9、k]==zifu

10、i

11、)IW[k]++;break;)if(k==j){Z[j]=zifu[i];W[j++]=1;)i++；1m=j;cout«"该字符串中冇"《m<〈"类字符共"《i«"个。cout«"M表示及出现频率分别为:H«endl;cout«”字符频率,r«endl;for(i=0;i

12、n2=9999;il=i2=0;for(inti=0;i

13、:break;case1:cout«T<

14、setw(24)«setfill(,•)«,<<，T，«setw(5)«setfill(,J)«，J；break;default:break;C++；cout«huffTree[g].weight«MH«huffTree[g].node«endl;