编码.cpp

实现哈夫曼编码,香农-费诺编码,RLE行程编码

#include<stdio.h>
#include<math.h>
#include<malloc.h>
typedef struct{                                      
	int weight;
	int parent,lchild,rchild;
}HTNode,*huffmantree;
typedef struct{
	int rate;
	int weight;
}ab,*at;
typedef struct{
	int rate;
	char* ma;
	int cishu;
}aa,*bb;
typedef struct{
	 int rate;
	 int mount;
}QQ,*QW;
QW jiedian;
void function1();
void function2();
void function3();
void function4();
double function5();
void  function6(at HT,bb code1,int n,int m);
int function7(at HT,int n,int m);
int a[8][8],n1=0,n2=0,n3=0,n4=0,n5=0,allmount=0,weishu=0;
double fun1,fun2,fun3,fun4,fun5,fun6;
typedef char* *huffmancode;
void main()
{   int d;
	printf("*********欢迎您使用初级编码软件*********\n");
    printf("1:*******哈夫曼算法*********************\n");
    printf("2:*******香农-费诺算法******************\n");
    printf("3:*******RLE算法************************\n");
    printf("4:*******选择较好的编码方法*************\n");
	printf("请输入您的原始数据\n");
	for(int i=0;i<8;i++)
		for(int j=0;j<8;j++)
		scanf("%d",&a[i][j]);
    printf("请您选择您要的功能或如果退出请按0键----");
	scanf("%d",&d);
	if(d<0||d>4) 
	{
		printf("您输入的数据有误不存在这种功能请重新输入数据范围在1-4:----");
	    scanf("%d",&d);
	}
    while(d)
	{    
		switch(d)
		{    
         case 1: function1(); break;
		 case 2: function2(); break;
         case 3: function3(); break;
		 case 4: function4(); break;
		}
		if(d>=1&&d<=4)
		{
		 printf("请您选择您要的功能或如果退出请按0键----");
         scanf("%d",&d);
		}
         if(d<0||d>4) 
		 {
			printf("您输入的数据有误不存在这种功能请重新输入数据范围在1-4----");
	         scanf("%d",&d);
		 }
	}
}
void function1()
{    printf("您使用的是哈夫曼编码算法\n");
     printf("\n");
	 huffmantree HR,HT;
	 int k6,k7;
     int shuju[2]={0},i,j,m,n,mix=0,n6,f,f1,t=0,n8;
	 int averge[64]={0};
     double HS=function5(),sum=0;
	 for(i=0;i<allmount;i++)
		 printf("%d:%d,  ",jiedian[i].rate,jiedian[i].mount);
	 t=allmount;
     HR=(huffmantree)malloc((2*t)*sizeof(HTNode));
     HT=HR+1;
	for(i=1;i<2*t;i++,HT++)
	 {   HT->weight=0;
	     HT->parent=0;
		 HT->lchild=0;
		 HT->rchild=0;
	 }
	 HR[0].weight=10000;
	 HR[0].lchild=0;
	 HR[0].parent=0;
	 HR[0].rchild=0;
	 HT=HR+1;
   for(i=0;i<t;i++)
	   if(jiedian[i].rate!=0)(HT+i)->weight=jiedian[i].mount;
     m=2*t;
	 HT=HR;
	 for(i=t+1;i<m;i++)
	 {
         for(j=0;j<2;j++)
		 {
			 for(n=0;n<i;n++)
			 {
				if(HT[0].weight<=HT[n].weight||HT[n].parent!=0) continue;
				else 
				{
					   HT[0].weight=HT[n].weight;
                       mix=n;
				}
			 }
			shuju[j]=mix;
			HT[mix].parent=-1;
			HT[0].weight=10000;
		 }
		 k6=shuju[0];
		 k7=shuju[1];
		 HT[i].weight=HT[k6].weight+HT[k7].weight;
		 HT[i].lchild=k7;
		 HT[i].rchild=k6;
		 HT[k6].parent=i;
		 HT[k7].parent=i;
	 }
   huffmancode code=(huffmancode)malloc(t*sizeof(char *));
   char code1[100];
   char *code2;
   n6=-1;
  for(i=1;i<=t;i++,n6=-1)
   {
       for(f=HR[i].parent,f1=i;HR[f1].parent!=0;f1=f,f=HR[f].parent)
           if(HR[f].lchild==f1) code1[++n6]='0';
		   else if(HR[f].rchild==f1) code1[++n6]='1';
          code2=(char*)malloc((n6+2)*sizeof(char));
		  averge[i-1]=n6+1;
		  for(n8=0;n8<=n6;n8++)
			  code2[n8]=code1[n6-n8];
		      code2[n8]='\0';
              code[i-1]=code2;
   }
     printf("\n");
	 for(i=0;i<t;i++)
		 printf("%d的编码是:%s\n",jiedian[i].rate,code[i]);
	 printf("输出哈夫曼编码的一些参数\n");
	 printf("此编码前的数据量为%dB\n",(64*weishu));
	 printf("此编码的图像的熵为%f\n",HS);
	 for(i=0;i<t;i++)
      sum=sum+averge[i]*jiedian[i].mount/64.0;
      printf("此编码的平均码长为:%f\n",sum);
	  printf("此编码后的数据量为%fB\n",sum*64);
      printf("此编码的压缩比为%f\n",weishu/sum);
	  fun1=weishu/sum;
      printf("此编码的效率为%f\n",HS/sum);
	  fun2=HS/sum;
}
void function2()
{	printf("您使用的是香农-费诺编码算法\n");
    printf("\n");
	double sum=0,HS=function5();
    int t=0,i,j,g[64]={0};
	int t2;
	  t2=allmount;
     char *code1;
	 ab HR={0,0};
     at HT=(at)malloc(allmount*sizeof(ab));
	 for(i=0;i<allmount;i++)
	 {
		 HT[i].rate=jiedian[i].rate;
		 HT[i].weight=jiedian[i].mount;
	 }
	 for(i=0;i<allmount-1;i++)
	   for(j=0;j<allmount-1-i;j++)
		 if(HT[j].weight>=HT[j+1].weight) continue;
		 else 
		 {
			     HR.rate=HT[j].rate;
				 HR.weight=HT[j].weight;
				 HT[j].rate=HT[j+1].rate;
				 HT[j].weight=HT[j+1].weight;
				 HT[j+1].rate=HR.rate;
				 HT[j+1].weight=HR.weight;
		 }
	  
      bb code=(bb)malloc(allmount*sizeof(aa));
	  for(i=0;i<allmount;i++)
	  {   code1=(char*)malloc(10*sizeof(char));
	      for(j=0;j<10;j++)
			  code1[j]='\0';
		  code[i].rate=jiedian[i].rate;
		  code[i].ma=code1;
		  code[i].cishu=0;
	  }
     function6(HT,code,t2,64);
	 printf("\n");
	 for(i=0;i<allmount;i++)
		 printf("%d的编码为:%s\n",jiedian[i].rate,code[i].ma);
         printf("输出香农-费诺编码的一些参数\n");
		   printf("此编码前的数据量为%dB\n",weishu*64.0);
		   printf("此编码的图像的熵为%f\n",HS);
		  for(i=0;i<allmount;i++)
		  for(g[i]=0,j=0;code[i].ma[j]!='\0';j++)g[i]++;
		  i=0;
          for(i=0;i<allmount;i++)
			 for(j=0;j<allmount;j++)
			     if(code[i].rate!=jiedian[j].rate)continue;
				 else sum=sum+g[i]*jiedian[j].mount/64.0;
          printf("此编码的平均码长为:%f\n",sum);
		   printf("此编码后的数据量为%fB\n",sum*64);
		   fun3=weishu/sum;
		   fun4=HS/sum;
           printf("此编码的压缩比为%f\n",weishu/sum);
           printf("此编码的效率为%f\n",HS/sum);
}
void function3()
{  printf("您使用的是RLE行程编码算法\n");
   printf("\n");
   double HS=function5();
   int b[8][8];
   int outlet[100]={0};
   int i,j,k=1,m=0,sign=1;
   for(i=0;i<8;i++)
	   for(j=0;j<8;j++)
	    b[i][j]=a[i][j];
	   printf("开始进行编码\n");
       for(i=0,j=0;i<8;i++)
	   {  j=0;
		   outlet[m]=a[i][j];
		   for(j=0,k=1;j<7;j++)
		   {      
		      if(a[i][j]==a[i][j+1])
			  {   k++;
		          continue;
			  }
			  else
			  {
				  m++;
				  outlet[m]=k;
			      m++;
				  outlet[m]=a[i][j+1];
			      k=1;
			  }
		   }
		   m++;
		   outlet[m]=k;
		   m++;
	   }
	   printf("输出编码后结果前面为数据后面为重复的量\n");
	   for(i=0;i<m;i++)
		   printf("%d,",outlet[i]);
	       printf("\n");
		   printf("输出RLE编码的一些参数\n");
		   printf("此编码前的数据量为%dB\n",(64*weishu));
		   printf("此编码的图像的熵为%f\n",HS);
           printf("此编码后的数据量为%dB\n",(m+1)*3);
           printf("此编码的压缩比为%f\n",64.0/(m+1));
		   fun5=64.0/(m+1);
		   fun6=HS/weishu;
           printf("此编码的效率为%f\n",HS/weishu);
		   
}
void function4()
{   printf("您使用的是选择较好编码算法的功能\n");
    printf("\n");
	int i;
    double func[3]={fun1,fun3,fun5},min=0;
	for(i=0;i<3;i++)
	if(min>=func[i])continue;
	else min=func[i];
    if(func[0]==min) printf("根据编码效率您可以选择哈夫曼算法比较好\n");
	if(func[1]==min) printf("根据编码效率您可以选择香农-费诺算法比较好\n");
    if(func[2]==min) printf("根据编码效率您可以选择RLE算法比较好\n");
}
double function5()
{
   int b[8][8],j,i,t;
   double HS=0;
   allmount=0;
   weishu=0;
  jiedian=(QW)malloc(64*sizeof(QQ));
  for(i=0;i<64;i++)
  {
	  jiedian[i].mount=0;
	  jiedian[i].rate=-1;
  }
   for(i=0;i<8;i++)
	 for(j=0;j<8;j++)
	   b[i][j]=a[i][j];
	for(i=0;i<8;i++)
		for(j=0;j<8;j++)
         for(t=0;t<64;t++)
		 {
             if(jiedian[t].rate!=b[i][j]&&jiedian[t].rate==-1){jiedian[t].rate=b[i][j];jiedian[t].mount++;break;}
			 else if(jiedian[t].rate!=b[i][j]&&jiedian[t].rate!=-1);
			 else if(jiedian[t].rate==b[i][j]) {jiedian[t].mount++;break;}
		 }
		 for(i=0;i<64;i++)
		   if(jiedian[i].rate!=-1) allmount++;
		   for(i=2;i<allmount;i=i*2)weishu++;
			   weishu++;
		   printf("%d,%d\n",allmount,weishu);
		 for(i=0;i<64;i++)
		 if(jiedian[i].rate!=-1) HS=HS+(jiedian[i].mount/64.0)*log10(64.0/jiedian[i].mount)/log10(2.0);
         return HS;
}
void  function6(at HT,bb code1,int n,int m)
{  at HR;
   int i=0,sum=0,t=0,ms,mx,j,sum1=0,sum2=0;
   t=function7(HT,n,m);
   HR=HT+t;
   ms=t;
   mx=n-t;
   for(i=0;i<ms;i++)
    sum1=sum1+(HT+i)->weight;
   for(i=0;i<mx;i++)
	sum2=sum2+(HR+i)->weight;
      for(i=0;i<ms;i++)
 	  for(j=0;j<allmount;j++)
 		  if((HT+i)->rate==code1[j].rate&&(HT+i)->weight!=0) {code1[j].ma[(code1[j].cishu)]='1';code1[j].cishu++;}
    for(i=0;i<mx;i++)
 	   for(j=0;j<allmount;j++)   
 		   if((HR+i)->rate==code1[j].rate&&(HR+i)->weight!=0){code1[j].ma[(code1[j].cishu)]='0';code1[j].cishu++;}
      if((HT+0)->weight==sum1&&(HR+0)->weight==sum2);
	  else if((HT+0)->weight!=sum1&&(HR+0)->weight==sum2) function6(HT,code1,ms,sum1);
	  else if((HT+0)->weight==sum1&&(HR+0)->weight!=sum2) function6(HR,code1,mx,sum2);
	  else if((HT+0)->weight!=sum1&&(HR+0)->weight!=sum2) {function6(HT,code1,ms,sum1);function6(HR,code1,mx,sum2);}
}
int function7(at HT,int n,int m)
{   
	int cd[64],t=0,i,j,sum=0,min=10000;
	for(i=0;i<64;i++)
		cd[i]=10000;
	 for(i=0;i<n;i++)
	 {   sum=sum+(HT+i)->weight;
		 cd[i]=abs(m-2*sum);
	 }
     for(j=0;j<n;j++)
	     if(min<=cd[j])continue;
		 else min=cd[j];
	  for(i=0;i<n;i++)
		  if(min!=cd[i])continue;
		  else { t=i;break;}
		  return (t+1);
}