huffman.cpp

编码程序

#include <stdio.h>
#include <math.h>
#define   N  30

typedef struct 
{
	float p;
    int   out[N];
	int   length;
	int   flag;// 0 原始概率  1  中间概率
}SCandP;

SCandP   scp[2*N];
int    da_num;//初始化为n＋1

typedef struct 
{
	int num[N];
	int length;
}dataNum;

dataNum dN;//存储剩余要编码的数据所在结构体数组的序号

int n;//实际数据量


void bianma(int a,int b)
{
	scp[a].out[ scp[a].length+1 ]=b;//编码b
	scp[a].length++;//编码长度加1
}

void justdo()
{
	int last0,last1;
	last0=dN.num[dN.length-1];
	last1=dN.num[dN.length];

	//---------------编码last0----------------
    if(scp[last0].flag==0)
    {
		bianma(last0,0);
	}
	if(scp[last0].flag==1)
	{
		for(int i=1;i<=scp[last0].length;i++)
			bianma(scp[last0].out[i],0);
	}
	//--------------------------------

    //---------------编码last1-----------------
    if(scp[last1].flag==0)
    {
		bianma(last1,1);
	}
	if(scp[last1].flag==1)
	{
		for(int i=1;i<=scp[last1].length;i++)
			bianma(scp[last1].out[i],1);
	}
	//--------------------------------

	//----------------合并----------------
    da_num++;
	scp[da_num].p =scp[last0].p+scp[last1].p;
	scp[da_num].flag  =1;
	scp[da_num].length=0;

	if(scp[last0].flag==0)
	{
		scp[da_num].length++;
		scp[da_num].out[ scp[da_num].length ]=last0;
	}
    
	if(scp[last0].flag==1)
	{
		for(int i=1;i<=scp[last0].length;i++)
		{
			scp[da_num].length++;
			scp[da_num].out[ scp[da_num].length ] = scp[last0].out[i]; 
		}
	} //接受last0的out数组的数据

	if(scp[last1].flag==0)
	{
		scp[da_num].length++;
		scp[da_num].out[ scp[da_num].length ]=last1;
	}
    
	if(scp[last1].flag==1)
	{
		for(int i=1;i<=scp[last1].length;i++)
		{
			scp[da_num].length++;
			scp[da_num].out[ scp[da_num].length ] = scp[last1].out[i]; 
		}
	} //接受last1的out数组的数据

    
	dN.num[dN.length-1]=da_num;
    dN.length--;

	//--------------------------------

}


void init()
{
	 printf("n=");
     scanf("%d",&n);
	 printf("input the possibility value of n symbols:\n");
	 for(int i=1;i<=n;i++)
	 {
		 scanf("%f",&scp[i].p);
		 scp[i].flag=0;
		 scp[i].length=0;
	 }
      
	 da_num=n+1;

	 dN.length=n;
	 for(i=1;i<=dN.length;i++)
		 dN.num[i]=i;
}


void cmp()
{
	int i,j;
	int tmp;
	for(i=1;i<=dN.length;i++)
		for(j=1;j<dN.length;j++)
			if(scp[ dN.num[j] ].p<scp[ dN.num[j+1] ].p)  
			    tmp=dN.num[j],dN.num[j]=dN.num[j+1],dN.num[j+1]=tmp;
}

void output()
{
	int i,j;
	printf("===================================\n");
    printf("huffman Encode:     chy\n");
    printf("probability - huffmanCode\n");
    for(i=1;i<=n;i++)
	{
	    printf("%-15.2f",scp[i].p); 
		for(j=scp[i].length;j>=1;j--)
	  	  	printf("%d",scp[i].out[j]);
		printf("\n");
	}
	printf("===================================\n");
//    printf("END\n");
	float H;      //信源符号的信息熵
	H=0;
	for(i=1;i<=n;i++)
	{
		H=H+scp[i].p*log(scp[i].p)/log(2);
	}
	H=-H;
	float K;          //平均信息率
	K=0;
	for(i=1;i<=n;i++)
	{
		K=K+scp[i].p*scp[i].length;
	}
	float yita;
	yita=H/K;
	printf("Calculate the efficiency of huffman:\n");
	printf("yita=%f\n",yita);

}

void main()
{	
	init();//读入数据，初始化存储空间
	
	while(dN.length>1)
	{
		cmp();
        justdo();
	}
     
	output();
}