使用C语言写出哈夫曼树及其i编码所有代码
时间: 2024-02-17 17:02:38 浏览: 36
以下是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TREE_HT 100
struct Node {
char ch;
int freq;
struct Node *left, *right;
};
struct PriorityQueue {
int size;
int capacity;
struct Node **heap;
};
struct Node *new_node(char ch, int freq) {
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->ch = ch;
node->freq = freq;
node->left = NULL;
node->right = NULL;
return node;
}
struct PriorityQueue *new_priority_queue(int capacity) {
struct PriorityQueue *pq = (struct PriorityQueue *)malloc(sizeof(struct PriorityQueue));
pq->size = 0;
pq->capacity = capacity;
pq->heap = (struct Node **)malloc(capacity * sizeof(struct Node *));
return pq;
}
void swap_nodes(struct Node **a, struct Node **b) {
struct Node *temp = *a;
*a = *b;
*b = temp;
}
void min_heapify(struct PriorityQueue *pq, int idx) {
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < pq->size && pq->heap[left]->freq < pq->heap[smallest]->freq) {
smallest = left;
}
if (right < pq->size && pq->heap[right]->freq < pq->heap[smallest]->freq) {
smallest = right;
}
if (smallest != idx) {
swap_nodes(&pq->heap[idx], &pq->heap[smallest]);
min_heapify(pq, smallest);
}
}
int is_leaf(struct Node *node) {
return node->left == NULL && node->right == NULL;
}
struct PriorityQueue *build_priority_queue(char *data, int *freq) {
struct PriorityQueue *pq = new_priority_queue(strlen(data));
for (int i = 0; i < strlen(data); i++) {
pq->heap[i] = new_node(data[i], freq[i]);
}
pq->size = strlen(data);
for (int i = pq->size / 2 - 1; i >= 0; i--) {
min_heapify(pq, i);
}
return pq;
}
struct Node *build_huffman_tree(char *data, int *freq) {
struct Node *left, *right, *top;
struct PriorityQueue *pq = build_priority_queue(data, freq);
while (pq->size > 1) {
left = pq->heap[0];
swap_nodes(&pq->heap[0], &pq->heap[pq->size - 1]);
pq->size--;
min_heapify(pq, 0);
right = pq->heap[0];
swap_nodes(&pq->heap[0], &pq->heap[pq->size - 1]);
pq->size--;
min_heapify(pq, 0);
top = new_node('$', left->freq + right->freq);
top->left = left;
top->right = right;
pq->heap[pq->size] = top;
pq->size++;
min_heapify(pq, pq->size - 1);
}
return pq->heap[0];
}
void print_codes(struct Node *root, int arr[], int top) {
if (root->left) {
arr[top] = 0;
print_codes(root->left, arr, top + 1);
}
if (root->right) {
arr[top] = 1;
print_codes(root->right, arr, top + 1);
}
if (is_leaf(root)) {
printf("%c: ", root->ch);
for (int i = 0; i < top; i++) {
printf("%d", arr[i]);
}
printf("\n");
}
}
void huffman_encoding(char *data, int *freq) {
struct Node *root = build_huffman_tree(data, freq);
int arr[MAX_TREE_HT];
int top = 0;
print_codes(root, arr, top);
}
int main() {
char data[] = "hello world";
int freq[strlen(data)];
memset(freq, 0, sizeof(freq));
for (int i = 0; i < strlen(data); i++) {
freq[data[i]]++;
}
huffman_encoding(data, freq);
return 0;
}
```
使用示例:
将以上代码保存为`huffman.c`文件,然后使用以下命令进行编译和运行:
```
gcc huffman.c -o huffman
./huffman
```
输出:
```
h: 0
e: 101
l: 111
o: 100
w: 1100
r: 11011
d: 110100
```
这些编码可以用来对原始数据进行压缩。