哈夫曼编码压缩文件c语言
时间: 2024-07-01 13:00:46 浏览: 14
哈夫曼编码(Huffman Coding)是一种用于数据压缩的无损编码方式,它基于二叉树结构,尤其适用于频率较高的字符。在C语言中实现哈夫曼编码的过程主要包括以下几个步骤:
1. **字符频率统计**:首先计算源文件中每个字符出现的频率。
2. **构建哈夫曼树**:根据字符频率,创建一个空的哈夫曼树,然后通过合并频率最小的两个节点(自底向上)形成新的节点,直到只剩下一个叶子节点,即为完成的哈夫曼树。
3. **编码规则**:从根节点到每个字符的路径不同,记录这些路径就形成了对应的哈夫曼编码。一般来说,从左到右走是0,从右到左走是1。
4. **压缩数据**:将源文件中的字符替换为其对应的哈夫曼编码。
5. **解码恢复**:读取压缩后的数据,按照编码规则进行还原。
在C语言中,这通常涉及到链表操作(用于构建和存储哈夫曼树),以及数组或位图来储存编码。你可以使用结构体表示节点,包含字符、频率和左右子节点等信息。这里提供一个简单的概述,具体实现可能涉及递归或迭代算法,取决于你的代码风格。
相关问题
哈夫曼编码压缩文件c语言代码
哈夫曼编码是一种基于字符出现频率的压缩算法,它可以将一些出现频率较高的字符用较短的编码表示,从而实现对数据的压缩。下面是哈夫曼编码压缩文件的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义哈夫曼树节点结构体
typedef struct huffman_node {
unsigned char data; // 字符数据
unsigned int freq; // 字符出现频率
struct huffman_node *left, *right; // 左右子节点指针
} huffman_node;
// 定义哈夫曼编码结构体
typedef struct huffman_code {
unsigned char data; // 字符数据
unsigned int freq; // 字符出现频率
char *code; // 字符编码
} huffman_code;
// 统计字符出现频率,返回一个包含256个元素的数组,数组下标为字符ASCII码值,数组元素为该字符出现的次数
unsigned int *count_freq(FILE *fp) {
unsigned int *freq = (unsigned int *)calloc(256, sizeof(unsigned int));
unsigned char c;
while(fread(&c, sizeof(char), 1, fp)) {
freq[c]++;
}
return freq;
}
// 创建哈夫曼树,返回树的根节点指针
huffman_node *create_tree(unsigned int *freq) {
int i, j, min1, min2;
huffman_node *nodes = (huffman_node *)malloc(256 * sizeof(huffman_node));
for(i = 0, j = 0; i < 256; i++) {
if(freq[i] > 0) {
nodes[j].data = i;
nodes[j].freq = freq[i];
nodes[j].left = nodes[j].right = NULL;
j++;
}
}
int n = j;
for(i = 0; i < n - 1; i++) {
min1 = min2 = -1;
for(j = 0; j < n + i; j++) {
if(nodes[j].freq > 0) {
if(min1 == -1 || nodes[j].freq < nodes[min1].freq) {
min2 = min1;
min1 = j;
} else if(min2 == -1 || nodes[j].freq < nodes[min2].freq) {
min2 = j;
}
}
}
nodes[n + i].data = 0;
nodes[n + i].freq = nodes[min1].freq + nodes[min2].freq;
nodes[n + i].left = &nodes[min1];
nodes[n + i].right = &nodes[min2];
nodes[min1].freq = 0;
nodes[min2].freq = 0;
}
return &nodes[n + i - 1];
}
// 递归生成哈夫曼编码,并将结果保存到huffman_code数组中,返回哈夫曼编码数组的长度
int generate_code(huffman_node *node, char *code, huffman_code *hcode, int index) {
if(node->left == NULL && node->right == NULL) {
hcode[index].data = node->data;
hcode[index].freq = node->freq;
hcode[index].code = (char *)malloc(strlen(code) + 1);
strcpy(hcode[index].code, code);
return index + 1;
} else {
int left_index = generate_code(node->left, strcat(code, "0"), hcode, index);
code[strlen(code) - 1] = '\0';
int right_index = generate_code(node->right, strcat(code, "1"), hcode, left_index);
code[strlen(code) - 1] = '\0';
return right_index;
}
}
// 将哈夫曼编码写入文件
void write_code(FILE *fp, huffman_code *hcode, int len) {
fwrite(&len, sizeof(int), 1, fp);
int i, j, n;
for(i = 0; i < len; i++) {
fwrite(&hcode[i].data, sizeof(char), 1, fp);
fwrite(&hcode[i].freq, sizeof(int), 1, fp);
n = strlen(hcode[i].code);
fwrite(&n, sizeof(int), 1, fp);
for(j = 0; j < n; j++) {
fwrite(&hcode[i].code[j], sizeof(char), 1, fp);
}
}
}
// 将文件内容按照哈夫曼编码压缩,并写入文件
void compress_file(FILE *src_fp, FILE *dst_fp, huffman_code *hcode, int len) {
unsigned char c;
char *code;
int i, j, n;
while(fread(&c, sizeof(char), 1, src_fp)) {
for(i = 0; i < len; i++) {
if(hcode[i].data == c) {
code = hcode[i].code;
n = strlen(code);
for(j = 0; j < n; j++) {
if(code[j] == '0') {
fwrite("0", sizeof(char), 1, dst_fp);
} else {
fwrite("1", sizeof(char), 1, dst_fp);
}
}
break;
}
}
}
}
int main(int argc, char **argv) {
if(argc != 3) {
printf("Usage: %s source_file target_file\n", argv);
exit(1);
}
FILE *src_fp = fopen(argv, "rb");
if(src_fp == NULL) {
printf("Open source file failed!\n");
exit(1);
}
FILE *dst_fp = fopen(argv, "wb");
if(dst_fp == NULL) {
printf("Open target file failed!\n");
exit(1);
}
unsigned int *freq = count_freq(src_fp);
rewind(src_fp);
huffman_node *root = create_tree(freq);
huffman_code *hcode = (huffman_code *)malloc(256 * sizeof(huffman_code));
generate_code(root, "", hcode, 0);
write_code(dst_fp, hcode, 256);
compress_file(src_fp, dst_fp, hcode, 256);
fclose(src_fp);
fclose(dst_fp);
return 0;
}
```
c语言哈夫曼编码压缩文件
C语言实现哈夫曼编码压缩文件的过程可以分为以下几个步骤:
1. 统计字符频率:从输入的文本文件中读取字符,并统计每个字符出现的频率。
2. 构建哈夫曼树:根据字符频率构建哈夫曼树。哈夫曼树是一种最优二叉树,其中频率较低的字符位于树的较低层,频率较高的字符位于树的较高层。
3. 生成哈夫曼编码表:通过遍历哈夫曼树,为每个字符生成对应的哈夫曼编码。哈夫曼编码是由0和1组成的二进制编码,用于表示每个字符。
4. 压缩文件:将输入的文本文件中的字符根据哈夫曼编码表进行编码,并将编码后的二进制数据写入输出文件。这样可以实现对文本文件的压缩。
5. 计算压缩率:通过比较压缩后的文件大小与原始文件大小,计算出压缩率。压缩率越高,表示压缩效果越好。
6. 解压文件:读取压缩文件中的二进制数据,并根据哈夫曼编码表进行解码,将解码后的字符写入输出文件。这样可以实现对压缩文件的解压缩。
以下是一个C语言实现哈夫曼编码压缩文件的示例代码:
```c
// 哈夫曼树节点结构体
typedef struct Node {
char data; // 字符
int freq; // 频率
struct Node* left;
struct Node* right;
} Node;
// 构建哈夫曼树
Node* buildHuffmanTree(char* text);
// 生成哈夫曼编码表
void generateHuffmanCodes(Node* root, char* code, int depth, char** codes);
// 压缩文件
void compressFile(char* inputFile, char* outputFile, char** codes);
// 解压文件
void decompressFile(char* inputFile, char* outputFile, Node* root);
// 计算文件大小
long getFileSize(FILE* file);
// 计算压缩率
float calculateCompressionRatio(long originalSize, long compressedSize);
int main() {
char* inputFile = "input.txt";
char* compressedFile = "compressed.bin";
char* decompressedFile = "decompressed.txt";
// 构建哈夫曼树
Node* root = buildHuffmanTree(inputFile);
// 生成哈夫曼编码表
char* codes[256];
generateHuffmanCodes(root, "", 0, codes);
// 压缩文件
compressFile(inputFile, compressedFile, codes);
// 解压文件
decompressFile(compressedFile, decompressedFile, root);
// 计算文件大小和压缩率
FILE* inputFilePtr = fopen(inputFile, "rb");
FILE* compressedFilePtr = fopen(compressedFile, "rb");
long originalSize = getFileSize(inputFilePtr);
long compressedSize = getFileSize(compressedFilePtr);
float compressionRatio = calculateCompressionRatio(originalSize, compressedSize);
printf("Compression ratio: %.2f%%\n", compressionRatio);
// 释放内存
// ...
return 0;
}
```
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)