哈夫曼树代码

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

通过画图更好理解代码