[ÇóÖú] ¹þ·òÂüÊ÷¾À´í£¡¼± ÄÄÀïÔËÐгöÎÊÌâ¡£¡£¡£

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define MAX 100
typedef struct
{
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void Select(HuffmanTree HT,int n,int &s1,int &s2)
{
    int small1,small2;
    s1=s2=0;small1=small2=MAX;
for(int i=1;i<=n;++i)
{
  if(HT[i].parent==0)
  {
   if(HT[i].weight<small1)
   {
    small2=small1;
    small1=HT[i].weight;
    s2=s1; s1=i;
   }
   else
    if(HT[i].weight<small2)
    {
     small2=HT[i].weight;
     s2=i;
    }
  }
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int*w,int n)
{
int m,s1,s2,i,c,start,f;
char *cd;
HuffmanTree p;
if(n<=1)
  return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
  p->weight=*w;
  p->lchild=0;
  p->parent=0;
  p->rchild=0;
}
for(;i<=m;++i,++p)
{
  p->weight=0;
  p->lchild=0;
  p->parent=0;
  p->rchild=0;
}
for(i=n+1;i<=m;++i)
{
  Select(HT,i-1,s1,s2);
  printf("%d  %d\n",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 PrintCode(HuffmanCode HC,int n,char *ch)
{
for(int i=1;i<=n;i++)
{
  printf("×Ö·û%cµÄ»ô·òÂü±àÂ룺",ch[i-1]);
  printf("%s\n",HC[i]);
}
}
void main()
{
HuffmanTree HT;
HuffmanCode HC;
int w[MAX],i,n;
char ch[MAX];
printf("ÇëÊäÈë×Ö·û¸öÊý:\n");
scanf("%d",&n);
printf("ÇëÊäÈë×Ö·û:\n");
for(i=0;i<n;i++)
  scanf("%c",&ch[i]);
printf("ÇëÊäÈë×Ö·û¶ÔӦȨֵ:\n");
for(i=0;i<n;i++)
  scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
PrintCode(HC,n,ch);
}

2Â¥: Originally posted by shyboylpf at 2013-05-09 20:18:44
Ϊ뻹ÄܼӱíÇé¡£¡£¡£