哈夫曼编码实验报告

实验目的与规定运用C++编写程序，解决哈夫曼编码问题。实验内容哈夫曼树定义：设二叉树共有n个端点，从二叉树第k个端点到树的根结点的途径长度l(k)为该端结点（或叶子）的祖先数，即该叶子的层数减1。同时，每一种结点都带一种权（实数），第k个端点所带权为w(k)。定义各个端结点的途径长l(k)与该点的权w(k)的乘积之和为该二叉树的带权途径长。哈夫曼树：对n个权值w(1),w(2),…,w(n)，构造出全部由n个分别带这些权值的叶结点构成的二叉树，其中带权途径长wpl最小的二叉树称为哈夫曼树。三．算法描述及实验环节哈夫曼算法哈夫曼给出一种贪心方略的算法，称为哈夫曼算法。1）根据给定的n个权值{w(1),w(2),…,w(n)}构成n棵二叉树的森林F=(T1,…,Tn)。其中每棵二叉树中只有一种带权为w(k)的根结点，其左右子树为空。2）在F中选用两棵结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上结点权值之和。3）在F中删除这两棵树，并把新得的二叉树加入F中。4）重复以上2），3），直到F只含一棵树为止。这棵树即为哈夫曼树。贪心算法设计(1)数据构造数组w：各字符频率或结点权值，操作中可变化；w(k)为第k个字符或结点的频率。数组u：各字符频率或结点权值，不参加操作。数组b：各字符或结点的次序号，如b[2]=4，即排序的第2位为第4位字符(结点)。数组lc：各字符或结点的左子号。数组rc：各字符或结点的右子号。数组p：各字符或结点的双亲号。数组q：计算各字符或结点的编码的十进制值。数组f：计算各字符或结点的的二进制位数。数组g：各字符或结点的编码十进制值转换的二进制数码。(2)构建哈夫曼树设立n-1次操作的k(1~n-1)循环。对每一种k，设立j(1或2)循环，比较产生须去掉的两个元素号b[2*k-2+j](每产生一种，该元素置非常大，以避免干扰背面比较)。产生一种新的结点：u[n+k]=u[b[2*k-1]]+u[b[2*k]];标注该结点的左右后继与双亲地址Lc[n+k]=b[2*k-1];rc[n+k]=b[2*k;P[b[2*k-1]]=n+k;p[b[2*k]]=n+k;至u[2*n-1]产生后结束构建哈夫曼树。(3)编码数值运算根据左边标注“0”右边标注“1”的规则，设立k(2n-1~n+1)循环逐级反推，前一级的数值须乘2，即q[lc[k]]=q[k]*2+0;q[rc[k]]=q[k]*2+1;f[rc[k]]=f[lc[k]]=f[k]+1;为了输出q[k](k=1,2,…,n)的哈夫曼编码，应用g数组存储分离q[k]的各个二进制数字g[i](i=1,2,…,j)输出时先输出f[k]-j个前置“0”，然后输出q[i](i=j,j-1,…,1)

四．程序设计#include<stdio.h>voidmain(){inta,k,i,j,n,w[100],u[100],b[100],lc[100],rc[100];intf[100],g[100],p[100],q[100];printf("请输入字符个数n：");scanf("%d",&n);for(k=1;k<=n;k++){printf("请输入第%d个字符频率:",k);scanf("%d",&w[k]);u[k]=w[k]; }for(k=1;k<=2*n;k++){p[k]=lc[k]=rc[k]=0;q[k]=0;}printf("原始频率为:");for(j=1;j<=n;j++)printf("%d",w[j]);for(k=1;k<=n-1;k++){for(j=1;j<=2;j++) {b[2*k-2+j]=1;for(i=2;i<=n+k-1;i++)if(w[i]<w[b[2*k-2+j]])b[2*k-2+j]=i;w[b[2*k-2+j]]=0+k+j;}u[n+k]=u[b[2*k-1]]+u[b[2*k]]; w[n+k]=u[n+k]; lc[n+k]=b[2*k-1];rc[n+k]=b[2*k]; p[b[2*k-1]]=n+k;p[b[2*k]]=n+k; }printf("\nkdaplcrc\n");for(k=1;k<=2*n-1;k++)printf("%4d%4d%4d%4d%4d\n",k,u[k],p[k],lc[k],rc[k]);q[2*n-1]=0;f[2*n-1]=0;for(k=2*n-1;k>n;k--){q[lc[k]]=q[k]*2+0;q[rc[k]]=q[k]*2+1;f[rc[k]]=f[lc[k]]=f[k]+1;}printf("kdabite\n");for(k=1;k<=n;k++){if(q[k]==0){j=1;g[1]=0;}else{a=q[k];j=0;while(a>0){j++;g[j]=a%2;a=a/2;}}printf("%c%2d",k+96,u[k]);for(i=1;i<=f[k]-j;i++)printf("0");for(i=j;i>=1;i--) printf("%d",g[i]);prin