#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
// 最大權(quán)值，用于初始化
#define MAX_WEIGHT INT_MAX
// --- 1. 數(shù)據(jù)結(jié)構(gòu)定義 ---
// 哈夫曼樹結(jié)點結(jié)構(gòu)體
typedef struct {
? ? int weight;? ? ? ? // 結(jié)點的權(quán)值
? ? int parent, lchild, rchild; // 雙親、左孩子、右孩子的下標
} HTNode, *HuffmanTree;
// 哈夫曼編碼表類型（字符指針數(shù)組）
typedef char **HuffmanCode;
// --- 2. 輔助函數(shù) Select ---
// 在 HT[1...k] 范圍內(nèi)，找出 parent 為 0 且權(quán)值最小的兩個結(jié)點，用 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++) {
? ? ? ? // 只考慮尚未加入樹的結(jié)點 (parent為0)
? ? ? ? if (HT[i].parent == 0) {
? ? ? ? ? ? if (HT[i].weight < min1) {
? ? ? ? ? ? ? ? // 如果當前結(jié)點權(quán)值小于 min1，則更新 min1 和 min2
? ? ? ? ? ? ? ? min2 = min1;
? ? ? ? ? ? ? ? *s2 = *s1;
? ? ? ? ? ? ? ? min1 = HT[i].weight;
? ? ? ? ? ? ? ? *s1 = i;
? ? ? ? ? ? } else if (HT[i].weight < min2) {
? ? ? ? ? ? ? ? // 如果當前結(jié)點權(quán)值介于 min1 和 min2 之間，則更新 min2
? ? ? ? ? ? ? ? min2 = HT[i].weight;
? ? ? ? ? ? ? ? *s2 = i;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
// --- 3. 核心函數(shù)：構(gòu)造哈夫曼樹 ---
// w 存放 n 個權(quán)值，構(gòu)造哈夫曼樹 HT
void CreateHuffmanTree(HuffmanTree *HT, int *w, int n) {
? ? if (n <= 1) return;
? ? int m = 2 * n - 1; // 哈夫曼樹總結(jié)點數(shù)
? ? *HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); // 0號單元未用，分配 m+1 個空間
? ? if (!*HT) {
? ? ? ? fprintf(stderr, "內(nèi)存分配失敗!\n");
? ? ? ? exit(EXIT_FAILURE);
? ? }
? ? // 初始化所有結(jié)點的雙親、左右孩子下標為0
? ? for (int i = 1; i <= m; i++) {
? ? ? ? (*HT)[i].parent = 0;
? ? ? ? (*HT)[i].lchild = 0;
? ? ? ? (*HT)[i].rchild = 0;
? ? }
? ? // 輸入前 n 個結(jié)點的權(quán)值
? ? for (int i = 1; i <= n; i++) {
? ? ? ? (*HT)[i].weight = w[i - 1]; // w數(shù)組從0開始，HT從1開始
? ? }
? ? // --- 開始創(chuàng)建哈夫曼樹 ---
? ? printf("\n--- 構(gòu)造哈夫曼樹過程 ---\n");
? ? for (int i = n + 1; i <= m; i++) {
? ? ? ? int s1, s2;
? ? ? ? // 在 HT[1...i-1] 中選擇兩個權(quán)值最小的結(jié)點
? ? ? ? Select(*HT, i - 1, &s1, &s2);
? ? ? ? printf("第 %2d 次合并: 選擇權(quán)值 %d (結(jié)點%d) 和 %d (結(jié)點%d)\n", i - n, (*HT)[s1].weight, s1, (*HT)[s2].weight, s2);
? ? ? ? // 將新結(jié)點 i 的雙親設為 s1, s2
? ? ? ? (*HT)[s1].parent = i;
? ? ? ? (*HT)[s2].parent = i;
? ? ? ? // s1, s2 分別作為 i 的左右孩子
? ? ? ? (*HT)[i].lchild = s1;
? ? ? ? (*HT)[i].rchild = s2;
? ? ? ? // i 的權(quán)值為 s1, s2 權(quán)值之和
? ? ? ? (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
? ? }
? ? printf("--- 哈夫曼樹構(gòu)造完成 ---\n\n");
}
// --- 4. 核心函數(shù)：生成哈夫曼編碼 ---
// 從哈夫曼樹 HT 反向生成哈夫曼編碼 HC
void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n) {
? ? *HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); // 分配 n 個字符編碼的頭指針
? ? if (!*HC) {
? ? ? ? fprintf(stderr, "內(nèi)存分配失敗!\n");
? ? ? ? exit(EXIT_FAILURE);
? ? }
? ?
? ? char *cd = (char *)malloc(n * sizeof(char)); // 分配臨時存放編碼的動態(tài)數(shù)組
? ? if (!cd) {
? ? ? ? fprintf(stderr, "內(nèi)存分配失敗!\n");
? ? ? ? exit(EXIT_FAILURE);
? ? }
? ? cd[n - 1] = '\0'; // 編碼結(jié)束符
? ? // 逐個字符求哈夫曼編碼
? ? for (int i = 1; i <= n; i++) {
? ? ? ? int start = n - 1; // start 指向編碼結(jié)束符
? ? ? ? int c = i;
? ? ? ? int f = HT[c].parent;
? ? ? ? // 從葉子結(jié)點開始向上回溯，直到根結(jié)點
? ? ? ? while (f != 0) {
? ? ? ? ? ? --start; // 回溯一次，start向前指一個位置
? ? ? ? ? ? if (HT[f].lchild == c) {
? ? ? ? ? ? ? ? cd[start] = '0'; // 結(jié)點c是f的左孩子，則生成代碼'0'
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? cd[start] = '1'; // 結(jié)點c是f的右孩子，則生成代碼'1'
? ? ? ? ? ? }
? ? ? ? ? ? c = f;
? ? ? ? ? ? f = HT[f].parent; // 繼續(xù)向上回溯
? ? ? ? }
? ? ? ? // 為第 i 個字符編碼分配空間
? ? ? ? (*HC)[i] = (char *)malloc((n - start) * sizeof(char));
? ? ? ? if (!(*HC)[i]) {
? ? ? ? ? ? fprintf(stderr, "內(nèi)存分配失敗!\n");
? ? ? ? ? ? exit(EXIT_FAILURE);
? ? ? ? }
? ? ? ? // 將求得的編碼從臨時空間 cd 復制到 HC 的當前行
? ? ? ? strcpy((*HC)[i], &cd[start]);
? ? }
? ? free(cd); // 釋放臨時空間
}
// --- 5. 打印函數(shù) ---
void PrintHuffmanCode(HuffmanCode HC, int *w, int n) {
? ? printf("--- 哈夫曼編碼結(jié)果 ---\n");
? ? printf("權(quán)值\t編碼\n");
? ? printf("--------------------\n");
? ? for (int i = 1; i <= n; i++) {
? ? ? ? printf("%d\t%s\n", w[i - 1], HC[i]);
? ? }
? ? printf("--------------------\n");
}
// --- 6. 主函數(shù) ---
int main() {
? ? int n = 8;
? ? int w[] = {5, 29, 7, 8, 14, 23, 3, 11}; // 【例5.2】的權(quán)值
? ? HuffmanTree HT = NULL;
? ? HuffmanCode HC = NULL;
? ? // 1. 構(gòu)造哈夫曼樹
? ? CreateHuffmanTree(&HT, w, n);
? ? // 2. 生成哈夫曼編碼
? ? HuffmanCoding(HT, &HC, n);
? ? // 3. 打印編碼結(jié)果
? ? PrintHuffmanCode(HC, w, n);
? ? // 4. 釋放內(nèi)存
? ? for (int i = 1; i <= n; i++) {
? ? ? ? free(HC[i]);
? ? }
? ? free(HC);
? ? free(HT);
? ? return 0;
}
