huffman.cpp

利用哈夫曼编码进行通信可以大大提高信道利用率

#include<stdio.h> 
#include<stdlib.h>
#include<string.h>

typedef struct
{ 
   char elem;
   int weight; 
   int parent,lchild,rchild; 
}HTNode,*HuffmanTree;           //动态分配数组存储赫夫曼树

typedef char **HuffmanCode;     //动态分配数组存储赫夫曼树编码表

void Initialization();
void Encoding();
void Decoding();
void HuffmanCoding(int); 
void Select(int,int *,int *); 
void PrintHufmFigue();
void putout(int,int);
void Turn(int,void(* Visit)(int,int));
void TreePrint();


//-------------------全局函数----------------------- 
int ipt=1,n,q,p=0,code_num=0,TempLen=0,diamonds,lay;
int w1=100000,w2=100000,w3=100000;
HuffmanCode HC=NULL; 
HuffmanTree HT,T=NULL;

int main()
{
	char key;
	system("color F0");
	printf("	       ╔━━━━━━━━━━━━━━━━━━━━━╗\n");
	printf("	       ┃              赫夫曼编/译码器             ┃\n");
	printf("	       ┃                                          ┃\n");
	printf("	       ┃             06计算机<4>郑康生            ┃\n");
	printf("	       ╚━━━━━━━━━━━━━━━━━━━━━╝\n");

	do{
		printf("\n\n\n");
		printf("	       ╔━━━━━━━━━━━━━━━━━━━━━╗\n");
		printf("	       ┃                 操作菜单                 ┃\n");
		printf("	       ┃                                          ┃\n");
		printf("	       ┃         I:初始化  (Initialization)       ┃\n");
		printf("	       ┃         E:编  码  (Encoding      )       ┃\n");
		printf("	       ┃         D:译  码  (Decoding      )       ┃\n");
		printf("	       ┃         P:打印表  (TreePrint     )       ┃\n");
		printf("	       ┃         T:打印图  (Initialization)       ┃\n");
		printf("	       ┃         Q:退  出  (Initialization)       ┃\n");
		printf("	       ┃                                          ┃\n");
		printf("	       ╚━━━━━━━━━━━━━━━━━━━━━╝\n");
		printf("\n\n");
		printf("Please Enter a key of the operation:");
		scanf("%c",&key);
		getchar();
		switch(key)
		{
			case 'i':
			case 'I':
				Initialization();
				break;
			case 'e':
			case 'E':
				Encoding();
				break;
			case 'd':
			case 'D':
				Decoding();
				break;
			case 'p':
			case 'P':
				PrintHufmFigue();
				break;
			case 't':
			case 'T':
				TreePrint();
		}
	}while(key!='q'&&key!='Q');

	return 1;
}


//-----------Initialization----------------------
void Initialization()
{
	int i,m;
	char style[]={' ','\0'};
	printf("Please input the number of Node:" ); 
	scanf("%d",&n); 
	getchar();

	m=2*n-1; 
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));     //0号单元未用
	T=HT+m;
	for(i=1;i<=n;i++)
	{ 
		printf("Input characters and weight(just like a 30Enter):"); 
		scanf("%c%d",&HT[i].elem,&HT[i].weight);
		getchar();
		HT[i].parent=HT[i].lchild=HT[i].rchild=0;
	} 
	HuffmanCoding(n);
	FILE* FhfmTreeP=NULL;
	if(NULL==(FhfmTreeP=fopen("E:\\hfmTree.txt","w")))
		printf("Open hfmTree.txt failed!\n");
	else
	{
		for(i=1;i<=n;i++) 
		{ 
			fprintf(FhfmTreeP,"%c",HT[i].elem);
			fputs(HC[i],FhfmTreeP); 
			fputs(style,FhfmTreeP); 
		}
	}
	fclose(FhfmTreeP);
	printf("Every charactor has been coded and puted into E:\\hfmTree.txt!\n");	
	return;
}



