(数据结构)哈夫曼编码实现(C语言)
哈夫曼的编码:从一堆数组当中取出来最小的两个值,按照左下右大的进行绘制,将两个权值之和,放入队列当中,然后再进行取出两个小的,以此类推,直到全部结束,在根据图根节点,到叶子节点,每一个分支来得出编码,向左0,向右1,即可得到一个结果。文章来源地址https://www.toymoban.com/news/detail-605256.html
#include <stdio.h>
#include <stdlib.h>
// 定义哈夫曼树结点的结构
struct Node {
int frequency;
char data;
struct Node* left;
struct Node* right;
};
// 创建一个新的哈夫曼树结点
struct Node* newNode(int frequency, char data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->frequency = frequency;
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
struct MinHeap {
int size;
int capacity;
struct Node** array;
};
// 创建最小堆
struct MinHeap* createMinHeap(int capacity) {
struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array = (struct Node**)malloc(capacity * sizeof(struct Node*));
return minHeap;
}
// 交换两个结点的位置
void swapNode(struct Node** a, struct Node** b) {
struct Node* temp = *a;
*a = *b;
*b = temp;
}
// 维护最小堆的性质
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]->frequency < minHeap->array[smallest]->frequency) {
smallest = left;
}
if (right < minHeap->size && minHeap->array[right]->frequency < minHeap->array[smallest]->frequency) {
smallest = right;
}
if (smallest != idx) {
swapNode(&minHeap->array[smallest], &minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}
// 检查最小堆是否只有一个元素
int isSizeOne(struct MinHeap* minHeap) {
return minHeap->size == 1;
}
// 检查结点是否是叶子结点
int isLeaf(struct Node* root) {
return !(root->left) && !(root->right);
}
// 从最小堆中提取最小值(即频率最小的结点)
struct Node* extractMin(struct MinHeap* minHeap) {
struct Node* 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 Node* node) {
++minHeap->size;
int i = minHeap->size - 1;
while (i && node->frequency < minHeap->array[(i - 1) / 2]->frequency) {
minHeap->array[i] = minHeap->array[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->array[i] = node;
}
// 构建哈夫曼树
struct Node* buildHuffmanTree(char data[], int frequency[], int size) {
struct Node *left, *right, *top;
// 创建一个最小堆并初始化
struct MinHeap* minHeap = createMinHeap(size);
// 向最小堆中插入结点
for (int i = 0; i < size; i++) {
insertMinHeap(minHeap, newNode(frequency[i], data[i]));
}
// 构建哈夫曼树
while (!isSizeOne(minHeap)) {
// 从最小堆中取出最小的两个结点作为左子树和右子树
left = extractMin(minHeap);
right = extractMin(minHeap);
// 创建一个新的结点作为父结点
top = newNode(left->frequency + right->frequency, '-');
top->left = left;
top->right = right;
// 将父结点插入最小堆中
insertMinHeap(minHeap, top);
}
// 最后剩下的结点就是哈夫曼树的根结点
return extractMin(minHeap);
}
// 打印哈夫曼编码
void printHuffmanCodes(struct Node* root, int arr[], int top) {
// 叶子结点是存有字符的结点
if (root->left) {
arr[top] = 0;
printHuffmanCodes(root->left, arr, top + 1);
}
if (root->right) {
arr[top] = 1;
printHuffmanCodes(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("\n");
}
}
int main() {
char data[] = { 'a', 'b', 'c', 'd', 'e' };
int frequency[] = { 5, 9, 12, 13, 16 };
int size = sizeof(data) / sizeof(data[0]);
struct Node* root = buildHuffmanTree(data, frequency, size);
int arr[100], top = 0;
printHuffmanCodes(root, arr, top);
return 0;
}
文章来源:https://www.toymoban.com/news/detail-605256.html
到了这里,关于(数据结构)哈夫曼编码实现(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!