huffman.cpp

huffman编码解码用于压缩

#include "Huffman.h"

void Select(HuffmanTree HT,int n,int &s1,int &s2)
{//选择两个最小的元素
	int i,j,t;
	for(i=1,j=0;i<=n;i++)
		if(HT[i].parent==0)
		{
			if(j==0){ s1=i;j++;}
			else if(j==1)
			{
				s2=i;j++;
				if(HT[s1].weight>HT[s2].weight)
				{t=s1;s1=s2;s2=t;}
			}
			else 
			{
				if(HT[i].weight<HT[s1].weight) {s2=s1;s1=i;}
				else if(HT[i].weight<HT[s2].weight) s2=i;
			}
		}
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,unsigned int *w,int n)
{//Huffman编码,生成Huffman树
	HuffmanTree  p;
	int m,i,c,f,s1,s2,start;
	char* cd;
	if(n<=1) return ;
	m=n*2-1;
	HT=(HuffmanTree )malloc((m+1)*sizeof(HTNode));
	for(p=HT+1,i=1;i<=n;++i,++p,++w)
	{
		p->weight=*w;p->lchild=p->rchild=p->parent=0;
	}
	for(i=n+1;i<=m;++i,++p)
		p->weight=p->lchild=p->rchild=p->parent=0;


	for(i=n+1;i<=m;i++)
	{
		Select(HT,i-1,s1,s2);
		HT[s1].parent=i;HT[s2].parent=i;
		HT[i].lchild=s2;HT[i].rchild=s1;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	//--------从叶子到根逆向求每个字符的HuffmanCode
	HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
	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==(unsigned)c) cd[--start]='0';
			else cd[--start]='1';
			HC[i]=(char *)malloc((n-start)*sizeof(char));
			strcpy(HC[i],&cd[start]);
	}
	free(cd);
}

void HuffmanCompress()
{	
	system("cls");
	cout<<"--------------------HuffmanCompress----------------------"<<endl;
	cout<<"请输入源文件名:"<<endl;
	FILE *infp,*outfp;
	char infname[256],outfname[256];
	cin >>infname;
	while(1)
	{
		if((infp=fopen(infname,"rb"))==NULL)
		{
			cout<<"源文件不存在!请输入源文件名:"<<endl;
			cin >> infname;continue;
		}
		fgetc(infp);
		if(feof(infp))
		{
			cout<<"源文件为空!请输入源文件名:"<<endl;
			cin>>infname;continue;
		}
		break;
	}//源文件多情况处理
	
	cout<<"请输入目标文件名:"<<endl;
	cin>>outfname;
	while((outfp=fopen(outfname,"wb"))==NULL )
	{
		cout<<"目标文件不存在!请输入目标文件名:"<<endl;
		cin >> outfname;
	}
	
	FILE* infofp;
	infofp=fopen("info.txt","w");//定义输出信息的文件指针
	
	cout<<">>>>>>>>处理中,请稍等………………"<<endl;

	ProgressBar();//进展条

	char ch;
	unsigned int w[N];
	unsigned int i,fsize=0,outsize=0;
	HuffmanTree HT;HuffmanCode HC;
	for(i=0;i<N;i++)
		w[i]=0;

	rewind(infp);
	ch=fgetc(infp);
	while(!feof(infp))
	{
		w[(unsigned char)ch]++;//ASCII码0-255字符相应出现的概率
		fsize++;
		ch=fgetc(infp);
	}//统计256个字符出现的概率

	HuffmanCoding(HT,HC,w,N);//编码

	fprintf(infofp,"ASCII值  出现次数  编码\n");
	rewind(outfp);//定位目标文件指针	
	for(i=0;i<N;i++)
	{
		fwrite(&w[i],sizeof(unsigned int),1,outfp);//写入权数组
		fprintf(infofp,"%-7d: %-8d  %s\n",i,w[i],HC[i+1]);//格式化输出到info.txt中
	}

	
	rewind(infp);
	ch=fgetc(infp);
	while(!feof(infp))
	{	outsize+=strlen(HC[(unsigned char)ch+1]);//文件大小统计
		fputs(HC[(unsigned char)ch+1],outfp);//输入编码
		ch=fgetc(infp);
	}//写入编码

	fclose(infp);fclose(outfp);fclose(infofp);

	cout<<"相关编码信息及字符出现概率已存储到info.txt中.可以打开查看!"<<endl;
	
	
	//显示处理结果:
	cout<<"压缩成功!"<<endl<<endl;
	cout<<"处理结果统计:"<<endl;
	cout<<"源文件大小为:"<<fsize<<endl;
	cout<<"编码文件大小:"<<outsize<<endl;
	cout<<"压缩比为:"<<outsize/(fsize*8.0)<<endl;
	ReturnMenu();

}

