huffman.cpp

霍夫曼编码解码。基本原理是频繁使用的数据用较短的代码代替

  /*Huffman编码与解码器-----可以完成对ASCII码表的所有字符的压缩功能 时间：2008年12月11日21:22:23*/

#include<stdio.h>
#include<malloc.h> 
#include<conio.h> 
#include<stdlib.h> 
#include<string.h>
#define TABLE 128                    //26个字母表，
#define MAX 64                     // MAX最长编码长度

int LENGHTH=0;                      // 全局变量_字符个数
  
typedef struct                      //Huffman树节点数据结构定义
{
	char data;                      // 节点的字符值
	int p;                          //字符出现的频率
	int lchild, rchild;             //节点的左右孩子位置
	int parent;                     //父节点的位置
}HNode;
HNode huffmannode[2*TABLE-1];


typedef struct                      //Huffman编码的数据结构
{
	int bit[MAX];                   //字符的编码
	int start;                      //编码存放的其实位置
}Hcode;
Hcode huffmancode[TABLE];

void initial()                      //初始化Huffman树节点
{
	int i;
	 for (i=0;i<2*TABLE-1;i++)         
      {
			 huffmannode[i].data=0;
		     huffmannode[i].p=0;
			 huffmannode[i].lchild=-1;
			 huffmannode[i].parent=-1;
			 huffmannode[i].rchild=-1;
	 }
}


void hufftreeconstruct()              //创建Huffman树
{
	int i,j,lnode,rnode,n;
	int min1,min2;
   
	n=LENGHTH;
	lnode=rnode=0;
	
	for(i=0;i<n-1;i++)
	{	
		min1=min2=65536;
		for(j=0;j<n+i;j++)
		{
			if(huffmannode[j].parent==-1)
			{
				if(huffmannode[j].p<min1)
				{
					min2=min1;
					rnode=lnode;
			    	min1=huffmannode[j].p;
				    lnode=j;

				}
		    	else if(huffmannode[j].p<min2)
				{
			     	min2=huffmannode[j].p;
			    	rnode=j;
				}
			}
		}
		huffmannode[lnode].parent=n+i; 
		huffmannode[rnode].parent=n+i; 
        huffmannode[n+i].p=huffmannode[lnode].p+huffmannode[rnode].p;
        huffmannode[n+i].lchild=lnode; 
		huffmannode[n+i].rchild=rnode; 

	}

	printf(" \n生成的Huffman 树如下:\n");  
	  printf("位置：      频率：     左孩子：      右孩子：    父节点位置：\n");
	for(i=0;i<2*n-1;i++) 
	{
		printf(" %3d        %3d          %3d           %3d            %3d\n",i,huffmannode[i].p,huffmannode[i].lchild,huffmannode[i].rchild,huffmannode[i].parent);
	}
	printf("\nHufman 树创建完毕\n");
}

FILE *fileopen()
{
	FILE *fp;
	if((fp=fopen("test.txt","r"))==NULL)
	{
		printf("\ntest.txt文件打开失败,文件可能不存在\n");
	    exit(0);
	}
	else
	{
		printf("\ntest.txt文件打开成功\n");
		
	}
	return fp;	

}


void tongjipinlv(FILE *fp)                       //从test.txt文件中读取字符 并统计各字符出现的频率
{
	int a[TABLE]={0};
	int i,j,b=0;
	char ch;
	
	while(feof(fp)==0)
	{	
		ch=fgetc(fp);
		i=ch;
		a[i]++;
	}
	fclose(fp);

	j=0;
	for(i=0;i<TABLE;i++)
	{
		if(a[i]!=0)
		{
			LENGHTH++;
            huffmannode[j].data=i;
            huffmannode[j].p=a[i];
			j++;
		}
	}	
	
      	printf("\n文件中出现的字符:                频率：\n");
	for(i=0;i<LENGHTH;i++)
	{
		printf("%c                                %d \n",huffmannode[i].data,huffmannode[i].p);
	}
	printf("\n");
	
}


