#include<string.h>
#include<stdlib.h>
#include<stdio.h>
int m,s1,s2;
typedef struct {
	char name;
    int weight;
    int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef struct {
	int weight;
	char name;
}codeweight;
typedef char **HuffmanCode;

void Select(HuffmanTree HT,int g,int &s1,int &s2)
{
  int j,k,m,n;
    for(k=1;k<=g;k++)
     {
		if(HT[k].parent==0)
		{  s1=k;  break;}
     }
   for(j=1;j<=g;j++)
   {
    if((HT[j].weight<HT[k].weight)&&(HT[j].parent==0))
       s1=j;
   }
     for(m=1;m<=g;m++)
      {
        if((HT[m].parent==0)&&(m!=s1))
		{s2=m;break;}
      }
      for(n=1;n<=g;n++)
       if((HT[n].weight<HT[m].weight)&&(HT[n].parent==0)&&(n!=s1)) s2=n;
}
//編碼
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, codeweight *cw, int n)
{
	 int i,m,s1=0,s2=0;
     int c,f,start;
     char *cd;
   if (n<=1) return;
   m = 2 * n - 1;
   HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));
    for (i=1; i<=n; i++)
    {
      HT[i].weight=cw[i-1].weight;
	  HT[i].name=cw[i-1].name;
      HT[i].parent=0;
      HT[i].lchild=0;
      HT[i].rchild=0;
    }
    for (i=n+1; i<=m; i++)
    {
      HT[i].weight=0;
      HT[i].parent=0;
      HT[i].lchild=0;
      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].weight = HT[s1].weight + HT[s2].weight;
   }
   HC = (HuffmanCode)malloc((n+1) * 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]);
   }
free(cd);
}
//******************譯碼*****************************//
void HuffmanTran(HuffmanTree &HT,FILE *fp4,FILE *fp5,int n)
{
HuffmanTree p=HT+2*n-1;
char ch=48;
 while(1)
 {
   ch=fgetc(fp4);
   if(ch==EOF)break;
   if(ch=='0') p=HT+p->lchild;
       else if(ch=='1') p=HT+p->rchild;
    if(p->lchild==0&&p->rchild==0)
	   {
             //共n個(gè)權(quán)值中查找weigt的對應(yīng)碼
          	 fprintf(fp5,"%c",p->name);
			 p=HT+2*n-1;
       }
 }
 fclose(fp4);
 fclose(fp5);
}
 //-----主函數(shù)---------
void main()
{
FILE *fp1;
FILE *fp2;
FILE *fp3;
FILE *fp4;
FILE *fp5;
int j=0;
int num[128]={0};
codeweight cw[128];char filename[50];
HuffmanTree HT;
HuffmanCode HC;
//統(tǒng)計(jì)源文件字符
printf("請輸入要譯碼的文件名(絕對路徑):");
scanf("%s",filename);
if( (fp1=fopen(filename,"r"))==NULL )
{
printf("open source.txt fail!");
exit(0);
}
if( (fp2=fopen("e:\\statistics.txt","w+"))==NULL )
{
printf("create statistics.txt fail!");
fclose(fp1);
exit(0);
}
//---建樹并輸出赫夫曼編碼
   char ch=48;int i;
  while(1)
  {
	 ch=fgetc(fp1);
	 if(ch==EOF){fseek(fp1,0,0);break;}
	 ++num[ch];
  }

  for(i=0;i<128;i++)

  {
    if(num[i])
    {
	  fprintf(fp2,"%c %d\n",i,num[i]);
	  cw[j].name=i;cw[j].weight=num[i];
      ++j;
	}
  }
fclose(fp1);
fclose(fp2);
HuffmanCoding(HT,HC,cw,j);
        if((fp3=fopen("e:\\code.txt","w+"))==NULL )
             {
                printf("create code.txt fail!");
                exit(0);
             }
		for(i = 1;i <= j;i++)
            fprintf(fp3,"%c %s\n",cw[i-1].name,HC[i]);
        fclose(fp3);
//二進(jìn)制壓縮編碼輸出
fp1=fopen(filename,"r");
fp4=fopen("c:\\source_code.txt","w+");
 ch=48;
 while(1)
 {
	 ch=fgetc(fp1);
	 if(ch==EOF)break;
	 for(i=0;i<j;i++)
	    if(ch==cw[i].name)fputs(HC[i+1],fp4);
 }
fclose(fp1);
fclose(fp4);
fp1=fopen("e:\\bin_code.txt","wb+");
fp4=fopen("c:\\source_code.txt","rb");
char bin=0; long int s=0;char c;
int t,x,left;
	 for(t=0;t<8;t++)
	 {
	    ch=fgetc(fp4);
		if(ch==EOF)
		{
                     for(left=0;left<t;left++)
                     if((bin&(1<<(7-left)))==0){c='0';fputc(c,fp1);}
                     else {c='1';fputc(c,fp1);}
		}
	    if(ch==EOF)break;
		if(ch==48)x=0;else x=1;
	     bin=bin|x<<(7-t);
	     ++s;
		 if(t==7){t=-1;fwrite(&bin,sizeof(char),1,fp1);bin=0; }
    }
fclose(fp1);
fclose(fp4);
//二進(jìn)制編碼的譯碼輸出
 unsigned char a;
fp1=fopen("e:\\bin_code.txt","rb");
fp4=fopen("c:\\pre2_code.txt","wb+");
for(i=0;i<s/8;i++)
{
    fread(&a,sizeof(char),1,fp1);
    for(t=0;t<8;t++)
    if((a&(1<<(7-t)))==0){ch='0';fputc(ch,fp4);}
    else {ch='1';fputc(ch,fp4);}
}
for(t=0;t<left;t++)
	fputc(fgetc(fp1),fp4);
fclose(fp1);
fclose(fp4);
fp4=fopen("c:\\pre2_code.txt","rb");
fp5=fopen("e:\\tran_code.txt","wb+");
HuffmanTran(HT,fp4,fp5,j);
}