huffman.cpp

哈弗曼编码算法的实现

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<conio.h>
void shuru(void);
void huffman();

void main()
{
  srand(time(NULL)); //   随机种子
    int i,j,num,f=0;
	int t=0;
	int randomshu[10000]={0};
	int dataH[2500]={0};
	char bian[100000]={0};
	float count[16]={0};
    char s[16]={0};
	char source[2500]={0};
	
    for(i=0;i<10000;i++)
	{
        randomshu[i]=rand()%2;// 产生随机的二进制码
	}

	for(i=0;i<10000;i++)
    {
		printf("%d",randomshu[i]); 
    }                                   //  输出随机的二进制码


	printf("\n******************************输入的以下信源符号********************************\n\n");
	for(j=0,i=0;j<9996;j+=4)
	 
	 {
		  dataH[i]=8*randomshu[j]+4*randomshu[j+1]+2*randomshu[j+2]+randomshu[j+3];  
	      switch (dataH[i])
		  {
			  case 0:source[i++]='0';count[0]++;s[0]='0';break;
			  case 1:source[i++]='1';count[1]++;s[1]='1';break;
			  case 2:source[i++]='2';count[2]++;s[2]='2';break;
			  case 3:source[i++]='3';count[3]++;s[3]='3';break;			
			  case 4:source[i++]='4';count[4]++;s[4]='4';break;
			  case 5:source[i++]='5';count[5]++;s[5]='5';break;
			  case 6:source[i++]='6';count[6]++;s[6]='6';break;
			  case 7:source[i++]='7';count[7]++;s[7]='7';break;
			  case 8:source[i++]='8';count[8]++;s[8]='8';break;
			  case 9:source[i++]='9';count[9]++;s[9]='9';break;
			  case 10:source[i++]='A';count[10]++;s[10]='A';break;			
			  case 11:source[i++]='B';count[11]++;s[11]='B';break;
			  case 12:source[i++]='C';count[12]++;s[12]='C';break;
			  case 13:source[i++]='D';count[13]++;s[13]='D';break;		  
			  case 14:source[i++]='E';count[14]++;s[14]='E';break;
			  case 15:source[i++]='F';count[15]++;s[15]='F';break;
				  
		  }
	}

	
	for(i=0;i<2500;i++)
		printf("%c",source[i]);//      将产生的二进制码进行四次扩展，并用16进制表示输出信源符号
	for(i=0;i<16;i++)
	{
		count[i]=(count[i])/2500.0;
		printf("\n%c的概率：%f",s[i],count[i]);  //输出个信源符号的概率
	}	  
    
  printf("\n");
typedef  struct    //    结构体定义，定义一个树
  {
      float quanzhi;
	  char  jiedian;
	  int lchild,rchild,parent;
  }hufmtree;
  hufmtree tree[31];

  int p1,p2;
  float zxiao,cxiao;
  for(i=0;i<31;i++)         //  初始化哈弗曼树的雏形
  {
    tree[i].parent=0;
	tree[i].lchild=0;
	tree[i].rchild=0;
	tree[i].quanzhi=0.0;
	tree[i].jiedian='0';
  }
  for(i=0;i<16;i++)      //给叶子几点赋值
  {
      tree[i].quanzhi=count[i];
	  tree[i].jiedian=s[i];
  }
  for(i=16;i<31;i++)
  {
     p1=p2=0;
	 zxiao=cxiao=1;
	 for(j=0;j<=i-1;j++)
	 {
		 if(tree[j].parent==0)
			 if(tree[j].quanzhi<zxiao)
			 {
			    cxiao=zxiao;
				zxiao=tree[j].quanzhi;
				p2=p1;
				p1=j;
			 }else if(tree[j].quanzhi<cxiao)
			 {
			    cxiao=tree[j].quanzhi;
				p2=j;
			 }
	 }
			 tree[p1].parent=i;
			 tree[p2].parent=i;
			 tree[i].lchild=p1;
			 tree[i].rchild=p2;
			 tree[i].quanzhi=tree[p1].quanzhi+tree[p2].quanzhi;     //  根据哈弗曼算法建立哈弗曼树
  }
  int c,p;
  typedef struct   //     定义一个结构体存放 各个信源符号通过哈弗曼编码所得的二进制码
  {
     char  bits[16];
	 int  start;
	 char data;
  }codetype;
  codetype code[16];
  codetype cd;
  for(i=0;i<16;i++)          //  哈弗曼编码
  {
     cd.start=16;
	 c=i;
	 p=tree[c].parent;
	 cd.data=tree[c].jiedian;
	 while(p!=0)
	 {
	       cd.start--;
		   if(tree[p].lchild==c) cd.bits[cd.start]='0';
		   else cd.bits[cd.start]='1';
		   c=p;
		   p=tree[c].parent;	
	 }
	 code[i]=cd;
  }

 //   for(i=0;i<16;i++){printf("%d",code[i].start);}
//	while (code[7].start!=16) printf("%c",code[7].bits[code[7].start++]);
  for (i=0;i<2500;i++)               //将原来输入的信源符号通过编码产生的哈弗曼编码的01序列输出
  {
      switch (source[i])
	  {
	      case '0': while (code[0].start!=16){ bian[t]=code[0].bits[code[0].start++];t++;f++;} code[0].start-=f;f=0; break;
		  case '1': while (code[1].start!=16){ bian[t]=code[1].bits[code[1].start++];t++;f++;} code[1].start-=f;f=0; break;
	      case '2': while (code[2].start!=16){ bian[t]=code[2].bits[code[2].start++];t++;f++;} code[2].start-=f;f=0; break; 
	      case '3': while (code[3].start!=16){ bian[t]=code[3].bits[code[3].start++];t++;f++;} code[3].start-=f;f=0; break;
		  case '4': while (code[4].start!=16){ bian[t]=code[4].bits[code[4].start++];t++;f++;} code[4].start-=f;f=0; break;
		  case '5': while (code[5].start!=16){ bian[t]=code[5].bits[code[5].start++];t++;f++;} code[5].start-=f;f=0; break;
		  case '6': while (code[6].start!=16){ bian[t]=code[6].bits[code[6].start++];t++;f++;} code[6].start-=f;f=0; break;
		  case '7': while (code[7].start!=16){ bian[t]=code[7].bits[code[7].start++];t++;f++;} code[7].start-=f;f=0; break;
		  case '8': while (code[8].start!=16){ bian[t]=code[8].bits[code[8].start++];t++;f++;} code[8].start-=f;f=0; break;
		  case '9': while (code[9].start!=16){ bian[t]=code[9].bits[code[9].start++];t++;f++;} code[9].start-=f;f=0; break;
		  case 'A': while (code[10].start!=16){ bian[t]=code[10].bits[code[10].start++];t++;f++;} code[10].start-=f;f=0; break;
		  case 'B': while (code[11].start!=16){ bian[t]=code[11].bits[code[11].start++];t++;f++;} code[11].start-=f;f=0; break;
		  case 'C': while (code[12].start!=16){ bian[t]=code[12].bits[code[12].start++];t++;f++;} code[12].start-=f;f=0; break;
		  case 'D': while (code[13].start!=16){ bian[t]=code[13].bits[code[13].start++];t++;f++;} code[13].start-=f;f=0; break;
		  case 'E': while (code[14].start!=16){ bian[t]=code[14].bits[code[14].start++];t++;f++;} code[14].start-=f;f=0; break;
		  case 'F': while (code[15].start!=16){ bian[t]=code[15].bits[code[15].start++];t++;f++;} code[15].start-=f;f=0; break;
	  }

  }

printf("\n");
printf("\n\n*****************************输出哈弗曼编码后的01序列***************************\n\n");
//printf("%d",t);
i=0;
while(t!=0){printf("%c",bian[i++]); t--;}  //输出编码序列
num=i;
printf("\n\n**************************哈弗曼解码后的信源符号********************************\n\n");
j=30;

for(i=0;i<num;i++)   //    哈弗曼解码
{
    if(bian[i]=='0') j=tree[j].lchild;
	else  j=tree[j].rchild;
	if(tree[j].lchild==0)
	{
	    putchar(code[j].data);
		j=30;
	}
}
getch();

 
	 
   

}