huf.c

huffman编码

//包含的头文件
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <fcntl.h>
#include <io.h>

struct HTNode
{						//压缩用Huffman树结点
	unsigned long weight;			//字符频度（权值）
    unsigned int parent,lchild,rchild;
};

typedef char ElemType;
typedef struct
{
   ElemType elem;
   unsigned int m_weight;
   unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;  //Huffman树对应结点

typedef char ** HuffmanCode;
typedef int Status;
typedef struct weight
{
	char elem;
	unsigned int m_weight;
}Weight;   //符号及其出现次数

int bits;			  	//记录实际比特数，清空缓冲区
char chl;				//字节
int lbits;
void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int);  //Huffman编码算法
void Select(HuffmanTree,int,int *,int *);                     //选择结点
void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);          //Huffman编码输出
void Write(unsigned int bit);		//向outfp中写入一个比特
void Writek(unsigned int num,unsigned int h);//向outfp中写入k个比特
void WriteToOutfp();				//强行写入outfp
unsigned int Read();		//从infp中读出一个比特
unsigned int Readk(unsigned int k);//从infp中读出k个比特
int  NToBits(unsigned int num);	//0~num之间的整数用二进位表示所需的最少位数

FILE *infp,*outfp;				//输入/出文件

Status main(void)
{
	HuffmanTree HT;
    HuffmanCode HC;
	
    Weight *w;
	
    char c;        //符号
	unsigned int i;        //用于循环
	int x;
	char y;
	unsigned int n;       //符号数
    int wei;    //符号对应的个数
    int total=0;
	int num;
	x=0;
	while(x!=3)
	{
	printf("请选择是从文件中读取还是自己输入要操作的数:\n(1:自己输入,2:从文件中读取,3:退出):");
	scanf("%d",&x);
	//gets(x);
	switch(x)
		{
		case 1:
		{
			float tnum;
			printf("自己输入只能进行压缩!\n");
			printf("请输入Huffman树的符号数:" );
			scanf("%d",&n);
			w=(Weight *)malloc(n*sizeof(Weight));//为w分配连续的内存空间
			printf("请输入符号及其个数：");
			for(i=0;i<n;i++)
			{
				scanf("%1s%d",&c,&wei);
				w[i].elem=c;
				w[i].m_weight=wei;
				total+=w[i].m_weight;
			}
			total=total;//计算输入的字符的总长度
			printf("压缩前,总字节数为:%d\n",total);

			HuffmanCoding(&HT,&HC,w,n);//进行Huffman编码
			OutputHuffmanCode(HT,HC,n);//输出Huffman编码
			num=0;
			for (i=0;i<n;i++)
			{
				num +=strlen(HC[i+1])*w[i].m_weight;//计算编码后的长度
			}
			tnum = num;
			num=ceil(tnum/8);
			printf("压缩后总字节数为:%d\n",num);
			break;
		}
		case 2:  
		{
			//Huffman();
			//char y;
			
			printf("请选择是进行压缩还是解压缩：(1:压缩，2:解压缩)");
			
			scanf("%s",&y);
			//gets(x);
			switch(y)
			{
			case '1':
			{
				unsigned int size,l;
				//stat buf;
				char infName[256],outfName[256];
				int ch;
				unsigned int k=0;  ////频度大于零的字符数  
				unsigned int char_index[256];	//字符对应在树结点表的下标(char_index[0]到char_index[n-1])
				bits=0;								//清空缓冲区
				chl=0;
				printf("请输入源文件名:(大小小于4GB):");  //被压缩文件最多4GB
				scanf("%s",&infName);                
				if((infp=fopen(infName,"rb"))==NULL)
				{
					printf("不能打开文件:%s\n",infName);
					exit(1);
				}
				if(feof(infp)!=0)
				{
					printf("空的源文件:%s\n",infName);
					 exit(1);
				}

				printf("请输入解码后要保存的文件名:");
				scanf("%s",&outfName);                   
				if((outfp=fopen(outfName,"wb"))==NULL)
				{
					printf("不能打开文件:%s\n",outfName);
					 exit(1);
				}

				printf("处理中...\n");
				fseek(infp,0,SEEK_END);
				size=ftell(infp);							//计算打开的文件的大小
				printf("压缩前文件的总字节数为:%d\n",size);
				rewind(infp);								//将文件指针重新指向开头
				w=(Weight *)malloc(256*sizeof(Weight)); //为w分配空间
				ch=fgetc(infp);							//从文件中获取一个字符
				
				w[0].elem=ch;
				w[0].m_weight=0;
				char_index[ch]=1;
				//ch=fgetc(infp);
				while(ch!=EOF)		//保存符合和出现次数
				{	
					unsigned int i;
					for(i=0;i<=k;i++)
					{
						if(ch == w[i].elem)
						{
							w[i].m_weight=w[i].m_weight+1;
							break;
						}
		
					}
					if(i>k)
					{
						k=k+1;
						w[k].elem=ch;
						w[k].m_weight=1;
						char_index[ch] = k+1;
					}
					ch=fgetc(infp);
				}
			
				k=k+1;
				HuffmanCoding(&HT,&HC,w,k);//进行Huffman编码
				
				num=0;
				
				rewind(outfp);			//将文件指针重新指向输出文件的开头
				fwrite(&size,sizeof(unsigned int),1,outfp);  //写入文件的长度
				Writek(k-1,8);								//写入符合的个数
				for(i=0;i<k;i++)
					fwrite(&(w[i].elem),sizeof(char),1,outfp);	//写入各个符合
				l=NToBits(2*k-1);		//k用二进位表示所需的最少位数
				for(i=k+1;i<=2*k-1;i++)		
				{
					Writek(HT[i].lchild,l);
					Writek(HT[i].rchild,l);
				}
				rewind(infp);	//将文件指针重新指向输入文件的开头
				ch=fgetc(infp);		//读取一个字符
				while(feof(infp)==0)		//将编码写入文件
				 {
					unsigned int c;
					c=char_index[ch];
					for(i=0;i<strlen(HC[c]);i++)
					{
					if(HC[c][i]=='0')Write(0);
					else Write(1);
					} 
					ch=fgetc(infp);
				}
				WriteToOutfp();		//最后一个字节没有则强行写入
				fseek(outfp,0,SEEK_END);
				num=ftell(outfp);		//计算压缩后文件的大小
				printf("压缩后文件的总字节数为:%d\n",num);
				fclose(infp);fclose(outfp);
				break;

			}

			case '2':		//选择解压缩
				{
				unsigned int size;
				unsigned int l;
				unsigned int bit,c,i;
				char infName[256],outfName[256];
				char Leaf[256];					//叶结点对应字符(leaf[1]到leaf[n])
				unsigned int k;  ////频度大于零的字符数  
			//	unsigned int char_index[256];	//字符对应在树结点表的下标(char_index[0]到char_index[n-1])
				bits=0;								//清空缓冲区
				chl=0;
				printf("请输入编码文件名::");  
				scanf("%s",&infName);                
				if((infp=fopen(infName,"rb"))==NULL)
				{
					printf("不能打开文件:%s\n",infName);
					exit(1);
				}
				if(feof(infp)!=0)
				{
					printf("空的编码文件:%s\n",infName);
					 exit(1);
				}

				printf("请输入目标文件文件名:");
				scanf("%s",&outfName);                   
				if((outfp=fopen(outfName,"wb"))==NULL)
				{
					printf("不能打开文件:%s\n",outfName);
					 exit(1);
				}
				printf("处理中...\n");
				fseek(infp,0,SEEK_END);
				size=ftell(infp);		//计算文件大小
				printf("解压缩前文件的总字节数为:%d\n",size);
				bits=0;								//清空缓冲区
				chl=0;
	
				rewind(infp);		//将文件指针重新指向输入文件的开头
				fread(&size,sizeof(unsigned int),1,infp);
				k=Readk(8);			//读取字符数目
				k=k+1;
				w=(Weight *)malloc(256*sizeof(Weight));		//分配空间
				for(i=1;i<=k;i++)
				fread(&Leaf[i],sizeof(char),1,infp);	
				l=NToBits(2*k-1);
				HT=(HuffmanTree)malloc((l+1)*sizeof(HTNode));	//分配空间
				for(i=1;i<=k;i++)		//读出叶结点
				{
					HT[i].lchild=HT[i].rchild=0;
				}
				
				for(i=k+1;i<=2*k-1;i++)
				{
					HT[i].lchild=Readk(l);
					HT[i].rchild=Readk(l);
				}

				bit=Read();	//读一个bit
				for(i=0;i<size;i++)
				{   
					c=2*k-1;						//2*k-1为根结点的下标
					while((HT[c].lchild!=0||HT[c].rchild!=0)&&(feof(infp)==0))
					{
						if(bit==0)
							c=HT[c].lchild;
						else 
							c=HT[c].rchild;
						bit=Read();  
					}
					fputc(Leaf[c],outfp);				//将字符写入outfp中
				}
				fseek(outfp,0,SEEK_END);
				size=ftell(outfp);
				printf("解压缩后文件的总字节数为:%d\n",size);
				fclose(infp);fclose(outfp);
				break;
				//结束
				}
			}
		}	
		}
		}
		return 1;
}

