typedef struct _HTNode {
unsigned int weight; /* 权值 */
unsigned int parent; /* 父节点索引 */
unsigned int lchild; /* 左孩子索引 */
unsigned int rchild; /* 右孩子索引 */
} HTNode, *HuffmanTree; /* 动态分配数组存储哈夫曼树 */
typedef char **HuffmanCode; /* 动态分配数组存储哈夫曼编码表 */
/* 从ht的1～n的节点中找出权值最小的两个节点，分别存于s1, s2中 */
void Select(HuffmanTree ht, int n, int *s1, int *s2)
{
int i;
*s1 = 0;
*s2 = 0;
/*设置s1, s2到开始两个parent等于0的节点位置*/
for (i = 1; i <= n; ++i) {
if (*s1 != 0 && *s2 != 0)
break;
if (ht[i].parent == 0)
*s1 == 0 ? *s1 = i : *s2 = i;
}
/*找出ht中parent等于0，且权值最小的两个节点位置，分别存于s1, s2中*/
for ( ; i <= n; ++i) {
if (ht[i].parent != 0) continue;
if ( (ht[*s1].weight > ht[*s2].weight) && (ht[*s1].weight > ht[i].weight))
*s1 = i;
else if ( (ht[*s2].weight > ht[*s1].weight) && (ht[*s2].weight > ht[i].weight))
*s2 = i;
}
}
/* 通过w存储的n个权值，来创建一颗哈夫曼树, ht_ptr指向这颗哈夫曼树 */
void CreateHuffmanTree(HuffmanTree *ht_ptr, int *w, int n)
{
int m;
int i;
int s1, s2;
HuffmanTree p;
if (n <= 1) return;
m = 2 * n - 1; /* n个字符，需要2n-1个空间来存储整颗huffman tree */
*ht_ptr = (HuffmanTree)malloc( (m + 1) * sizeof(HTNode)); /* 0号单元不用 */
for (p = *ht_ptr + 1, i = 1; i <= n; ++i, ++p, ++w) { /* 初始化数组中前n个单元存储的字符 */
p->weight = *w;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for ( ; i <= m; ++i, ++p) { /* 初始化数组中剩余的单元 */
p->weight = 0;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for (i = n + 1; i <= m; ++i) {
Select(*ht_ptr, i - 1, &s1, &s2);
/* 设置s1, s2的父亲为i */
(*ht_ptr + s1)->parent = i;
(*ht_ptr + s2)->parent = i;
/* 设置i的左孩子为s1, 右孩子为s2 */
(*ht_ptr + i)->lchild = s1;
(*ht_ptr + i)->rchild = s2;
/* 设置i的权值为s1, s2之和 */
(*ht_ptr + i)->weight = (*ht_ptr + s1)->weight + (*ht_ptr + s2)->weight;
}
}
/* 对ht_ptr存储的哈夫曼树的n个叶子节点进行哈夫曼编码 */
void HuffmanCoding(HuffmanTree *ht_ptr, HuffmanCode *hc_ptr, int n)
{
int i;
int start;
char *cd = NULL;
*hc_ptr = (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;
int current, father;
for (current = i, father = (*ht_ptr + i)->parent; /* 从叶子节点开始，并取得父节点father */
father != 0; /* 父节点为0时及到达了根节点 */
current = father, father = (*ht_ptr + father)->parent) { /* 逐渐向根节点靠拢 */
if ( (*ht_ptr + father)->lchild == current) /* 当前节点为左孩子 */
cd[--start] = '0';
else
cd[--start] = '1';
}
*(*hc_ptr + i) = (char *)malloc( (n - start) * sizeof(char));
strcpy(*(*hc_ptr +i), &cd[start]);
}
free(cd);
}