main.cpp

这是huffman无损压缩简单压缩代码,能把txt文件成后缀为lf文件同时支持解压lf文件成txt文件!对自己理解哈夫曼树的理解很有用!(查资料做出来了的)

#include "Huffman.h"

int Compress(const char* fileName)
{
	/*打开两个流用来读写压缩信息(二进制文件流)
	压缩后的文件主名和原文件相同并且以xyz为后缀*/
	FILE *inFile,*outFile;
	if(!(inFile=fopen(fileName,"rb")))
	{
		ERROR err = FILE_OPEN_ERROR;
		throw err;
	}
	
	/*剔除后缀文件名字,得到文件主名字*/ 
	char *file =new char[30];
	long i=strlen(fileName);
	while(*(fileName+i--)!='.');
	memcpy(file,fileName,(++(++i)));
	*(file+i)=0;

	/*剔除成功后新建一个二进制文件后缀名是xyz的压缩后的文件*/
	if(!(outFile=fopen(strcat(file,"lf"),"wb")))
	{
		ERROR err = FILE_OPEN_ERROR;
		throw err;
	}

	/*计算字符出现的频率由weight记录,并且记下字数（文件的长度）*/
	long infileLength=0,j=0;
	unsigned char _c;
    while(!feof(inFile)) 
	{
		fread(&_c,1,1,inFile); 
		node[_c]._weight++;    //字符重复出现频率+1
		infileLength++;            //字符出现原文件长度+1
	}
	infileLength--; 

	/*如果文件为空的话就退出本压缩程序*/
	if(!infileLength)
	{
		cout<<endl;
		cout<<"    此文件为空文件,不能压缩!";
		fclose(outFile);
		fclose(inFile);
		int error =remove(file);
		return 0;
	}

	char*	out=new char[infileLength+1];
	/*以上完成了对原文件的遍历记录了ascii中字符的频率在原文件中*/

	/*对所以的节点初始化*/
	for(i=0;i<512;i++)
	{
		if(node[i]._weight!=0)
			node[i]._ch=(char)i;
		else
			node[i]._ch=0;
		node[i]._parent=node[i]._left=node[i]._right=-1;
	}
		
	/*对所以的节点进行排序，按权重由大到小进行排序*/
	for(i=0;i<256;++i)
	{
		for(j=i+1;j<=256;++j)
		{
			if(node[i]._weight<node[j]._weight)
			{
				tmp=node[i];
				node[i]=node[j];
				node[j]=tmp;
			}
		}
	}

	/*求出此哈夫曼树外部叶子节点数目和_extern，内部节点数目为_extern-1
	哈夫曼树节点为huffman(2*_extern-1)*/
	for(i=0;i<256;++i) 
		if(node[i]._weight==0) break;
	long _extern=i;
	long _huffman=2*_extern-1;

	/*对哈夫曼树的构建,原理每次选择两个权重最小的节点合并为一个节点把最小两个节点的
	父亲（parent）指向合并后的父节点节点数组下标(既是以顺序表的形式来确定树的关系)
	根据最小权重的最大数值来比较,i就是父节点的下标开始依次后推*/
	unsigned int index=0;
	long min = 999999999;
	for(i=_extern;i<_huffman;++i)
	{
		min = 999999999;
		for(j=0;j<(long)i;++j)
		{
			if(node[j]._parent!=-1)	continue;  
			//parent!=-1说明该结点已存在哈夫曼树中*/
	
			if(min>node[j]._weight) 
			{/*此时找到一个权重最小的节点*/
				index=j; 
				min=node[j]._weight; 
                continue; 
			} 
		}
		node[i]._weight+=node[index]._weight;
		node[index]._parent=i;
		node[i]._left=index;
		/*以上node[i]就是作为node[index]的父节点,并且把自身的权重也给node[i],
		父节点的左孩子就是node[index]*/

		min = 999999999;
		for(j=0;j<(long)i;++j)
		{
			if(node[j]._parent!=-1)	continue; 
			if(min>node[j]._weight) 
			{
				index=j; 
				min=node[j]._weight; 
                continue; 
			} 
		}
		node[i]._weight+=node[index]._weight;
		node[index]._parent=i;
		node[i]._right=index;
		/*以上node[i]就是作为node[index]的父节点,并且把自身的权重也给node[i],
		父节点的由孩子就是node[index]*/
	}

	/*置哈夫曼前缀编码'0','1'*/
	unsigned int _i=0;
	for(i=0;(long)i<_extern;++i)
	{
		_i =i;
		node[i]._bits[0]=0;   //根结点编码0(开始编码)
		while(node[_i]._parent!=-1)		//_parent!=-1说明不为根节点要继续向下找
		{
			j=_i;						//i和j和_c是同一个节点的下标
			_i=node[_i]._parent;		//得到i的父节点的下标
			if(node[_i]._left ==j)
			{
				/*此时i的父节点的左孩子就是i本身(左孩子我们置0)*/
				j=(unsigned int)strlen(node[i]._bits); 
				memmove(node[i]._bits+1,node[i]._bits,j+1);
				node[i]._bits[0]='0'; 
			}
			else
			{
				/*此时i的父节点的右孩子就是i本身(右孩子我们置1)*/
				j=(unsigned int)strlen(node[i]._bits); 
				memmove(node[i]._bits+1,node[i]._bits,j+1);
				node[i]._bits[0]='1'; 
			}
		}
	}

	/*定位到文件流的开始位置*/
	fseek(inFile,0,SEEK_SET);
	fwrite(&infileLength,sizeof(int),1,outFile);

	/*对流进行写入根据节点中的_bits中的字符来对流进行操作*/
	char buf[512];		
	long num=0;
	_i=0;
	buf[0]=0;
	/*_i来控制程序读出原文件长度多少,num用来控制缓冲字符数组的下标*/

	while(!feof(inFile))
	{
		_c=fgetc(inFile);
		_i++;
		if((int)_c<0)	break;

		/*寻找字符的哈夫曼树中对应的节点*/
		for(i=0;(long)i<_extern;++i) 
			if(_c==node[i]._ch)	break; 

		/*连接各次的哈拂曼编码*/
		strcat(buf,node[i]._bits);	
		j=(unsigned int)strlen(buf);
		while(j>=8)
		{
			/*说明有８个以上的字符可以抽象的构成一个字节来存储,_c此时的作用是用来做位运算的一个字节*/
			_c=0;
			for(i=0;i<8;i++) 
			{
				/*比如buf中是"００１０１１０"的话把_c的８个位来移动0向左移1最后一位就抽象的
				添加了一个0,如果是1的话首先移在最后位与1作|运算既相对于前面在最一位添加了1
				就这样一位一位的添加就把每次buf前８位都用_c运算后表示出来再存储*/
				if(buf[i]=='1') 
					_c=(_c<<1)|1; 
				else 
					_c=_c<<1; 
			}

			/*首先把运算后的字符用缓冲数组来存储结束时再一次写入文件提高效率*/
			out[num++]=_c;
			strcpy_s(buf,buf+8);
			j=(unsigned int)strlen(buf);
		}
		if(_i==infileLength)	break;
	}
	
	/*最后一次有可能不满足8个就退出上面的循环了在这里来处理*/
	if(j)
	{
		/*因为我们知道j一定小于7,首先加7个0保证此时的能够8个字符*/
		strcat(buf,"0000000");
		for(i=0;i<8;i++) 
		{
			if(buf[i]=='1')
				_c=(_c<<1)|1; 
			else 
				_c=_c<<1; 
		}
		out[num++]=_c;
	}

	fseek(outFile,8,SEEK_SET);
	fwrite(out,1,num,outFile);
	num+=8;
	/*以上把压缩后的重要数据都放进了缓冲区,下面就是再向压缩后的*/

	fseek(outFile,4,SEEK_SET);
	fwrite(&num,sizeof(long),1,outFile);
	fseek(outFile,num,SEEK_SET); 
	fwrite(&_extern,sizeof(long),1,outFile);
	memset(out,0,infileLength);

	/*文件里再添加哈夫曼树和压缩结构,为解压文件存储解压数据
	(既是把哈夫曼编码先放入对应的字符在放入对应字符的位表示)*/
	char *buffer =new char[1000];
	unsigned char c;
	int f=0,n=0;
	for(i=0;(long)i<_extern;++i)
	{
		fwrite(&(node[i]._ch),1,1,outFile); 
		c =strlen(node[i]._bits);
		fwrite(&c,1,1,outFile); 
		j =(int)strlen(node[i]._bits);
		if(j%8!=0)   //若存储的位数不是8的倍数，则补0   
		{
			for(f=j%8;f<8;f++) 
				strcat(node[i]._bits,"0"); 
		}
		while(node[i]._bits[0]!=0) 
		{
			c =0;
			for(j=0;j<8;j++)   //字符的有效存储不超过8位，则对有效位数左移实现两字符编码的连接
			{
				if(node[i]._bits[j]=='1') 
					c=(c<<1)|1;   //|1不改变原位置上的“0”“1”值
				else 
					c=c<<1; 
			}
			strcpy_s(node[i]._bits,node[i]._bits+8);
			fwrite(&c,1,1,outFile);
		} 
	}

	/*安全的关闭个流文件*/
	fclose(outFile);
	fclose(inFile);

	cout<<"    压缩成功!!保存在本目录文件名字:  "<<file;
	return 1;
}

