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);
}