compress.h

利用哈夫曼编码进行对已有文件进行压缩 在文件使用时

#ifndef Compress_
#define Compress_

//#include "ldcDlg.h"
#include <stdlib.h> 
#include <conio.h> 
#include "stdafx.h"

struct head 
{
    unsigned char b;        
    long count;             
    long parent,lch,rch;   
    char bits[256];        
} 
header[512],tmp; 

/*压缩*/
void compress(CString CcompressFileName,CString  H_C_FileName) 
{
    char filename[255],outputfile[255],buf[512]; 
    strcpy(filename,CcompressFileName);
    strcpy(outputfile,H_C_FileName);
    unsigned char c; 
    long i,j,m,n,f; 
    long min1,pt1,flength,length1,length2; 
    double div;
    FILE *ifp,*ofp; 

    ifp=fopen(filename,"rb"); 
    if(ifp==NULL) 
    {
        AfxMessageBox(_T("文件打开失败!！"));
        return; 
    }
	ofp=fopen(strcat(outputfile,".Hub"),"wb"); 
    if(ofp==NULL) 
    {
        AfxMessageBox(_T("压缩文件失败!！"));
        return; 
    }
    flength=0; 
    while(!feof(ifp)) 
    {
        fread(&c,1,1,ifp); 
        header[c].count++;    
        flength++;           
    }
    flength--; 
    length1=flength;          
    header[c].count--; 
    for(i=0;i<512;i++) 
    {
        if(header[i].count!=0) 
			header[i].b=(unsigned char)i; 
        else
			header[i].b=0; 
            header[i].parent=-1;
		    header[i].lch=header[i].rch=-1;    
    } 
    for(i=0;i<256;i++)   
    {
        for(j=i+1;j<256;j++)
        {
            if(header[i].count<header[j].count)
            {
                tmp=header[i];
                header[i]=header[j]; 
                header[j]=tmp; 
            } 
        } 
    }
    for(i=0;i<256;i++) 
        if(header[i].count==0) 
            break; 
    n=i;       
    m=2*n-1;
    for(i=n;i<m;i++)    //构建哈夫曼树
    {
        min1=999999999;   
        for(j=0;j<i;j++) 
        {
            if(header[j].parent!=-1) 
				continue;    
            if(min1>header[j].count) 
            {
                pt1=j; 
                min1=header[j].count; 
                continue; 
            } 
        }
        header[i].count=header[pt1].count; 
        header[pt1].parent=i;   
        header[i].lch=pt1;  //计算左分支权值大小
        min1=999999999;   
        for(j=0;j<i;j++) 
        {
            if(header[j].parent!=-1) continue; 
            if(min1>header[j].count) 
            {
                pt1=j; 
                min1=header[j].count; 
                continue; 
            } 
        }
        header[i].count+=header[pt1].count; 
        header[i].rch=pt1;   //计算右分支权值大小
        header[pt1].parent=i; 
    }
    for(i=0;i<n;i++)   
    {
        f=i; 
        header[i].bits[0]=0;   
        while(header[f].parent!=-1) 
        {
            j=f; 
            f=header[f].parent; 
            if(header[f].lch==j)   
            {
                j=strlen(header[i].bits); 
                memmove(header[i].bits+1,header[i].bits,j+1);
               
                header[i].bits[0]='0'; 
            }
            else   
            {
                j=strlen(header[i].bits); 
                memmove(header[i].bits+1,header[i].bits,j+1); 
                header[i].bits[0]='1'; 
            } 
        } 
    }
    fseek(ifp,0,SEEK_SET);   
    fwrite(&flength,sizeof(int),1,ofp);
    fseek(ofp,8,SEEK_SET); 
    buf[0]=0;   
    f=0; 
    pt1=8; 
    while(!feof(ifp)) //对哈夫曼编码位操作进行压缩存储
    {
        c=fgetc(ifp); 
        f++; 
        for(i=0;i<n;i++) 
        {
            if(c==header[i].b) break; 
        }
        strcat(buf,header[i].bits); 
        j=strlen(buf);
        c=0; 
        while(j>=8)   
        {
            for(i=0;i<8;i++) 
            {
                if(buf[i]=='1') c=(c<<1)|1; 
                else c=c<<1; 
            }
            fwrite(&c,1,1,ofp); 
            pt1++;   
            strcpy(buf,buf+8);  
            j=strlen(buf); 
        }
        if(f==flength) break; 
    }
    if(j>0)    
    {
        strcat(buf,"00000000"); 
        for(i=0;i<8;i++) 
        {
            if(buf[i]=='1') c=(c<<1)|1; 
            else c=c<<1; 
        }
        fwrite(&c,1,1,ofp); 
        pt1++; 
    }
    fseek(ofp,4,SEEK_SET); 
    fwrite(&pt1,sizeof(long),1,ofp); 
    fseek(ofp,pt1,SEEK_SET); 
    fwrite(&n,sizeof(long),1,ofp); 
    for(i=0;i<n;i++) 
    {
        fwrite(&(header[i].b),1,1,ofp); 
        c=strlen(header[i].bits); 
        fwrite(&c,1,1,ofp); 
        j=strlen(header[i].bits); 
        if(j%8!=0)     
        {
            for(f=j%8;f<8;f++) 
                strcat(header[i].bits,"0"); 
        }
        while(header[i].bits[0]!=0) 
        {
            c=0; 
            for(j=0;j<8;j++)   
            {
                if(header[i].bits[j]=='1') c=(c<<1)|1;   
                else c=c<<1; 
            }
            strcpy(header[i].bits,header[i].bits+8);  
            fwrite(&c,1,1,ofp); 
        } 
    } 
    length2=pt1--;
    div=((double)length1-(double)length2)/(double)length1; 
    fclose(ifp); 
    fclose(ofp); 
    CString css;
    float a=div*100;
    css.Format(_T("压缩文件成功!\n压缩率为 :%f %%"),a);
    AfxMessageBox(css);

   return; 
} 

