# 赫夫曼编码c++中的实现

#include<cctype>
#include<cstdlib>
#include<cstdio>
#include<cstring>

typedef struct {
unsigned int weight;
unsigned int parent, lchild,rchild;
}HTNode, *HuffmanTree;
typedef char ** HuffmanCode;

//find the min value of two item in Tree
void Select(HuffmanTree &HT,unsigned int i, unsigned int &min1,unsigned int &min2)
{
unsigned int tmp=HT[1].weight,j=0,t=1;
//  for(t=1;HT[t].parent!=0;t++);
while(HT[t].parent>0)
t++;
for( j=1,min1=t;j<= i; j++){
if(HT[j].parent==0&&HT[j].weight<HT[min1].weight)
min1=j;
}
for(j=1,min2=t;j<=i;j++)
{
if((HT[j].parent==0)&&(HT[j].weight<HT[min2].weight)&&(!(j==min1)))
min2=j;
}
if(min1==min2)
{
do
{  t++;
}while(HT[t].parent>0);
for(j=1,min2=t;j<=i;j++)
{
if((HT[j].parent==0)&&(HT[j].weight<HT[min2].weight)&&(!(j==min1)))
min2=j;
}
}
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, unsigned int *w,unsigned int n)
{
unsigned  int i,s1=1,s2=1;
unsigned  int m ,start;
unsigned int k;
HuffmanTree p;
//*p={ *w,0,0,0};
char *cd;
if(n<=1) return;
m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
HTNode HN;
//  HN={*w,0,0,0};
p=HT;
for(p=p+1,i=1;i<=n;++i,++p,++w)
{
p->weight=*w;
p->lchild=0;
p->parent=0;
p->rchild=0;
//*p={*w,0,0,0};
}
for(;i<=m;++i,++p)
{
p->weight=0;
p->lchild=0;
p->parent=0;
p->rchild=0;
//*p={*w,0,0,0};
}
// *p={0,0,0,0};
for(i=n+1;i<=m;++i)//Create HuffmanTree
{
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;
printf("%6d  %6d   %6d   %6d %d/n",HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild,i);
}
//get the Huffman code
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='/0';

for(k=1;k<=m;++k)
{
printf("%6d  %6d   %6d   %6d   %7d/n",HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild,k);
}
for(k=1;k<=n;++k)
{
unsigned int c,f;
start = n-1;
for(c=k, f=HT[k].parent;f != 0;c=f, f=HT[f].parent)
{
if(HT[f].lchild==c)
cd[--start]='0';
else cd[--start]='1';
}
HC[k] = (char *)malloc((n-start)*sizeof(char));
//    printf("cd is %s/n", cd);
strcpy(HC[k],&cd[start]);
printf("k %6d is %s  /n", k,HC[k]);
}

free(cd);
}

void main()
{
unsigned int a[]={5,29,7,8,14,23,3,11};
unsigned int *w=a;
/* for(int i=1;i<=8;i++,w++)
printf("%d/n",*w);
w=a;*/
HuffmanTree HT;
HuffmanCode HC;
HuffmanCoding(HT,HC, w,  8);
for(int i=1;i<=8;i++)
printf("%S  %6d",HC[i],HT[i].weight);

//printf("%d/n",*(w+1));
system("pause");

}

2，逻辑算法能力有待提高，加强训练。

Top