hzy_huffman.c

实现霍夫曼编码

/*Hzy_huffman.c
**This is a C program
**fuction:huffman coding
**author:HZY
**This program is protected by copyright law
*/
//******************************************************************************************//

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
//#include<alloc.h>
#define ARRAYLEN 50                                  //最大存储空间
#define TESTVALUE 1.0e-6                                //允许最小误差
#define FORMAT "%s\t\t %s\t\t\t%5.4f\t\n"            //输出格式

//******************************************************************************************//

struct huff                                             //定义结构体存储编码信息
{
	char  codeName[20];                              //信源符号
	char  code[10];                                     //编码
	float probability;                               //信源概率
	int tag_1;                                          //排序标记
	int tag_2;                                       //编码标记
	int number;                                         //输入次序
};

//******************************************************************************************//

int input(struct huff * info,int * num)              //输入信源个数、概率信息
{
	int i;
	int N;	
	float sum = 0.0;                                //变量判断输入是否正确
	printf("\n************  WELCOME TO HUFFMAN CODER !  ************\n");
	printf("\n======================================================");
	printf("\n====================INPUT BEGIN=======================\n");
	printf("\n请输入信源个数:\t");
	scanf("%d",num);
	N=*num;
	if(N > ARRAYLEN )
	{
		printf("\n输入值超出范围，最大值为50，请与作者联系修改!\n\n");
			return -1;
	}
	printf("\n请输入信源符号及概率\n\n");
	for(i=0;i<N;i++)
	{
		printf("No.  %d\n",i+1);
		(info+i)->number = (i+1);
		printf("信源符号：");
		scanf("%s",(info+i)->codeName);
		printf("信源概率：");		
		scanf("%f",&((info+i)->probability));
		printf("\n");
		if(((info+i)->probability > 1.0)||((info+i)->probability < 0.0))
		{
			printf("\n输入数据有误!!\n");
			return -1;
		}
		sum += (info+i)->probability;
	}
	if((fabs(sum-1.0))>TESTVALUE)
	{
		printf("\n输入数据有误!!\n");
		return(-1);
	}
	printf("\n====================INPUT END=========================");
	printf("\n======================================================\n");
	return 0;
}

//******************************************************************************************//

void initial(struct huff * info,int num)   //信源内部初始化
{
	int i;
	for(i=0;i<num;i++)
	{
		strcpy((info+i)->code,"");
		(info+i)->tag_1 = 0;
		(info+i)->tag_2 = 0;
	}
}

//******************************************************************************************//

void output(struct huff * info,int num)     //huffman 编码信息输出
{
	int i,j;
	j=1;
	printf("\n\n\n\n***************  THE HUFFMAN CODER !  ****************\n");
	printf("信源符号\t HUFFMAN编码\t \t概率\n");            
	for(i=0;i<num;i++)
	{
		if(info[i].number == j)             //当结构内部顺序与输入次序相同时输出
		{
			printf(FORMAT,(info+i)->codeName,(info+i)->code,(info+i)->probability);
			j++;
			i=-1;
		}
	}
	printf("****************  THANKS FOR USING!  *****************\n");
}

//******************************************************************************************//

void WriteCode(struct huff * info,int num)        //将结果以屏幕输出的格式保存到文件Code_Output.txt
{
  FILE *fp ;
  int i,j;
  j=1;
  fp = fopen("Code_Output.txt", "w") ;
  fprintf(fp,"信源个数：%d\n",num);
  fprintf(fp,"\n***************  THE HUFFMAN CODER !  ****************\n\n");
  fprintf(fp,"信源符号\t HUFFMAN编码\t \t概率\n"); 
  for(i=0;i<num;i++)
  {
	  if(info[i].number == j)    
	  {
		  fprintf(fp,FORMAT,(info+i)->codeName,(info+i)->code,(info+i)->probability);
		  j++;
		  i=-1;
	  }
  }
  fprintf(fp,"\n****************  THANKS FOR USING!  *****************\n");
  fclose(fp) ;
}

//******************************************************************************************//

