huffzip.cpp

大学时期的计算机课程设计——压缩和解压文件

#include<stdio.h>
#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>

double start, end;

struct  HuffmanNode
{
	int weight;
	int parent,lchild,rchild;
};
struct  HuffmanTree
{
	HuffmanNode *nodes;
};
struct  HuffmanCode
{
	char **codes;
};
struct Bitbuffer
{
	int  buffer;
	int  bitcount;
};
//构造哈夫曼树并存入压缩文件中构成编码头
int  CreateHuffmanTree(HuffmanTree & T,int count[],FILE * fp2)
{
	//初始化哈夫曼树,分配结点空间
	T.nodes=new  HuffmanNode[512];
    if(T.nodes==NULL)  return 0;
	//填入叶结点
	for(int i=0;i<256;i++)
	{
		T.nodes[i].parent=-1;
		T.nodes[i].weight=count[i];
		T.nodes[i].lchild=-1;
        T.nodes[i].rchild=-1;
	}
    //开始构造哈夫曼树
	for(i=256;i<512;i++)
	{
		//从nodes[0]-nodes[256]中找出两个parent为-1的权值最小的结点
		int m1=-1,m2=-1;
        for(int j=0;j<i;j++)
		{
			if(T.nodes[j].parent==-1)
			{
				if(m1==-1||T.nodes[j].weight<T.nodes[m2].weight)
				{
					m2=m1;
					m1=j;
				}
				else if(m2==-1||T.nodes[j].weight<T.nodes[m2].weight)
				{
					m2=j;
				}
			}//endif
		}//endfor
		//合并m1和m2到i的结点上
		T.nodes[i].weight=T.nodes[m1].weight+T.nodes[m2].weight;
		T.nodes[i].parent=-1;
		if(m1<m2)
		{
			T.nodes[i].lchild=m1;
			T.nodes[i].rchild=m2;
		}
		else
		{
			T.nodes[i].lchild=m2;
			T.nodes[i].rchild=m1;
		}
		T.nodes[m1].parent=i;
		T.nodes[m2].parent=i;
	}//endfor
	//将哈夫曼树存入压缩文件中
	for(i=0;i<511;i++)
	{
		char ch=T.nodes[i].parent-256;
		fputc(ch,fp2);
	}
	return 1;
}//end CreateHuffmanTree

//撤销哈夫曼树
int DestroyHuffmanTree(HuffmanTree & T)
{
     for(int i=0;i<512;i++)
		 delete []T.nodes;
	 return 1;
}

//初始化哈夫曼编码
int InitHuffmanCode(HuffmanCode & C)
{
	  C.codes=new char  *[256];
	  if(C.codes==NULL) return 0;
	  for(int i=0;i<256;i++)
		  C.codes[i]=NULL;
	  return 1;
}

//撤销哈夫曼编码
int DestroyHuffmanCode(HuffmanCode & C)
{
	for(int i=0;i<256;i++)
		delete []C.codes[i];
	delete []C.codes;
	return 1;
}

//构造哈夫曼编码
int  CreateHuffmanCode(HuffmanCode & C,HuffmanTree  & T)
{
	InitHuffmanCode(C);
	char * buffer = new char[256];
	buffer[255] = '\0';
	T.nodes[510].parent = -1;
	for (int i=0; i<256; i++)
	{
		char *p = buffer+255;
		for (int cld=i,f=T.nodes[i].parent; f!=-1;cld=f,f=T.nodes[f].parent)
		{
			p--;
			if (cld==T.nodes[f].lchild)
				*p = '0';
			else
				*p = '1';
		}
		C.codes[i] = new char[strlen(p)+1];  
		strcpy( C.codes[i], p );
	}

	delete []buffer;
	return 1;
}

//统计字节的频率
int Frequent(FILE * fp,int count[])
{
	int ch;
	while((ch=fgetc(fp))!=EOF)
         count[ch]++;
	return 1;
}

//实现位流缓冲
int  ClearBitbuffer(Bitbuffer  & B)
{
	B.buffer=0;
	B.bitcount=0;
	return 1;							
}
int  AppendBitFromRight(Bitbuffer & B,int bit)
{
	if(B.bitcount>=8)  return 0;
	B.buffer<<=1;
	if(bit)  B.buffer|=1;
	B.bitcount++;
	return 1;
}
int BufferFull(Bitbuffer & B)
{
	return B.bitcount>=8;
}
//位流缓冲函数
int BitInsert(FILE * fp1,HuffmanCode & C,Bitbuffer & B,HuffmanTree & T,FILE * fp2)
{ 
    ClearBitbuffer(B);
	fseek(fp1,0L,0);
	fseek(fp2,512L,0);
	int ch=fgetc(fp1);
	while(ch!=EOF)
	{
        char *p=new char[strlen(C.codes[ch])];
        strcpy(p,C.codes[ch]);
		for(int i=0;i<(int)strlen(p);i++)
		{
			AppendBitFromRight(B,p[i]-'0');
			if(BufferFull(B))
			{
				fputc(B.buffer,fp2);
				ClearBitbuffer(B);
				
			}
		}	
		ch=fgetc(fp1);
	}
	if(B.bitcount>0)
	{
		fputc(B.buffer,fp2);   //将剩余位写入目标文件中　
		fseek(fp2,511L,0);
		fputc(B.bitcount,fp2);   //将最后一个字节的有效位数写入编码头的末字节
	}
	else
	{
		fseek(fp2,511L,0);
		fputc(8,fp2);         //将最后一个字节的有效位数写入编码头的末字节
	}
    DestroyHuffmanCode(C);
	return 1;
}

