数据结构哈夫曼树C++实现

1、实验报告一、 实验目的1. 掌握哈夫曼树的基本概念及所用的存储结构。2. 掌握哈夫曼树的建立算法。3. 掌握哈夫曼树的应用（哈夫曼树的编码和译码） 。二、 实验内容给定权值 5、 29、 7、 8、 14、 23、 3、 11，建立哈夫曼树，输出哈夫曼编码。对上述给定的哈夫曼树及得到的哈夫曼编码， 试输入一串二进制编码， 输出它的 哈夫曼译码。 三、 实验与算法分析建立哈夫曼树， 将哈夫曼树的机构定义为一个结构型的一维数组每个元素含有四项：权值、双亲、左孩子、右孩子。给定的权值可以从键盘输入，要输出所建立的哈夫曼树，只要输出表示哈夫曼树的一维数组中的全部元素即可。要实现哈夫曼编码，只要在所建立

2、的哈夫曼树上进行二进制编码：往左走，编码为0，往右走编码为1，然后将从根结点到树叶中的所有0,1 排列起来，则得到该树叶的哈夫曼编码。 哈夫曼编码可以用一个结构型的一维数组保存， 每个元素包含：编码，编码的开始位置，编码所对应的字符三项。哈夫曼译码，就是将输入的译码还原成对应的字符。抽象的算法描述： 将建立哈夫曼树、 实现哈夫曼编码、 哈夫曼译码都定义成子函数的的形式， 然后在主函数中调用它们。 哈夫曼树的构造： 假设有 n 个权值，则构造出的有n个叶子结点。n个权值分别设为w1,w2,wn,则哈夫曼树的构造规则为：（1）将w1,w2,wn看成是有n棵树的森林（每棵树仅有一个结点） ； （ 2

3、）在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左右子树， 且新树的根结点权值为其左右子树的根结点的权值之； （ 3） 从森林中删除选取的两棵树，并将新树加入森林。（ 4）重复（2） 、 （ 3）步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。四、 可执行程序及注释实验代码#include#includeconst int n=8; /maxn 表示叶子数目const int m=2*n-1; /m 为森林中树的棵数struct tree/哈夫曼树中的一个结点float weight; / 权值 int parent; /双亲 int lch,rch; /左孩子、右孩子;

4、 struct codetype/哈弗曼编码int bitsn+1; /哈弗曼编码int start; /编码的存放位置 char ch; /所对应的字符;tree hftreem+1;codetype coden+1;void creathuffmantree() /建立哈夫曼树 int i,j,p1,p2;float s1,s2;for(i=1;i=m;i+) hftreei.parent=0;hftreei.lch=0;hftreei.rch=0;hftreei.weight=0;cout请输入n个权值endl;for(i=1;ihftreei.weight;/输入权值p1=p2=0;s

5、1=s2=32767;for(j=1;j=i-1;j+)for(i=n+1;i=m;i+)/进行次合并/p1,p2 分别指向两个权值最小的值的位置/s1,s2代表两个最小权值/选两个最小值 if(hftreej.parent=0) /该权值还没有选中if(hftreej.weights1)s2=s1;s1=hftreej.weight;p2=p1;p1=j;else if(hftreej.weights2)s2=hftreej.weight;p2=j;/以下为合并hftreep1.parent=i;hftreep2.parent=i;hftreei.lch=p1;hftreei.rch=p2;

6、hftreei.weight=hftreep1.weight+hftreep2.weight;void huffcode() / 哈弗曼编码codetype cd;int c,p;for(int i=1;i=n;i+)(cd.start=n+1;cd.ch=96+i;/第一个树叶对应字母a,其余依此类推c=i;p=hftreei.parent;while(p!=0)(cd.start-;if(hftreep.lch=c)cd.bitscd.start=0;elsecd.bitscd.start=1;c=p;p=hftreep.parent;codei=cd;for(i=1;i=n;i+)(cout字 符codei.ch 的 权 值 为hftreei.weightsetw(5)编码为：;for(int j=codei.start;j=n;j+)coutcodei.bitsj;coutendl;void trancode()/哈弗曼译码(int i=m;char b;cout请输入一审二进制编码(0、1以外的数结束)b;while(b=0)|(b=1)(if(b=0)i=hftreei.lch;elsei=hftreei.rch;if(hft