#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
typedef struct
{
char data; ///结点字符
int weight; ///结点权值
int parent,lchild,rchild; ///父子结点
} HTNode,* HuffmanTree;///结构体数组类型
typedef char * *HuffmanCode;
void Select(HuffmanTree HT, int m, int& s1, int& s2)
{
int i;
s1=s2=1;
///找第一个权值最小的节点
for(i=1; i<=m; i++)
{
if(HT[i].parent==0)///这个点还没有父节点，即它还没有被选过
{
s1=i;
break;
}
}
for(i=i+1; i<=m; i++)
{
if(HT[i].parent==0&&HT[s1].weight>HT[i].weight)///在s1后面的没有被选过的节点权值比s1小
s1=i;
}
///找第二个权值最小的节点
for(i=1; i<=m; i++)
{
if(HT[i].parent==0&&i!=s1) ///没有被选过，并且这个节点不是s1
{
s2=i;
break;
}
}
for(i=i+1; i<=m; i++)
{
if(HT[i].parent==0&&HT[i].weight<HT[s2].weight&&i!=s1)///在s2后面的没有被选过的节点权值比s2小，并且不等于s1
s2=i;
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n)
///w存放n个字符的权值，构造赫夫曼树HT，并求出n个字符的赫夫曼树编码HC
{
int f;
int m,i,s1,s2;
int c;
HuffmanTree p;/// 定义一个结构体数组，放哈夫曼树
char *cd; ///定义一个字符数组，放哈夫曼编码
if(n<=1)
return;
m=2*n-1;///节点总数为n-1个
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));///分配当前求编码的工作空间
for(p=HT+1,i=1; i<=n; ++i,++p,++w) ///初始化，建树之前只有n个节点
{
(*p).weight=*w;///权值
(*p).parent=0;///父节点，左右孩子都初始化为0，因为建树之前他们都没有双亲和孩子
(*p).lchild=0;
(*p).rchild=0;
}
for(; i<=m; ++i,++p)
(*p).parent=0;/// 非叶节点的父节点初始化为0
for(i=n+1; i<=m; ++i) ///建立赫夫曼树
///在HT[1..i-1]选择parent为0且weight最小的两个节点，其序号分别为s1,s2.
{
Select(HT,i-1,s1,s2);///调用函数，找出权值最小的两个节点
HT[s1].parent=i;///s1,s2的父节点都为i
HT[s2].parent=i;
HT[i].lchild=s1;/// i的左孩子是s1
HT[i].rchild=s2;///i的右孩子是s2
HT[i].weight=HT[s1].weight+HT[s2].weight;///i的权值就是左右孩子的权值之和
}
///****从叶子到根逆向求每个字符的赫夫曼编码****
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));///分配n个字符编码的头指针向量
cd=(char*)malloc(n*sizeof(char)); ///分配求编码的工作区间
cd[n-1]='\0'; ///编码结束符
for(i=1; i<=n; ++i)
{
int start;
start=n-1; ///哈夫曼编码的长度最多为n-1 //编码结束符位置
for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent) ///从叶子到根逆向求编码, f==0是它已经没有父节点，所以循环结束
if(HT[f].lchild==c)///c是f的左孩子
cd[--start]='0';///左孩子编码为0
else ///c是f的右孩子
cd[--start]='1'; ///右孩子为1
HC[i]=(char *)malloc((n-start)*sizeof(char)); ///为第i个字符编码分配空间
strcpy(HC[i],&cd[start]); ///从cd复制编码（串）到HC
}
free(cd); ///释放空间
}
int main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
printf("请输入权值的个数(): ");
scanf("%d",&n);
w=(int *)malloc(n*sizeof(int));///分配内存空间
printf("请依次输入%d个权值(整型):\n",n);
for(i=0; i<=n-1; i++)
scanf("%d",w+i);
HuffmanCoding(HT,HC,w,n);
for(i=1; i<=n; i++)
{
printf("对应的编码为：");
puts(HC[i]);
}
}
