bianma.cpp

霍夫曼压缩算法

#include "stdafx.h"
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
#include <conio.h> 
#include <iostream>
using namespace std ;
double frequency;
struct head 
{
    unsigned char b;        
    long count;             
    long parent,lch,rch;   
    char bits[256];         
}header[512],tmp; 

/*压缩*/
void compress() 
{
    char filename[255],outputfile[255],buf[512]; 
    unsigned char c; 
    long i,j,m,n,f; 
    long min1,pt1,flength,length1,length2; 
    double div;
	
    FILE *ifp,*ofp; 
    printf("\t请您输入需要压缩的文件："); 
    gets(filename); 
    ifp=fopen(filename,"rb"); 
	
    if(ifp==NULL) 
	{
        printf("\n\t文件打开失败!\n\n"); 
        return; 
	}
    printf("\t请您输入压缩后的文件名："); 
    gets(outputfile); 
    ofp=fopen(outputfile,"wb");
	
    if(ofp==NULL) 
	{
        printf("\n\t压缩文件失败!\n\n"); 
        return; 
	}
	flength=0; 
	printf("原文件为：");
    while(!feof(ifp)) 
	{
        fread(&c,1,1,ifp);
		printf("%c",c);
        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)
			printf("\t字符 %c 的频率为: %f\n",header[i].b ,(double)header[i].count/(double)flength);
	}
    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;   //依据parent域值（结点层数）确定树中结点之间的关系
			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)   //置左分支编码0
				{
					j=strlen(header[i].bits); 
					memmove(header[i].bits+1,header[i].bits,j+1);
					//依次存储连接“0”“1”编码
					header[i].bits[0]='0'; 
				}
				else   //置右分支编码1
				{
					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);   //从文件开始位置向前移动0字节，即定位到文件开始位置
		fwrite(&flength,sizeof(int),1,ofp);
		
		fseek(ofp,8,SEEK_SET); 
		buf[0]=0;   //定义缓冲区,它的二进制表示00000000
		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_CUR); 
		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)   //若存储的位数不是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++)   //字符的有效存储不超过8位，则对有效位数左移实现两字符编码的连接
				{
					if(header[i].bits[j]=='1') c=(c<<1)|1;   //|1不改变原位置上的“0”“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; 
		frequency=div;
		fclose(ifp); 
		fclose(ofp); 
		printf("\n\t压缩成功!\n"); 
		printf("\t压缩率为 %f%%\n\n",div*100);
		return; 
} 

/*解压缩*/
void uncompress() 
{
    char filename[255],outputfile[255],buf[255],bx[255]; 
    unsigned char c; 
    long i,j,m,n,f,p,l; 
    long flength; 
    FILE *ifp,*ofp; 
    printf("\t请您输入需要解压缩的文件："); 
    gets(filename); 
    ifp=fopen(filename,"rb"); 
    if(ifp==NULL) 
	{
        printf("\n\t文件打开失败!\n"); 
        return; 
	}
    printf("\t请您输入解压缩后的文件名："); 
    gets(outputfile); 
    ofp=fopen(outputfile,"wb");
    if(ofp==NULL) 
	{
        printf("\n\t解压缩文件失败!\n"); 
        return; 
	}
    fread(&flength,sizeof(long),1,ifp);   
    fread(&f,sizeof(long),1,ifp); 
    fseek(ifp,f,SEEK_CUR); 
    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=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) 
		{
			int a=strlen(bx);
            fread(&c,1,1,ifp); 
            f=c; 
            itoa(f,buf,2); 
            f=strlen(buf); 
			for(l=8;l>f;l--) //在单字节内对相应位置补0
			{
				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(ofp);//这边要关一次再打开 因为原来是用wr打开的 而现在是要读....
	ofp=fopen(outputfile,"rb");
	while(!feof(ofp))
	{
		c = fgetc(ofp);
		printf("%c",c);
	}
    fclose(ifp); 
    fclose(ofp); 
    printf("\n解压缩文件成功!\n");
	
    return; 
}

void ShowFile()//显示压缩前后的文件内容
{
	FILE *fp,*fp2;
	char c;
	char filename1[10]={0};
	char filename2[10]={0};
	printf("请输入压缩前的文件名:\n");
	scanf("%s",filename1);
	
	fp=fopen(filename1,"rb");
	if (!fp)
	{
		printf("找不到该文件!\n");
		return;
	}
	while(!feof(fp))
	{
		c = fgetc(fp);
		printf("%c",c);
	}
	printf("\n以上是压缩前文件的内容.\n");
	getch();
	getchar();
	printf("请输入压缩后的文件名:\n");
	scanf("%s",filename2);
	
	fp2=fopen(filename2,"rb");
	if (!fp2)
	{
		printf("找不到该文件!\n");
		return;
	}
	while(!feof(fp2))
	{
		c = fgetc(fp2);
		printf("%c",c);
	}
	printf("\n以上是压缩后文件的内容.\n");
	printf("压缩率为 %f%%\n\n",frequency*100);
	getch();

}




/*主函数*/
int main() 
{
	int c; 
	while(1)   //菜单工具栏
	{	
		printf("\n");
		printf("\t1.压缩  \n");   
		printf("\t2.解压缩  \n"); 
		printf("\t3.对比显示  \n");
		printf("\t0.退出  \n");
		printf("\n\t*请选择相应功能(0-3):");
		do   //对用户输入进行容错处理
		{
			c=getch(); 
			printf("%c\n",c); 
			if(c!='0' && c!='1' && c!='2' && c!='3' )
			{ 
				printf("\t输入在0-2之间!\n");
			}
		}while(c!='0' && c!='1' && c!='2' && c!='3' );

		if(c=='1')	
			compress();          
		else if(c=='2') 
			uncompress();
		else if(c=='3')
			ShowFile();
		else 
			exit(0);
		
		system("pause");   
		system("cls");     
	}
	return 0;
}