huff_header.h

赫夫曼编码程序

#include<string.h>
typedef struct
{int weight;
 int lchild,rchild,parent;
}HNode,*HTree;

typedef char* *HuffCode;


void CreateHuffTree(HTree &HT,int *w,HuffCode &HC,int n)
{ int m;
  m=2*n-1;
  HT=(HTree)malloc(sizeof(HNode)*(m+1));


  for( int i=1;i<=n;i++)
  {HT[i].weight=w[i];
   HT[i].lchild=0;
   HT[i].rchild=0;
   HT[i].parent=0;
  }
   

  for(i=n+1;i<=m;i++)
  { HT[i].weight=0;
	HT[i].lchild=0;
    HT[i].rchild=0;
    HT[i].parent=0;
  }

  HT[0].weight=10000;
  for( i=n+1;i<=m;i++)
  {  int s1=0;int s2=0;
	  for(int j=1;j<=i-1;j++)
         if(HT[s1].weight>HT[j].weight&&HT[j].parent==0)
			 s1=j;

	  HT[s1].parent=i;
	  HT[i].lchild=s1;


	  for( j=1;j<=i-1;j++)
         if(HT[s2].weight>HT[j].weight&&HT[j].parent==0)
			 s2=j;

	 HT[s2].parent=i;
	 HT[i].rchild=s2;


  }


  //从叶子到根逆向求huffman编码
  char*cd;
  int start;
  HC=(HuffCode)malloc(sizeof(char*)*(n+1));
 
  cd=(char*)malloc(n*sizeof(char));
  cd[n-1]='\0';
  for( i=1;i<=n;i++)
  { start=n-1;
    for(int 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);    

//cout<<HC[3];

}



int weight_search(int weight,int w[])
{for (int i=0;i<=128;i++)
  if(w[i]==weight)
	  return i;

}

//对文档进行编码


void Huff_encoder(fstream infile,fstream &outfile,HuffCode HC,int n)
{   char inch;
    char *outch;
	int intch;
	outch=(char*)malloc(n*sizeof(char));
	
	infile.clear();
	outfile.clear();

	infile.seekg(0L,ios::beg);
	outfile.seekp(0L,ios::beg);
	
   
    while(!infile.eof())
	{ infile.get(inch);
	  if(infile.fail())
		  break;
	  intch=(int)inch;
	  if(intch>=0&&intch<=128)
	       outfile<<HC[(int)inch];
	  else
		   continue;
	 
	}



	/*while(!infile.eof())
    { if(!inch)
	    break;
	if((int)inch>128||(int)inch<0)
	{infile.get(inch);	continue;}
		strcpy(outch,HC[(int)inch]);
	    outfile.write(outch,sizeof(HC[(int)inch]));
	    printf("%s\n",outch);
	    infile.get(inch);
	}*/

}


//对文章进行解码
void Huff_decoder(fstream infile,fstream &outfile,HuffCode HC,int n,HTree HT)
{   /*fstream Password;
    
    Password.open("Password.txt",ios::in|ios::binary);
	Password.clear();
	Password.seekg(0L,ios::beg);
	Password.read((char*)w,sizeof(w));*/

	infile.clear();
    infile.seekg(0L,ios::beg);
	char ch; 
    int Index=128;
    char *code[128];
	int flag=1;

	while(!infile.eof())
	{int index=2*n-1;
		while(HT[index].lchild !=0)
		{
			infile.get(ch);
			if(infile.fail())
			{ flag=0;
			 break;
			}
			
				if(ch=='0')
					index=HT[index].lchild;
				else
					index=HT[index].rchild;
			
		}
		
		ch=index;                                                
		if(flag!=0)
			outfile.put(ch); }  
}