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

《数据结构 哈夫曼树 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,

3、w2,……,wn看成是有n棵树的森林（每棵树仅有一个结点）；（2）在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左右子树，且新树的根结点权值为其左右子树的根结点的权值之；（3）从森林中删除选取的两棵树，并将新树加入森林。（4）重复（2）、（3）步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。四、可执行程序及注释实验代码#include#includeconstintn=8;//maxn表示叶子数目constintm=2*n-1;//m为森林中树的棵数structtre

4、e//哈夫曼树中的一个结点{floatweight;//权值intparent;//双亲intlch,rch;//左孩子、右孩子};structcodetype//哈弗曼编码{intbits[n+1];//哈弗曼编码intstart;//编码的存放位置charch;//所对应的字符};treehftree[m+1];codetypecode[n+1];voidcreathuffmantree()//建立哈夫曼树{inti,j,p1,p2;floats1,s2;for(i=1;i<=m;i++){hftree[i].parent=0;h

5、ftree[i].lch=0;hftree[i].rch=0;hftree[i].weight=0;}cout<<"请输入"<>hftree[i].weight;//输入权值for(i=n+1;i<=m;i++)//进行次合并{p1=p2=0;//p1,p2分别指向两个权值最小的值的位置s1=s2=32767;//s1,s2代表两个最小权值for(j=1;j<=i-1;j++)//选两个最小值if(hftree[j].parent==0)//该权值还没有选中if

6、(hftree[j].weight

7、码{codetypecd;intc,p;for(inti=1;i<=n;i++){cd.start=n+1;cd.ch=96+i;//第一个树叶对应字母a，其余依此类推c=i;p=hftree[i].parent;while(p!=0){cd.start--;if(hftree[p].lch==c)cd.bits[cd.start]=0;elsecd.bits[cd.start]=1;c=p;p=hftree[p].parent;}code[i]=cd;}for(i=1;i<=n;i++){cout<<"字符"<

8、<<"的权值为："<