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

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

2、 huffman树是一种特殊的二叉树，其叶结点的编码是一种前缀码，同时，通过统计字符的频度，能够达到编码电文的最小化。 哈夫曼树的构造 假设有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 /哈夫曼树类

4、的声明 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; /哈夫曼树的叶子结点数 ;hufftree:hufftree(huffinit w,int n) si

5、ze=n;for(int 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.l

6、child=min1;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(in

7、t i=0;i2*size-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(

8、int i=0;in;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树还有些有欠纯熟，还要多加炼金，并且要对基础的二叉树等知识要多加练习。注