huffmancode.cpp

对一篇英文文章

#include "stdio.h"
#include "stdlib.h"
#include "string.h"


#define N_CHR 29
#define LIST_SIZE 2*N_CHR-1

typedef struct              //节点类型
{
	char chr;
	int weight;
	int parent,lchild,rchild;
}HTNode,*HuffmanTree;

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

//**************************创建线性表**************************************************
void CreatList(HuffmanTree &HT)             
{
	HT=(HuffmanTree)malloc((2*N_CHR+1)*sizeof(HTNode));
	if(!HT)
	{
		printf("HuffmanTree creat error\n");
		exit(0);
	}
	for(int i='a';i<='z';i++)
	{
		HT[i-'a'].chr=(char)i;
		HT[i-'a'].weight=HT[i-'a'].lchild=HT[i-'a'].parent=HT[i-'a'].rchild=0;
	}
	HT[i-'a'].chr=',';
	HT[i-'a'].weight=HT[i-'a'].lchild=HT[i-'a'].parent=HT[i-'a'].rchild=0; i++;
	HT[i-'a'].chr='.';
	HT[i-'a'].weight=HT[i-'a'].lchild=HT[i-'a'].parent=HT[i-'a'].rchild=0; i++;
	HT[i-'a'].chr=' ';
	HT[i-'a'].weight=HT[i-'a'].lchild=HT[i-'a'].parent=HT[i-'a'].rchild=0; i++;
	for(;i-'a'<LIST_SIZE;i++)                                 //初始化（权值清零）
	{
		HT[i-'a'].chr=0;
		HT[i-'a'].weight=HT[i-'a'].lchild=HT[i-'a'].parent=HT[i-'a'].rchild=0;
	}
}
//**************************************************************************************
//***************************读文件，统计字符频度（权值）*******************************
void read(HuffmanTree &HT)                
{
	char c,i;
	FILE *fp;
	if(!(fp=fopen("original.txt","r")))
	{
		printf("file open error\n");
		exit(0);
	}
	while(c!=EOF)
	{
		c=fgetc(fp);
		for(i='a';i<='z';i++)           //第一个空间空闲
		{
			if(c==i)
			{
				HT[i-'a'].weight++;
				break;
			}
		}
		if(i!='z'+1)                     //已找到匹配字符，不需再向下判断
		{
			continue;
		}
		if(c==',')
		{
			HT[i-'a'].weight++;
			continue;
		}
		i++;
		if(c=='.')
		{
			HT[i-'a'].weight++;
			continue;
		}
		i++;
		if(c==' ')
		{
			HT[i-'a'].weight++;
			continue;
		}
	}
	fclose(fp);
}
//*****************************************************************************************
/*
void order(HuffmanTree &HT)                   //按频度（权值）非递减顺序排序
{
	HTNode temp;
	HTNode *max;
	for(int i=0;i<N_CHR;i++)
	{
		max=&HT[i];
		for(int j=i+1;j<N_CHR;j++)
		{
			if(HT[j].weight<max->weight)
			{
				max=&HT[j];
			}
		}
		temp=HT[i];
		HT[i]=*max;
		*max=temp;
	}
}*/
//****************************创建赫夫曼树****************************************************
void Select(HuffmanTree &HT,int line,int &s1,int &s2)  //在HT[1]~HT[i-1]选择parent为0且weight最小的节点
{
	int minwt;
	minwt=999;
	s1=s2=LIST_SIZE+1;
	for(int i=0;i<=line;i++)
	{
		if(HT[i].weight<minwt&&HT[i].parent==0)
		{
			s1=i;
			minwt=HT[i].weight;
		}
	}
	minwt=999;
	for(i=1;i<=line;i++)
	{
		if(HT[i].weight<minwt&&HT[i].parent==0&&i!=s1)
		{
			s2=i;
			minwt=HT[i].weight;
		}
	}
}