void Write(unsigned int bit)				//向outfp中写入一个比特
{
	bits++;
	chl=(chl<<1)+bit;
	if(bits==8)
	{  //缓冲区已满,写入outfp
		fputc(chl,outfp);
		bits=0;
		chl=0;
	}
}


void Writek(unsigned int num,unsigned int h)		//向outfp中写入k个比特
{
	int *s;
	
	unsigned int i,bit;
	bit =0;
	s=(int *)malloc((h+2)*sizeof(int));
	for(i=1;i<=h;i++)
	{
		s[i]=0;
		s[i]=num & 1;
		num=num>>1;
	}

	for(i=h;i>0;)
	{
		bit=s[i];
		Write(bit);
		i--;
	}

}


void WriteToOutfp()			//强行写入outfp
{
	int i;
	int l;
	l=bits;
	if(l>0)
		for(i=0;i<8-l;i++)
			Write(0);
}

int NToBits(unsigned int num)	//0~num之间的整数用二进位表示所需的位数
{
	unsigned int l=0,power=1;
	while(power<=num){
		l++;power=power*2;
	}
	return l;
}

unsigned int Read()				//从infp中读出一个比特
{
	unsigned int bit;
	if(bits==0)
	{
		chl=fgetc(infp);
		bits=8;
	}
	bit=(chl & 128)>>7;    
	chl=chl<<1;
	bits--;
	return bit;
}