//----------------P147 算法6.12-------------------
void HuffmanCoding(int n)
{ //weight存放n个字符的权值（均>0），构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC。
	int i,m,s1,s2,start,c,f; 
	char *cd; 
	m=2*n-1;
	for(i=n+1;i<=m;++i)
	{ 
		HT[i].elem='0'; 
		HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=0; 
	}

	for(i=n+1;i<=m;++i)
	{											//建赫夫曼树
		Select(i-1,&s1,&s2);					//在HT[1...i-1]选择parent为0且weight最小的两个结点，其序号分别为s1,s2.
		HT[s1].parent=i;HT[s2].parent=i; 
		HT[i].lchild=s1;HT[i].rchild=s2; 
		HT[i].weight=HT[s1].weight+HT[s2].weight; 
	} 
	//-----------------从叶子到根逆向求每个字符的赫夫曼编码--------------------------
	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));         //分配n个字符编码的头指针向量
	cd=(char *)malloc(n*sizeof(char));					//分配求编码的工作空间
	cd[n-1]='\0';										//编码结束符
	for(i=1;i<=n;++i)
	{													//逐个字符求赫夫曼编码
		start=n-1; 
		for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //从叶子到根逆向求编码
		{ 
			if(HT[f].lchild==c) cd[--start]='0'; 
			else cd[--start]='1'; 
		} 

		HC[i]=(char *)malloc((n-start)*sizeof(char));   //为第i个字符编码分配空间
		strcpy(HC[i],&cd[start]);						//从cd复制编码（串）到HC
	}
	free(cd);											//释放工作空间
	return;
}//HuffanCoding

void Select(int n,int *s1,int *s2) 
{ 
  int i; 
  (*s1)=(*s2)=0; 
  for(i=1;i<=n;i++)
  { 
    if(HT[i].weight<HT[(*s2)].weight&&HT[i].parent==0&&(*s2)!=0)
	{ 
      if(HT[i].weight<HT[(*s1)].weight)
		{ 
			(*s2)=(*s1); 
			(*s1)=i; 
		}	 
      else (*s2)=i; 

    } 

    if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)
	{ 
      if((*s1)==0) (*s1)=i; 
      else if((*s2)==0)
		{ 
			if(HT[i].weight<HT[(*s1)].weight)
			{ 
				(*s2)=(*s1); 
				(*s1)=i; 
			} 
			else (*s2)=i; 
		} 
	} 
  } 

  if((*s1)>(*s2))
  { 
    i=(*s1); 
	(*s1)=(*s2); 
	(*s2)=i; 
  } 
  return; 
}



//--------------------Encoding------------------------
void Encoding()
{
	int i,j,all;
	char temp[1000],code[10000];
	printf("Please put in the sentence you want to Encoding:");
	//scanf("%s",temp);
	getchar();
	gets(temp);
		code[0]='\0';
	FILE* FToBeTranP=NULL;
	if(NULL==(FToBeTranP=fopen("E:\\ToBeTran.txt","w")))
		printf("Open ToBeTran.txt failed!\n");
	else
		fputs(temp,FToBeTranP);
	fclose(FToBeTranP);

	TempLen=strlen(temp);
	for(i=0;i<TempLen;i++)
	{
		all=0;
		for(j=1;j<=n;j++)
		{
			if(temp[i]==HT[j].elem)
			{
				strcat(code,HC[j]);
				all=1;
			}
		}
		if(all=0)
			printf("Some charactor in the sentence are not matching!!!");
	}
	
	code_num=strlen(code);
	printf("Codes of the sentence are:\n%s\n",code);
	FILE* FCodeFileP=NULL;
	if(NULL==(FCodeFileP=fopen("E:\\CodeFile.txt","w")))
		printf("Open CodeFile.txt failed!\n");
	else
		fputs(code,FCodeFileP);
	fclose(FCodeFileP);
	printf("And have put into E:\\CodeFile.txt!\n");
	return;
} 



