用c语言完成1、输入一段100—200字的英文短文,存入一文件a中。 2、写函数统计短文出现的字母个数n及每个字母的出现次数。 3、写函数以字母出现次数作权值,建Haffman树(n个叶子),给出每个字母的Haffman编码。 4、用每个字母编码对原短文进行编码,码文存入文件b中。 5、用Haffman树对b中码文进行译码,结果存入文件c中,比较a,c是否一致,以检验编码、译码的正确性。
时间: 2023-07-16 10:17:33 浏览: 143
哈夫曼树编码和译码,C语言实现
以下是用C语言完成上述任务的代码,其中假设输入的英文短文为纯小写字母```c
#include <stdio.h>
#include <stdlib>
#include <string.h>
#include <ctype.h>
#define MAX_CHAR 26
#define MAX_CODE_LEN 20
typedef struct node {
char ch;
int freq;
struct node *left, *right;
} Node;
typedef struct {
char ch;
char code[MAX_CODE_LEN];
} Code;
void count_chars(char *text, int *freq) {
int i;
for (i = 0; i < strlen(text); i++) {
if (islower(text[i])) {
freq[text[i] - 'a']++;
}
}
}
void build_huffman_tree(Node **nodes, int *freq) {
int i, j, min1_idx, min2_idx;
Node *min1, *min2, *new_node;
// 初始化节点数组
for (i = 0; i < MAX_CHAR; i++) {
nodes[i] = (Node *) malloc(sizeof(Node));
nodes[i]->ch = i + 'a';
nodes[i]->freq = freq[i];
nodes[i]->left = nodes[i]->right = NULL;
}
// 构建Huffman树
for (i = 0; i < MAX_CHAR - 1; i++) {
min1_idx = -1;
min2_idx = -1;
min1 = min2 = NULL;
for (j = 0; j < MAX_CHAR + i; j++) {
if (nodes[j] != NULL) {
if (min1 == NULL || nodes[j]->freq < min1->freq) {
min2 = min1;
min2_idx = min1_idx;
min1 = nodes[j];
min1_idx = j;
} else if (min2 == NULL || nodes[j]->freq < min2->freq) {
min2 = nodes[j];
min2_idx = j;
}
}
}
new_node = (Node *) malloc(sizeof(Node));
new_node->ch = '\0';
new_node->freq = min1->freq + min2->freq;
new_node->left = min1;
new_node->right = min2;
nodes[min1_idx] = new_node;
nodes[min2_idx] = NULL;
}
}
void generate_codes(Node *node, char *code, int len, Code *codes) {
if (node->left == NULL && node->right == NULL) {
codes[node->ch - 'a'].ch = node->ch;
strncpy(codes[node->ch - 'a'].code, code, len);
codes[node->ch - 'a'].code[len] = '\0';
} else {
code[len] = '0';
generate_codes(node->left, code, len + 1, codes);
code[len] = '1';
generate_codes(node->right, code, len + 1, codes);
}
}
void encode_text(char *text, Code *codes, char *encoded_text) {
int i, j, k;
for (i = 0; i < strlen(text); i++) {
if (islower(text[i])) {
for (j = 0; j < MAX_CHAR; j++) {
if (text[i] == codes[j].ch) {
for (k = 0; k < strlen(codes[j].code); k++) {
encoded_text[strlen(encoded_text)] = codes[j].code[k];
}
break;
}
}
}
}
}
void decode_text(char *encoded_text, Node *root, char *decoded_text) {
int i;
Node *node = root;
for (i = 0; i < strlen(encoded_text); i++) {
if (encoded_text[i] == '0') {
node = node->left;
} else {
node = node->right;
}
if (node->left == NULL && node->right == NULL) {
decoded_text[strlen(decoded_text)] = node->ch;
node = root;
}
}
}
int main() {
char text[201], encoded_text[10001], decoded_text[201];
int freq[MAX_CHAR] = {0};
Node *nodes[MAX_CHAR * 2 - 1], *root;
Code codes[MAX_CHAR];
FILE *fp;
// 读入短文
fp = fopen("a.txt", "r");
fgets(text, 201, fp);
fclose(fp);
// 统计字符频率
count_chars(text, freq);
// 建Huffman树
build_huffman_tree(nodes, freq);
root = nodes[MAX_CHAR * 2 - 2];
// 生成Huffman编码
generate_codes(root, codes, 0, codes);
// 编码短文
encode_text(text, codes, encoded_text);
// 将编码后的短文写入文件
fp = fopen("b.txt", "w");
fprintf(fp, "%s", encoded_text);
fclose(fp);
// 解码短文
decode_text(encoded_text, root, decoded_text);
// 将解码后的短文写入文件
fp = fopen("c.txt", "w");
fprintf(fp, "%s", decoded_text);
fclose(fp);
// 检验编码、译码的正确性
fp = fopen("a.txt", "r");
fgets(text, 201, fp);
fclose(fp);
fp = fopen("c.txt", "r");
fgets(decoded_text, 201, fp);
fclose(fp);
if (strcmp(text, decoded_text) == 0) {
printf("编码、译码正确\n");
} else {
printf("编码、译码错误\n");
}
return 0;
}
```
上述代码实现了以下功能:
1. 从文件中读入英文短文。
2. 统计短文中每个字母的出现次数。
3. 以字母出现次数作为权值,建立Huffman树,并给出每个字母的Huffman编码。
4. 将原短文用Huffman编码进行编码,并将编码后的短文写入文件。
5. 对编码后的短文进行译码,并将译码后的短文写入文件。最后比较原短文和译码后的短文,检验编码、译码的正确性。
需要注意的是,上述代码中为了简化实现,假设输入的英文短文只包含小写字母。如果需要处理其他字符,比如大写字母、数字或标点符号,需要对代码进行相应的修改。
阅读全文