编写构造哈夫曼树和求哈夫曼编码的算法
时间: 2023-07-19 19:18:48 浏览: 143
构建哈夫曼树和编码
好的,下面是构造哈夫曼树和求哈夫曼编码的算法。
构造哈夫曼树算法:
1. 初始化一个权值数组 `w[]`,其中 `w[i]` 表示第 `i` 个叶子节点的权值。
2. 创建一个哈夫曼树森林,即将每个叶子节点看作是一个单独的树。
3. 从哈夫曼树森林中选取两个根节点权值最小的树,合并成一棵新的树,根节点的权值为两个子树根节点权值之和。
4. 将新的树插入哈夫曼树森林中,并删除原来的两棵树。
5. 重复步骤3和步骤4,直到哈夫曼树森林中只剩下一棵树,即为哈夫曼树。
下面是求哈夫曼编码的算法:
1. 对于哈夫曼树中每个叶子节点,将其从叶子节点向上遍历到根节点的路径上的所有边进行编号,规定左孩子为0,右孩子为1,得到该叶子节点的哈夫曼编码。
2. 对于哈夫曼树中的每个叶子节点,将其权值和哈夫曼编码存储在一个编码表中。
下面是 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEN 100 // 最大编码长度
typedef struct {
int weight; // 权值
int parent, lchild, rchild; // 双亲和左右孩子指针
} HTNode, *HuffmanTree;
typedef char *HuffmanCode[MAXLEN]; // 动态数组存储哈夫曼编码
// 选择权值最小的两个节点
void Select(HuffmanTree HT, int n, int *s1, int *s2) {
int i, min1, min2;
min1 = min2 = 0;
for (i = 1; i <= n; i++) {
if (HT[i].parent == 0) {
if (HT[i].weight < HT[min1].weight) {
min2 = min1;
min1 = i;
} else if (HT[i].weight < HT[min2].weight) {
min2 = i;
}
}
}
*s1 = min1;
*s2 = min2;
}
// 构造哈夫曼树
void CreateHuffmanTree(HuffmanTree *HT, int n) {
int i, s1, s2;
if (n <= 1) {
return;
}
int m = 2 * n - 1;
*HT = (HuffmanTree) malloc((m + 1) * sizeof(HTNode)); // 分配空间
for (i = 1; i <= m; i++) { // 初始化
(*HT)[i].parent = (*HT)[i].lchild = (*HT)[i].rchild = 0;
(*HT)[i].weight = 0;
}
for (i = 1; i <= n; i++) { // 输入权值
scanf("%d", &(*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 HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n) {
char *cd = (char *) malloc(n * sizeof(char)); // 暂存编码
cd[n-1] = '\0';
int i, c, p;
for (i = 1; i <= n; i++) { // 逐个叶子节点求哈夫曼编码
int start = n - 1;
for (c = i, p = HT[i].parent; p != 0; c = p, p = HT[p].parent) {
if (HT[p].lchild == c) {
cd[--start] = '0';
} else {
cd[--start] = '1';
}
}
HC[i-1] = (char *) malloc((n - start) * sizeof(char));
strcpy(HC[i-1], &cd[start]); // 复制编码
}
free(cd); // 释放空间
}
int main() {
int n, i;
printf("请输入叶子节点的个数:");
scanf("%d", &n);
HuffmanTree HT;
HuffmanCode HC;
CreateHuffmanTree(&HT, n);
HuffmanCoding(HT, HC, n);
printf("哈夫曼编码如下:\n");
for (i = 0; i < n; i++) {
printf("%d: %s\n", i+1, HC[i]);
}
free(HT);
for (i = 0; i < n; i++) {
free(HC[i]);
}
return 0;
}
```
输入格式:
第一行输入叶子节点的个数 `n`。
接下来一行输入 `n` 个整数,表示每个叶子节点的权值。
输出格式:
输出每个叶子节点的哈夫曼编码。
希望对您有所帮助!
阅读全文