请用C语言编程实现哈夫曼树的构造,以及对该哈夫曼树的编码。
时间: 2024-03-29 16:13:21 浏览: 38
哈夫曼树的构造:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 1000
// 哈夫曼树节点
typedef struct node {
int weight; // 权重
int parent, lchild, rchild; // 父节点,左孩子,右孩子的下标
} Node;
// 构造哈夫曼树
void huffman(Node *nodes, int n) {
// 初始化
for (int i = 0; i < n * 2 - 1; i++) {
nodes[i].parent = nodes[i].lchild = nodes[i].rchild = -1;
}
// 构造哈夫曼树
for (int i = n; i < n * 2 - 1; i++) {
int min1 = -1, min2 = -1;
for (int j = 0; j < i; j++) {
if (nodes[j].parent == -1) {
if (min1 == -1 || nodes[j].weight < nodes[min1].weight) {
min2 = min1;
min1 = j;
} else if (min2 == -1 || nodes[j].weight < nodes[min2].weight) {
min2 = j;
}
}
}
nodes[min1].parent = i;
nodes[min2].parent = i;
nodes[i].lchild = min1;
nodes[i].rchild = min2;
nodes[i].weight = nodes[min1].weight + nodes[min2].weight;
}
}
int main() {
Node nodes[MAX_N];
int n;
// 输入节点个数和各个节点的权重
printf("Please input the number of nodes: ");
scanf("%d", &n);
printf("Please input the weight of each node: ");
for (int i = 0; i < n; i++) {
scanf("%d", &nodes[i].weight);
}
// 构造哈夫曼树
huffman(nodes, n);
// 输出哈夫曼树
printf("The Huffman tree:\n");
for (int i = 0; i < n * 2 - 1; i++) {
printf("Node %d: weight=%d, parent=%d, lchild=%d, rchild=%d\n",
i, nodes[i].weight, nodes[i].parent, nodes[i].lchild, nodes[i].rchild);
}
return 0;
}
```
对哈夫曼树的编码:
```c
// 哈夫曼编码
void huffman_encoding(Node *nodes, int n, char **codes) {
// 初始化编码
for (int i = 0; i < n; i++) {
codes[i] = (char *)malloc(sizeof(char) * n);
codes[i][0] = '\0';
}
// 从叶子节点向根节点递归,计算编码
for (int i = 0; i < n; i++) {
int j = i;
while (nodes[j].parent != -1) {
int parent = nodes[j].parent;
if (nodes[parent].lchild == j) {
strcat(codes[i], "0");
} else {
strcat(codes[i], "1");
}
j = parent;
}
// 反转编码
int len = strlen(codes[i]);
for (int k = 0; k < len / 2; k++) {
char temp = codes[i][k];
codes[i][k] = codes[i][len - k - 1];
codes[i][len - k - 1] = temp;
}
}
}
int main() {
Node nodes[MAX_N];
char *codes[MAX_N];
int n;
// 输入节点个数和各个节点的权重
printf("Please input the number of nodes: ");
scanf("%d", &n);
printf("Please input the weight of each node: ");
for (int i = 0; i < n; i++) {
scanf("%d", &nodes[i].weight);
}
// 构造哈夫曼树
huffman(nodes, n);
// 哈夫曼编码
huffman_encoding(nodes, n, codes);
// 输出编码
printf("The Huffman code:\n");
for (int i = 0; i < n; i++) {
printf("Node %d: weight=%d, code=%s\n", i, nodes[i].weight, codes[i]);
}
// 释放空间
for (int i = 0; i < n; i++) {
free(codes[i]);
}
return 0;
}
```