用C语言Huffman编码方法,实现对任意通信字符的编码和解码。(输入任意字符串)
时间: 2024-04-30 10:21:02 浏览: 29
以下是用C语言实现的Huffman编码和解码程序,可以对任意输入的字符串进行编码和解码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TREE_HT 100 // 最大哈夫曼树高度
#define MAX_CHAR 256 // 最大字符数
// 哈夫曼树节点结构体
struct MinHNode {
char ch; // 字符
int freq; // 出现频率
struct MinHNode *left, *right; // 左右子节点指针
};
// 最小堆节点结构体
struct MinHeap {
int size; // 当前堆大小
int capacity; // 堆容量
struct MinHNode **array; // 堆节点数组
};
// 新建哈夫曼树节点
struct MinHNode *newNode(char ch, int freq) {
struct MinHNode *node = (struct MinHNode *) malloc(sizeof(struct MinHNode));
node->ch = ch;
node->freq = freq;
node->left = node->right = NULL;
return node;
}
// 新建最小堆
struct MinHeap *createMinHeap(int capacity) {
struct MinHeap *minHeap = (struct MinHeap *) malloc(sizeof(struct MinHeap));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array = (struct MinHNode **) malloc(minHeap->capacity * sizeof(struct MinHNode *));
return minHeap;
}
// 交换两个哈夫曼树节点
void swapMinHNodes(struct MinHNode **a, struct MinHNode **b) {
struct MinHNode *t = *a;
*a = *b;
*b = t;
}
// 维护最小堆性质
void minHeapify(struct MinHeap *minHeap, int idx) {
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq) {
smallest = left;
}
if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq) {
smallest = right;
}
if (smallest != idx) {
swapMinHNodes(&minHeap->array[idx], &minHeap->array[smallest]);
minHeapify(minHeap, smallest);
}
}
// 检查堆是否只有一个节点
int isSizeOne(struct MinHeap *minHeap) {
return (minHeap->size == 1);
}
// 取出堆中最小的节点
struct MinHNode *extractMin(struct MinHeap *minHeap) {
struct MinHNode *temp = minHeap->array[0];
minHeap->array[0] = minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeapify(minHeap, 0);
return temp;
}
// 插入节点到最小堆
void insertMinHeap(struct MinHeap *minHeap, struct MinHNode *node) {
++minHeap->size;
int i = minHeap->size - 1;
while (i && node->freq < minHeap->array[(i - 1) / 2]->freq) {
minHeap->array[i] = minHeap->array[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->array[i] = node;
}
// 构建最小堆
void buildMinHeap(struct MinHeap *minHeap) {
int n = minHeap->size - 1;
for (int i = (n - 1) / 2; i >= 0; --i) {
minHeapify(minHeap, i);
}
}
// 判断是否是叶子节点
int isLeaf(struct MinHNode *node) {
return !(node->left) && !(node->right);
}
// 创建哈夫曼树
struct MinHNode *buildHuffmanTree(char *data, int *freq, int n) {
struct MinHNode *left, *right, *top;
struct MinHeap *minHeap = createMinHeap(n);
for (int i = 0; i < n; ++i) {
insertMinHeap(minHeap, newNode(data[i], freq[i]));
}
buildMinHeap(minHeap);
while (!isSizeOne(minHeap)) {
left = extractMin(minHeap);
right = extractMin(minHeap);
top = newNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
insertMinHeap(minHeap, top);
}
return extractMin(minHeap);
}
// 打印哈夫曼编码表
void printCodes(struct MinHNode *root, int arr[], int top) {
if (root->left) {
arr[top] = 0;
printCodes(root->left, arr, top + 1);
}
if (root->right) {
arr[top] = 1;
printCodes(root->right, arr, top + 1);
}
if (isLeaf(root)) {
printf("%c: ", root->ch);
for (int i = 0; i < top; ++i) {
printf("%d", arr[i]);
}
printf("\n");
}
}
// 哈夫曼编码主函数
void huffmanCoding(char *data, int *freq, int n) {
struct MinHNode *root = buildHuffmanTree(data, freq, n);
int arr[MAX_TREE_HT], top = 0;
printCodes(root, arr, top);
}
// 解码哈夫曼编码
void huffmanDecoding(struct MinHNode *root, char *str) {
int len = strlen(str);
struct MinHNode *cur = root;
for (int i = 0; i < len; ++i) {
if (str[i] == '0') {
cur = cur->left;
} else {
cur = cur->right;
}
if (isLeaf(cur)) {
printf("%c", cur->ch);
cur = root;
}
}
}
int main() {
char str[100];
printf("Enter a string: ");
gets(str);
int n = strlen(str);
int freq[MAX_CHAR] = {0};
for (int i = 0; i < n; ++i) {
++freq[str[i]];
}
huffmanCoding(str, freq, n);
char code[100] = "0111110010011010001011011100111011001100100111010101101011111111011100111010011101000101011111101";
huffmanDecoding(buildHuffmanTree(str, freq, n), code);
return 0;
}
```
编译运行该程序,输入任意字符串,程序将输出每个字符的哈夫曼编码。程序还演示了如何对一个哈夫曼编码进行解码,输出解码后的字符串。