typedef struct _HTNode {
unsigned int weight; /* 權(quán)值 */
unsigned int parent; /* 父節(jié)點(diǎn)索引 */
unsigned int lchild; /* 左孩子索引 */
unsigned int rchild; /* 右孩子索引 */
} HTNode, *HuffmanTree; /* 動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹 */
typedef char **HuffmanCode; /* 動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表 */
/* 從ht的1～n的節(jié)點(diǎn)中找出權(quán)值最小的兩個(gè)節(jié)點(diǎn)，分別存于s1, s2中 */
void Select(HuffmanTree ht, int n, int *s1, int *s2)
{
int i;
*s1 = 0;
*s2 = 0;
/*設(shè)置s1, s2到開始兩個(gè)parent等于0的節(jié)點(diǎn)位置*/
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，且權(quán)值最小的兩個(gè)節(jié)點(diǎn)位置，分別存于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存儲(chǔ)的n個(gè)權(quán)值，來創(chuàng)建一顆哈夫曼樹, 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個(gè)字符，需要2n-1個(gè)空間來存儲(chǔ)整顆huffman tree */
*ht_ptr = (HuffmanTree)malloc( (m + 1) * sizeof(HTNode)); /* 0號(hào)單元不用 */
for (p = *ht_ptr + 1, i = 1; i <= n; ++i, ++p, ++w) { /* 初始化數(shù)組中前n個(gè)單元存儲(chǔ)的字符 */
p->weight = *w;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for ( ; i <= m; ++i, ++p) { /* 初始化數(shù)組中剩余的單元 */
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);
/* 設(shè)置s1, s2的父親為i */
(*ht_ptr + s1)->parent = i;
(*ht_ptr + s2)->parent = i;
/* 設(shè)置i的左孩子為s1, 右孩子為s2 */
(*ht_ptr + i)->lchild = s1;
(*ht_ptr + i)->rchild = s2;
/* 設(shè)置i的權(quán)值為s1, s2之和 */
(*ht_ptr + i)->weight = (*ht_ptr + s1)->weight + (*ht_ptr + s2)->weight;
}
}
/* 對(duì)ht_ptr存儲(chǔ)的哈夫曼樹的n個(gè)葉子節(jié)點(diǎn)進(jì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; /* 從葉子節(jié)點(diǎn)開始，并取得父節(jié)點(diǎn)father */
father != 0; /* 父節(jié)點(diǎn)為0時(shí)及到達(dá)了根節(jié)點(diǎn) */
current = father, father = (*ht_ptr + father)->parent) { /* 逐漸向根節(jié)點(diǎn)靠攏 */
if ( (*ht_ptr + father)->lchild == current) /* 當(dāng)前節(jié)點(diǎn)為左孩子 */
cd[--start] = '0';
else
cd[--start] = '1';
}
*(*hc_ptr + i) = (char *)malloc( (n - start) * sizeof(char));
strcpy(*(*hc_ptr +i), &cd[start]);
}
free(cd);
}