C语言 实现哈夫曼编码
时间: 2023-10-28 11:08:56 浏览: 58
好的,我来给你讲解如何用 C 语言实现哈夫曼编码。
哈夫曼编码是一种用于数据压缩的编码方法,它能够有效地减少数据的大小。哈夫曼编码的基本思想是:给出一个字符串,根据字符串中每个字符的出现频率,构建一棵二叉树,然后为每个字符分配一个二进制编码,使得字符串中出现频率较高的字符的编码较短,这样就能有效地减少数据的大小。
下面是一个简单的 C 语言实现的哈夫曼编码的例子:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TREE_SIZE 100
typedef struct {
// 存储哈夫曼编码的字符数组
char ch[MAX_TREE_SIZE];
// 存储哈夫曼编码的权值
int weight[MAX_TREE_SIZE];
// 存储哈夫曼编码的左儿子
int left[MAX_TREE_SIZE];
// 存储哈夫曼编码的右儿子
int right[MAX_TREE_SIZE];
// 哈夫曼编码的节点数
int n;
} HuffmanTree;
// 哈夫曼树的节点
typedef struct {
// 节点的权值
int weight;
// 左儿子的下标
int left;
// 右儿子的下标
int right;
// 父亲节点的下标
int parent;
} HTNode;
相关问题
用C语言实现哈夫曼编码
以下是使用C语言实现哈夫曼编码的基本步骤:
1. 定义结构体来表示每个字符及其对应的频率和编码:
```
struct node {
char ch;
int freq;
char *code;
};
```
2. 统计每个字符出现的频率,并将其存储到一个数组中:
```
int freq[256] = {0};
for (int i = 0; i < strlen(input); i++) {
freq[input[i]]++;
}
```
3. 构建哈夫曼树,可以使用优先队列(也称为堆)来实现:
```
struct node *buildHuffmanTree(int freq[]) {
priority_queue<struct node*, vector<struct node*>, compare> pq;
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
struct node *n = new node;
n->ch = (char)i;
n->freq = freq[i];
n->left = NULL;
n->right = NULL;
pq.push(n);
}
}
while (pq.size() > 1) {
struct node *n1 = pq.top();
pq.pop();
struct node *n2 = pq.top();
pq.pop();
struct node *n = new node;
n->freq = n1->freq + n2->freq;
n->left = n1;
n->right = n2;
pq.push(n);
}
return pq.top();
}
```
其中,compare是一个比较函数,用于将节点按照频率从小到大排序。
4. 通过递归遍历哈夫曼树,生成每个字符的编码:
```
void generateCodes(struct node *root, char *code, int index) {
if (root->left == NULL && root->right == NULL) {
code[index] = '\0';
root->code = strdup(code);
return;
}
code[index] = '0';
generateCodes(root->left, code, index + 1);
code[index] = '1';
generateCodes(root->right, code, index + 1);
}
```
5. 使用生成的编码对原始数据进行编码:
```
char *encodeData(char *input, struct node *root) {
char *output = (char*)malloc(sizeof(char) * strlen(input) * 8);
int index = 0;
for (int i = 0; i < strlen(input); i++) {
struct node *n = findNode(root, input[i]);
strcat(output, n->code);
}
return output;
}
```
其中,findNode函数用于在哈夫曼树中查找指定字符对应的节点。
6. 使用生成的编码对压缩后的数据进行解码:
```
char *decodeData(char *input, struct node *root) {
char *output = (char*)malloc(sizeof(char) * strlen(input));
int index = 0;
struct node *n = root;
for (int i = 0; i < strlen(input); i++) {
if (input[i] == '0') {
n = n->left;
} else {
n = n->right;
}
if (n->left == NULL && n->right == NULL) {
output[index++] = n->ch;
n = root;
}
}
output[index] = '\0';
return output;
}
```
以上就是使用C语言实现哈夫曼编码的基本步骤。
用c语言实现哈夫曼编码
哈夫曼编码是一种无损数据压缩算法,它的核心思想是将出现频率较高的字符用较短的编码表示,而出现频率较低的字符用较长的编码表示,从而达到压缩数据的目的。下面是用C语言实现哈夫曼编码的基本步骤:
1. 定义哈夫曼树的节点结构体
```c
typedef struct HuffmanNode {
char ch; // 字符
int freq; // 字符出现的频率
struct HuffmanNode *left, *right; // 左右子节点指针
} HuffmanNode;
```
2. 统计每个字符出现的频率
```c
int freq[256] = {0}; // 存储每个字符出现的频率,ASCII码共有256个字符
// 遍历字符串,统计每个字符出现的频率
char *str = "hello world";
for (int i = 0; i < strlen(str); i++) {
freq[str[i]]++;
}
```
3. 构建哈夫曼树
```c
// 比较函数,用于按照字符出现频率从小到大排序
int cmp(const void *a, const void *b) {
HuffmanNode **node1 = (HuffmanNode**)a;
HuffmanNode **node2 = (HuffmanNode**)b;
return (*node1)->freq - (*node2)->freq;
}
// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(int *freq) {
// 构建叶子节点
HuffmanNode *nodes[256];
int count = 0;
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
HuffmanNode *node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
node->ch = (char)i;
node->freq = freq[i];
node->left = node->right = NULL;
nodes[count++] = node;
}
}
// 构建哈夫曼树
while (count > 1) {
qsort(nodes, count, sizeof(HuffmanNode*), cmp); // 按照频率从小到大排序
HuffmanNode *node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
node->left = nodes[0];
node->right = nodes[1];
node->freq = nodes[0]->freq + nodes[1]->freq;
nodes[0] = node;
count--;
for (int i = 1; i < count; i++) {
nodes[i] = nodes[i+1];
}
}
return nodes[0];
}
```
4. 生成哈夫曼编码
```c
// 生成哈夫曼编码
void genHuffmanCode(HuffmanNode *root, char *code, int depth) {
if (root == NULL) return;
if (root->left == NULL && root->right == NULL) {
printf("%c: %s\n", root->ch, code);
return;
}
code[depth] = '0';
genHuffmanCode(root->left, code, depth+1);
code[depth] = '1';
genHuffmanCode(root->right, code, depth+1);
}
// 生成哈夫曼编码表
void genHuffmanCodeTable(HuffmanNode *root, char *codeTable[]) {
char code[256];
memset(code, 0, sizeof(code));
genHuffmanCode(root, code, 0);
}
```
完整代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct HuffmanNode {
char ch; // 字符
int freq; // 字符出现的频率
struct HuffmanNode *left, *right; // 左右子节点指针
} HuffmanNode;
int freq[256] = {0}; // 存储每个字符出现的频率,ASCII码共有256个字符
// 比较函数,用于按照字符出现频率从小到大排序
int cmp(const void *a, const void *b) {
HuffmanNode **node1 = (HuffmanNode**)a;
HuffmanNode **node2 = (HuffmanNode**)b;
return (*node1)->freq - (*node2)->freq;
}
// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(int *freq) {
// 构建叶子节点
HuffmanNode *nodes[256];
int count = 0;
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
HuffmanNode *node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
node->ch = (char)i;
node->freq = freq[i];
node->left = node->right = NULL;
nodes[count++] = node;
}
}
// 构建哈夫曼树
while (count > 1) {
qsort(nodes, count, sizeof(HuffmanNode*), cmp); // 按照频率从小到大排序
HuffmanNode *node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
node->left = nodes[0];
node->right = nodes[1];
node->freq = nodes[0]->freq + nodes[1]->freq;
nodes[0] = node;
count--;
for (int i = 1; i < count; i++) {
nodes[i] = nodes[i+1];
}
}
return nodes[0];
}
// 生成哈夫曼编码
void genHuffmanCode(HuffmanNode *root, char *code, int depth) {
if (root == NULL) return;
if (root->left == NULL && root->right == NULL) {
printf("%c: %s\n", root->ch, code);
return;
}
code[depth] = '0';
genHuffmanCode(root->left, code, depth+1);
code[depth] = '1';
genHuffmanCode(root->right, code, depth+1);
}
// 生成哈夫曼编码表
void genHuffmanCodeTable(HuffmanNode *root, char *codeTable[]) {
char code[256];
memset(code, 0, sizeof(code));
genHuffmanCode(root, code, 0);
}
int main() {
// 统计每个字符出现的频率
char *str = "hello world";
for (int i = 0; i < strlen(str); i++) {
freq[str[i]]++;
}
// 构建哈夫曼树
HuffmanNode *root = buildHuffmanTree(freq);
// 生成哈夫曼编码表
char *codeTable[256] = {0};
genHuffmanCodeTable(root, codeTable);
return 0;
}
```