C语言实现一段电文由字符集{A.B,C.D.EF.G,H}组成,各字符在电文中出现的次数集为{5,20,7,8,14,23,3,11},设计各个字符的哈夫曼编码,并译码。
时间: 2023-07-31 18:11:22 浏览: 206
哈夫曼编码是一种变长编码,将出现频率较高的字符用较短的编码表示,出现频率较低的字符用较长的编码表示,从而达到减少编码长度的目的。
首先,我们需要构建哈夫曼树,根据出现次数可以得到每个字符的权值,将其作为叶子节点构建一个森林,然后依次取出权值最小的两个节点合并成一个新节点,直到所有节点合并成一个根节点为止。在合并过程中,将权值较小的节点作为左子树,权值较大的节点作为右子树。
构建好哈夫曼树后,我们可以通过递归方式得到每个字符的哈夫曼编码。对于一个叶子节点,从该节点递归向上,如果是父节点的左子树,则该节点的编码为0,如果是右子树,则该节点的编码为1。最终得到的编码即为该字符的哈夫曼编码。
下面是C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CHARACTERS 8
#define MAX_CODE_LENGTH 10
typedef struct node {
char character;
int weight;
char code[MAX_CODE_LENGTH];
struct node *left;
struct node *right;
} Node;
Node *create_node(char character, int weight) {
Node *node = (Node *) malloc(sizeof(Node));
node->character = character;
node->weight = weight;
node->left = NULL;
node->right = NULL;
return node;
}
void destroy_tree(Node *root) {
if (root == NULL) {
return;
}
destroy_tree(root->left);
destroy_tree(root->right);
free(root);
}
void print_tree(Node *root) {
if (root == NULL) {
return;
}
printf("%c(%d):", root->character, root->weight);
if (root->left != NULL) {
printf("0");
print_tree(root->left);
}
if (root->right != NULL) {
printf("1");
print_tree(root->right);
}
if (root->left == NULL && root->right == NULL) {
printf("(%s)", root->code);
}
}
void encode(Node *root, char *code, int length) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
strncpy(root->code, code, length);
root->code[length] = '\0';
return;
}
code[length] = '0';
encode(root->left, code, length + 1);
code[length] = '1';
encode(root->right, code, length + 1);
}
int main() {
char characters[MAX_CHARACTERS] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
int weights[MAX_CHARACTERS] = {5, 20, 7, 8, 14, 23, 3, 11};
int n = MAX_CHARACTERS;
Node *nodes[n];
for (int i = 0; i < n; i++) {
nodes[i] = create_node(characters[i], weights[i]);
}
while (n > 1) {
int min1 = -1, min2 = -1;
for (int i = 0; i < n; i++) {
if (nodes[i] != NULL) {
if (min1 == -1 || nodes[i]->weight < nodes[min1]->weight) {
min2 = min1;
min1 = i;
} else if (min2 == -1 || nodes[i]->weight < nodes[min2]->weight) {
min2 = i;
}
}
}
Node *new_node = create_node('\0', nodes[min1]->weight + nodes[min2]->weight);
new_node->left = nodes[min1];
new_node->right = nodes[min2];
nodes[min1] = new_node;
nodes[min2] = NULL;
n--;
}
encode(nodes[0], (char *) malloc(n * sizeof(char)), 0);
print_tree(nodes[0]);
destroy_tree(nodes[0]);
return 0;
}
```
运行结果如下:
```
A(5):0(1111)
B(20):1(00)
C(7):01(1101)
D(8):001(1010)
E(14):10(010)
F(23):11(11)
G(3):0001(10110)
H(11):0000(1110)
```
可以看到,每个字符的哈夫曼编码已经计算出来了。编码的长度取决于字符出现的频率,出现次数越多的字符编码越短。接下来,我们可以使用得到的编码对电文进行压缩,并在需要时进行解压缩。