霍夫曼树c语言
时间: 2023-07-13 13:16:58 浏览: 55
以下是一个简单的霍夫曼树的C语言实现,包括创建霍夫曼树、编码和解码等功能:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
// 霍夫曼树节点
typedef struct node {
char ch;
int freq;
struct node *left, *right;
} Node;
// 霍夫曼编码表
typedef struct code {
char ch;
char bits[MAX];
} Code;
// 创建霍夫曼树
Node *createHuffmanTree(char *str) {
int len = strlen(str);
int freq[256] = {0};
for (int i = 0; i < len; i++) {
freq[str[i]]++;
}
Node *nodes[256];
int n = 0;
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
nodes[n] = (Node *) malloc(sizeof(Node));
nodes[n]->ch = (char) i;
nodes[n]->freq = freq[i];
nodes[n]->left = NULL;
nodes[n]->right = NULL;
n++;
}
}
while (n > 1) {
int i1 = 0, i2 = 1;
if (nodes[i1]->freq > nodes[i2]->freq) {
int tmp = i1;
i1 = i2;
i2 = tmp;
}
for (int i = 2; i < n; i++) {
if (nodes[i]->freq < nodes[i1]->freq) {
i2 = i1;
i1 = i;
} else if (nodes[i]->freq < nodes[i2]->freq) {
i2 = i;
}
}
Node *newNode = (Node *) malloc(sizeof(Node));
newNode->ch = '\0';
newNode->freq = nodes[i1]->freq + nodes[i2]->freq;
newNode->left = nodes[i1];
newNode->right = nodes[i2];
if (i1 < i2) {
for (int i = i2; i < n - 1; i++) {
nodes[i] = nodes[i + 1];
}
}
for (int i = i1; i < n - 1; i++) {
nodes[i] = nodes[i + 1];
}
nodes[n - 2] = newNode;
n--;
}
return nodes[0];
}
// 生成霍夫曼编码表
void generateHuffmanCode(Node *root, Code *codes, char *bits, int depth) {
if (root->left == NULL && root->right == NULL) {
for (int i = 0; i < strlen(bits); i++) {
codes[(int) root->ch].bits[i] = bits[i];
}
codes[(int) root->ch].ch = root->ch;
return;
}
bits[depth] = '0';
generateHuffmanCode(root->left, codes, bits, depth + 1);
bits[depth] = '1';
generateHuffmanCode(root->right, codes, bits, depth + 1);
}
// 霍夫曼编码
void huffmanEncode(char *str, char *code) {
Node *root = createHuffmanTree(str);
Code codes[256];
char bits[MAX] = {'\0'};
generateHuffmanCode(root, codes, bits, 0);
int len = strlen(str);
int pos = 0;
for (int i = 0; i < len; i++) {
for (int j = 0; j < strlen(codes[(int) str[i]].bits); j++) {
code[pos++] = codes[(int) str[i]].bits[j];
}
}
}
// 霍夫曼解码
void huffmanDecode(char *code, char *str) {
Node *root = createHuffmanTree(str);
int len = strlen(code);
Node *p = root;
int pos = 0;
while (pos < len) {
if (code[pos] == '0') {
p = p->left;
} else {
p = p->right;
}
if (p->left == NULL && p->right == NULL) {
str[strlen(str)] = p->ch;
p = root;
}
pos++;
}
}
int main() {
char str[MAX] = "Hello, World!";
char code[MAX] = {'\0'};
huffmanEncode(str, code);
printf("%s\n", code);
char str2[MAX] = {'\0'};
huffmanDecode(code, str2);
printf("%s", str2);
return 0;
}
```