huffman.cpp

基于microsoft visual c++的哈弗曼编码

#include <stdio.h>
#include <iostream.h>
#include <string.h>
class HTNode
{public :
	long weight;
	long parent,lchild,rchild;
	long key;
	HTNode ()
	{   weight =0;
		key =0;
		parent = lchild = rchild = NULL;
	}
};
class Huffman
{private :
	long	n;
	HTNode	node[515];
	char	code[257][257];
	char	s[1000];
	long	LengthCode;
public :
	Huffman ()	{ n=0; LengthCode=0; }
	void	Count();
	void	Create();
	void	Encode();
	void	Select(long, long *, long *);
	void	printCode();
	void	WriteFile();
	void	Decode();
}; 
void Huffman::Count()
{	long		flag[256];
	FILE	*fp;
	for (long i=0; i<256; i++)
		flag[i] = 0;
	i=0;
	cout<<"输入文件:"<<endl;
	cin>>s;
	fp=fopen(s,"rb");
	short x=0;
	while (fread(&x,1,1,fp))
	{	flag[x]++;
		LengthCode++;
	}
	for (i=0; i<256; i++)
	{	if (flag[i]!=0)
		{	n++;
			node[n].weight = flag[i];
			node[n].key = i;
		}
	}
	fclose(fp);
}
void Huffman::Create()
{
	long i;
	long s1=0,s2=0;
	for (i=n+1; i<=2*n-1; i++)
	{	Select(i-1, &s1, &s2);
		node[s1].parent = i; node[s2].parent = i;
		node[i].lchild = s1; node[i].rchild = s2;
		node[i].weight = node[s1].weight+node[s2].weight;
	}
}
void Huffman::Encode()
{	Count();Create();
	long i;
	long f,c,start;
	char cd[9];
	cd[8]='\0';
	for (i=1; i<=n; i++)
	{	start = 8;
		for (c=i, f=node[i].parent; f!=NULL; c=f,f=node[f].parent)
		{	if (node[f].lchild==c) 
				cd[--start]='0';
			else
				cd[--start]='1';
		}strcpy(code[i],&cd[start]);
	}
	WriteFile();
}
void Huffman::WriteFile()//头依次 长度 关键字 长度 编码
{	FILE *fp;
	char s1[1000];
	long len,len1,x;
	strcpy(s1,s);
	strcat(s1,".huf");
	fp=fopen(s1,"wb");
	long tmp=LengthCode,tmp1;
	for (long i=1; i<=4; i++)
	{	tmp1=tmp%256;
		fwrite(&tmp1,1,1,fp);
		tmp=tmp/256;
	}
	tmp=n%256;
	fwrite(&tmp,1,1,fp);
	tmp=n/256;
	fwrite(&tmp,1,1,fp);
	for (i=1; i<=n; i++)
	{	fwrite(&node[i].key,1,1,fp);
		len=strlen(code[i]);
		fwrite(&len,1,1,fp);
		len1=len;
		if (len%8!=0) 
		{len1=((len/8)+1)*8;}
		char tmps[1000];
		strcpy(tmps,code[i]);	
		for (long  j=len; j<len1; j++)
		{strcat(tmps,"0");}
		for (j=0; j<len1/8; j++)
		{	x=1;
			tmp=0;
			for (long k=7; k>=0; k--)
			{tmp+=(tmps[j*8+k]-'0')*x; x=2*x;}
			fwrite(&tmp,1,1,fp);
		}
	}
	FILE *fp1;
	fp1=fopen(s,"rb");
	short y=0;
	char tmps1[520]="";
	len=0;
	while (fread(&y,1,1,fp1))
	{for (i=1; i<=n; i++)
		{if (node[i].key==y)
			{strcat(tmps1,code[i]);
				break;
			}
		}
		len=strlen(tmps1);
		while (len>=8)
		{	x=1;
			tmp=0;
			for (i=7;i>=0; i--)
			{	tmp+=(tmps1[i]-'0')*x;
				x=2*x;
			}
			fwrite(&tmp,1,1,fp);
			strcpy(tmps1,&tmps1[8]);
			len=strlen(tmps1);
		}
	}
	if (len!=0)
	{	for (i=len;i<8; i++)
			strcat(tmps1,"0");
			x=1;
			tmp=0;
			for (i=7;i>=0; i--)
			{	tmp+=(tmps1[i]-'0')*x;
				x=2*x;
			}
			fwrite(&tmp,1,1,fp);
	}
	fclose(fp1);
	fclose(fp);
}
void Huffman::Select(long x, long *s1, long *s2)
{
	long  i,j,t;
	long temp[515]; 
	long temp1[515];
	for (i=1; i<=x; i++)
	{	temp[i] = node[i].weight;
		temp1[i] = i;
	}
	for (i=1; i<x; i++)
		for (j=i+1; j<=x; j++)
		{	if ( temp[i]>temp[j])
			{	t=temp[i];temp[i]=temp[j];temp[j]=t;
				t=temp1[i];temp1[i]=temp1[j];temp1[j]=t;
			}
		}
	for (i=1; i<=x; i++)
	{
		if (node[temp1[i]].parent==NULL)
		{	*s1 = temp1[i];
			node[temp1[i]].parent=1;
			break;
		}
	}
	for (i=1; i<=x; i++)
	{	if (node[temp1[i]].parent==NULL)
		{
			*s2 = temp1[i];
			break;
		}
	}
}
void Huffman::printCode()
{
	long i;
	for (i=1; i<=n; i++)
	{printf("%d : %s\n",node[i].key,code[i]);}
}

