#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
// 最大权值，用于初始化
#define MAX_WEIGHT INT_MAX
// --- 1. 数据结构定义 ---
// 哈夫曼树结点结构体
typedef struct {
int weight; // 结点的权值
int parent, lchild, rchild; // 双亲、左孩子、右孩子的下标
} HTNode, *HuffmanTree;
// 哈夫曼编码表类型（字符指针数组）
typedef char **HuffmanCode;
// --- 2. 辅助函数 Select ---
// 在 HT[1...k] 范围内，找出 parent 为 0 且权值最小的两个结点，用 s1 和 s2 返回其下标
void Select(HuffmanTree HT, int k, int *s1, int *s2) {
int min1 = MAX_WEIGHT, min2 = MAX_WEIGHT; // 初始化为最大值
*s1 = 0;
*s2 = 0;
for (int i = 1; i <= k; i++) {
// 只考虑尚未加入树的结点 (parent为0)
if (HT[i].parent == 0) {
if (HT[i].weight < min1) {
// 如果当前结点权值小于 min1，则更新 min1 和 min2
min2 = min1;
*s2 = *s1;
min1 = HT[i].weight;
*s1 = i;
} else if (HT[i].weight < min2) {
// 如果当前结点权值介于 min1 和 min2 之间，则更新 min2
min2 = HT[i].weight;
*s2 = i;
}
}
}
}
// --- 3. 核心函数：构造哈夫曼树 ---
// w 存放 n 个权值，构造哈夫曼树 HT
void CreateHuffmanTree(HuffmanTree *HT, int *w, int n) {
if (n <= 1) return;
int m = 2 * n - 1; // 哈夫曼树总结点数
*HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); // 0号单元未用，分配 m+1 个空间
if (!*HT) {
fprintf(stderr, "内存分配失败!\n");
exit(EXIT_FAILURE);
}
// 初始化所有结点的双亲、左右孩子下标为0
for (int i = 1; i <= m; i++) {
(*HT)[i].parent = 0;
(*HT)[i].lchild = 0;
(*HT)[i].rchild = 0;
}
// 输入前 n 个结点的权值
for (int i = 1; i <= n; i++) {
(*HT)[i].weight = w[i - 1]; // w数组从0开始，HT从1开始
}
// --- 开始创建哈夫曼树 ---
printf("\n--- 构造哈夫曼树过程 ---\n");
for (int i = n + 1; i <= m; i++) {
int s1, s2;
// 在 HT[1...i-1] 中选择两个权值最小的结点
Select(*HT, i - 1, &s1, &s2);
printf("第 %2d 次合并: 选择权值 %d (结点%d) 和 %d (结点%d)\n", i - n, (*HT)[s1].weight, s1, (*HT)[s2].weight, s2);
// 将新结点 i 的双亲设为 s1, s2
(*HT)[s1].parent = i;
(*HT)[s2].parent = i;
// s1, s2 分别作为 i 的左右孩子
(*HT)[i].lchild = s1;
(*HT)[i].rchild = s2;
// i 的权值为 s1, s2 权值之和
(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
}
printf("--- 哈夫曼树构造完成 ---\n\n");
}
// --- 4. 核心函数：生成哈夫曼编码 ---
// 从哈夫曼树 HT 反向生成哈夫曼编码 HC
void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n) {
*HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); // 分配 n 个字符编码的头指针
if (!*HC) {
fprintf(stderr, "内存分配失败!\n");
exit(EXIT_FAILURE);
}
char *cd = (char *)malloc(n * sizeof(char)); // 分配临时存放编码的动态数组
if (!cd) {
fprintf(stderr, "内存分配失败!\n");
exit(EXIT_FAILURE);
}
cd[n - 1] = '\0'; // 编码结束符
// 逐个字符求哈夫曼编码
for (int i = 1; i <= n; i++) {
int start = n - 1; // start 指向编码结束符
int c = i;
int f = HT[c].parent;
// 从叶子结点开始向上回溯，直到根结点
while (f != 0) {
--start; // 回溯一次，start向前指一个位置
if (HT[f].lchild == c) {
cd[start] = '0'; // 结点c是f的左孩子，则生成代码'0'
} else {
cd[start] = '1'; // 结点c是f的右孩子，则生成代码'1'
}
c = f;
f = HT[f].parent; // 继续向上回溯
}
// 为第 i 个字符编码分配空间
(*HC)[i] = (char *)malloc((n - start) * sizeof(char));
if (!(*HC)[i]) {
fprintf(stderr, "内存分配失败!\n");
exit(EXIT_FAILURE);
}
// 将求得的编码从临时空间 cd 复制到 HC 的当前行
strcpy((*HC)[i], &cd[start]);
}
free(cd); // 释放临时空间
}
// --- 5. 打印函数 ---
void PrintHuffmanCode(HuffmanCode HC, int *w, int n) {
printf("--- 哈夫曼编码结果 ---\n");
printf("权值\t编码\n");
printf("--------------------\n");
for (int i = 1; i <= n; i++) {
printf("%d\t%s\n", w[i - 1], HC[i]);
}
printf("--------------------\n");
}
// --- 6. 主函数 ---
int main() {
int n = 8;
int w[] = {5, 29, 7, 8, 14, 23, 3, 11}; // 【例5.2】的权值
HuffmanTree HT = NULL;
HuffmanCode HC = NULL;
// 1. 构造哈夫曼树
CreateHuffmanTree(&HT, w, n);
// 2. 生成哈夫曼编码
HuffmanCoding(HT, &HC, n);
// 3. 打印编码结果
PrintHuffmanCode(HC, w, n);
// 4. 释放内存
for (int i = 1; i <= n; i++) {
free(HC[i]);
}
free(HC);
free(HT);
return 0;
}
