- #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); /*輸出編碼效率*/
- }
-
|
