HuffmanTree.h#ifndef HUFFMAN_TREE_H #define HUFFMAN_TREE_H /* Huffman樹通過待編碼的節(jié)點(diǎn)數(shù)量計(jì)算出總共的節(jié)點(diǎn)個(gè)數(shù) m 2*n -1個(gè) * 用數(shù)組0的單元表示無效節(jié)點(diǎn)從1號單元開始進(jìn)行填充那么申請2*n個(gè)空間 */ typedef struct { int weight; // 節(jié)點(diǎn)的權(quán)值 int parent; // 該節(jié)點(diǎn)的父節(jié)點(diǎn)編號0值表示該節(jié)點(diǎn)就是根 int lChild, rChild; // 指向該節(jié)點(diǎn)的左右孩子節(jié)點(diǎn)的編號 } HuffmanNode, *HuffmanTree; HuffmanTree createHuffmanTree(const int *w, int n); void releaseHuffmanTree(HuffmanTree tree); /* Huffman編碼用一個(gè)字符數(shù)組空間來保存每個(gè)符號的編碼字符串 * 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 { // 比較權(quán)值大小更新最小的2個(gè)節(jié)點(diǎn)下標(biāo) 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個(gè)空間預(yù)留一個(gè)0號位置 HuffmanTree tree malloc(sizeof(HuffmanNode) * (m 1)); if (tree NULL) { return NULL; } // 2.1 初始化1 ~ 2n - 1個(gè)節(jié)點(diǎn) for (int i 1; i m; i) { tree[i].parent tree[i].lChild tree[i].rChild 0; tree[i].weight 0; } // 2.2 初始化權(quán)值 1 ~ n for (int i 1; i n; i) { tree[i].weight w[i - 1]; } // 初始化結(jié)束開始構(gòu)建HuffmanTree // 填充從n1下標(biāo)到m下標(biāo)的空間 int s1, s2; // 沒有parent約束的兩個(gè)最小的權(quán)值 for (int i n 1; i m; i) { // 在[1...i-1]范圍內(nèi)父節(jié)點(diǎn)為0權(quán)值最小的兩個(gè) selectTwoMin(tree, i - 1, s1, s2); // 將這2個(gè)權(quán)值最小的節(jié)點(diǎn)組合到第i個(gè)位置 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個(gè)葉子節(jié)點(diǎn)找到根節(jié)點(diǎn)逆向求每個(gè)葉子的對應(yīng)的編碼 HuffmanCode* createHuffmanCodes(HuffmanTree tree, int n) { // 申請了一個(gè)數(shù)組空間每個(gè)元素都保存一個(gè)地址這個(gè)地址指向了對應(yīng)元素的編碼結(jié)果 HuffmanCode* codes malloc(sizeof(HuffmanCode) * n); if (codes NULL) { return NULL; } memset(codes, 0, sizeof(HuffmanCode) * n); // 生成每個(gè)符號對應(yīng)的編碼結(jié)果 // n個(gè)節(jié)點(diǎn)樹的高度最大為n而HuffmanTree要低于任意樹的最大值 char *temp malloc(sizeof(char) * (n 1)); for (int i 1; i n; i) { int start n - 1; // 標(biāo)識(shí)temp空間的編碼起始位置從后往前編碼,編碼臨時(shí)結(jié)果從后往前 temp[start] \0; int pos i; // 當(dāng)前正在編碼的位置 int p tree[i].parent; // 存放當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)信息 while (p) { --start; temp[start] (tree[p].lChild pos) ? 0 : 1; pos p; p tree[p].parent; } // 將第i個(gè)字符編碼進(jìn)行填充 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); } }