用C语言实现(1)统计某电文中字符出现的频率(假设电文中只含有大小写英文字母,以及逗号和点号);(2)把字符出现的频率作为权值建立哈夫曼树,进行哈夫曼编码,并输出每个字符的编码结果;(3)对电文进行哈夫曼编码。(4)把电文的哈夫曼编码进行译码,输出对应电文的内容。
时间: 2023-07-19 20:28:05 浏览: 75
好的,我会根据您的要求进行回答。
首先,我需要说明一下:由于哈夫曼编码是一种动态编码,需要先统计字符出现的频率,再建立哈夫曼树,才能进行哈夫曼编码。因此,要实现这道题目,需要先完成字符频率统计和哈夫曼树的建立。
以下是一份可能的实现方案,供您参考:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义哈夫曼树节点
typedef struct huff_node {
char ch; // 储存字符
int freq; // 储存字符出现频率
struct huff_node *left; // 左子树指针
struct huff_node *right;// 右子树指针
} huff_node;
// 统计字符出现频率
void count_freq(char *str, int freq[]) {
int i;
for (i = 0; i < strlen(str); i++) {
if (str[i] >= 'a' && str[i] <= 'z') {
freq[str[i] - 'a']++;
} else if (str[i] >= 'A' && str[i] <= 'Z') {
freq[str[i] - 'A']++;
} else if (str[i] == ',' || str[i] == '.') {
freq[26]++;
}
}
}
// 创建哈夫曼树节点
huff_node *create_node(char ch, int freq) {
huff_node *node = (huff_node *)malloc(sizeof(huff_node));
node->ch = ch;
node->freq = freq;
node->left = NULL;
node->right = NULL;
return node;
}
// 从小到大排序
void sort(huff_node **nodes, int n) {
int i, j;
huff_node *temp;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (nodes[j]->freq > nodes[j + 1]->freq) {
temp = nodes[j];
nodes[j] = nodes[j + 1];
nodes[j + 1] = temp;
}
}
}
}
// 建立哈夫曼树
huff_node *build_huff_tree(int freq[]) {
int i, n = 0;
huff_node *nodes[28];
for (i = 0; i < 26; i++) {
if (freq[i] > 0) {
nodes[n] = create_node(i + 'a', freq[i]);
n++;
}
}
if (freq[26] > 0) {
nodes[n] = create_node(',', freq[26]);
n++;
}
if (freq[27] > 0) {
nodes[n] = create_node('.', freq[27]);
n++;
}
while (n > 1) {
sort(nodes, n);
huff_node *temp = create_node('\0', nodes[0]->freq + nodes[1]->freq);
temp->left = nodes[0];
temp->right = nodes[1];
nodes[0] = temp;
for (i = 2; i < n; i++) {
nodes[i - 1] = nodes[i];
}
n--;
}
return nodes[0];
}
// 输出哈夫曼编码
void print_huff_code(huff_node *root, char code[], int len) {
if (root->left == NULL && root->right == NULL) {
printf("%c: ", root->ch);
int i;
for (i = 0; i < len; i++) {
printf("%c", code[i]);
}
printf("\n");
} else {
code[len] = '0';
print_huff_code(root->left, code, len + 1);
code[len] = '1';
print_huff_code(root->right, code, len + 1);
}
}
// 哈夫曼编码
void huff_encode(huff_node *root, char *str, char *code[]) {
int i, j, len;
for (i = 0; i < strlen(str); i++) {
huff_node *node = root;
len = 0;
while (node->left != NULL && node->right != NULL) {
if (str[i] >= 'a' && str[i] <= 'z') {
node = (str[i] - 'a' == node->left->ch - 'a') ? node->left : node->right;
} else if (str[i] >= 'A' && str[i] <= 'Z') {
node = (str[i] - 'A' == node->left->ch - 'a') ? node->left : node->right;
} else if (str[i] == ',') {
node = (26 == node->left->ch - 'a') ? node->left : node->right;
} else if (str[i] == '.') {
node = (27 == node->left->ch - 'a') ? node->left : node->right;
}
code[i][len] = (node == node->left) ? '0' : '1';
len++;
}
code[i][len] = '\0';
}
}
// 哈夫曼译码
void huff_decode(huff_node *root, char *code[], int n) {
int i, j;
huff_node *node;
for (i = 0; i < n; i++) {
node = root;
for (j = 0; j < strlen(code[i]); j++) {
if (code[i][j] == '0') {
node = node->left;
} else {
node = node->right;
}
}
printf("%c", node->ch);
}
printf("\n");
}
int main() {
char str[1000];
int freq[28] = {0};
printf("请输入电文:\n");
scanf("%[^\n]", str);
getchar(); // 读取换行符
count_freq(str, freq);
huff_node *root = build_huff_tree(freq);
char code[1000][100] = {0};
printf("各字符编码如下:\n");
print_huff_code(root, code[0], 0);
huff_encode(root, str, code);
printf("编码后电文为:\n");
int i;
for (i = 0; i < strlen(str); i++) {
printf("%s", code[i]);
}
printf("\n");
printf("译码后电文为:\n");
huff_decode(root, code, strlen(str));
return 0;
}
```
以上代码实现了:
1. 统计给定电文中每个字符出现的频率;
2. 建立哈夫曼树,并输出每个字符的哈夫曼编码;
3. 对电文进行哈夫曼编码;
4. 对哈夫曼编码进行译码,并输出原电文。
请注意,以上代码并不是唯一的实现方案,也不一定是最优的实现方案。不同的编写习惯和实现思路,可能会导致代码的不同。
阅读全文