(数据结构)哈夫曼编码实现（C语言）

哈夫曼的编码:从一堆数组当中取出来最小的两个值，按照左下右大的进行绘制，将两个权值之和，放入队列当中，然后再进行取出两个小的，以此类推，直到全部结束，在根据图根节点，到叶子节点，每一个分支来得出编码，向左0，向右1，即可得到一个结果。

#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;
}