huff.cpp

用huffamn算法实现了文本文件的压缩和解压缩

#include "stdafx.h"
#include <iostream.h>
#include"string.h"
#include<fstream.h>
int code[1000];
int num=0;
int codes[10000];
int nums=0;
class TreeNode
{

public:
	TreeNode(TreeNode *p,TreeNode *q,char c,int k,int j)
	{
		leftchild=p;
		rightchild=q;
		ch=c;
		value=k;
		keys=j;
	   
	}
	
    TreeNode():leftchild(NULL),rightchild(NULL),ch('$'),value(0),keys(1){}
	TreeNode *leftchild,*rightchild;
	char ch;        
	int value;
	int keys;       
	
};
//创建Huffman树
TreeNode *Huffman( TreeNode *a[100],int m)
{   
	TreeNode *q;
	int n=m;
	int d=2;
	while(d>1)
	{
    d=0;
	int a1,a2;
    TreeNode *first=new TreeNode(NULL,NULL,'$',100000,1);
	TreeNode *second=new TreeNode(NULL,NULL,'$',100000,1);
	
	for(int i=0;i<n;i++)
	{
		if(first->value>a[i]->value&&a[i]->keys==1)
		{
			first=a[i];	
			a1=i;
		}

	}
	
    a[a1]->keys=0;
    
	for(int j=0;j<n;j++)
	{
	    
		if(second->value>a[j]->value&&a[j]!=first&&a[j]->keys==1)
		
		{	
			second=a[j];	
			a2=j;

		}
	}
    a[a2]->keys=0;
	
	TreeNode *newnode=new TreeNode(first,second,'$',first->value+second->value,1);
	
	    a[a1]=newnode;	
	  
		q=newnode;
	
		for(int g=0;g<m;g++)
		{
			if(a[g]->keys==1)    
			d++;
		}

	
	}
	return q;    
}
  
//为Huffman树进行编码
void Find( TreeNode *a,char c)
   {   
	     
	   if(a->leftchild!=NULL)
	   {		  
		   code[num++]=0;		   
		   Find(a->leftchild,c);
	   }
	   
	   if(a->rightchild!=NULL)
	   {
	       code[num++]=1;
		   Find(a->rightchild,c);
	   }
		   
		if(a->rightchild==NULL&&a->leftchild==NULL&&a->ch==c)
		
		{   
			for(int k2=0;k2<num;k2++)
			{
				codes[nums]=code[k2];
				nums++;
			}

		}	
		else num--;
} 


	  
void main(int argc, char* argv[])
{
    //统计字符种类和个数
	fstream file;   
	file.open(" t1.txt",ios::in);
	char cc[100000];
    file.getline(cc,sizeof(cc));
	file.close();
    int b1=strlen(cc);
    char c1[10000];
	int c2[10000];
	int c3;
	int c4;
	c3=0;c4=0;
	c1[0]=cc[0];

	while(c4<b1)
	{   
		c2[c3]=0;
		int key=0;
        for(int j=0;j<c3;j++)
		{
			if(c1[j]==cc[c4])
			{
				key++;
				c2[j]++;
			    break;
			}
		}
            
	    if(key==0)
        {
		    c1[c3]=cc[c4];
		    c2[c3]+=1;
            c3++;
		}
        c4++;
	}
	TreeNode *n[1000];
	
	for(int k=0;k<c3;k++)
	{
		n[k]= new TreeNode( NULL,NULL,c1[k],c2[k],1);
	}
	//输出各种字符的个数
	for(int l1=0;l1<c3;l1++)
	{
		cout<<n[l1]->ch<<"  "<<n[l1]->value<<"  ";

	}
    cout<<endl;
    TreeNode *p=Huffman(n,c3);
    for(int k1=0;k1<b1;k1++)
	{
		
	    Find(p,cc[k1]);
		num=0;
	}
   //压缩
	fstream fileout;
	fileout.open("t2.txt",ios::out);
	unsigned int st[10000]={0};
	char real[10000];
	int s=0;
    int m1=7;

	for(int k2=1;k2<=nums;k2++)
	{     
		 unsigned int m2=codes[k2-1]; 
		 
		 for(int k3=0;k3<m1;k3++)
			 m2=m2*2;
			 
	     st[s]+=m2;
		 m1--;
		 
		     if(k2%8==0)
			 {   
			    real[s]=(char)st[s];
		        s++;
			    m1=7;
			 }
			 
		 
		
	}
	for(int k4=0;k4<s;k4++)
	fileout<<real[k4];
	fileout.close();
	cout<<"压缩成功,压缩比为:"<<(float)s/b1;
    cout<<endl;

    //生成解压缩过渡文件
    fstream filein;
	fstream filemid;
    filein.open("t2.txt",ios::in);
	filemid.open("t3.txt",ios::out);
	int f=0;
	int tt=0;
	int qq=0;
	while(qq<s)
	{
       
        char buf;
		filein.get(buf);
		buf=(unsigned int)buf;
		qq++;
	    filein.seekp(sizeof(char)*qq);
	   unsigned int  com=0x0080;
	   for(int u=0;u<8;u++)
	   {   
		   
		   tt=buf&com;
		   if(tt==0)
		    filemid<<0;
		   else
			   
			   filemid<<1;
		   com=com>>1;
		   f++;
	   }
	  }
	filein.close();
    filemid.close();
	//解压缩
	fstream fileuncompress;

	filemid.open("t3.txt",ios::in);
	fileuncompress.open ("t4.txt",ios::out);
	
	int k5=0;
	TreeNode *node_m=p;
	while(k5<f)
	{   
		char chc;
		filemid.get(chc);
		if(chc=='0')
		node_m=node_m->leftchild;
		else
			if(chc=='1')
				node_m=node_m->rightchild;
		if(node_m->leftchild==NULL&&node_m->rightchild==NULL)
		{
			fileuncompress<<(char)node_m->ch;
			node_m=p;
		}
		k5++;
	}
	filemid.close();
	fileuncompress.close();
}