问题描述:利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。 基本要求:一个完整的系统应具有以下功能: (1)I:初始化:从键盘读入字符集大小N,以及N个字符和N个权值,建立哈夫曼树,并将它保存在文件HFMTREE中。 (2)E:编码:利用已建好的哈夫曼树(如不在内存,则从文件HFMTREE中读入),对文件TOBETRAN中的正文进行编码,然后将结果存入文件CODEFILE中。 (3)D:译码:利用已建好的哈夫曼树将文件CODEFILE中的代码进行译码,结果存入文件TEXTFILE中。(1)用户界面可以设计为菜单方式:显示上述功能符号,再加上“Q”,表示退出系统运行QUIT。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单,直至某次用户选择了“Q”为止。 (2)在程序的一次执行过程中,第一次执行I,D或E命令之后,哈夫曼树已经在内存了,不必再读入。每次执行中不一定执行I命令,因为HFMTREE可能早已建好。
时间: 2024-03-25 13:36:38 浏览: 86
以下是一个基于C语言的哈夫曼编/译码系统的实现,包括初始化、编码和译码三个功能:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 100
typedef struct node {
char ch;
int freq;
struct node *left, *right;
} Node;
typedef struct {
char code[MAX_N];
int len;
} Code;
Node *build_tree(char *chars, int *freq, int n) {
Node *nodes[MAX_N];
for (int i = 0; i < n; i++) {
nodes[i] = (Node *)malloc(sizeof(Node));
nodes[i]->ch = chars[i];
nodes[i]->freq = freq[i];
nodes[i]->left = nodes[i]->right = NULL;
}
int m = n;
while (m > 1) {
int i1, i2;
if (nodes[0]->freq < nodes[1]->freq) {
i1 = 0;
i2 = 1;
} else {
i1 = 1;
i2 = 0;
}
for (int i = 2; i < m; i++) {
if (nodes[i]->freq < nodes[i1]->freq) {
i2 = i1;
i1 = i;
} else if (nodes[i]->freq < nodes[i2]->freq) {
i2 = i;
}
}
Node *new_node = (Node *)malloc(sizeof(Node));
new_node->ch = '\0';
new_node->freq = nodes[i1]->freq + nodes[i2]->freq;
new_node->left = nodes[i1];
new_node->right = nodes[i2];
nodes[i1] = new_node;
nodes[i2] = nodes[m - 1];
m--;
}
return nodes[0];
}
void save_tree(Node *root, FILE *fp) {
if (root->ch != '\0') {
fputc('1', fp);
fputc(root->ch, fp);
} else {
fputc('0', fp);
save_tree(root->left, fp);
save_tree(root->right, fp);
}
}
Node *load_tree(FILE *fp) {
int c = fgetc(fp);
if (c == '1') {
Node *node = (Node *)malloc(sizeof(Node));
node->ch = fgetc(fp);
node->freq = 0;
node->left = node->right = NULL;
return node;
} else {
Node *node = (Node *)malloc(sizeof(Node));
node->ch = '\0';
node->freq = 0;
node->left = load_tree(fp);
node->right = load_tree(fp);
return node;
}
}
void traverse_tree(Node *root, Code *table, char *code, int len) {
if (root->ch != '\0') {
Code *c = &table[root->ch];
c->len = len;
strcpy(c->code, code);
} else {
code[len] = '0';
traverse_tree(root->left, table, code, len + 1);
code[len] = '1';
traverse_tree(root->right, table, code, len + 1);
}
}
void encode(Node *root, Code *table, char *text, char *code) {
int len = strlen(text);
int pos = 0;
for (int i = 0; i < len; i++) {
Code *c = &table[text[i]];
for (int j = 0; j < c->len; j++) {
code[pos++] = c->code[j];
}
}
code[pos] = '\0';
}
void decode(Node *root, char *code, char *text) {
int len = strlen(code);
int pos = 0;
Node *p = root;
for (int i = 0; i < len; i++) {
if (code[i] == '0') {
p = p->left;
} else {
p = p->right;
}
if (p->ch != '\0') {
text[pos++] = p->ch;
p = root;
}
}
text[pos] = '\0';
}
int main() {
int n;
char chars[MAX_N];
int freq[MAX_N];
printf("Enter the size of character set: ");
scanf("%d", &n);
printf("Enter the characters and their frequencies:\n");
for (int i = 0; i < n; i++) {
scanf(" %c %d", &chars[i], &freq[i]);
}
Node *root = build_tree(chars, freq, n);
FILE *fp = fopen("HFMTREE", "w");
save_tree(root, fp);
fclose(fp);
Code table[256];
char code[MAX_N];
traverse_tree(root, table, code, 0);
while (1) {
printf("\nChoose a function:\n");
printf("I: Initialize\n");
printf("E: Encode\n");
printf("D: Decode\n");
printf("Q: Quit\n");
char cmd;
scanf(" %c", &cmd);
if (cmd == 'I') {
fp = fopen("HFMTREE", "r");
root = load_tree(fp);
fclose(fp);
traverse_tree(root, table, code, 0);
printf("Huffman tree loaded.\n");
} else if (cmd == 'E') {
char text[MAX_N];
printf("Enter the text to be encoded: ");
scanf("%s", text);
encode(root, table, text, code);
fp = fopen("CODEFILE", "w");
fprintf(fp, "%s", code);
fclose(fp);
printf("Encoded text saved in CODEFILE.\n");
} else if (cmd == 'D') {
fp = fopen("CODEFILE", "r");
fgets(code, MAX_N, fp);
fclose(fp);
char text[MAX_N];
decode(root, code, text);
fp = fopen("TEXTFILE", "w");
fprintf(fp, "%s", text);
fclose(fp);
printf("Decoded text saved in TEXTFILE.\n");
} else if (cmd == 'Q') {
break;
} else {
printf("Invalid command.\n");
}
}
return 0;
}
```
在这个实现中,我们首先定义了一个结构体 `Node` 表示哈夫曼树的节点,其中 `ch` 表示字符,`freq` 表示该字符出现的频率,`left` 和 `right` 分别表示左子树和右子树。然后就是构建哈夫曼树的过程,我们根据给定的字符集和频率数组建立哈夫曼树,并将其保存到文件 `HFMTREE` 中。接着定义了一个结构体 `Code` 表示字符对应的编码,其中 `code` 表示编码序列,`len` 表示编码序列的长度。通过遍历哈夫曼树,我们可以得到每个字符对应的编码,并将其保存在一个编码表 `table` 中。最后就是编码和译码的过程,我们可以从文件中读入编码或文本,进行编码或译码,然后将结果保存到文件中。用户可以通过简单的菜单来选择进行初始化、编码、译码或退出操作。
阅读全文