huffman.cpp

数据结构是编程的基础

// huffman.cpp : Defines the entry point for the console application.
//

#define NULL 0
#include "stdafx.h"
//////////////////////////////////定义哈夫曼编码表//////////////////////////////////////////
struct huffmantable
{
	char value;
	char code[20];
};
//////////////////////////////////定义哈夫曼编码表//////////////////////////////////////////

////////////////////////////////////定义哈夫曼树////////////////////////////////////////
struct huffmantree
{
	char   value;
	float  frequence;
	struct huffmantree *father;
	struct huffmantree *lchild;
	struct huffmantree *rchild;	
};
/////////////////////////////////////定义哈夫曼树///////////////////////////////////////

/////////////////////////////定义公共变量和函数///////////////////////////////////////////////
int count=0;
struct huffmantree *huffman=NULL;
void treeprinting(int level,struct huffmantree *huffman,int width,FILE *outfile);
//////////////////////////////定义公共变量和函数//////////////////////////////////////////////

//////////////////////////////初始化哈夫曼树，生成哈夫曼编码表//////////////////////////////////////////////
struct huffmantable ** inittree()
{
	FILE *fp;
	int i=0,min=0,number;
	struct huffmantree **leaf,**codechar;
	struct huffmantable **huffmantable;
	struct huffmantree *treeboot=NULL;
	char temp[5]={0,0,0,0,0};
	printf("请输入字符集的大小：");
	scanf("%d",&count);
	//////////////////////分配空间存放huffman叶子的地址指///////////////////////
	leaf=(struct huffmantree **)malloc(count*sizeof(struct huffmantree *));
	codechar=(struct huffmantree **)malloc(count*sizeof(struct huffmantree *));
	huffmantable=(struct huffmantable **)malloc(count*sizeof(struct huffmantable *));
	printf("请输入字符集中的字符及相应可权值或出现频率：\n");
    //////////////////////接收字符及其权值///////////////////////
	for(i=0;i<count;i++)
	{
		leaf[i]=(struct huffmantree *)malloc(sizeof(struct huffmantree));
		huffmantable[i]=(struct huffmantable *)malloc(sizeof(struct huffmantable));
		scanf("%s",temp);
		leaf[i]->value=*temp;
	    *temp=0;
		//scanf("%s",&leaf[i]->value);
		scanf("%f",&leaf[i]->frequence);
		leaf[i]->lchild=NULL;
		leaf[i]->rchild=NULL;
		leaf[i]->father=NULL;
		huffmantable[i]->value=leaf[i]->value;
		huffmantable[i]->code[0]=0;
		codechar[i]=leaf[i];
	}
	 //////////////////////生成huffman编码树///////////////////////
	number=count;
	while(number>1)
	{
		for(i=0;i<count;i++)
		{
			if(NULL!=leaf[i])
			{
				min=i;
				break;
			}
		}
		for(i=0;i<count;i++)
		{
			if(NULL!=leaf[i]&&leaf[i]->frequence<leaf[min]->frequence)
			{
				min=i;
			}
		}
		treeboot=(struct huffmantree *)malloc(sizeof(struct huffmantree));
		treeboot->father=NULL;
		treeboot->lchild=leaf[min];
		leaf[min]->father=treeboot;
		treeboot->frequence=leaf[min]->frequence;
		leaf[min]=NULL;
		number--;

		for(i=0;i<count;i++)
		{
			if(NULL!=leaf[i])
			{
				min=i;
				break;
			}
		}
		for(i=0;i<count;i++)
		{
			if(NULL!=leaf[i]&&leaf[i]->frequence<leaf[min]->frequence)
			{
				min=i;
			}
		}
		treeboot->rchild=leaf[min];
		leaf[min]->father=treeboot;
		treeboot->frequence=treeboot->frequence+leaf[min]->frequence;
		leaf[min]=treeboot;
	}
///////////////////////////////保存进行huffman编码并保存到hfmtree.txt中//////////////////

	fp=fopen("hfmtree.txt","w");
	fprintf(fp,"%d\n",count);
	for(i=0;i<count;i++)
	{
		while(NULL!=codechar[i]->father)
		{
			if(codechar[i]==codechar[i]->father->lchild)
			{
				for(min=strlen(huffmantable[i]->code)+1;min>0;min--)
				{
					huffmantable[i]->code[min]=huffmantable[i]->code[min-1];
				}
				huffmantable[i]->code[0]='0';
			}
			else
			{
				for(min=strlen(huffmantable[i]->code)+1;min>0;min--)
				{
					huffmantable[i]->code[min]=huffmantable[i]->code[min-1];
				}
				huffmantable[i]->code[0]='1';
			}

			codechar[i]=codechar[i]->father;
		}
		fprintf(fp,"%c %s\n",huffmantable[i]->value,huffmantable[i]->code);
	}

