哈夫曼编码树

#include <stdio.h> #include <stdlib.h> #include <string.h> int w[100]; // 存放每个叶子结点的权值 char m[100]; // 存放待编码的字符 int n; // 叶子结点个数 // 哈夫曼树结点结构体 typedef struct Node { int weight; // 权值 int fa; // 父结点下标，-1表示无父结点（即当前为根） int l, r; // 左右孩子下标，-1表示无孩子 } HuffmanTree; /** * 在 tree[0] ~ tree[x] 范围内，选出两个父结点为 -1 且权值最小的结点 * s1 存放最小权值结点的下标，s2 存放次小权值结点的下标 */ void find(HuffmanTree* tree, int x, int* s1, int* s2) { int minn = 0; // 找第一个未使用的结点作为起始基准 for (int i = 0; i <= x; ++i) { if (tree[i].fa == -1) { minn = i; break; } } // 选出当前范围内权值最小的未使用结点 for (int i = 0; i <= x; ++i) { if (tree[i].fa == -1 && tree[i].weight < tree[minn].weight) { minn = i; // 更新最小值下标 } } *s1 = minn; // 最小结点下标存入 s1 // 找第二个未使用的结点（排除已选的 s1） for (int i = 0; i <= x; ++i) { if (tree[i].fa == -1 && i != (*s1)) { minn = i; break; } } // 选出除 s1 外权值最小的未使用结点 for (int i = 0; i <= x; ++i) { if (tree[i].fa == -1 && tree[i].weight < tree[minn].weight && i != (*s1)) { minn = i; } } *s2 = minn; // 次小结点下标存入 s2 } /** * 根据权值数组 w 构造哈夫曼树 * n: 叶子结点个数 * 返回包含 2*n-1 个结点的哈夫曼树数组 */ HuffmanTree* CreatHuffmanTree(int w[], int n) { int sum = 2 * n - 1; // 哈夫曼树总结点数 HuffmanTree* tree = (HuffmanTree*)malloc(sizeof(HuffmanTree) * sum); // 初始化前 n 个叶子结点（每个都是独立的根） for (int i = 0; i < n; ++i) { tree[i].weight = w[i]; tree[i].fa = -1; tree[i].l = tree[i].r = -1; } int s1, s2; // 逐次合并两个权值最小的树，产生 n-1 个内部结点 for (int i = n; i < sum; ++i) { find(tree, i - 1, &s1, &s2); // 在当前可用的树中找权值最小的两棵 tree[i].weight = tree[s1].weight + tree[s2].weight; // 新结点权值为子结点权值之和 tree[i].fa = -1; // 新结点暂时没有父结点 tree[i].l = s1; // 左孩子 tree[i].r = s2; // 右孩子 tree[s1].fa = i; // 更新左孩子的父结点 tree[s2].fa = i; // 更新右孩子的父结点 } return tree; } /** * 根据哈夫曼树生成 n 个叶子结点的编码 * 编码规则：左分支为 '1'，右分支为 '0' （也可反过来，不影响压缩本质） * 返回字符串数组，每个元素是叶子结点对应的编码 */ char** Creatcode(HuffmanTree* tree, int n) { // temp 用于暂存一个叶子结点的编码（从后向前填充） char* temp = (char*)malloc(sizeof(char) * n); // codes 是二维数组，存放所有字符的编码 char** codes = (char**)malloc(sizeof(char*) * n); memset(codes, 0, sizeof(char*) * n); // 初始化为空指针 for (int i = 0; i < n; ++i) { int p = i; // 当前结点，从叶子开始 int pre = 0; // 父结点下标 int t = n - 1; // temp 数组末尾位置 temp[t] = '\0'; // 字符串结束符 pre = tree[p].fa; // 获取叶子的父结点 // 自底向上走到根结点（根结点的 fa == -1） while (pre != -1) { t--; // 腾出位置存放新编码位 if (tree[pre].l == p) { temp[t] = '1'; // 是左孩子，编码记为 1 } else { temp[t] = '0'; // 是右孩子，编码记为 0 } p = pre; // 移向父结点 pre = tree[p].fa; // 更新 pre 为更高层的父结点 } // 为编码字符串分配刚好够用的内存，并复制过去 codes[i] = (char*)malloc(sizeof(char) * (n - t)); strcpy(codes[i], &temp[t]); } free(temp); // 释放临时数组 temp = NULL; return codes; } int main() { // 输入叶子结点个数 scanf("%d", &n); getchar(); // 吸收换行符 // 输入每个叶子对应字符（连续输入，可带空格） for (int i = 0; i < n; ++i) { scanf("%c", &m[i]); } // 输入每个字符的权值（整数） for (int i = 0; i < n; ++i) { scanf("%d", &w[i]); } // 构造哈夫曼树 HuffmanTree* Tree = CreatHuffmanTree(w, n); // 生成哈夫曼编码 char** codes = Creatcode(Tree, n); // 输出每个字符及其对应编码 for (int i = 0; i < n; i++) { printf("%c:%s\n", m[i], codes[i]); } return 0; }