用Huffman树进行编码与解码算法

1、佛山科学技术学院实 验 报 告课程名称 数据结构 实验项目 用Huffman树进行编码与解码算法 专业班级 网络工程2 姓 名 陈浩明 学 号 指导教师 成 绩 日 期 2011.11.13 1、 实验目的 1、通过本实验，熟悉二叉树、Huffman树的基本概念，掌握二叉树的存储结构及各种算法2、熟悉用Huffman树进行电文的加密与解密算法二、实验内容1、Huffman树的存储方式2、加密与解密算法在电文编码中的应用三、实验原理 给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。 Huffman树是一

2、种特殊的二叉树，其叶结点的编码是一种前缀码，同时，通过统计字符的频度，能够达到编码电文的最小化。 哈夫曼树的构造 假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、wn，则哈夫曼树的构造规则为： (1) 将w1、w2、，wn看成是有n 棵树的森林(每棵树仅有一个结点)； (2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。四、实验步骤 1、统计电文中字符的出现

3、频率。 2. 用统计频率建立Hffman树。 3生成前缀码； 4建立huffman树的解码算法 5用随机输入的电文完成编码与解码过程。5、 程序源代码及注释#include #include const int MAX=20; struct huffnodeint weight;int lchild,rchild,parent;struct huffinit /输入的权值信息的结构 char data; int weight;struct huffcode /哈夫曼树编码的结构 char data; char codeMAX+1;class HuffTree /哈夫曼树类的声明 public:

4、 HuffTree(huffinit w,int n); HuffTree() void Select(int &min1,int &min2,int m); void Output(); /输出哈夫曼树最终状态（tree数组） void Encode(); /编码 void Decode(char code); /解码 private: huffnode tree2*MAX-1; /存储哈夫曼树 huffcode cdMAX; /存储各个哈夫曼编码 int size; /哈夫曼树的叶子结点数 ;HuffTree:HuffTree(huffinit w,int n) size=n;for(in

5、t i=0;i2*n-1;i+)treei.parent=-1;treei.lchild=-1;treei.rchild=-1;for(i=0;in;i+) treei.weight=wi.weight; cdi.data=wi.data; int min1=-1; int min2=-1;int m=size;for(int k=n;k2*n-1;k+) Select(min1,min2, m);treemin1.parent=k;treemin2.parent=k;treek.weight=treemin1.weight+treemin2.weight;treek.lchild=min1;

6、treek.rchild=min2;m+;void HuffTree:Select(int &min1,int &min2,int m)/选择两个权值最小的结点 int a=100; int b=100; for(int i=0;im;i+) if(treei.weighta&treei.parent=-1) a=treei.weight; min1=i; for(i=0;im;i+) if(treei.weightb&treei.parent=-1&i!=min1) b=treei.weight; min2=i; void HuffTree:Output()for(int i=0;i2*si

7、ze-1;i+)couttreei.weight treei.parent treei.lchild treei.rchildendl;void HuffTree:Encode() /编码 int m;int a;int j; char b100; int k; for(int i=0;i=0;j-) cdi.codek+=bj; cdi.codek=0; coutcdi.datacdi.codeendl; void HuffTree:Decode(char code) /解码 int n=strlen(code); int a=2*size-2;/根节点的下标 for(int i=0;in;

8、i+)if(codei=0) a=treea.lchild; if(codei=1) a=treea.rchild; if(treea.lchild=-1&treea.rchild=-1) coutcda.data; a=2*size-2; elseif(codei+1=0)couterror; coutendl; void main() huffinit w20;int n;char s100;coutn;for(int i=0;in;i+) cout请输入第i+1wi.data;cinwi.weight; HuffTree H(w,n); cout已经建好的节点信息为endl;H.Output(); cout已经建好的节点编码信息为endl;H.Encode();char q; do couts;H.Decode(s);coutendl;coutq;while(q=Y);结果截图: 六、实验结果分析及实验体会 通过用Huffman树进行编码与解码算法的实验后，对于huffman树的理解和应用都有了进一步的了解，但对于快速构建huffman树还有些有欠纯熟，还要多加炼金，并且要对基础的二叉树等知识要多加练习。注：