void HuffmanDeCompress()
{
	system("cls");
	cout<<"--------------------HuffmanDeCompress----------------------"<<endl;
	cout<<"请输入源文件名:"<<endl;
	FILE *infp,*outfp;
	char infname[256],outfname[256];
	cin >>infname;
	while(1)
	{
		if((infp=fopen(infname,"rb"))==NULL)
		{
			cout<<"源文件不存在!请输入源文件名:"<<endl;
			cin >> infname;continue;
		}
		fgetc(infp);
		if(feof(infp))
		{
			cout<<"源文件为空!请输入源文件名:"<<endl;
			cin>>infname;continue;
		}
		break;
	}//源文件多情况处理
	
	cout<<"请输入目标文件名:"<<endl;
	cin>>outfname;
	while((outfp=fopen(outfname,"wb"))==NULL)
	{
		cout<<"目标文件不存在!请输入目标文件名:"<<endl;
		cin >> outfname;
	}

	cout<<">>>>>>>>处理中,请稍等………"<<endl;

	ProgressBar();

	char ch;
	unsigned int w[N];
	unsigned int i,outfsize=0,infsize=0,m;
	HuffmanTree HT;HuffmanCode HC;
	
	rewind(infp);//重新定位源文件指针
	for(i=0;i<N;i++)
		fread(&w[i],sizeof(unsigned int),1,infp);//读出权值数组
	HuffmanCoding(HT,HC,w,N);
	ch=fgetc(infp);
	while(!feof(infp))
	{
		m=2*N-1;		
		while(HT[m].lchild!=0)
		{
			infsize++;//输入文件大小统计
			if(ch=='0')m=HT[m].lchild;
			if(ch=='1')m=HT[m].rchild;
			ch=fgetc(infp);
		}
		fputc((char)(m-1),outfp);
		outfsize++;
	}
	fclose(infp);fclose(outfp);
	cout<<endl<<"处理结果统计:"<<endl;
	cout<<"解压成功!"<<endl;
	cout<<"解压文件大小为:"<<infsize<<endl;
	cout<<"解压出文件大小为:"<<outfsize<<endl;
	cout<<"解压比为:"<<outfsize*8.0/infsize<<endl;

	ReturnMenu();
}

void mainmenu()
{
	system("cls");
	cout<<"          ********************Compress & Decompress system********"<<endl;
	cout<<"          $                     1=>Compress                      $"<<endl;
	cout<<"          $                     2=>Decompress                    $"<<endl;
	cout<<"          $                     3=>exit                          $"<<endl;
	cout<<"          $******************************************************$"<<endl;
	cout<<"          $  Designed by Wang Sheng on 12/05/09(纪念汶川地震!)   $"<<endl;
	cout<<"          ********************************************************"<<endl;
}

void ProgressBar()
{//进展条
	for(int i=0;i<5;i++)
	{
		printf("█");
		Sleep(500);
		printf("█");
		Sleep(500);
	}
	printf("\n");
}

void ReturnMenu()
{//返回主界面倒计数
	printf("\n程序将在5秒后返回主界面!\n");
	printf("剩余:");
	for(int i=5;i>=0;i--)
	{
		printf("%ds",i);
		Sleep(1000);
		printf("\b\b");
	}
}