huffman.c

建立huffman树,并进行huffman编码.

/* Note:Your choice is C IDE */
#include "stdio.h"
#define n 8
#define m 2*n-1
#define max 32767
typedef struct
{   int wi;
	char data;
	int parent,lchild,rchild;
}huffm;
typedef struct
{char bits[n+1];
 int start;
 char ch;
}ctype;



void HuffmTree(huffm HT[m+1])
{int i,j,p1,p2;
 int s1,s2;
 for(i=1;i<=m;i++)
  {HT[i].wi=0;
   HT[i].parent=0;
   HT[i].lchild=HT[i].rchild=0;
  }

 for(i=n+1;i<=m;i++)
 {p1=p2=0;
  s1=s2=max;
  for(j=1;j<=i-1;j++)
  if(HT[j].parent==0)
    if(HT[j].wi<s1)
     {  s2=s1;
     	s1=HT[j].wi;
     	p2=p1;
     	p1=j;
     }
     else if(HT[j].wi<s2)
      {s2=HT[j].wi;
      	p2=j;}
  HT[p1].parent=HT[p2].parent=i;
  HT[i].lchild=p1;
  HT[i].rchild=p2;
  HT[i].wi=HT[p1].wi+HT[p2].wi;
 }
}
 

void Huffmcode(ctype code[n+1],char chh[n+1],int w[n+1])
{int i,j,p,s,r;
 huffm HT[m+1];
 ctype md;
 for(i=1;i<=n;i++)
  HT[i].data=code[i].ch=chh[i];
   for(i=1;i<=n;i++)
 {
  HT[i].wi=w[i];
 }
 HuffmTree(HT);
 for(i=1;i<=n;i++)
  {md.ch=code[i].ch;
  	md.start=n+1;
  	s=i;
  	p=HT[i].parent;
  	while(p!=0)
  	{md.start--;
  	 if(HT[p].lchild==s)md.bits[md.start]='0';
  	 else md.bits[md.start]='1';
  	 s=p;p=HT[p].parent;
  	}
  	code[i]=md;
  	printf("%c:",code[i].ch);
  	for(r=md.start;r<=n;r++)printf("%c",md.bits[r]);
  	printf("\n");
  }
}
void main()
{int i;int w[n+1];
 char chh[n+1];
 huffm HT[m+1];
 ctype code[n+1];
 for(i=1;i<=n;i++)
 chh[i]=getchar();
 getchar();
 while(chh[1]!='#')
  {for(i=1;i<=n;i++)
   scanf("%d",&w[i]);
   getchar(); 
   Huffmcode(code,chh,w);
   printf("请继续输入:\n");
    for(i=1;i<=n;i++)
      chh[i]=getchar();
    for(i=1;i<=n;i++)printf("%c",chh[i]);
  }
}