	printf("\n");
	fputc('\n',fp);
	treeprinting(0,treeboot,60/count,fp);

	fclose(fp);
	huffman=treeboot;
	return huffmantable;
}
//////////////////////////////初始化哈夫曼树，生成哈夫曼编码表//////////////////////////////////////////////

////////////////////////////将哈夫曼编码表导入内存////////////////////////////////////////////////
struct huffmantable ** loadtree()
{
	char temp[5]={0,0,0,0,0};
	FILE *codefile;
	int i=0;
	struct huffmantable **treebootbak=NULL;
	codefile=fopen("hfmtree.txt","r");
	fscanf(codefile,"%d",&count);
	treebootbak=(struct huffmantable **)malloc(count*sizeof(struct huffmantable *));
	for(i=0;i<count;i++)
	{
		treebootbak[i]=(struct huffmantable *)malloc(sizeof(struct huffmantable));
		fscanf(codefile,"%s",temp);
		treebootbak[i]->value=*temp;
		*temp=0;
		fscanf(codefile,"%s",&treebootbak[i]->code);
	}
	fclose(codefile);
	return treebootbak;
}
///////////////////////////将哈夫曼编码表导入内存/////////////////////////////////////////////////

///////////////////////////进行哈夫曼编码/////////////////////////////////////////////////
void encoding(struct huffmantable **treeboot)
{
	char tempchar=0;
	FILE *infile,*outfile;
	int i=0;
	infile=fopen("tobetran.txt","r");
	outfile=fopen("codefile.txt","w");
	while(!feof(infile))
	{
		tempchar=fgetc(infile);
		for(i=0;i<count;i++)
		{
			if(tempchar==treeboot[i]->value)
			{
				//fputs(treeboot[i]->code,outfile);
				fprintf(outfile,"%s",treeboot[i]->code);
			}
		}
	}
	fclose(infile);
	fclose(outfile);
}
///////////////////////进行哈夫曼编码////////////////////////////////////////////////////

///////////////////////进行哈夫曼译码/////////////////////////////////////////////////////
void decoding(struct huffmantable **treeboot)
{
	char tempchar=0,*tempstring;
	FILE *infile,*outfile;
	int i=0,length=0;
	tempstring=(char *)malloc(count+1);
	*tempstring=0;
	infile=fopen("codefile.txt","r");
	outfile=fopen("textfile.txt","w");
	while(-1!=*tempstring)
	{
		for(i=strlen(tempstring);i<count && !feof(infile);i++)
		{
			tempstring[i]=fgetc(infile);
		}
		tempstring[i]=0;
		for(i=0;i<count;i++)
		{
			if(strstr(tempstring,treeboot[i]->code)==tempstring)
			{
				fputc(treeboot[i]->value,outfile);
				length=strlen(treeboot[i]->code);
				for(i=length;i<count+1;i++)
				{
					tempstring[i-length]=tempstring[i];
				}
				break;
			}

		}

	}
	fclose(infile);
	fclose(outfile);
}
//////////////////////////进行哈夫曼译码//////////////////////////////////////////////////

///////////////////////////打印哈夫曼代码/////////////////////////////////////////////////
void printing()
{
	int i=1;
	char tempchar;
	FILE *infile,*outfile;
	infile=fopen("codefile.txt","r");
	outfile=fopen("codeprin.txt","w");
	while(1)
	{
		tempchar=fgetc(infile);
		if(-1==tempchar)break;
		printf("%c",tempchar);
		fputc(tempchar,outfile);i++;
		if(0==(i++%50))
		{
			printf("\n");
			fputc('\n',outfile);
		}
	}
	fclose(infile);
	fclose(outfile);
}
///////////////////////////打印哈夫曼代码/////////////////////////////////////////////////