//---------------------Decoding-----------------------
void Decoding()
{
	int m,i,p=0;
	char q,*Decode,*Sentence;
	FILE* FDecodeP=NULL;

		if(NULL==(FDecodeP=fopen("E:\\CodeFile.txt","r")))
			printf("Open E:\\CodeFile.txt failed!\n");
		else
		{
			FILE *TxtFile=NULL;
			if(NULL==(TxtFile=fopen("E:\\TxtFile.txt","w")))
				printf("Open E:\\TxtFile.txt failed!\n");
			else
			{
				Sentence=(char*)malloc(TempLen*sizeof(char));
				Decode=(char*)malloc(code_num*sizeof(char));
				fgets(Decode,code_num+1,FDecodeP);
				m=2*n-1;
				for(i=0;Decode[i-1]!='\0';i++) 
				{ 
					q=Decode[i]; 
					if(HT[m].lchild==0) 
					{	 
						Sentence[p]=HT[m].elem; 
						p++; 
						m=2*n-1; 
						i--; 
					} 
					else if(q=='0') m=HT[m].lchild; 
					else if(q=='1') m=HT[m].rchild; 
				} 
				Sentence[p]='\0';
				fputs(Sentence,TxtFile);
				printf("Codes have been Encoded and get a sentence:\n%s\n",Sentence);
				printf("And have been put into TxtFile.txt!\n");

			}
		}
}



//------------------------打印赫夫曼的存储情况--------------------------------
void PrintHufmFigue()
{
	int i,m;
	char end[]={'\\','\0'};
	printf("╔━━━┳━━━━┳━━━┳━━━━┳━━━━┳━━━━┳━━━━━━━━━━╗");
	printf("┃Number┃ Element┃Weight┃Parents ┃ Lchild ┃ Rchild ┃    HuffmanCode     ┃");
	printf("┣━━━╋━━━━╋━━━╋━━━━╋━━━━╋━━━━╋━━━━━━━━━━┫");
	for(i=1;i<=n;i++)
	{
	printf("┃%6d┃%8c┃%6d┃%8d┃%8d┃%8d┃%20s┃",i,HT[i].elem,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild,HC[i]);
	printf("┣━━━╋━━━━╋━━━╋━━━━╋━━━━╋━━━━╋━━━━━━━━━━┫");
	}
	m=2*n-1;
	for(i=n+1;i<=m-1;i++)
	{
	printf("┃%6d┃%8c┃%6d┃%8d┃%8d┃%8d┃%20s┃",i,HT[i].elem,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild,end);
	printf("┣━━━╋━━━━╋━━━╋━━━━╋━━━━╋━━━━╋━━━━━━━━━━┫");
	}
	printf("┃%6d┃%8c┃%6d┃%8d┃%8d┃%8d┃%20s┃",m,HT[m].elem,HT[m].weight,HT[m].parent,HT[m].lchild,HT[m].rchild,end);
	printf("╚━━━┻━━━━┻━━━┻━━━━┻━━━━┻━━━━┻━━━━━━━━━━╝");
	return;
}




//----------------Tree Printing--------------------
void TreePrint()
{
	int MaxCode,MaxI=1,Floor,numb,i;
	numb=2*n-1;
	MaxCode=strlen(HC[1]);
	for(i=1;i<=n;i++)
	{
		if(strlen(HC[i])>MaxCode)
		{
			MaxCode=strlen(HC[i]);
			MaxI=i;
		}
	}

	Floor=MaxCode+1;
	diamonds=Floor+10;
	lay=diamonds;
	Turn(numb,putout);
	return;
}

void Turn(int w,void(* Visit)(int,int))
{
		p++;
		w3=w2;
		w2=w1;
		w1=w;
		if(w3<w2&&w2<w1)
			lay++;
		if(HT[w].weight!=0)
			Visit(w,lay);
		if(HT[w].lchild!=0)
		{
			lay=diamonds-p;
			Turn(HT[w].lchild,Visit);
		}
		if(HT[w].rchild!=0)
		{
			q=--p;
			lay=diamonds-q;
			Turn(HT[w].rchild,Visit);
		}

	return;
}



void putout(int lr,int count)
{
	for(;count>=1;count--)
	{
		printf("█");
	}
	if(HT[lr].lchild!=0)
		printf("%d\n",HT[lr].weight);
	else
		printf("%c\n",HT[lr].elem);
	printf("\n");
	return;
}