unsigned int Readk(unsigned int k)		//从infp中读出k个比特
{
	unsigned int bit;
	unsigned int i;
	int num=0;
	for(i=0;i<k;)
	{
		bit=Read();
		num=(num<<1)+bit;
		i++;
	}
	return num;
}
/*
*/
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n)  //Huffman编码算法
{
	int i,m,s1,s2,start,c,f;
	char *cd;
//	HuffmanTree p;
	if(n<=1)
	return;

	m=2*n-1;
	//在内存为*HT分配长度为m+1个HTNode结构体大小的连续空间
	(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	//初始化HuffmanTree前n个节点
	for(i=1;i<=n;++i)
	{
		(*HT)[i].elem=w[i-1].elem;
		(*HT)[i].m_weight=w[i-1].m_weight;
		(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
	}
	//初始化HuffmanTree前n+1到m节点
	for(;i<=m;++i)
	{
		(*HT)[i].elem='0';
		(*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
	}
	//构造Huffman
	for(i=n+1;i<=m;++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].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight;
	}
	//在内存为*HT分配长度为n个char大小的连续空间
	(*HC)=(HuffmanCode)malloc(n*sizeof(char*));
	cd=(char *)malloc(n*sizeof(char));  //为cd分配n个char占的空间大小
	cd[n-1]='\0';

	//为每个叶子结点进行编码
	for(i=1;i<=n;++i)
	{
		start=n-1;
		//从叶子结点开始向上搜索，如果它是其父结点的左孩子，则其编码为0，否则为1，直到根结点
		for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent)
		{
			if((*HT)[f].lchild ==c) 
				cd[--start]='0';
			else 
				cd[--start]='1';
		}

		(*HC)[i]=(char *)malloc((n-start)*sizeof(char)); //为每个结点的编码分配存储空间
		strcpy((*HC)[i],&cd[start]);//将结点的编码首地址保存到HC中
	}
}
//选择出权值最小并且父亲结点的权值为0的2个结点
void Select(HuffmanTree HT,int n,int *s1,int *s2)
{
	int i;
    (*s1)=(*s2)=0;//初始化s1和s2
    for(i=1;i<=n;i++)
	{
		if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0)
		{
			if(HT[i].m_weight<HT[(*s1)].m_weight)//将权值最小的结点地址保存在s1中
			{
				(*s2)=(*s1);
				(*s1)=i;
			}	
			else 
				(*s2)=i;
		}

		if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)//为s1和s2初始植入结点
		{
			if((*s1)==0) 
				(*s1)=i;
			else if((*s2)==0)
			{
				if(HT[i].m_weight<HT[(*s1)].m_weight)
				{
					(*s2)=(*s1);
					(*s1)=i;
				}
				else (*s2)=i;
			} 
		} 
  }

  if((*s1)>(*s2))
  {
	  i=(*s1);
	  (*s1)=(*s2);
	  (*s2)=i;
  }
  return;
}
//Huffman编码输出
void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)
{
	int i;
	printf("\n序号     符号    权重    huffman编码\n");
	for(i=1;i<=n;i++)
	{
		printf(" %d        %c       %d           %s\n",i,HT[i].elem,HT[i].m_weight,HC[i]);
	}
}