1、源代码（详解见注释）
#include <stdio.h> #include<stdlib.h> #include<string.h> typedef struct { int weight; int parent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组存储赫夫曼树 typedef char* HCNode; typedef HCNode* HuffmanCode; //动态分配数组存储哈夫曼编码表 void Select(HuffmanTree HT,int m,int *s1,int *s2){ //在HT【1，m】中选择parent为0且weight最小的两个结点，其序号分别为s1,s2 int i,min1=2000,min2=2000,a=0,b=0; for(i=1;i<=m;i++){ if(HT[i].parent==0&&(HT[i].weight<min1||HT[i].weight<min2)){ if(HT[i].weight<min1){ min1=HT[i].weight; a=i; }else{ min2=HT[i].weight; b=i; } } } *s1=a;*s2=b; } //w存放n个字符的权值，构造赫夫曼树HT void HuffmanCoding(HuffmanTree *HT,int *w,int n){ if(n<=1) return; int m=2*n-1; //n个字符（叶子节点）需要2n-1个节点 *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用 HuffmanTree p; int i,s1,s2; for(i=1; i<=m; i++) //初始化结点[1...2*n+1]，存储叶子结点及双亲结点 { if(i<=n) (*HT)[i].weight = w[i-1]; //[1...n]，叶子结点 else (*HT)[i].weight = 0; //[n+1...2*n+1]，双亲结点 (*HT)[i].parent = 0; (*HT)[i].lchild = 0; (*HT)[i].rchild = 0; } for(i=n+1;i<=m;i++){ 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; } } //从叶子到根逆向求每个字符的赫夫曼编码 void HuffmanCodingFinding(HuffmanTree HT,HuffmanCode *HC,int n){ *HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //相当于二维数组,分配n个字符编码的头指针向量,0号单元不用 char *cd; int start; cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间（暂时存放)，每个编码最多有n-1个字符组成 cd[n-1]='\0'; //结束标志 for(int i=1; i<=n; i++) //逐次求每个叶子结点的哈夫曼编码 { start = n - 1; //赋值起点 for(int 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]); //从start开始复制 } free(cd); } //测试函数 int main() { int w[8]={5,29,7,8,14,23,3,11}; HuffmanTree HT; HuffmanCode HC; HuffmanCoding(&HT,w,8); HuffmanCodingFinding(HT,&HC,8); for(int i=1;i<=8;i++) printf("%s\n",HC[i]); }2、结果
