#include stdio.h #include stdlib.h // 修正使用标准库头文件替换malloc.h #define MAX_CODE_LENGTH 100 // 新增定义最大编码长度 #define INT_MAX 9999 typedef struct HuffmanNode { char character; int parent; int direction; // 0-左子树/1-右子树 int weight; } HuffmanNode; // 初始化哈夫曼树 HuffmanNode* huffmanTreeInit(const char characters[], const int weights[], int num) { if (num 0) { printf(Error: Invalid number of characters!\n); return NULL; } const int totalNodes num * 2 - 1; HuffmanNode* tree (HuffmanNode*)malloc(sizeof(HuffmanNode) * totalNodes); if (!tree) { printf(Error: Memory allocation failed!\n); return NULL; } // 初始化叶子节点 for (int i 0; i num; i) { tree[i] (HuffmanNode){ .character characters[i], .weight weights[i], .parent -1, .direction -1 }; } // 初始化内部节点 for (int i num; i totalNodes; i) { tree[i] (HuffmanNode){ .character x, .weight -1, .parent -1, .direction -1 }; } return tree; } // 打印哈夫曼树 void huffmanTreePrint(const HuffmanNode* tree, int numLeaves) { const int totalNodes numLeaves * 2 - 1; printf(%-8s%-8s%-8s%-8s\n, Char, Parent, Dir, Weight); for (int i 0; i totalNodes; i) { printf(%-8c%-8d%-8d%-8d\n, tree[i].character, tree[i].parent, tree[i].direction, tree[i].weight); } } // 查找最小权重节点改进版 int findMinWeightIndex(const HuffmanNode* tree, int currentSize) { int minWeight INT_MAX; int minIndex -1; for (int i 0; i currentSize; i) { if (tree[i].parent -1 tree[i].weight minWeight tree[i].weight ! -1) { minWeight tree[i].weight; minIndex i; } } return minIndex; } // 构建哈夫曼树重构核心逻辑 void buildHuffmanTree(HuffmanNode* tree, int numLeaves) { if (!tree || numLeaves 1) return; int currentSize numLeaves; const int totalNodes numLeaves * 2 - 1; for (int pos numLeaves; pos totalNodes; pos) { // 查找两个最小节点 int min1 findMinWeightIndex(tree, currentSize); if (min1 -1) break; tree[min1].parent pos; tree[min1].direction 0; // 标记为左子树 int min2 findMinWeightIndex(tree, currentSize); if (min2 -1) break; tree[min2].parent pos; tree[min2].direction 1; // 标记为右子树 // 创建父节点 tree[pos].weight tree[min1].weight tree[min2].weight; tree[pos].parent -1; tree[pos].direction -1; currentSize; } } // 查找编码改进内存管理 void findEncoding(const HuffmanNode* tree, char target, int numLeaves) { int code[MAX_CODE_LENGTH] {0}; int codeLength 0; // 查找目标字符位置 int index -1; for (int i 0; i numLeaves; i) { if (tree[i].character target) { index i; break; } } if (index -1) { printf(Character %c not found!\n, target); return; } // 回溯生成编码 int current index; while (tree[current].parent ! -1) { code[codeLength] tree[current].direction; current tree[current].parent; } // 打印结果 printf(%c encoding: , target); for (int i codeLength-1; i 0; --i) { printf(%d, code[i]); } printf(\n); } // 测试用例改进变量管理 void huffmanTest() { const int numChars 5; const char chars[] {a, b, c, d, e}; const int weights[] {52, 8, 15, 23, 2}; printf(\n Huffman Tree Test \n); HuffmanNode* tree huffmanTreeInit(chars, weights, numChars); if (!tree) return; printf(\nInitial tree:\n); huffmanTreePrint(tree, numChars); buildHuffmanTree(tree, numChars); printf(\nAfter construction:\n); huffmanTreePrint(tree, numChars); printf(\nEncodings:\n); for (int i 0; i numChars; i) { findEncoding(tree, chars[i], numChars); } free(tree); } int main() { huffmanTest(); return 0; }通过画图更好理解代码
哈夫曼树代码
#include stdio.h #include stdlib.h // 修正使用标准库头文件替换malloc.h #define MAX_CODE_LENGTH 100 // 新增定义最大编码长度 #define INT_MAX 9999 typedef struct HuffmanNode { char character; int parent; int direction; // 0-左子树/1-右子树 int weight; } HuffmanNode; // 初始化哈夫曼树 HuffmanNode* huffmanTreeInit(const char characters[], const int weights[], int num) { if (num 0) { printf(Error: Invalid number of characters!\n); return NULL; } const int totalNodes num * 2 - 1; HuffmanNode* tree (HuffmanNode*)malloc(sizeof(HuffmanNode) * totalNodes); if (!tree) { printf(Error: Memory allocation failed!\n); return NULL; } // 初始化叶子节点 for (int i 0; i num; i) { tree[i] (HuffmanNode){ .character characters[i], .weight weights[i], .parent -1, .direction -1 }; } // 初始化内部节点 for (int i num; i totalNodes; i) { tree[i] (HuffmanNode){ .character x, .weight -1, .parent -1, .direction -1 }; } return tree; } // 打印哈夫曼树 void huffmanTreePrint(const HuffmanNode* tree, int numLeaves) { const int totalNodes numLeaves * 2 - 1; printf(%-8s%-8s%-8s%-8s\n, Char, Parent, Dir, Weight); for (int i 0; i totalNodes; i) { printf(%-8c%-8d%-8d%-8d\n, tree[i].character, tree[i].parent, tree[i].direction, tree[i].weight); } } // 查找最小权重节点改进版 int findMinWeightIndex(const HuffmanNode* tree, int currentSize) { int minWeight INT_MAX; int minIndex -1; for (int i 0; i currentSize; i) { if (tree[i].parent -1 tree[i].weight minWeight tree[i].weight ! -1) { minWeight tree[i].weight; minIndex i; } } return minIndex; } // 构建哈夫曼树重构核心逻辑 void buildHuffmanTree(HuffmanNode* tree, int numLeaves) { if (!tree || numLeaves 1) return; int currentSize numLeaves; const int totalNodes numLeaves * 2 - 1; for (int pos numLeaves; pos totalNodes; pos) { // 查找两个最小节点 int min1 findMinWeightIndex(tree, currentSize); if (min1 -1) break; tree[min1].parent pos; tree[min1].direction 0; // 标记为左子树 int min2 findMinWeightIndex(tree, currentSize); if (min2 -1) break; tree[min2].parent pos; tree[min2].direction 1; // 标记为右子树 // 创建父节点 tree[pos].weight tree[min1].weight tree[min2].weight; tree[pos].parent -1; tree[pos].direction -1; currentSize; } } // 查找编码改进内存管理 void findEncoding(const HuffmanNode* tree, char target, int numLeaves) { int code[MAX_CODE_LENGTH] {0}; int codeLength 0; // 查找目标字符位置 int index -1; for (int i 0; i numLeaves; i) { if (tree[i].character target) { index i; break; } } if (index -1) { printf(Character %c not found!\n, target); return; } // 回溯生成编码 int current index; while (tree[current].parent ! -1) { code[codeLength] tree[current].direction; current tree[current].parent; } // 打印结果 printf(%c encoding: , target); for (int i codeLength-1; i 0; --i) { printf(%d, code[i]); } printf(\n); } // 测试用例改进变量管理 void huffmanTest() { const int numChars 5; const char chars[] {a, b, c, d, e}; const int weights[] {52, 8, 15, 23, 2}; printf(\n Huffman Tree Test \n); HuffmanNode* tree huffmanTreeInit(chars, weights, numChars); if (!tree) return; printf(\nInitial tree:\n); huffmanTreePrint(tree, numChars); buildHuffmanTree(tree, numChars); printf(\nAfter construction:\n); huffmanTreePrint(tree, numChars); printf(\nEncodings:\n); for (int i 0; i numChars; i) { findEncoding(tree, chars[i], numChars); } free(tree); } int main() { huffmanTest(); return 0; }通过画图更好理解代码
