哈夫曼编码.cpp

可以对文本字符进行ｈａｆｆｍａｎ编码

#include<stdio.h>
#include"stdio.h" 
#include"stdlib.h"
#include"string.h"
char ch[27];//暂时使用有20个字符的文件，可以增加
int frequency[26];//各个字符的使用频率
int numch[27]={0};
typedef char ElemType; 
char cflag;
typedef struct
{ 
   ElemType elem;
   unsigned int m_weight; 
   unsigned int parent,lchild,rchild; 
}HTNode,*HuffmanTree; 

typedef char** HuffmanCode; 
typedef int Status; 
typedef struct weight
{
  char elem; 
  unsigned int m_weight; 
}Weight; 
 HuffmanCode HC;// save the information of the symbolizes; 
void readfile()
{
	FILE *fr; char ch1;int i;
	for(i=0;i<26;i++)
		frequency[i]=0;
    for(i=1;i<27;i++)
		ch[i]=96+i;
	if((fr=fopen("test.dat","r"))==NULL)
	{
		printf("Can't open the file! please make sure!\n");
		exit(0);
	}
	ch1=fgetc(fr);
	while(ch1!=EOF)
	{
		ch[ch1-96]=ch1;
		frequency[ch1-97]++;
		ch1=fgetc(fr);
	}
	printf("\n各个字符的频率\n");
	for(i=0;i<26;i++)
	{printf("%c:%d ",ch[i+1],frequency[i]);}
	fclose(fr);
    
}
void sort_fre()
{
	int i,j,k,temp;char temp1;
	for(i=0;i<26;i++)
	{
		j=i;
		for(k=i+1;k<26;k++)
			if(frequency[k]>frequency[j])
				j=k;
	    if(j!=i)
		{
			temp=frequency[i];
			frequency[i]=frequency[j];
			frequency[j]=temp;
			temp1=ch[i+1];
			ch[i+1]=ch[j+1];
			ch[j+1]=temp1;
		}
	}
	for(i=0;i<26;i++)
	  printf("%c:%d ",ch[i+1],frequency[i]);
}
void Select(HuffmanTree HT,int n,int *s1,int *s2) 
{ 
  int i; 
  (*s1)=(*s2)=0; 
  for(i=1;i<=n;i++)
  { 
    if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0)
{ 
      if(HT[i].m_weight<HT[(*s1)].m_weight)
  { 
  (*s2)=(*s1); 
  (*s1)=i; 
      } 
      else (*s2)=i; 

    } 

    if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)
{ 
      if((*s1)==0) (*s1)=i; 
      else if((*s2)==0)
  { 
  if(HT[i].m_weight<HT[(*s1)].m_weight)
  { 
  (*s2)=(*s1); 
  (*s1)=i; 
  } 
  else (*s2)=i; 
      } 
    } 
  } 

  if((*s1)>(*s2))
  { 
    i=(*s1); 
(*s1)=(*s2); 
(*s2)=i; 
  } 
  return; 
} 

void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n)
{ 
  int i,m,s1,s2,start,c,f; 
  char *cd; 
  HuffmanTree p; 
  if(n<=1)
  return; 

  m=2*n-1; 
  (*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
  for(i=1;i<=n;++i)
  { 
     (*HT)[i].elem=w[i-1].elem; 
     (*HT)[i].m_weight=w[i-1].m_weight; 
     (*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0; 
  } 

  for(;i<=m;++i)
  { 
    (*HT)[i].elem='0'; 
    (*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0; 
  } 

  for(i=n+1;i<=m;++i)
  { 
    Select(*HT,i-1,&s1,&s2); 
    (*HT)[s1].parent=i;(*HT)[s2].parent=i; 
    (*HT)[i].lchild=s1;(*HT)[i].rchild=s2; 
    (*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight; 
  } 

  (*HC)=(HuffmanCode)malloc(n*sizeof(char*)); 
  cd=(char *)malloc(n*sizeof(char)); 
  cd[n-1]='\0'; 
  for(i=1;i<=n;++i)
  { 
     start=n-1; 
     for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent)
 { 
		 if((*HT)[f].lchild==c) cd[--start]='0'; 
       else cd[--start]='1'; 
     } 

     (*HC)[i]=(char *)malloc((n-start)*sizeof(char));
     strcpy((*HC)[i],&cd[start]); 
  } 
} 

void calutenum(){
	int i=0,k=0;
	for(i=0;i<26;i++)
	{		k=0;
		while(HC[i+1][k]!='\0')
		{numch[i+1]=numch[i+1]*2+HC[i+1][k]-48;k++;}

	}
}
void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n) 
{ 
  int i; calutenum();
  printf("\nnumber---element---weight---huffman code\n"); 
  for(i=1;i<=n;i++) 
  {
	  if(frequency[i]==0)
		  cflag=ch[i];
    printf("  %d        %c         %d        %s\n",numch[i],HT[i].elem,HT[i].m_weight,HC[i]);
  }
} 

Status Humanf() 
{ 
  HuffmanTree HT; 
  Weight *w; 
  char c;    
  int i,n;      
  int wei;    
  n=26;
  w=(Weight *)malloc(n*sizeof(Weight)); 
  for(i=0;i<n;i++)
  { 
    w[i].elem=ch[i+1]; 
    w[i].m_weight=frequency[i]; 
  } 

  HuffmanCoding(&HT,&HC,w,n); 
  OutputHuffmanCode(HT,HC,n); 
  return 1; 
}
void writefile(){
	FILE *fp,*fw;char ch1,re[8];int i=0, k=0,sum=0,count=0;
	if((fp=fopen("test.dat","r"))==NULL)
	{
		printf("Can't open the file! please make sure!\n");
		exit(0);
	}
	if((fw=fopen("compress_data.txt","w"))==NULL)
	{
		printf("Can't open the file! please make sure!\n");
		exit(0);
	}
	ch1=fgetc(fp);
	while(ch1!=EOF)
	{
	 for(i=0;i<26;i++)
	 {
		if(ch1==ch[i+1])
		{

			while(HC[i+1][k]!='\0')
			{
				count++;
				sum=sum*2+HC[i+1][k]-48;
				if(count==8)
				{
					fputc(sum,fw);
					sum=0;
					count=0;
				}
				k++;
			}
			k=0;	
			break;
		}
	 }
		ch1=fgetc(fp);
	}
	while(count<8)
		{sum*=2;count++;}
	fputc(sum,fw);
	fputc(cflag,fw);
	fclose(fw);
}
void chartobinary(char ch,int re[])
{
	int i,k=7;
	for(i=0;i<=7;i++)
		re[i]=0;
	while(ch!=0)
	{
		re[k--]=ch%2;
		ch/=2;
	}
}
int compare(int sum)
{
	for(int i=1;i<=26;i++)
		if(sum==numch[i])
			return i;
	return -1;
}
void recoverfile(){
	FILE *fv,*fr;char c;int i,sum=0,t,cp[8];
	if((fv=fopen("compress_data.txt","r"))==NULL)
	{
		printf("Can't open the file! please make sure!\n");
		exit(0);
	}
		if((fr=fopen("recover.txt","w"))==NULL)
	{
		printf("Can't open the file! please make sure!\n");
		exit(0);
	}
	c=fgetc(fv);
	while(c!=cflag)
	{
		chartobinary(c,cp);
		for(i=0;i<8;i++)
		{
			sum=sum*2+cp[i];
			t=compare(sum);
			if(t!=-1)
				fputc(ch[t],fr);
		}
		c=fgetc(fv);
	}
}
void main()
{
	readfile();
	sort_fre();
	Humanf();
	writefile();
	recoverfile();
}