霍夫曼编码树状图

以下是 c 语言实现

的

：

 #include <stdio.h> #include <stdlib.h> #include <string.h>  #define MAX_TREE_HT 100  struct node { int freq; char data; struct node* left; struct node* right; };  struct priority_queue { int size; int capacity; struct node array; };  // 创建一个新节点 struct node* new_node(char data, int freq) { struct node* temp = (struct node*)malloc(sizeof(struct node)); temp->left = NULL; temp->right = NULL; temp->data = data; temp->freq = freq; return temp; }  // 创建一个优先队列 struct priority_queue* create_priority_queue(int capacity) { struct priority_queue* pq = (struct priority_queue*)malloc(sizeof(struct priority_queue)); pq->size = 0; pq->capacity = capacity; pq->array = (struct node)malloc(pq->capacity * sizeof(struct node*)); return pq; }  // 交换两个节点 void swap(struct node a, struct node b) { struct node* t = *a; *a = *b; *b = t; }  // 下滤操作 void min_heapify(struct priority_queue* pq, int index) { int smallest = index; int left = 2 * index + 1; int right = 2 * index + 2; if (left < pq->size && pq->array[left]->freq < pq->array[smallest]->freq) { smallest = left; } if (right < pq->size && pq->array[right]->freq < pq->array[smallest]->freq) { smallest = right; } if (smallest != index) { swap(&pq->array[smallest], &pq->array[index]); min_heapify(pq, smallest); } }  // 判断队列是否为空 int is_empty(struct priority_queue* pq) { return pq->size == 0; }  // 取出队列中最小的节点 struct node* extract_min(struct priority_queue* pq) { struct node* node = pq->array[0]; pq->array[0] = pq->array[pq->size - 1]; pq->size--; min_heapify(pq, 0); return node; }  // 将节点插入队列中 void insert(struct priority_queue* pq, struct node* node) { pq->size++; int i = pq->size - 1; while (i && node->freq < pq->array[(i - 1) / 2]->freq) { pq->array[i] = pq->array[(i - 1) / 2]; i = (i - 1) / 2; } pq->array[i] = node; }  // 建造哈夫曼 树 struct node* build_huffman_tree(char data[], int freq[], int size) { struct node *left, *right, *top; struct priority_queue* pq = create_priority_queue(size); for (int i = 0; i < size; i++) { insert(pq, new_node(data[i], freq[i])); } while (!is_empty(pq) && pq->size > 1) { left = extract_min(pq); right = extract_min(pq); top = new_node('$', left->freq + right->freq); top->left = left; top->right = right; insert(pq, top); } return extract_min(pq); }  // 打印 哈夫曼编码 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 (!root->left && !root->right) { printf("%c: ", root->data); for (int i = 0; i < top; i++) { printf("%d", arr[i]); } printf(" "); } }  // 哈夫曼编码 void huffman_encoding(char data[], int freq[], int size) { struct node* root = build_huffman_tree(data, freq, size); int arr[MAX_TREE_HT], top = 0; print_codes(root, arr, top); }  int main() { char data[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; int freq[] = { 5, 9, 12, 13, 16, 45 }; int size = sizeof(data) / sizeof(data[0]); huffman_encoding(data, freq, size); return 0; } 

在

中，`create_priority_queue()` 函数用于创建优先队列，`new_node()` 函数用于创建新的节点，`swap()` 函数用于交换两个节点，`min_heapify()` 函数用于下滤操作，`is_empty()` 函数用于判断队列是否为空，`extract_min()` 函数用于取出队列中最小的节点，`insert()` 函数用于将节点插入队列中，`build_huffman_tree()` 函数用于建造哈夫曼

，`print_codes()` 函数用于打印

，`huffman_encoding()` 函数用于执行

。

在 `main()` 函数中，我们定义了一个字符数组 `data` 和一个频率数组 `freq`，用于存储待编码的字符及其频率。然后，我们计算出 `data` 数组的大小，并调用 `huffman_encoding()` 函数进行

。

运行程序，即可输出各个字符的

。

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/7095.html