文化传媒有限公司 网站建设,wordpress模板 图片站,做属于公司的网站有什么好处,织梦网站新闻列表调用### 思路 1. **选择最小权值节点**#xff1a;在哈夫曼树构建过程中#xff0c;选择两个权值最小且父节点为0的节点。 2. **构建哈夫曼树**#xff1a;根据权值构建哈夫曼树#xff0c;确保左子树权值小于右子树权值。 3. **生成哈夫曼编码**#xff1a;从叶子节点到根节点…
### 思路 1. **选择最小权值节点**在哈夫曼树构建过程中选择两个权值最小且父节点为0的节点。 2. **构建哈夫曼树**根据权值构建哈夫曼树确保左子树权值小于右子树权值。 3. **生成哈夫曼编码**从叶子节点到根节点逆向生成每个字符的哈夫曼编码。
### 伪代码 1. **选择最小权值节点** - 遍历节点找到两个权值最小且父节点为0的节点。 2. **构建哈夫曼树** - 初始化哈夫曼树节点。 - 输入值。 - 迭代构建哈夫曼树选择两个最小权值节点更新父节点和子节点信息。 3. **生成哈夫曼编码** - 从叶子节点到根节点逆向生成编码存储在编码数组中。
### C代码
#include stdio.h
#include string.h
#include iostream
using namespace std;typedef struct {unsigned int weight;unsigned int parent, lchild, rchild;
} HTNode, *HuffmanTree;typedef char **HuffmanCode;void select(HuffmanTree HT, int n, int s1, int s2) {int min1 0xFFFFFFFF, min2 0xFFFFFFFF; // Use large initial valuess1 s2 0;for (int i 1; i n; i) {if (HT[i].parent 0) {if (HT[i].weight min1) {min2 min1;s2 s1;min1 HT[i].weight;s1 i;} else if (HT[i].weight min2) {min2 HT[i].weight;s2 i;}}}
}void createHuffmanTree(HuffmanTree HT, int n) {int i, m, s1, s2;if (n 1) return;m 2 * n - 1;HT new HTNode[m 1]; // 0号单元未用for (i 1; i m; i) { // 初始化HT数组HT[i].parent 0;HT[i].lchild 0;HT[i].rchild 0;}for (i 1; i n; i)cin HT[i].weight;for (i n 1; i m; i) { // 建哈夫曼树select(HT, i - 1, s1, s2);HT[s1].parent i;HT[s2].parent i;HT[i].lchild s1;HT[i].rchild s2;HT[i].weight HT[s1].weight HT[s2].weight;}
}void createHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n) {char *cd new char[n]; // 分配求编码的工作空间cd[n - 1] \0; // 编码结束符。int i, c, f, start;for (i 1; i n; i) {start n - 1;c i, f HT[i].parent;while (f) { // 从叶子到根逆向求编码--start;if (HT[f].lchild c) cd[start] 0;else cd[start] 1;c f, f HT[f].parent;}HC[i] new char[n - start]; // 为第i个字符编码分配空间strcpy(HC[i], cd[start]); // 从cd复制编码(串)到HC}delete[] cd;
}int main() {int i, n;HuffmanTree HT;HuffmanCode HC;scanf(%d, n); // 权值个数HC new char*[n 1]; // 0空间未用createHuffmanTree(HT, n);createHuffmanCode(HT, HC, n);for (i 1; i n; i)printf(%s\n, HC[i]); // 输出哈夫曼编码for (i 1; i n; i)delete[] HC[i];delete[] HC;delete[] HT;return 0;
}
### 总结 1. **选择最小权值节点**通过遍历找到两个值最小且父节点为0的节点。 2. **构建哈夫曼树**始化节点输入权值迭代构建哈夫曼树。 3. **生成哈夫曼编码**从叶子节点到根节点逆向生成编码存储在编码数组中。
