哈夫曼树的实现

HuffmanTree.h#ifndef HUFFMAN_TREE_H #define HUFFMAN_TREE_H /* Huffman树通过待编码的节点数量计算出总共的节点个数 m 2*n -1个 * 用数组0的单元表示无效节点从1号单元开始进行填充那么申请2*n个空间 */ typedef struct { int weight; // 节点的权值 int parent; // 该节点的父节点编号0值表示该节点就是根 int lChild, rChild; // 指向该节点的左右孩子节点的编号 } HuffmanNode, *HuffmanTree; HuffmanTree createHuffmanTree(const int *w, int n); void releaseHuffmanTree(HuffmanTree tree); /* Huffman编码用一个字符数组空间来保存每个符号的编码字符串 * char *codes[n]; HuffmanCode codes[n]; */ typedef char *HuffmanCode; HuffmanCode *createHuffmanCodes(HuffmanTree tree, int n); void releaseHuffmanCodes(HuffmanCode *codes, int n); #endif //HUFFMAN_TREE_HHuffmanTree.c#include stdio.h #include stdlib.h #include string.h #include HuffmanTree.h static void selectTwoMin(HuffmanTree tree, int n, int *s1, int *s2) { *s1 *s2 0; for (int i 1; i n; i) { if (tree[i].parent 0) { if (*s1 0) { *s1 i; } else if (*s2 0) { *s2 i; if (tree[*s1].weight tree[*s2].weight) { int t *s1; *s1 *s2; *s2 t; } } else { // 比较权值大小更新最小的2个节点下标 if (tree[i].weight tree[*s1].weight) { *s2 *s1; *s1 i; } else if (tree[i].weight tree[*s2].weight) { *s2 i; } } } } } HuffmanTree createHuffmanTree(const int *w, int n) { int m 2*n - 1; // 1. 申请2n个空间预留一个0号位置 HuffmanTree tree malloc(sizeof(HuffmanNode) * (m 1)); if (tree NULL) { return NULL; } // 2.1 初始化1 ~ 2n - 1个节点 for (int i 1; i m; i) { tree[i].parent tree[i].lChild tree[i].rChild 0; tree[i].weight 0; } // 2.2 初始化权值 1 ~ n for (int i 1; i n; i) { tree[i].weight w[i - 1]; } // 初始化结束开始构建HuffmanTree // 填充从n1下标到m下标的空间 int s1, s2; // 没有parent约束的两个最小的权值 for (int i n 1; i m; i) { // 在[1...i-1]范围内父节点为0权值最小的两个 selectTwoMin(tree, i - 1, s1, s2); // 将这2个权值最小的节点组合到第i个位置 tree[s1].parent tree[s2].parent i; tree[i].lChild s1; tree[i].rChild s2; tree[i].weight tree[s1].weight tree[s2].weight; } return tree; } void releaseHuffmanTree(HuffmanTree tree) { if (tree) { free(tree); } } // 从n个叶子节点找到根节点逆向求每个叶子的对应的编码 HuffmanCode* createHuffmanCodes(HuffmanTree tree, int n) { // 申请了一个数组空间每个元素都保存一个地址这个地址指向了对应元素的编码结果 HuffmanCode* codes malloc(sizeof(HuffmanCode) * n); if (codes NULL) { return NULL; } memset(codes, 0, sizeof(HuffmanCode) * n); // 生成每个符号对应的编码结果 // n个节点树的高度最大为n而HuffmanTree要低于任意树的最大值 char *temp malloc(sizeof(char) * (n 1)); for (int i 1; i n; i) { int start n - 1; // 标识temp空间的编码起始位置从后往前编码,编码临时结果从后往前 temp[start] \0; int pos i; // 当前正在编码的位置 int p tree[i].parent; // 存放当前节点的父节点信息 while (p) { --start; temp[start] (tree[p].lChild pos) ? 0 : 1; pos p; p tree[p].parent; } // 将第i个字符编码进行填充 codes[i - 1] malloc(sizeof(char) * (n - start)); strcpy(codes[i - 1], temp[start]); } free(temp); return codes; } void releaseHuffmanCodes(HuffmanCode*codes, int n) { if (codes) { for (int i 0; i n; i) { if (codes[i]) { free(codes[i]); } } free(codes); } }