1.cpp

哈夫曼编码

#include<stdlib.h>
#include<string.h> 
#include<stdio.h>
#include<math.h> 
#include<time.h>
#define sour_16_num 100
void main()
{
	int i=0,j=0,k=0,sour_2[4*sour_16_num];
	char sour_16[sour_16_num],word[16]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
	float prob[16]={0};
	srand(time(NULL));
	printf("******************************产生的16进制信源为：******************************");
	for(i=0;i<sour_16_num;i++)
	{
		sour_2[j++]=rand()%2;
		sour_2[j++]=rand()%2;
		sour_2[j++]=rand()%2;
		sour_2[j++]=rand()%2;
		sour_16[i]=sour_2[j-4]*8+sour_2[j-3]*4+sour_2[j-2]*2+sour_2[j-1];
		switch(sour_16[i])
		{
		case 0:  sour_16[i]='0'; prob[0]++;  break;
		case 1:  sour_16[i]='1'; prob[1]++;  break;
		case 2:  sour_16[i]='2'; prob[2]++;  break;
		case 3:  sour_16[i]='3'; prob[3]++;  break;
		case 4:  sour_16[i]='4'; prob[4]++;  break;
		case 5:  sour_16[i]='5'; prob[5]++;  break;
		case 6:  sour_16[i]='6'; prob[6]++;  break;
		case 7:  sour_16[i]='7'; prob[7]++;  break;
		case 8:  sour_16[i]='8'; prob[8]++;  break;
		case 9:  sour_16[i]='9'; prob[9]++;  break;
		case 10: sour_16[i]='A'; prob[10]++; break;
		case 11: sour_16[i]='B'; prob[11]++; break;
		case 12: sour_16[i]='C'; prob[12]++; break;
		case 13: sour_16[i]='D'; prob[13]++; break;
		case 14: sour_16[i]='E'; prob[14]++; break;
		case 15: sour_16[i]='F'; prob[15]++; break;
		}
		printf("%c ",sour_16[i]);
	}
	printf("\n******************************产生的二进制信源为：******************************");
	for(j=0;j<4*sour_16_num;j++)
		printf("%d",sour_2[j]);
	for(j=0;j<16;j++)
		prob[j]=prob[j]/sour_16_num;
	typedef char datatype;
	typedef  struct
	{
		float weight;
		datatype data;
		int lchild,rchild,parent;
	}hufmtree;
	hufmtree tree[31];
	float small1,small2;
	int p1,p2;
	for(i=0;i<31;i++)
	{
		tree[i].parent=0;
		tree[i].lchild=0;
		tree[i].rchild=0;
		tree[i].weight=0.0;
		tree[i].data='0';
	}
	for(i=0;i<16;i++)
	{
		tree[i].weight=prob[i]/sour_16_num;
		tree[i].data=word[i];
	}
	for(i=16;i<31;i++)
	{
		p1=p2=0;
		small2=3.4*pow(10,38);
		small1=small2;
		for(j=0;j<=i-1;j++)
			if(tree[j].parent==0.0)
				if(tree[j].weight<small1)
				{
					small2=small1;
					small1=tree[j].weight;
					p2=p1;
					p1=j;
				}
				else  if(tree[j].weight<small2)
				{
					small2=tree[j].weight;
					p2=j;
				}
				tree[p1].parent=i;
				tree[p2].parent=i;
				tree[i].lchild=p1;
				tree[i].rchild=p2;
				tree[i].weight=tree[p1].weight+tree[p2].weight;
	}
	typedef char datatype;
	typedef struct
	{
		char bits[16];
		int start;
		datatype data;
	}codetype;
	codetype code[16];
	int c,p;
	codetype cd;
	for(i=0;i<16;i++)
	{
		cd.start=16;
		c=i;
		p=tree[c].parent;
		cd.data=tree[c].data;
		while(p!=NULL)
		{
			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;
		code[i].bits[cd.start-1]='S';
	}
	for(i=0;i<16;i++)
	{
		j=0;k=0;
		while(code[i].bits[j]!='S')
			j++;
		j=j+1;
		for(;j<16;j++)
		{
			code[i].bits[k++]=code[i].bits[j];
		}
		code[i].bits[k]='\0';
	}
	printf("\n************************************码字为：************************************");
	for(i=0;i<16;i++)
	{
		j=0;
		while(code[i].bits[j]!='\0')
			printf("%c",code[i].bits[j++]);
		printf("   ");
	}
	k=0;
	char code_2[6*sour_16_num];
	for(i=0;i<sour_16_num;i++)
		switch(sour_16[i])
		{
		case '0':  for(j=0;code[0].bits[j]!='\0';j++)   code_2[k++]=code[0].bits[j];  break;
		case '1':  for(j=0;code[1].bits[j]!='\0';j++)   code_2[k++]=code[1].bits[j];  break;
		case '2':  for(j=0;code[2].bits[j]!='\0';j++)   code_2[k++]=code[2].bits[j];  break;
		case '3':  for(j=0;code[3].bits[j]!='\0';j++)   code_2[k++]=code[3].bits[j];  break;
		case '4':  for(j=0;code[4].bits[j]!='\0';j++)   code_2[k++]=code[4].bits[j];  break;
		case '5':  for(j=0;code[5].bits[j]!='\0';j++)   code_2[k++]=code[5].bits[j];  break;
		case '6':  for(j=0;code[6].bits[j]!='\0';j++)   code_2[k++]=code[6].bits[j];  break;
		case '7':  for(j=0;code[7].bits[j]!='\0';j++)   code_2[k++]=code[7].bits[j];  break;
		case '8':  for(j=0;code[8].bits[j]!='\0';j++)   code_2[k++]=code[8].bits[j];  break;
		case '9':  for(j=0;code[9].bits[j]!='\0';j++)   code_2[k++]=code[9].bits[j];  break;
		case 'A':  for(j=0;code[10].bits[j]!='\0';j++)  code_2[k++]=code[10].bits[j]; break;
		case 'B':  for(j=0;code[11].bits[j]!='\0';j++)  code_2[k++]=code[11].bits[j]; break;
		case 'C':  for(j=0;code[12].bits[j]!='\0';j++)  code_2[k++]=code[12].bits[j]; break;
		case 'D':  for(j=0;code[13].bits[j]!='\0';j++)  code_2[k++]=code[13].bits[j]; break;
		case 'E':  for(j=0;code[14].bits[j]!='\0';j++)  code_2[k++]=code[14].bits[j]; break;
		case 'F':  for(j=0;code[15].bits[j]!='\0';j++)  code_2[k++]=code[15].bits[j]; break;
		}
	code_2[k]='\0';
	printf("\n************************************编码为：************************************");
	for(i=0;code_2[i]!='\0';i++)
		printf("%c",code_2[i]);
	printf("\n************************************译码为：************************************");
	k=0;
	while(code_2[k]!='\0')
	{
		for(i=0;i<16;i++)
		{
			for(j=0;code[i].bits[j]!='\0';j++)
				if(code[i].bits[j]!=code_2[k++])
				{
					k=k-j-1;
					break;
				}
			if(code[i].bits[j]=='\0')
				break;
		}
		printf("%c ",code[i].data);
	}
	float Hs=0,leng=0;
	for(i=0;i<16;i++)
	{
		Hs=Hs-prob[i]*log(prob[i])/log(2.0);
		leng=leng+prob[i]*(strlen(code[i].bits));
	}
	printf("\n熵为：%f  平均码长为：%f  效率为：%f\n",Hs,leng,Hs/leng);
	system("pause");
}