设计内容:对输入的一串电文字符实现哈夫曼编码,再对哈夫曼编码生成的代码串进行译码,输出电文字符串。 实现功能: 根据输入的字符串,统计每种字符的出现概率,以此为基础完成对应哈夫曼树的建立; 哈夫曼编码的生成; 从文件中读入需要译码的串,完成译码。 设计要求: 三个功能模块要求用函数的形式实现。 以菜单的方式选择编码或者译码。用C语言完成
时间: 2023-06-17 16:02:18 浏览: 272
以下是一个可能的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CHARACTERS 256
typedef struct Node {
char character;
int frequency;
struct Node *left;
struct Node *right;
} Node;
typedef struct Code {
char character;
char *code;
} Code;
Node *new_node(char character, int frequency, Node *left, Node *right) {
Node *node = (Node *) malloc(sizeof(Node));
node->character = character;
node->frequency = frequency;
node->left = left;
node->right = right;
return node;
}
void swap_nodes(Node **a, Node **b) {
Node *temp = *a;
*a = *b;
*b = temp;
}
void sort_nodes_by_frequency(Node **nodes, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (nodes[j]->frequency > nodes[j+1]->frequency) {
swap_nodes(&nodes[j], &nodes[j+1]);
}
}
}
}
Node *build_huffman_tree(int *frequencies) {
Node *nodes[MAX_CHARACTERS];
int n = 0;
for (int i = 0; i < MAX_CHARACTERS; i++) {
if (frequencies[i] > 0) {
nodes[n] = new_node(i, frequencies[i], NULL, NULL);
n++;
}
}
while (n > 1) {
sort_nodes_by_frequency(nodes, n);
Node *left = nodes[0];
Node *right = nodes[1];
Node *parent = new_node('$', left->frequency + right->frequency, left, right);
nodes[0] = parent;
for (int i = 2; i < n; i++) {
nodes[i-1] = nodes[i];
}
n--;
}
return nodes[0];
}
void free_huffman_tree(Node *root) {
if (root != NULL) {
free_huffman_tree(root->left);
free_huffman_tree(root->right);
free(root);
}
}
void print_codes(Node *node, char *code, Code *codes, int *n) {
if (node != NULL) {
if (node->left == NULL && node->right == NULL) {
codes[*n].character = node->character;
codes[*n].code = strdup(code);
(*n)++;
} else {
char left_code[strlen(code) + 2];
strcpy(left_code, code);
strcat(left_code, "0");
print_codes(node->left, left_code, codes, n);
char right_code[strlen(code) + 2];
strcpy(right_code, code);
strcat(right_code, "1");
print_codes(node->right, right_code, codes, n);
}
}
}
char *encode(char *text, Code *codes, int n) {
int text_length = strlen(text);
char *encoded = (char *) malloc((text_length + 1) * sizeof(char));
int k = 0;
for (int i = 0; i < text_length; i++) {
for (int j = 0; j < n; j++) {
if (text[i] == codes[j].character) {
strcat(encoded, codes[j].code);
k += strlen(codes[j].code);
break;
}
}
}
encoded[k] = '\0';
return encoded;
}
char *decode(char *code, Node *root) {
int code_length = strlen(code);
char *decoded = (char *) malloc((code_length + 1) * sizeof(char));
int k = 0;
Node *node = root;
for (int i = 0; i < code_length; i++) {
if (code[i] == '0') {
node = node->left;
} else {
node = node->right;
}
if (node->left == NULL && node->right == NULL) {
decoded[k] = node->character;
k++;
node = root;
}
}
decoded[k] = '\0';
return decoded;
}
void print_codes_table(Code *codes, int n) {
printf("Character\tCode\n");
for (int i = 0; i < n; i++) {
printf("%c\t\t%s\n", codes[i].character, codes[i].code);
}
}
int main() {
char text[1000];
printf("Enter text to encode: ");
fgets(text, sizeof(text), stdin);
int frequencies[MAX_CHARACTERS] = {0};
int text_length = strlen(text);
for (int i = 0; i < text_length; i++) {
frequencies[text[i]]++;
}
Node *root = build_huffman_tree(frequencies);
Code codes[MAX_CHARACTERS];
int n = 0;
print_codes(root, "", codes, &n);
print_codes_table(codes, n);
char *encoded = encode(text, codes, n);
printf("Encoded code: %s\n", encoded);
char code[1000];
printf("Enter code to decode: ");
fgets(code, sizeof(code), stdin);
char *decoded = decode(code, root);
printf("Decoded text: %s\n", decoded);
free(encoded);
free(decoded);
free_huffman_tree(root);
return 0;
}
```
这个实现包含了三个函数模块:
1. `build_huffman_tree` 统计每种字符的出现概率,以此为基础完成对应哈夫曼树的建立;
2. `print_codes` 哈夫曼编码的生成;
3. `decode` 从文件中读入需要译码的串,完成译码。
除此之外,还包含了一些辅助函数和一个简单的菜单,用于选择编码或者译码。这个实现假设输入的电文字符串只包含ASCII字符(共256种),并且将编码和译码分别用不同的字符串表示,而不是将它们写入文件中。如果需要将编码和译码写入文件中,需要使用一些额外的函数来处理文件I/O。
阅读全文