void sortByPrb(struct huff * structArray,int arrayNum)  //排序
{
	int i,j;
    struct huff temp;                                   //内部变量用来交换
	if(arrayNum == 1)
	{
	}
	else
	{
		for(i=0;i<=arrayNum-1;i++)
		{
			for(j=i+1;j<=arrayNum-1;j++)
			{
				if(structArray[i].probability < structArray[j].probability)
				{
					temp = structArray[i];
					structArray[i] = structArray[j];
					structArray[j] = temp;
				}
				else if(structArray[i].probability == structArray[j].probability)
				{
					if(structArray[j].tag_1 == 1)          //当概率相等时按标记tag_1的值确定排序位置
					{
						structArray[j].tag_1 = 0;                
						temp = structArray[i];
						structArray[i] = structArray[j];
						structArray[j] = temp;
					}
				}
			}
		}
		for(i=0;i<arrayNum;i++)
		{
			if(structArray[i].tag_1 == 1)
			{
				structArray[i].tag_1 = 0;                 //将tag_1置0;
			}
		}
	}
}

//******************************************************************************************//

void huff_encode(struct huff * structArray,int arrayNum)        //HUFFMAN编码
{
	struct huff  * subArray;                         //内部结构体指针变量,用来保存信息及下一次迭代	
	int subArrayNum = arrayNum-1;
	int i,j=0;
	subArray = (struct huff *)calloc(arrayNum,sizeof(struct huff)); //分配内存空间
	for(i=0;i<arrayNum;i++)
	{
		subArray[i] = structArray[i];
	}
	sortByPrb(subArray,arrayNum);
	if(arrayNum == 1)
	{
		strcpy(structArray[0].code,"1");
	}
	else
	{
		if(arrayNum == 2)                                //递归出口
		{
			strcpy(subArray[0].code,"0");
			strcpy(subArray[1].code,"1");
		}
		else
		{
			for(i=0;i<subArrayNum;i++)                   //将上一层tag_2置0,避免冲突
			{
				subArray[i].tag_2 = 0;
			}                                            //将排序后的后两个概率相加后重新赋给数组
			subArray[subArrayNum-1].probability = subArray[subArrayNum].probability + subArray[subArrayNum-1].probability;
			strcpy(subArray[subArrayNum-1].codeName,"new");
			subArray[subArrayNum-1].tag_1 = 1;           //置排序标记tag_1
			subArray[subArrayNum-1].tag_2 = 1;                //置编码标记tag_2
			sortByPrb(subArray,subArrayNum);		     //再排序
			huff_encode(subArray,subArrayNum);                //递归
		}
	}
		if(arrayNum == 2)                               //递归返回
		{
			strcpy(structArray[0].code,subArray[0].code);
			strcpy(structArray[1].code,subArray[1].code);
		}
		else
		{
			for(i=0;i<subArrayNum;i++)
			{
				if(subArray[i].tag_2 == 1)             //将tag_2=1的编码传递给上一层的最后的两个信源,并进行本次编码
				{
					strcpy(structArray[arrayNum-1].code,subArray[i].code);				
					strcpy(structArray[arrayNum-2].code,subArray[i].code);				
					strcat(structArray[arrayNum-1].code,"1");				
					strcat(structArray[arrayNum-2].code,"0");		
				}
				else
				{
					strcpy(structArray[j].code,subArray[i].code);  //tag_2=0的直接传给上一层的对应信源
					j++;
				}
			}
		}
	
	free(subArray);                                              //释放出本次调用分配空间
}


//******************************************************************************************//

int main()
{
	struct huff info[ARRAYLEN];
	int signalNum,Error;	
	Error = input(info,&signalNum);                 //数据输入
	if(Error < 0)
	{
		return -1;
	}
	initial(info,signalNum);                        //内部初始化
	sortByPrb(info,signalNum);                      //排序
	huff_encode(info,signalNum);                    //编码
	output(info,signalNum);                         //输出到屏幕
	WriteCode(info,signalNum);                      //写到文件
	return 0;
}

//******************************************************************************************//
//THE END