/*解压缩*/
void uncompress(CString UnC_FileName,CString H_UnC_FileName) 
{
    char filename[255],outputfile[255],buf[255],bx[255]; 
    strcpy(filename,UnC_FileName);
    strcpy(outputfile,H_UnC_FileName);
    unsigned char c; 
    long i,j,m,n,f,p,l; 
    long flength; 
    FILE *ifp,*ofp; 

    ifp=fopen(filename,"rb"); 
    if(ifp==NULL) 
    {
        AfxMessageBox(_T("文件打开失败!"));
        return; 
    }
    ofp=fopen(outputfile,"wb"); 
    if(ofp==NULL) 
    {
        AfxMessageBox(_T("解压缩文失败!！"));
        return; 
    }
    fread(&flength,sizeof(long),1,ifp);   //读取原文件长度，对文件进行定位
    fread(&f,sizeof(long),1,ifp); 
    fseek(ifp,f,SEEK_SET); 
    fread(&n,sizeof(long),1,ifp); 
    for(i=0;i<n;i++) 
    {
        fread(&header[i].b,1,1,ifp); 
        fread(&c,1,1,ifp); 
        p=(long)c;   //读取原文件字符的权值
        header[i].count=p; 
        header[i].bits[0]=0; 
        if(p%8>0) m=p/8+1; 
        else m=p/8; 
        for(j=0;j<m;j++) 
        {
            fread(&c,1,1,ifp); 
            f=c; 
            itoa(f,buf,2);   //将f转换为二进制表示的字符串
            f=strlen(buf); 
            for(l=8;l>f;l--) 
            {
                strcat(header[i].bits,"0"); 
            }
            strcat(header[i].bits,buf); 
        } 
        header[i].bits[p]=0; 
    } 
    for(i=0;i<n;i++)   //根据哈夫曼编码的长短，对结点进行排序
    {
        for(j=i+1;j<n;j++) 
        {
            if(strlen(header[i].bits)>strlen(header[j].bits)) 
            {
                tmp=header[i]; 
                header[i]=header[j]; 
                header[j]=tmp; 
            } 
        } 
    } 
    p=strlen(header[n-1].bits); 
    fseek(ifp,8,SEEK_SET); 
    m=0; 
    bx[0]=0; 
    while(1)    
    {
        while(strlen(bx)<(unsigned int)p) 
        {
            fread(&c,1,1,ifp); 
            f=c; 
            itoa(f,buf,2); 
            f=strlen(buf); 
            for(l=8;l>f;l--)
            {
                strcat(bx,"0"); 
            }
            strcat(bx,buf); 
        }
        for(i=0;i<n;i++) 
        {
            if(memcmp(header[i].bits,bx,header[i].count)==0) break; 
        }
        strcpy(bx,bx+header[i].count);   
        c=header[i].b; 
        fwrite(&c,1,1,ofp); 
        m++;   
        if(m==flength) break;   
    } 
    fclose(ifp); 
    fclose(ofp);
	if(m==flength) 
    AfxMessageBox(_T("解压缩文件成功!")); 
    else 
        AfxMessageBox(_T("解压缩文件与原文件不同!")); 
    return; 
} 

#endif