void huffman_code()                                //对Huffman树进行编码
{
	Hcode code;
	int i,j,k,m;
	FILE *fp;

	for(i=0;i<LENGHTH;i++)
	{
		code.start=MAX-1;
		m=i;
		k=huffmannode[m].parent;
		while(k!=-1)
		{
			if(huffmannode[k].lchild==m)
				code.bit[code.start]=0;
			else code.bit[code.start]=1;
			code.start--;
			m=k;
			k=huffmannode[m].parent;
		}
	
		for(j=code.start+1;j<MAX;j++)
			huffmancode[i].bit[j]=code.bit[j];
	
		huffmancode[i].start=code.start;
		
	}
	printf("\nHuffman编码如下:\n");
	for(i=0;i<LENGHTH;i++)
	{	printf("%c:        ",huffmannode[i].data);
		for(j=huffmancode[i].start+1;j<MAX;j++)
			printf(" %d",huffmancode[i].bit[j]);
		printf("\n");
	}

	printf("\n编码结束 \n");
	
	if((fp=fopen("code.txt","w+"))!=NULL)
		for(i=0;i<LENGHTH;i++)
		{
			fprintf(fp,"%c       ",huffmannode[i].data);
		    for(j=huffmancode[i].start+1;j<MAX;j++)
			fprintf(fp,"%d",huffmancode[i].bit[j]);		
	        fprintf(fp,"\n");	
		}
	else 
	{
		printf("Can not open or create the file \"code.txt\".\n");
        exit(0);
	}

	fclose(fp);
	printf("\nHuffman编码方案文件----code.txt创建成功!\n");
	
}


void code_ef()                                //计算编码效率 用Huffman编码的总长度除以等长编码的总长度
{
	float m,n,t;
	int i;
	m=0;
	for(i=0;i<LENGHTH;i++)
		m=m+huffmannode[i].p*(MAX-huffmancode[i].start);
	n=huffmannode[2*LENGHTH-2].p*MAX;
    t=m/n*100;
	printf("\nHuffman 编码效率：    %f%%\n",t);

}

void compression()                          //对test.txt文件进行压缩，所以内容转换成Huffman码
{
	int  i,j,m=0;
	char ch;
	FILE *fp1,*fp2;
	
	fp1=fileopen();
	
	if((fp2=fopen("compression.txt","w+"))==NULL)
	{
		printf("\n文件创建不成功\n");
		exit(0);
	}
	else 
		printf("\ncompression.txt文件创建成功。\n");

	ch=fgetc(fp1);
 	while(feof(fp1)==0)
	{

		for(i=0;i<LENGHTH;i++)
			if(ch==huffmannode[i].data)
				break;
		for(j=huffmancode[i].start+1;j<MAX;j++)
			fprintf(fp2,"%d",huffmancode[i].bit[j]);
     	ch=fgetc(fp1);

	}	
     fclose(fp1);
	 fclose(fp2);
}


void huffman_decode()                     //Huffman  解码函数
{
	FILE *fp1,*fp2;
	char ch;
    int m;
    if((fp1=fopen("compression.txt","r"))==NULL)
	{
		printf("\n在解码时compression.txt文件不成功!\n");
		exit(0);
	}
	if((fp2=fopen("huffman_decode.txt","w+"))==NULL)
	{
		printf("\nhuffman_decode.txt文件创建不成功\n");
		exit(0);
	}
	else 
		printf("\nhuffman_decode.txt文件创建成功!\n\n下面进行解码：\n");
    
	ch=fgetc(fp1);
	m=2*LENGHTH-2;
 	while(feof(fp1)==0)
	{
		if(ch=='0')
		{
			if(huffmannode[huffmannode[m].lchild].data==0)
				m=huffmannode[m].lchild;
			else
			{
			   fprintf(fp2,"%c",huffmannode[huffmannode[m].lchild].data);
			   m=2*LENGHTH-2;
			}
		}
		else
		{
			if(huffmannode[huffmannode[m].rchild].data==0)
				m=huffmannode[m].rchild;
			else
			{
			   fprintf(fp2,"%c",huffmannode[huffmannode[m].rchild].data);
			   m=2*LENGHTH-2;
			}	
		}
        ch=fgetc(fp1);
	}	
     fclose(fp1);
     fclose(fp2);
	 printf("\nHuffman 解码成功，解码结果保存在huffman_decode.txt中。请注意检查！\n\n");

}

void main()
{
	FILE *fp;
	printf("\nHuffman 编码器-------<李海  2601307023>\n");
	initial();
	fp=fileopen();
	tongjipinlv(fp);
	hufftreeconstruct();
	huffman_code();
	code_ef();
	compression();
    huffman_decode();

}