//压缩文件
int  Huffzip_P(char * fpin,char  * fpout)
{
	FILE * fp1, * fp2;
	if((fp1 = fopen(fpin,"rb"))==NULL)
	{
		cout<<endl<<"\tCan't open the file:"<<fpin<<endl;
		exit(0);
	}
	
    if((fp2 = fopen(fpout,"wb"))==NULL)
	{
		cout<<endl<<"\tCan't open the file:"<<fpout<<endl;
		exit(0);
	}
	int count[256];
	start = (double)clock()/CLK_TCK; //计时开始
	for(int i=0;i<256;i++)
		count[i]=0;
	Frequent(fp1,count);      //统计字节出现的频率
	HuffmanTree T;
	CreateHuffmanTree(T,count,fp2);      
	HuffmanCode C;
	CreateHuffmanCode(C,T);    //哈夫曼编码
	Bitbuffer  B;
	BitInsert(fp1,C,B,T,fp2);
	end = (double)clock()/CLK_TCK; //计时结束
	cout<<"\n压缩该文件所用时间为:  "<<(end-start)<<"秒."<<endl;
	DestroyHuffmanTree(T);
	fclose(fp1);
	fclose(fp2);
	return 1;
}

//解码函数
int  ReadFromFile(FILE * fp1,FILE * fp2)
{
	
	//由需解压文件的编码头建造哈夫曼树
	HuffmanTree T;
    T.nodes=new HuffmanNode[512];
	for(int i=0;i<511;i++)
	{
		int ch=fgetc(fp1);
		T.nodes[i].parent=ch+256;
		T.nodes[i].weight=i;
		T.nodes[i].lchild=-1;
		T.nodes[i].rchild=-1;
	}
	for(i=256;i<511;i++)
	{
		for(int j=0;j<511;j++)
		{
			if(T.nodes[j].parent==i)
			{
				if(T.nodes[i].lchild==-1)
					T.nodes[i].lchild=j;
				else
                    T.nodes[i].rchild=j;
			}	
		}
	}
    //对压缩文件进行位解码
	fseek(fp1,512L,0);
	int ch1,ch2;
	int cld=510;
	ch1=fgetc(fp1);
	while((ch2=fgetc(fp1))!=EOF)
	{
		//处理ch1
		for(i=0;i<8;i++)
		{
			int ch = ch1&128;  //ch1与(1000 0000)相与
			if(ch==0)
				cld=T.nodes[cld].lchild;
			else 
				cld=T.nodes[cld].rchild;
			if(T.nodes[cld].lchild==-1||T.nodes[cld].rchild==-1)
			{
				char in=T.nodes[cld].weight;
				fputc(in,fp2);
				cld=510;
			}
			ch1<<=1;
		}
		ch1=ch2;
	}
	//处理最后一个字节
	fseek(fp1,511L,0);
	int bitcount=fgetc(fp1);
	ch1<<=(8-bitcount);
	for(i=0;i<bitcount;i++)
	{
		int ch = ch1 & 128;  //ch1与(1000 0000)相与
		if(ch==0)
			cld=T.nodes[cld].lchild;
		else
			cld=T.nodes[cld].rchild;
		if(T.nodes[cld].lchild==-1||T.nodes[cld].rchild==-1)
		{
			char in=T.nodes[cld].weight;
			fputc(in,fp2);
			cld=510;
		}
		ch1<<=1;
	}
//	DestroyHuffmanTree(T);
	return 1;
}

//解压文件
int Huffzip_E(char * fpin,char * fpout)
{
	FILE * fp1,* fp2;
	if((fp1 = fopen(fpin,"rb"))==NULL)
	{
		cout<<endl<<"\tCan't open the file:"<<fpin<<endl;
		exit(0);
	}
	
    if((fp2 = fopen(fpout,"wb"))==NULL)
	{
		cout<<endl<<"\tCan't open the file:"<<fpout<<endl;
		exit(0);
	}
	start = (double)clock()/CLK_TCK; //计时开始
    ReadFromFile(fp1,fp2);
	end = (double)clock()/CLK_TCK; //计时结束
	cout<<"\n解压该文件所用时间为:  "<<(end-start)<<"秒."<<endl;
	fclose(fp1);
	fclose(fp2);
	return 1;
}
main(int argc,char * argv[])
{
	if(argc!=4)
	{
		cout<<endl<<"\t输入格式有误!"<<endl;
		exit(0);
	}	
	if(!strcmp(argv[1],"-p"))
		Huffzip_P(argv[2],argv[3]);   //压缩文件
	if(!strcmp(argv[1],"-e"))
		Huffzip_E(argv[2],argv[3]);   //解压文件	    
	return 1;
}