这个代码是使用优先队列的方式实现的哈夫曼树
//使用优先级队列实现的哈夫曼编码
#include "stdio.h"
#include "stdlib.h"
#include "string.h"typedef char ElemType;typedef struct TreeNode {ElemType data;int weight;//节点权重struct TreeNode *left;struct TreeNode *right;
} Node;typedef struct node {Node *element;struct node *next;
} linknode_t;typedef struct {linknode_t *front;linknode_t *rear;
} linkqueue_t;linkqueue_t *linkqueue_create() {linkqueue_t *queue = (linkqueue_t *) malloc(sizeof(linkqueue_t));if (queue == NULL) {exit(-1);}queue->front = queue->rear = (linknode_t *) malloc(sizeof(linknode_t));if (queue->front == NULL) {exit(-1);}queue->front->next = NULL;return queue;
}int linkqueue_enter(linkqueue_t *queue, Node *element) {linknode_t *node = (linknode_t *) malloc(sizeof(linknode_t));if (node == NULL) {exit(-1);}node->element = element;node->next = NULL;//这里找位置进行插入linknode_t *pre = queue->front;while (pre->next && pre->next->element->weight <= element->weight) {pre = pre->next;}if (pre == queue->rear) {queue->rear->next = node;queue->rear = node;} else { // 核心在这里node->next = pre->next;pre->next = node;}return 1;
}int linkqueue_empty(linkqueue_t *queue) {return queue->front == queue->rear ? 1 : 0;
}Node *linkqueue_out(linkqueue_t *queue) {if (linkqueue_empty(queue)) {return NULL;}linknode_t *temp = queue->front;queue->front = queue->front->next;Node *value = queue->front->element;free(temp);temp = NULL;return value;
}//创建节点
Node *create_node(ElemType value, int weight) {Node *temp = (Node *) malloc(sizeof(Node));if (temp == NULL) {exit(-1);}temp->data = value;temp->weight = weight;temp->left = temp->right = NULL;return temp;
}// 递归遍历哈夫曼树并生成编码
void generate_huffman_codes(Node *root, char *code, int depth) {if (root == NULL) {return;}// 如果当前节点是叶子节点，打印它的编码if (root->left == NULL && root->right == NULL) {code[depth] = '\0';printf("Char: %c, Huffman Code: %s\n", root->data, code);}// 向左子树递归，编码为'0'if (root->left != NULL) {code[depth] = '0';generate_huffman_codes(root->left, code, depth + 1);}// 向右子树递归，编码为'1'if (root->right != NULL) {code[depth] = '1';generate_huffman_codes(root->right, code, depth + 1);}
}int main() {linkqueue_t *queue = linkqueue_create();linkqueue_enter(queue, create_node('A', 5));linkqueue_enter(queue, create_node('B', 16));linkqueue_enter(queue, create_node('C', 8));linkqueue_enter(queue, create_node('D', 13));/*Node *elem = linkqueue_out(queue);if (elem != NULL) {printf("char %c weight %d\n", elem->data, elem->weight);}elem = linkqueue_out(queue);if (elem != NULL) {printf("char %c weight %d\n", elem->data, elem->weight);}elem = linkqueue_out(queue);if (elem != NULL) {printf("char %c weight %d\n", elem->data, elem->weight);}elem = linkqueue_out(queue);if (elem != NULL) {printf("char %c weight %d\n", elem->data, elem->weight);}*/while (queue->front->next != queue->rear) {Node *left = linkqueue_out(queue);Node *right = linkqueue_out(queue);Node *node = create_node(' ', left->weight + right->weight);node->left = left;node->right = right;linkqueue_enter(queue, node);}Node *root = linkqueue_out(queue);// 生成并打印哈夫曼编码char code[100] = {0}; // 假设编码长度不超过100generate_huffman_codes(root, code, 0);return 0;
}运行效果
