- #include <stdio.h>
- #include <math.h>
- /*huffman tree 结构定义*/
- typedef struct
- {
- float weight;
- int flag;
- int parent;
- int lchild;
- int rchild;
- }huffnode;
-
- void main(void)
- {
- huffnode huff_node[50]; /*为huffman tree 定义了50个结点*/
- int huff_code[50][10],cd,d[10],a[50];
- int i,j,x1,x2,n,c,p;
- float m1,m2,temp,hx=0,L=0,sum=0;/*hx为信源熵，L为平均码长*/
- printf("the number of input information source:\nN= "); /*输入信源符号的个数*/
- scanf("%d",&n);
- for(i=0;i<=2*n-1;i++) /*初始化huffman树各个结点的值*/
- {
- huff_node[i].weight=0;
- huff_node[i].parent=0;
- huff_node[i].flag=0;
- huff_node[i].lchild=-1;
- huff_node[i].rchild=-1;
- }
- printf("Please input probability distribution :\n");
- for(i=0;i<n;i++) /*输入信源输入分布*/
- {
- printf("p[%d]= ",i+1);
- scanf("%f",&temp);
- sum+=temp;
- huff_node[i].weight=temp;
- hx=hx-temp*3.332*log10(temp); /*求信源的熵H(X)*/
- }
-
- if(fabs((sum-1))>0.00001) /*判断信源输入分布是否正确*/
- {
- printf("Error!");
- exit(-1);
- }
-
- /*构建霍夫曼树（参考数据结构书）*/
- for(i=0;i<n-1;i++)
- {
- m1=m2=1.1;
- x1=x2=0;
- for(j=0;j<n+i;j++)
- {
- if(huff_node[j].weight<m1&&huff_node[j].flag==0)
- {
- m2=m1;
- x2=x1;
- m1=huff_node[j].weight;
- x1=j;
- }
- else
- if(huff_node[j].weight<m2&&huff_node[j].flag==0)
- {
- m2=huff_node[j].weight;
- x2=j;
- }
-
- }
- huff_node[x1].parent=n+i;
- huff_node[x2].parent=n+i; /*将找出的两棵子树合并为一棵子树*/
- huff_node[x1].flag=1;
- huff_node[x2].flag=1;
- huff_node[n+i].weight=huff_node[x1].weight+huff_node[x2].weight;
-
- if(huff_node[x1].weight==huff_node[x2].weight) /*如果值相等，则将其置于最上面*/
- {
- huff_node[n+i].lchild=x1;
- huff_node[n+i].rchild=x2;
- }
- else
- {
- huff_node[n+i].lchild=x2;
- huff_node[n+i].rchild=x1;
- }
- }
-
-
- /*求信源符号的huffman编码*/
- for(i=0;i<n;i++)
- {
- cd=n;
- c=i;
- p=huff_node[c].parent;
- while(p!=0) /*为信源si编码*/
- {
- if(huff_node[p].lchild==c) /*左孩子编码为0*/
- d[cd]=0;
- else
- d[cd]=1; /*左孩子编码为1*/
- cd=cd-1;
- c=p;
- p=huff_node[p].parent;
- }
- cd++;
- for(j=cd;j<=n;j++) /*存储信源si的huffman编码*/
- huff_code[i][j]=d[j];
- a[i]=cd;
- }
-
- /*输出信源符号的huffman编码、信源熵和平均码长*/
- printf("\ninformaition source\thuffmancode\n");
- for(i=0;i<n;i++)
- {
- printf("p[%d]=%2.3f\t\t",i+1,huff_node[i].weight);/*输出信源分布*/
- for(j=a[i];j<=n;j++)
- printf("%d",huff_code[i][j]); /*输出huffman编码*/
- /*求平均码长*/
- L=L+(n+1-a[i])*huff_node[i].weight; /*(n-cd+1)表示的是信源符号si的码长*/
- printf("\n");
- }
- printf("\nH(X)=%.2f bit/Symbol\n",hx);/*输出信源熵*/
- printf("The average length of code is:\tL=%.2f\n",L);/*输出平均码长*/
- printf("The rate is:\tR=%.3f",hx/L); /*输出编码效率*/
- }
-
|
