2.cpp

huffman 编码与译码 对任意文件二进制的编码与译码

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include"math.h"
int main()
{FILE *fp,*fp1;
 int n,i,j,k,l,*turn;
 float t,*P_i,*p_i,sum,HS,Ratio;
 double avelength;
 char **c,*s,ch[256],ch1;
 fp=fopen("out1.txt","r");
 fp1=fopen("temp1.txt","w");
 fscanf(fp,"%d",&n);
 P_i=(float *)calloc(n,sizeof(float));
 p_i=(float *)calloc(n,sizeof(float));
 turn=(int *)calloc(n,sizeof(int));
 c=(char **)calloc(n,sizeof(char *));
 for(i=0;i<n;i++)
     c[i]=(char *)calloc(10,sizeof(char));
 s=(char *)calloc(10,sizeof(char));
 sum=0;
 for(i=0;i<n;i++)
 {fscanf(fp,"%d%f",&ch[i],&(p_i[i]));
  P_i[i]=p_i[i];
  sum+=p_i[i];
  turn[i]=i;
 }
 if(fabs(sum-1.0)>1.0e-4)
 {printf("ERROR!");
 return 1;
 }
 fclose(fp);
 for(i=0;i<n;i++)
 c[i][0]=0;
for(j=0;j<n-1;j++)
{

	for(i=0;i<n-j-1;i++)
	{
		if(P_i[i]>P_i[i+1])
		{ 
			t=P_i[i];
			P_i[i]=P_i[i+1];
			P_i[i+1]=t;
			for(k=0;k<n;k++)
			{
				if(turn[k]==i)
				turn[k]=i+1;

				else if(turn[k]==i+1)
					turn[k]=i;
			}
		}
	}
}
for(i=0;i<n-1;i++)
{
	for(k=0;k<n;k++)
	{ 
		if(turn[k]==i)
		{   
			l=strlen(c[k]);
			realloc(s,l+1);
			strcpy(s,c[k]);
			realloc(c[k],l+2);
			strcpy(c[k],"0");
			strcat(c[k],s);
		}
		else if(turn[k]==i+1)
		{
			l=strlen(c[k]);
			realloc(s,l+1);
			strcpy(s,c[k]);
			realloc(c[k],l+2);
			strcpy(c[k],"1");
			strcat(c[k],s);
		}
	}
	P_i[i+1]=P_i[i]+P_i[i+1];
	for(k=0;k<n;k++)
	{
		if(turn[k]==i)
		turn[k]=i+1;
	}
	for(j=i+1;j<n-1;j++)
	{
		if(P_i[j]>P_i[j+1])
		{
			t=P_i[j];
			P_i[j]=P_i[j+1];
			P_i[j+1]=t;
			for(k=0;k<n;k++)
			{
				if(turn[k]==j)
					turn[k]=j+1;
				else if(turn[k]==j+1)
					turn[k]=j;
			}
		}
		else break;
	}
}
HS=0;
for(i=0;i<n;i++)
if(p_i[i]>0)
HS-=p_i[i]*log(p_i[i])/log(2.0);
avelength=0;
for(i=0;i<n;i++)
avelength+=p_i[i]*strlen(c[i]);
Ratio=HS/avelength;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(p_i[i]<p_i[j])
{ t=p_i[i];
  p_i[i]=p_i[j];
p_i[j]=t;
l=strlen(c[i]);
realloc(s,l+1);
strcpy(s,c[i]);
l=strlen(c[j]);
realloc(c[i],l+1);
strcpy(c[i],c[j]);
l=strlen(s);
realloc(c[j],l+1);
strcpy(c[j],s);
ch1=ch[i];
ch[i]=ch[j];
ch[j]=ch1;
}
for(i=0;i<n;i++)
{printf("字符  %4d  概率 %10f    编码 %-20s 码长   %d\n",ch[i],p_i[i],c[i],strlen(c[i]));
fprintf(fp1,"%4d     %-20s\n",ch[i],c[i]);
}
printf("编码效率为:%lf\n",Ratio);
return 0;
}