哈夫曼树的构造

实验题目设需要编码的字符集为{d1,d2,…,dn}，它们出现的频率为{w1,w2,…,wn}，应用哈夫曼树构造最短的不等长编码方案。实验目的（1）了解前缀编码的概念，理解数据压缩的基本方法；（2）掌握贪心法的设计思想并能熟练运用。实验内容（包括代码和对应的执行结果截图）代码如下：#includeiostream.h//结点类型定义structelement{doubleweight;intlchild,rchild,parent;};//建立霍夫曼树voidHuffmanTree(elementhuffTree[],intw[],intn){for(inti=0;i2*n-1;i++){huffTree[i].parent=-1;huffTree[i].lchild=-1;huffTree[i].rchild=-1;}for(i=0;in;i++)huffTree[i].weight=w[i];for(i=0;in-1;i++){doublem1=1000,m2=1000;intx1=0,x2=0;for(intj=0;jn+i;j++){if(huffTree[j].weightm1&&huffTree[j].parent==-1){m2=m1;x2=x1;m1=huffTree[j].weight;x1=j;}elseif(huffTree[j].weightm2&&huffTree[j].parent==-1){m2=huffTree[j].weight;x2=j;}}huffTree[x1].parent=n+i;huffTree[x2].parent=n+i;huffTree[n+i].weight=huffTree[x1].weight+huffTree[x2].weight;huffTree[n+i].lchild=x1;huffTree[n+i].rchild=x2;}}//霍夫曼编码voidHuffmanCode(elementhuffTree[],charD[],intn){ints[21];for(inti=0;in;i++){intj=i;intx=0;coutD[i]对应的霍夫曼编码:ends;while(huffTree[j].parent!=-1){if(huffTree[huffTree[j].parent].lchild==j)s[x]=0;elses[x]=1;j=huffTree[j].parent;x++;}for(x--;x=0;x--)couts[x];coutendl;}}voidmain(){charD[21];intw[21];elementhuffTree[21];cout输入编码字符集的元素个数:ends;intx;cinx;coutendl;cout输入编码字符集元素：endlendl;for(inti=0;ix;i++){cout第i+1个字符集元素:ends;cinD[i];coutendl;}coutendl;cout输入权值数组的元素：endlendl;for(i=0;ix;i++){cout第i+1个权值数组元素:ends;cinw[i];coutendl;}coutendl;HuffmanTree(huffTree,w,x);HuffmanCode(huffTree,D,x);}截图如下：实验结果分析由贪心算法求解哈夫曼编码，先找出权限值最小的两个值，得出它的下标后，生成一个父结点作为权限值最小的两个结点的父结点，且它的权限值为这两个权限值的和；如此类推，直到形成一棵霍夫曼树；然后，再根据霍夫曼树的结点位置得出霍夫曼编码。