huffman编码程序.txt

图形图像处理中常用的编码

Huffman编码程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
FILE *charsetfile;
FILE *inputfile;
FILE *outputfile;
  
typedef struct{
   int weight;
   int parent,lchild,rchild;
}HTNode,*Huffmantree;

void main()
{
int i,j,k,l,m,num,start,s1,s2,*w;
char chfile[10],infile[10],out[10],cur,*cd;
HuffmanTree HT,p;
char **HC;
printf("Enter the character set file name:\n");
scanf("%s",chfile);
printf("Enter the inputfile name:\n");
scanf("%s",infile);
printf("Enter the outputfile name:\n");
scanf("%s",outfile);
if((charsetfile=fopen(chfile,"r"))==NULL)
{
   printf("cannot open the character set file\n");
   exit(0);
}
if((inputfile=fopen(infile,"r"))==NULL)
{
   printf("cannot open the inputfile\n");
   exit(0);
}
if((outputfile=fopen(infile "wb"))==NULL)
{
   printf("cannot open the outputfile\n");
   exit(0);
}

//计算已知num个字符所出现的概率
num=0;
while(!feof(charsetfile))
{
cur=fgetc(charsetfile);
num++;
}
w=(int *)malloc(num * sizeof(int));
for(i=0;i<num;i++)
  w[i]=0;
fseek(charsetfile,0,0)
while(!feof(inputfile))
{
  cur=fgetc(inputfile);
  for(i=0;i<num;i++)
  {
    if(cur==fgetc(charsetfile+fseek(charsetfile,i,0)))
    break;
   }
  w[i]+=1;
}

//构造Huffman树
m=2*num-1;
HT=(HuffmanTree)malloc((m+1) * sizeof(HTNode));
p=HT+1;
for(i=0;i<num;i++,p++)
{
  p->weight=w[i];
  p->parent=0;
  p->lchild=0;
  p->rchild=0;
}
for(i=0;i<m+1;i++,p++)
{
  p->weight=0;
  p->parent=0;
  p->lchild=0;
  p->rchild=0;
}
for(i=m+1;i<m;i++)
{
  //在HT[1..i-1]选择parent为0且weight最小的两个节点
  s1=1;
while(HT[s1].parent!=0)
s1++;
for(j=s1+1;j<i;j++)
  if(HT[j].parent==0&&HT[j].weight<HT[s1].weight)
    s1=j;
HT[s1].parent=i;
s2=1;
while(HT[s2].parent!=0)
s2++;
for(j=s2+1;j<i;j++)
  if(HT[j].parent==0&&HT[j].weight<HT[s2].weight)
    s2=j;
HT[s2].parent=i;

HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}

从叶子节点到根逆向求每个字符的Huffman编码
HC=(char * * )malloc((num+1) * siziof(char * ));
cd=(char * )malloc(num * siziof(char));
cd[num-1]='\\';
for(i=1;i<num;i++)
{
  start=num-1;
  for(k=i,l=HT[i].parent;l!=0;k=l,l=HT[l].parent)
    if(HT[l],lchild==k)
      cd[--start]='0';
    else
      cd[--start]='1';
  HC=(char * )malloc((num-start) * siziof(char));
  strcpy(HC[i],&cd[start]);
}

//输出编码
fseek(inputfile,0,0);
fseek(charsetfile,0,0);
while(!feof(inputfile))
{
cur=fgetc(inputfile);
for(i=0;i<num;i++)
{
    if(cur==fgetc(charsetfile+fseek(charsetfile,i,0)))
    break;
}
fwrite(HC[i+1],1,strlen(HC[i+1]),outputfile);
}

fclose(charsetfile);
fclose(inputfile);
fclose(outputfile);
}