void Huffman::Decode()
{
	FILE *fp1,*fp2;
	short x=0;
	long tmp;
	long i,j,k,l,t;
	cout<<"输入文件:"<<endl;
	cin>>s;
	t=strlen(s);
	fp1=fopen(s,"rb");
	s[t-4]='\0';
	fp2=fopen(s,"wb");
	tmp=1;
	LengthCode=0;
	for (i=0; i<4; i++)
	{	fread(&x,1,1,fp1);
		LengthCode += tmp*x;
		tmp=256*tmp;
	}
	fread(&n,1,1,fp1);
	fread(&x,1,1,fp1);
	n=x*256+n;
	for (i=1; i<=n; i++)
	{	short len=0;
		fread(&node[i].key,1,1,fp1);
		fread(&len,1,1,fp1);
		if (len%8!=0)
			k=len/8+1;
		else
			k=len/8;
		strcpy(code[i],"");
		for (j=1; j<=k; j++)
		{	char tmps[9];
			tmps[8]='\0';
			fread(&x,1,1,fp1);
			for (l=7; l>=0; l--)
			{	tmps[l]=(x%2)+'0';
				x=x/2;
			}
			strcat(code[i],tmps);
		}
		code[i][len]='\0';
	}
	long p,h=2*n-1;
	for (i=1; i<=n; i++)
	{
		p=2*n-1;
		long len=strlen(code[i]);
		for (j=0; j<len-1; j++)
		{if (code[i][j]=='0')
			{if (node[p].lchild==NULL)
				{h--;node[p].lchild=h;}
				p=node[p].lchild;
			}
			else
			{if (node[p].rchild==NULL)
				{h--;node[p].rchild=h;}
				p=node[p].rchild;
			}
		}
		if (code[i][j]=='0')
			node[p].lchild = i;
		else
			node[p].rchild = i;
	}
	long length=0;
	p=2*n-1;	//  编码位置
	while (fread(&x,1,1,fp1))
	{char tmps[9];
		tmps[8]='\0';
		for (l=7; l>=0; l--)
		{tmps[l]=(x%2)+'0';x=x/2;}
		t=0;
		while (t<=7)
		{if (p<=n)
			{	fwrite(&node[p].key,1,1,fp2);
				length++;
				if (length==LengthCode) break;
				p=2*n-1;
			}
			else
			{if (tmps[t]=='0')
				{p=node[p].lchild;}
				else
				{p=node[p].rchild ;}
				t++;
			}
		}
	}
	fclose(fp1);
	fclose(fp2);
}
long main ()
{
	Huffman x,y;
	x.Encode();
	y.Decode();
	return 0;
}