//////////////////////////////打印哈夫曼代树凹入表//////////////////////////////////////////////
void treeprinting(int level,struct huffmantree *huffman,int width,FILE *outfile)
{
	int i=0;
	if(NULL==huffman->lchild)
	{
		printf("叶子 %c ：  ",huffman->value);
		fprintf(outfile,"叶子 %c ：  ",huffman->value);
		for(i=0;i<width*level;i++)
		{
			printf(" ");
			fputc(' ',outfile);
		}
		printf("|");
		fputc('|',outfile);
		while(60>i++)
		{
			printf("_");
			fputc('_',outfile);
		}
		printf("|\n");
		fputc('|',outfile);
		fputc('\n',outfile);
		return;
	}
	else
	{
		if(NULL!=huffman->father)
		{
			printf("分支结点： ");
			fprintf(outfile,"分支结点： ");
		}
		else
		{
			printf("树根结点： ");
			fprintf(outfile,"树根结点： ");
		}
	}
	for(i=0;i<width*level;i++)
	{
		printf(" ");
		fputc(' ',outfile);
	}
	printf("|");
	fputc('|',outfile);
	while(60>i++)
	{
		printf("_");
		fputc('_',outfile);
	}
	printf("|\n");
	fputc('|',outfile);
	fputc('\n',outfile);
//////////////////////////////递归遍历哈夫曼树/////////////////////////////////////////////////
	treeprinting(level+1,huffman->lchild,width,outfile);
	treeprinting(level+1,huffman->rchild,width,outfile);
	return;
}
////////////////////////////////打印哈夫曼代树凹入表///////////////////////////////////////////

/////////////////////////////////将哈夫曼代树凹入表写入文件///////////////////////////////////////////
void printtreetotxt()
{
	FILE *outfile;
	outfile=fopen("treeprin.txt","w");
	printf("\n");
	fputc('\n',outfile);
	treeprinting(0,huffman,60/count,outfile);
	fclose(outfile);
}
///////////////////////////////将哈夫曼代树凹入表写入文件/////////////////////////////////////////////

///////////////////////////////将哈夫曼代树凹入表写入文件/////////////////////////////////////////////
void hfmtreetotreeprin()
{
	FILE *codefile,*outfile;
	int i=0;
	char strtxt;
	codefile=fopen("hfmtree.txt","r");
	fscanf(codefile,"%d",&count);
	for(i=0;i<count;i++)
	{
		fscanf(codefile,"%s");
		fscanf(codefile,"%s");
	}
	outfile=fopen("treeprin.txt","w");
	while(!feof(codefile))
	{
		strtxt=fgetc(codefile);
		printf("%c",strtxt);		
		fputc(strtxt,outfile);	
	}
	fclose(outfile);
	fclose(codefile);
}
//////////////////////////////将哈夫曼代树凹入表写入文件/////////////////////////////////////////////

int main(int argc, char* argv[])
{
	struct huffmantable **tablehead=NULL;
	char select=0;
	FILE *fp;
	fp=fopen("hfmtree.txt","r");
/////////////////////////////////进行判断要求初始化///////////////////////////////////////////////
	if(-1==fgetc(fp))
	{
		tablehead=inittree();
		printf("初始化成功!\n");
		printf("请按任意键继续。。。。。。。。。。。。。\n");
		getch();
		system("cls");
	}
	fclose(fp);

	while(1)
	{
/////////////////////////////////定制菜单///////////////////////////////////////////////////////
		printf("请按键选择相应操作\n");
    	printf(" I:初始化：(从终端字符集大小、字符和相应权值)。\n");
	    printf(" E:编码：(利用哈夫曼树将tobetran.txt的正文编码到codefile.txt中)。\n");
		printf(" D:译码：(利用哈夫曼树将codefile.txt的代码译到textfile.txt)。\n");
		printf(" P:印代码文件：(将codefile.txt中的代码按每行50个显示到终端)。\n");
		printf(" T:印哈夫曼树：(将哈夫曼树以凹入表显示到终端并保存在treeprin.txt中)。\n");
		printf(" Q:退出哈夫曼编码系统!!\n");
		select=toupper(getch());
	switch(select)
	{
	case 'I' : tablehead=inittree();printf("初始化成功!\n");break;
	case 'E' : 
		if(NULL==tablehead)
		{
			tablehead=loadtree();	
		}	
		encoding(tablehead);
		printf("编码成功，代码已存入codefile.txt中!\n");
		break;
	case 'D' :
		if(NULL==tablehead)
		{
			tablehead=loadtree();	
		}	
		decoding(tablehead);
	    printf("译码成功，代码已存入文本textfile.txt中!\n");
		break;
	case 'P' : printing();break;
	case 'T' :
		if(NULL!=huffman)
		{
			printtreetotxt();break;
		}
		else
		{
			hfmtreetotreeprin();break;
		}
	case 'Q' : printf("欢迎使用，再见!\n"); return 0;
	}	
	printf("请按任意键继续。。。。。。。。。。。。。\n");
	getch();
	system("cls");
	}
	return 0;
}