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

1、佛山科学技术学院实 验 报 告课程名称 数据结构 实验工程 用Huffman树进行编码与解码算法 专业班级 网络工程2 姓 名 陈浩明 学 号 2021394223 指导教师 成 绩 日 期 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<iostream.h> #include<string.h> const int MAX=20; struct huffnodeint weight;int lchild,rchild,parent;struct huffinit /输入的权值信息的结构 char data; int weight;struct huffcode /哈夫曼树编码的结构 char data; char code

4、MAX+1;class HuffTree /哈夫曼树类的声明 public: 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; /哈夫曼树的叶子结点数 ;HuffT

5、ree:HuffTree(huffinit w,int n) size=n;for(int i=0;i<2*n-1;i+)treei.parent=-1;treei.lchild=-1;treei.rchild=-1;for(i=0;i<n;i+) treei.weight=wi.weight; cdi.data=wi.data; int min1=-1; int min2=-1;int m=size;for(int k=n;k<2*n-1;k+) Select(min1,min2, m);treemin1.parent=k;treemin2.parent=k;treek.w

6、eight=treemin1.weight+treemin2.weight;treek.lchild=min1;treek.rchild=min2;m+;void HuffTree:Select(int &min1,int &min2,int m)/选择两个权值最小的结点 int a=100; int b=100; for(int i=0;i<m;i+) if(treei.weight<a&&treei.parent=-1) a=treei.weight; min1=i; for(i=0;i<m;i+) if(treei.weight<b

7、&&treei.parent=-1&&i!=min1) b=treei.weight; min2=i; void HuffTree:Output()for(int i=0;i<2*size-1;i+)cout<<treei.weight<<" "<<treei.parent<<" "<<treei.lchild<<" "<<treei.rchild<<endl;void HuffTree:Encode(

8、) /编码 int m;int a;int j; char b100; int k; for(int i=0;i<size;i+) m=i; j=0; while(treem.parent!=-1) a=m; m=treem.parent; if(treem.lchild=a) bj+='0' else bj+='1' for(k=0,j=j-1;j>=0;j-) cdi.codek+=bj; cdi.codek='0' cout<<cdi.data<<"->"<<cdi.

9、code<<endl; void HuffTree:Decode(char code) /解码 int n=strlen(code); int a=2*size-2;/根节点的下标 for(int i=0;i<n;i+)if(codei='0') a=treea.lchild; if(codei='1') a=treea.rchild; if(treea.lchild=-1&&treea.rchild=-1) cout<<cda.data; a=2*size-2; elseif(codei+1='0'

10、)cout<<"error" cout<<endl; void main() huffinit w20;int n;char s100;cout<<"请输入字符个数："cin>>n;for(int i=0;i<n;i+) cout<<"请输入第"<<i+1<<"个字符及权值：" ; cin>>wi.data;cin>>wi.weight; HuffTree H(w,n); cout<<&qu

11、ot;已经建好的节点信息为"<<endl;H.Output(); cout<<"已经建好的节点编码信息为"<<endl;H.Encode();char q; do cout<<"请输入密码：" cin>>s;H.Decode(s);cout<<endl;cout<<"还要继续解码吗?(Y/N)"cin>>q;while(q='Y');结果截图: 六、实验结果分析及实验体会 通过用Huffman树进行编码与解码算法的实验后，对于huffman树的理解和应用都有了进一步的了解，但对于快速构建huff