hfm.h

霍夫曼压缩解压缩算法

#include"String1.h"
#include"ExtBinTree1.h"
const int charnumber=256;
struct Inchar{
	unsigned char ch;//
	long key;
};
struct Storechar{
	unsigned char ch;//
	int len;
	int code;
};
struct Outchar{
	char ch;
};
void frequency(String& s,Inchar IC[],int& num){
    int y;unsigned char c;
	for(int i=0;i<charnumber;i++){
		IC[i].key=0;IC[i].ch=unsigned char(i);}
	for(i=0;i<s.Length();i++){
		c=s[i];y=int(c);
		IC[y].key++;}i=0;
	for( int t=0;t<charnumber;t++){
		if(IC[t].key!=0){
			IC[i]=IC[t];i++;}
	}
	num=i;
	Inchar temp;
	for(i=0;i<num-1;i++)
	{long max=IC[i].key;
	for(int j=i+1;j<num;j++)
		if(IC[j].key>max)
		{temp=IC[i];IC[i]=IC[j];IC[j]=temp;}
	}
}
void coding(BinaryTree<Inchar> a, Storechar SC[],Inchar IC[],int n){
	int s=0;
	for(int i=0;i<n;i++){
		SC[i].ch=IC[i].ch;SC[i].code=SC[i].code&s;SC[i].len=SC[i].len&s;}
	BinTreeNode<Inchar> *t,*p;
	for( i=0;i<n;i++){
		int f=1;
		t=a.Find(IC[i]);
		while(a.Parent(t)){
			p=a.Parent(t);
			if(p->GetLeft()==t){
				SC[i].len++;f=f<<1;
			}
			else if(p->GetRight()==t){
				SC[i].code=SC[i].code|f;SC[i].len++;f=f<<1;
			}
			t=p;
		}
	}
}
void outcode(Storechar& a){
	int s=1;s=s<<(a.len-1);
	for(int i=0;i<a.len;i++){
		if((a.code&s)==0)cout<<0;
		else cout<<1;
		s=s>>1;
	}
}
void outcode(Storechar sc[],int n)
{
	for(int i=0;i<n;i++){
	    cout<<sc[i].ch<<": ";
		outcode(sc[i]);
		cout<<endl;
	}
}
void coded(String& s,Storechar sc[],int n){
	for(int i=0;i<s.Length();i++)
		for(int j=0;j<n;j++)
			if(sc[j].ch==s[i])
				outcode(sc[j]);
}
void decode(String& s,Storechar sc[],int n){
	int i,j,k;int t=0; int len=0;
	for( i=0;i<s.Length();)
	{ 
		t=t|int(s[i]-48);len++;
		for( j=i+1;j<=s.Length();j++)
		{
			for(k=0;k<n;k++)
		if((sc[k].code==t)&&(len==sc[k].len)){
			cout<<sc[k].ch;
			t=0;len=0;i=j;break;}
		t=t<<1;len++;t=t|int(s[j]-48);
		}
	}
}
void stringcode(String& out,String& in,Storechar SC[],int n,int& last){
	int bytelen=0;int i,j,k,t1,t2,left,s=1,x;
	int c=0; unsigned char ch;//
	Storechar sc;
	for(i=0;i<in.Length();i++){
		for(j=0;j<n;j++)
		if(SC[j].ch==in[i]){sc=SC[j];break;}
		bytelen+=sc.len;
		if(bytelen<8)
		{c=c<<sc.len;c=c|sc.code;}
		else
		{t1=t2=sc.code;bytelen-=sc.len;
		left=8-bytelen;c=c<<left;
		x=sc.len-left;bytelen=x;t1=t1>>x;
		if(left)c=c|t1;ch=unsigned char(c);//
		out+=ch;
		c=0;
		for(k=0;k<x;k++)
		{if(!((s&t2)==0))c=c|s;s=s<<1;}
		}
		s=1;
	}	
	if(bytelen){
		last=bytelen;
		left=8-bytelen;
		c=c<<left;
		ch=unsigned char(c);out+=ch;
	}else last=8;
}
void stringdecode(String& decode, String& code,Storechar sc[],int n,int last){
	int i,j,k;int c,t=0,s=0x80; unsigned char ch;int len=0;//
	long num=code.Length();
	for( i=0;i<(num-1);i++){
		ch=code[i];c=int(ch);
		for(j=0;j<8;j++){
			len++;
			if(!((c&s)==0))t=t|1;
			for(k=0;k<n;k++)
		if((sc[k].code==t)&&(len==sc[k].len)){//
			decode+=sc[k].ch;
			t=0;len=0;break;}//
		t=t<<1;s=s>>1;}s=0x80;
	}	
	ch=code[int(num-1)];c=int(ch);
		for(j=0;j<last;j++){
			len++;
			if(!((c&s)==0))t=t|1;
			for(k=0;k<n;k++)
		if((sc[k].code==t)&&(len==sc[k].len)){
			decode+=sc[k].ch;
			t=0;len=0;break;}
		t=t<<1;s=s>>1;}
}