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

《用Huffman树进行编码与解码算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。四、实验步骤1、统计电文中字符的出现频率。2.用统计频率建立Hffman树。3．生成前缀码；4．建立huffman树的解码算法．5．用随机输入的电文完成编码与解码过程。五、程序源代码及注释#include#includeconstintMAX=20;structhuffnode{intweight;intlchild,rchild,parent;};structhuffinit//输入的权值信息的结构{char

4、data;intweight;};structhuffcode//哈夫曼树编码的结构{chardata;charcode[MAX+1];};classHuffTree//哈夫曼树类的声明{public:HuffTree(huffinitw[],intn);~HuffTree(){}voidSelect(int&min1,int&min2,intm);voidOutput();//输出哈夫曼树最终状态（tree数组）voidEncode();//编码voidDecode(charcode[]);//解码privat

5、e:huffnodetree[2*MAX-1];//存储哈夫曼树huffcodecd[MAX];//存储各个哈夫曼编码intsize;//哈夫曼树的叶子结点数};HuffTree::HuffTree(huffinitw[],intn){size=n;for(inti=0;i<2*n-1;i++){tree[i].parent=-1;tree[i].lchild=-1;tree[i].rchild=-1;}for(i=0;i

6、w[i].data;}intmin1=-1;intmin2=-1;intm=size;for(intk=n;k<2*n-1;k++){Select(min1,min2,m);tree[min1].parent=k;tree[min2].parent=k;tree[k].weight=tree[min1].weight+tree[min2].weight;tree[k].lchild=min1;tree[k].rchild=min2;m++;}}voidHuffTree::Select(int&min1,int&m

7、in2,intm)//选择两个权值最小的结点{inta=100;intb=100;for(inti=0;i

8、*size-1;i++){cout<