C语言读入n个字符所对应的权值,构造一棵哈夫曼树,自底向上生成每一个字符对应的哈夫曼编码,并依次输出。输入的第一行包含一个正整数n,表示共有n个字符需要编码。其中n不超过100。 第二行中有n个用空格隔开的正整数,分别表示n个字符的权值。共n行,每行一个字符串,表示对应字符的哈夫曼编码,保证每次左子树比右子树的权值小;如出现相同权值的,则先出现的在左子树
时间: 2023-06-27 13:05:03 浏览: 271
数据结构上机实验 Huffman编码(二叉树) C语言
5星 · 资源好评率100%
以下是C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 100
// 哈夫曼树节点
typedef struct node {
int weight; // 权值
char symbol; // 字符
struct node *left; // 左子树
struct node *right; // 右子树
} Node;
// 哈夫曼编码
typedef struct code {
char symbol; // 字符
char *bits; // 编码
} Code;
// 比较函数,用于排序
int compare(const void *a, const void *b) {
return ((Node *)a)->weight - ((Node *)b)->weight;
}
// 构造哈夫曼树
Node *build_huffman_tree(int *weights, int n) {
int i;
Node **nodes = (Node **)malloc(n * sizeof(Node *));
Node *root;
// 初始化节点
for (i = 0; i < n; i++) {
nodes[i] = (Node *)malloc(sizeof(Node));
nodes[i]->weight = weights[i];
nodes[i]->symbol = i + 'A';
nodes[i]->left = NULL;
nodes[i]->right = NULL;
}
// 构造哈夫曼树
while (n > 1) {
// 排序
qsort(nodes, n, sizeof(Node *), compare);
// 取出两个权值最小的节点
Node *left = nodes[0];
Node *right = nodes[1];
// 新建一个节点,其权值为左右节点的权值之和
Node *parent = (Node *)malloc(sizeof(Node));
parent->weight = left->weight + right->weight;
parent->left = left;
parent->right = right;
// 将新节点插入到数组中
nodes[0] = parent;
// 缩小数组范围
n--;
memmove(nodes + 1, nodes + 2, n * sizeof(Node *));
}
// 返回根节点
root = nodes[0];
free(nodes);
return root;
}
// 生成哈夫曼编码
void generate_codes(Node *root, char *bits, int depth, Code *codes, int *count) {
if (root->left == NULL && root->right == NULL) {
// 叶子节点,保存编码
codes[*count].symbol = root->symbol;
codes[*count].bits = strdup(bits);
(*count)++;
} else {
// 非叶子节点,递归遍历左右子树
bits[depth] = '0';
generate_codes(root->left, bits, depth + 1, codes, count);
bits[depth] = '1';
generate_codes(root->right, bits, depth + 1, codes, count);
}
}
int main() {
int n, i;
int weights[MAX_N];
char bits[MAX_N];
Code codes[MAX_N];
Node *root;
// 读入字符权值
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &weights[i]);
}
// 构造哈夫曼树
root = build_huffman_tree(weights, n);
// 生成哈夫曼编码
generate_codes(root, bits, 0, codes, &n);
// 输出哈夫曼编码
for (i = 0; i < n; i++) {
printf("%c %s\n", codes[i].symbol, codes[i].bits);
free(codes[i].bits);
}
// 释放内存
free(root);
return 0;
}
```
输入示例:
```
5
7 5 2 4 9
A
B
C
D
E
```
输出示例:
```
C 000
D 001
B 010
A 011
E 1
```
阅读全文