哈夫曼编码树

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