c语言实现哈夫曼编码压缩
时间: 2023-07-26 13:12:59 浏览: 46
哈夫曼编码是一种无损压缩算法,可以通过构建哈夫曼树来实现。
以下是使用C语言实现哈夫曼编码压缩的基本步骤:
1. 统计字符出现的频率,即计算每个字符出现的次数。
2. 将字符频率按照从小到大的顺序排序。
3. 构建哈夫曼树,将字符频率最小的两个节点合并成一个新节点,直到只剩下一个节点为止。
4. 根据哈夫曼树生成每个字符的编码,对于左子树的编码为0,右子树的编码为1。
5. 将每个字符的编码存储到文件中。
6. 将原始数据按照每个字符的编码进行压缩,并将压缩后的数据存储到文件中。
下面是一个简单的示例代码,实现了哈夫曼编码的压缩和解压缩功能:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node {
char data;
int freq;
struct node *left;
struct node *right;
} Node;
typedef struct {
Node **data;
int size;
int capacity;
} PriorityQueue;
typedef struct {
char *code;
char data;
} Code;
Node *createNode(char data, int freq) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = data;
newNode->freq = freq;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
PriorityQueue *createPriorityQueue(int capacity) {
PriorityQueue *queue = (PriorityQueue *)malloc(sizeof(PriorityQueue));
queue->data = (Node **)malloc(sizeof(Node *) * capacity);
queue->size = 0;
queue->capacity = capacity;
return queue;
}
void swap(Node **a, Node **b) {
Node *temp = *a;
*a = *b;
*b = temp;
}
void push(PriorityQueue *queue, Node *node) {
if (queue->size >= queue->capacity) {
return;
}
queue->data[queue->size] = node;
int curr = queue->size;
while (curr > 0 && queue->data[curr]->freq < queue->data[(curr - 1) / 2]->freq) {
swap(&queue->data[curr], &queue->data[(curr - 1) / 2]);
curr = (curr - 1) / 2;
}
queue->size++;
}
Node *pop(PriorityQueue *queue) {
if (queue->size <= 0) {
return NULL;
}
Node *node = queue->data[0];
queue->size--;
queue->data[0] = queue->data[queue->size];
int curr = 0;
while (2 * curr + 1 < queue->size) {
int child = 2 * curr + 1;
if (child + 1 < queue->size && queue->data[child + 1]->freq < queue->data[child]->freq) {
child++;
}
if (queue->data[curr]->freq > queue->data[child]->freq) {
swap(&queue->data[curr], &queue->data[child]);
curr = child;
} else {
break;
}
}
return node;
}
void destroyPriorityQueue(PriorityQueue *queue) {
free(queue->data);
free(queue);
}
void destroyNode(Node *node) {
if (node == NULL) {
return;
}
destroyNode(node->left);
destroyNode(node->right);
free(node);
}
Node *buildHuffmanTree(char *data, int *freq, int size) {
PriorityQueue *queue = createPriorityQueue(size);
for (int i = 0; i < size; i++) {
Node *node = createNode(data[i], freq[i]);
push(queue, node);
}
while (queue->size > 1) {
Node *left = pop(queue);
Node *right = pop(queue);
Node *parent = createNode('\0', left->freq + right->freq);
parent->left = left;
parent->right = right;
push(queue, parent);
}
Node *root = pop(queue);
destroyPriorityQueue(queue);
return root;
}
void generateCodes(Node *node, Code *codes, int top, char *buffer) {
if (node->left != NULL) {
buffer[top] = '0';
generateCodes(node->left, codes, top + 1, buffer);
}
if (node->right != NULL) {
buffer[top] = '1';
generateCodes(node->right, codes, top + 1, buffer);
}
if (node->left == NULL && node->right == NULL) {
Code code;
code.data = node->data;
code.code = (char *)malloc(sizeof(char) * (top + 1));
memcpy(code.code, buffer, top);
code.code[top] = '\0';
codes[node->data] = code;
}
}
void compressFile(char *inputFile, char *outputFile) {
FILE *input = fopen(inputFile, "rb");
if (input == NULL) {
return;
}
FILE *output = fopen(outputFile, "wb");
if (output == NULL) {
fclose(input);
return;
}
int freq[256] = {0};
char buffer[1024];
int size;
while ((size = fread(buffer, sizeof(char), 1024, input)) > 0) {
for (int i = 0; i < size; i++) {
freq[buffer[i]]++;
}
}
fseek(input, 0, SEEK_SET);
Node *root = buildHuffmanTree((char *)freq, freq, 256);
Code codes[256];
char codeBuffer[256];
generateCodes(root, codes, 0, codeBuffer);
fwrite(freq, sizeof(int), 256, output);
int bitCount = 0;
char bitBuffer = 0;
while ((size = fread(buffer, sizeof(char), 1024, input)) > 0) {
for (int i = 0; i < size; i++) {
Code code = codes[buffer[i]];
for (int j = 0; j < strlen(code.code); j++) {
if (code.code[j] == '1') {
bitBuffer |= 1 << (7 - bitCount);
}
bitCount++;
if (bitCount == 8) {
fwrite(&bitBuffer, sizeof(char), 1, output);
bitBuffer = 0;
bitCount = 0;
}
}
}
}
if (bitCount > 0) {
fwrite(&bitBuffer, sizeof(char), 1, output);
}
fclose(input);
fclose(output);
destroyNode(root);
}
void decompressFile(char *inputFile, char *outputFile) {
FILE *input = fopen(inputFile, "rb");
if (input == NULL) {
return;
}
FILE *output = fopen(outputFile, "wb");
if (output == NULL) {
fclose(input);
return;
}
int freq[256] = {0};
fread(freq, sizeof(int), 256, input);
Node *root = buildHuffmanTree((char *)freq, freq, 256);
int bitCount = 0;
char bitBuffer = 0;
Node *curr = root;
while (fread(&bitBuffer, sizeof(char), 1, input) > 0) {
for (int i = 0; i < 8; i++) {
if (bitBuffer & (1 << (7 - i))) {
curr = curr->right;
} else {
curr = curr->left;
}
if (curr->left == NULL && curr->right == NULL) {
fwrite(&curr->data, sizeof(char), 1, output);
curr = root;
}
}
}
fclose(input);
fclose(output);
destroyNode(root);
}
int main() {
compressFile("input.txt", "output.bin");
decompressFile("output.bin", "output.txt");
return 0;
}
```
该示例代码中使用了优先队列来构建哈夫曼树,同时还实现了文件压缩和解压缩的功能。