C语言:利用哈夫曼编码进行信息通讯可以大大提高信道的利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传输数据预先编码;在接受端将传来的数据进行译码。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个哈夫曼码的编/译码系统。 基本要求:根据某字符文件统计字符出现频度,构造Huffman 树,编制Huffman 编码,并将给定字符文件编码,生成编码文件;再将给定编码文件解码,生成字符文件。(要求按二进制位表示编码) 测试数据:英文文件。 提高要求:用二进制表示编码,生成二进制的编码文件。
时间: 2024-02-18 15:01:38 浏览: 42
以下是基于C语言的哈夫曼编/译码实现代码,包括了基本要求和提高要求的实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 256 // 最大字符数
#define MAX_BIT 30 // 最大编码位数
// 哈夫曼树节点结构体
typedef struct TreeNode
{
char ch;
int weight;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 哈夫曼编码结构体
typedef struct HuffmanCode
{
char ch; // 字符
int len; // 编码长度
char code[MAX_BIT]; // 编码字符串
} HuffmanCode;
// 统计字符出现频度
void count(char *filename, int *freq)
{
FILE *fp;
char ch;
fp = fopen(filename, "rb");
if (fp == NULL)
{
printf("文件打开失败!");
exit(1);
}
while ((ch = fgetc(fp)) != EOF)
{
freq[ch]++;
}
fclose(fp);
}
// 初始化哈夫曼树节点
TreeNode *initNode(char ch, int weight)
{
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->ch = ch;
node->weight = weight;
node->left = NULL;
node->right = NULL;
return node;
}
// 构建哈夫曼树
TreeNode *buildTree(int *freq)
{
int i, j, k;
TreeNode *node1, *node2, *node;
TreeNode **tree = (TreeNode **)malloc(MAX_SIZE * sizeof(TreeNode *));
for (i = 0, j = 0; i < MAX_SIZE; i++)
{
if (freq[i])
{
tree[j++] = initNode(i, freq[i]);
}
}
for (i = 0; i < j - 1; i++)
{
k = i + 1;
node1 = tree[i];
node2 = tree[k];
node = initNode('\0', node1->weight + node2->weight);
node->left = node1;
node->right = node2;
j++;
for (k = i + 2; k < j; k++)
{
tree[k - 1] = tree[k];
}
tree[j - 1] = node;
// 插入排序,保证树节点按权重递增排序
for (k = i + 1; k < j - 1 && node->weight > tree[k]->weight; k++)
{
tree[k - 1] = tree[k];
}
tree[k - 1] = node;
}
free(tree);
return node;
}
// 生成哈夫曼编码
void generateCode(TreeNode *root, HuffmanCode *code, int len, char *str)
{
if (root == NULL)
{
return;
}
if (root->left == NULL && root->right == NULL)
{
code[(int)root->ch].ch = root->ch;
code[(int)root->ch].len = len;
strcpy(code[(int)root->ch].code, str);
return;
}
str[len] = '0';
generateCode(root->left, code, len + 1, str);
str[len] = '1';
generateCode(root->right, code, len + 1, str);
}
// 哈夫曼编码压缩文件
void compress(char *filename, char *outname, HuffmanCode *code)
{
FILE *in, *out;
int i, j, count = 0;
char ch, buffer[MAX_BIT];
unsigned char byte = 0;
int len = 0;
in = fopen(filename, "rb");
out = fopen(outname, "wb");
while ((ch = fgetc(in)) != EOF)
{
for (i = 0; i < code[(int)ch].len; i++)
{
buffer[len++] = code[(int)ch].code[i];
if (len == 8)
{
len = 0;
for (j = 0; j < 8; j++)
{
byte <<= 1;
if (buffer[j] == '1')
{
byte |= 1;
}
}
fputc(byte, out);
byte = 0;
count++;
}
}
}
if (len > 0)
{
for (i = len; i < 8; i++)
{
buffer[i] = '0';
}
for (i = 0; i < 8; i++)
{
byte <<= 1;
if (buffer[i] == '1')
{
byte |= 1;
}
}
fputc(byte, out);
count++;
}
fclose(in);
fclose(out);
}
// 哈夫曼编码解压文件
void decompress(char *filename, char *outname, TreeNode *root)
{
FILE *in, *out;
char ch;
TreeNode *node = root;
in = fopen(filename, "rb");
out = fopen(outname, "wb");
while ((ch = fgetc(in)) != EOF)
{
int i;
for (i = 7; i >= 0; i--)
{
if (((ch >> i) & 1) == 1)
{
node = node->right;
}
else
{
node = node->left;
}
if (node->left == NULL && node->right == NULL)
{
fputc(node->ch, out);
node = root;
}
}
}
fclose(in);
fclose(out);
}
// 打印哈夫曼编码
void printCode(HuffmanCode *code)
{
int i;
printf("\n字符\t频度\t编码\n");
for (i = 0; i < MAX_SIZE; i++)
{
if (code[i].len > 0)
{
printf("%c\t%d\t%s\n", code[i].ch, code[i].len, code[i].code);
}
}
}
int main()
{
int i, freq[MAX_SIZE] = {0};
char filename[20], outname[20], str[MAX_BIT] = {'\0'};
HuffmanCode code[MAX_SIZE];
for (i = 0; i < MAX_SIZE; i++)
{
code[i].len = 0;
memset(code[i].code, 0, MAX_BIT);
}
printf("请输入需要压缩的文件名:");
scanf("%s", filename);
count(filename, freq);
TreeNode *root = buildTree(freq);
generateCode(root, code, 0, str);
printf("\n哈夫曼编码如下:\n");
printCode(code);
printf("\n请输入压缩后的文件名:");
scanf("%s", outname);
compress(filename, outname, code);
printf("\n文件压缩成功!\n");
printf("\n请输入需要解压的文件名:");
scanf("%s", outname);
decompress(outname, "output.txt", root);
printf("\n文件解压成功!\n");
return 0;
}
```
以上代码实现了基本要求和提高要求,可以根据输入的文件名进行哈夫曼编码压缩和解压缩操作,生成二进制的编码文件。