int uncompress() 
{
	/*获得压缩要用的数据数据*/ 
	char* name=new char[10];
	cout<<"    请输入要解压的文件(不需要后缀名):  ";
	cin>>name;
	
	/*根据上面的name打开流进入文件，既是要解压的文件流*/
	FILE *inFile,*outFile;
	if(!(inFile=fopen(strcat(name,".lf"),"rb")))
	{
		ERROR err = FILE_OPEN_ERROR;
		throw err;
	}

	/*剔除后缀文件名字,得到文件主名字,*/ 
	char *file =new char[30];
	long i=(unsigned int)strlen(name);
	while(*(name+i--)!='.');
	memcpy(file,name,(++(++i)));
	*(file+i)=0;

	/*由剔除后的名字来新建一个文件用于放置解压后的数据自动加上.txt*/
	if(!(outFile=fopen(strcat(file,"txt"),"wb")))
	{
		ERROR err = FILE_OPEN_ERROR;
		throw err;
	}

	/*首先把哈夫曼树从压缩文件读出来,准备解压数据,还有其他关联数据读出文件*/
	int infileLength(0),p(0),m(0),j(0),f(0);
	long haffmanPos(0),appearCh(0);
	unsigned char _c;
	fread(&infileLength,sizeof(int),1,inFile);
	fseek(inFile,4,SEEK_SET);
	fread(&haffmanPos,sizeof(long),1,inFile);
	fseek(inFile,haffmanPos,SEEK_SET);
	fread(&appearCh,sizeof(long),1,inFile);
	/*数据头已经读出*/

	char buf[255],bx[255];
	for(i=0;i<appearCh;++i)
	{
		fread(&node[i]._ch,1,1,inFile);
		fread(&_c,1,1,inFile);
		p =(int)_c;

		node[i]._weight =p;
		node[i]._bits[0]=0;

		if(p%8>0)
			m=p/8+1;
		else
			m=p/8;

		for(j=0;j<m;j++) 
		{
			fread(&_c,1,1,inFile); 
            f=_c; 
            _itoa_s(f,buf,2);   //将f转换为二进制表示的字符串
            f=(int)strlen(buf); 
            for(int l=8;l>f;l--) 
			{
				strcat(node[i]._bits,"0"); 
			}
			strcat(node[i]._bits,buf); 
		} 
		node[i]._bits[p]=0;
	}

	for(i=0;i<appearCh;i++)   //根据哈夫曼编码的长短，对结点进行排序
	{
		for(j=i+1;j<appearCh;j++) 
		{
			if(strlen(node[i]._bits)>strlen(node[j]._bits)) 
			{
				tmp=node[i]; 
                node[i]=node[j]; 
                node[j]=tmp; 
			} 
		} 
	} 

	p=(int)strlen(node[appearCh-1]._bits);
	fseek(inFile,8,SEEK_SET); 
	m =0;
	bx[0] =0;

	while(1)    
	{
		while((int)strlen(bx)<p) 
		{
			fread(&_c,1,1,inFile); 
            f=_c; 
            _itoa_s(f,buf,2); 
            f=(int)strlen(buf); 
            for(int l=8;l>f;l--) 
				strcat(bx,"0"); 
			strcat(bx,buf); 
		}
		for(i=0;i<appearCh;i++) 
		{
			if(memcmp(node[i]._bits,bx,node[i]._weight)==0) break; 
		}
		strcpy_s(bx,bx+node[i]._weight); 
 
		_c=node[i]._ch; 
        fwrite(&_c,1,1,outFile); 
        m++; 
        if(m==infileLength) break;  
	} 

	fclose(outFile);
	fclose(inFile);

	cout<<endl;
	cout<<"    解压后的文件保存在本目录下名字是  "<<file;
	return 1;
}
void main()
{
	cout<<endl;
	cout<<endl;
	cout<<"    *************************************************************************"<<endl;
	cout<<"    *";
	cout<<"                              my haffman                              *"<<endl;
	cout<<"    *";
	cout<<"    实现简单数据压缩目前只支持txt源文件,压缩后的文件后缀名是.xyz      *"<<endl;
	cout<<"    *";
	cout<<"    1.压缩                                                            *"<<endl;
	cout<<"    *";
	cout<<"    2.解压                                                            *"<<endl;
	cout<<"    *************************************************************************"<<endl;

	/*压缩的选择项目*/
	unsigned int select(0);
	cout<<"    你的选择:  ";
	cin>>select;
	if(select ==1)
	{
		char *name =new char[10];
		cout<<"    输入你要压缩的文件名(包括后缀):  ";
		cin>>name;
		try
		{
			Compress(name);
		}
		catch(ERROR e)
		{
			cout<<endl;
			if(e==FILE_OPEN_ERROR)
				cout<<"    文件打开失败(请确保文件存在)!";
		}
	}
	else if(select ==2)
	{
		try
		{
			uncompress();
		}
		catch(ERROR e)
		{
			cout<<endl;
			if(e==FILE_OPEN_ERROR)
				cout<<"    文件打开失败(请确保文件存在)!";
		}
	}
	cout<<endl;
	system("pause");
}