void HuffmanCreat(HuffmanTree &HT)          //建赫夫曼树
{
	int s1,s2;
	for(int i=N_CHR;i<LIST_SIZE;i++)
	{
		Select(HT,i-1,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;
	}
}
//***************************************************************************************
//***************************求赫夫曼编码************************************************
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC)         
{
	char *CODE;
	int start;                                              //编码结束符位置
	int c,f;
	CODE=(char *)malloc(N_CHR*sizeof(char));                //用以临时存储编码
	HC=(HuffmanCode)malloc(N_CHR*sizeof(char *));       	//编码表
	CODE[28]='\0';
	for(int i=0;i<30;i++)                                   //逐个字符求赫夫曼编码 
	{
		start=28;                                           //编码结束符位置
		for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)     //从叶子到根逆向求编码
		{
			if(HT[f].lchild==c)
			{
				CODE[--start]='0';
			}
			else
			{
				CODE[--start]='1';
			}
		}
		HC[i]=(char *)malloc((N_CHR-start)*sizeof(char));      //为第i个字符编码分配空间
		strcpy(HC[i],&CODE[start]);                         //从CODE复制编码(串)到HC
	}
	free(CODE);
}
//*****************************************************************************************
//**********************将文章编码结果保存到文件code.txt中*********************************
void Writefile(HuffmanTree &HT,HuffmanCode &HC)        
{
	char c;
	int i;
	FILE *fp,*fp2;
	if(!(fp=fopen("original.txt","r")))
	{
		printf("file creat error\n");
		exit(0);
	}
	if(!(fp2=fopen("code.txt","w+")))
	{
		printf("file creat error\n");
		exit(0);
	}
	while(c!=EOF)
	{
		c=fgetc(fp);
		for(i=0;i<30;i++)
		{
			if(c==HT[i].chr)
			{
				fwrite(HC[i],strlen(HC[i]),1,fp2);
			}
		}
	}
	fclose(fp);
	fclose(fp2);
}
//*****************************************************************************************
//******************************读编码生成原文件*******************************************
void TransBack(HuffmanTree &HT,HuffmanCode &HC)
{
	FILE *fp,*fp2;
	char c;
	char *code;
	int i,sign;
	code=(char *)malloc(N_CHR*sizeof(char));
	if(!(fp=fopen("code.txt","r")))
	{
		printf("file open error\n");
		exit(0);
	}
	if(!(fp2=fopen("revert.txt","w")))
	{
		printf("file creat error\n");
		exit(0);
	}
	for(i=0;i<N_CHR;i++)                               //code置空
	{
		code[i]='\0';
	}
	c=1;
	sign=0;
	while(c!=EOF)
	{
		for(i=0;i<N_CHR;i++)
		{
			c=fgetc(fp);
			code[i]=c;
			for(int j=0;j<N_CHR;j++)          //遍历编码表
			{
				if(!strcmp(code,HC[j]))  //当前code中的字符串是编码
				{
					sign=1;
					fputc(HT[j].chr,fp2);
					for(int k=0;k<N_CHR;k++)         //code置空
					{
						code[k]='\0';
					}
					break;
				}
			}
			if(sign==1)                    //编码已匹配，code不需再向下延长
			{
				sign=0;break;
			}
		}
	}
	free(code);
	fclose(fp);
	fclose(fp2);
}
//******************************************************************************************
//*********************************生成编码表***********************************************
void WriteCodeList(HuffmanTree &HT,HuffmanCode &HC)
{
	FILE *fp;
	if(!(fp=fopen("codelist.txt","w")))
	{
		printf("file creat error\n");
		exit(0);
	}
	fprintf(fp,"chr weight parent code \n");
	for(int i=0;i<N_CHR;i++)
	{
		fprintf(fp,"%c     %d     %s \n",HT[i].chr,HT[i].weight,HC[i]);
	}
	fclose(fp);
}
//*******************************************************************************************
//****************************主函数*********************************************************
void main()
{
	HuffmanTree HT;
	HuffmanCode HC;
	CreatList(HT);                        //创建线性表
	read(HT);                             //读文件，统计字符频度（权值）
 //   order(HT);
	HuffmanCreat(HT);                     //创建赫夫曼树
	HuffmanCoding(HT,HC);                 //求赫夫曼编码
	Writefile(HT,HC);                     //将文章编码结果保存到文件code.txt中
	WriteCodeList(HT,HC);                 //生成编码表
 	TransBack(HT,HC);                     //读编码生成原文件
	free(HT);
	for(int i=0;i<N_CHR;i++)
	{
		free(HC[i]);
	}
	printf("功能:根据编码表codelist.txt将原文件original.txt编码为code.txt并还原为正常文件revert.txt\n");
}