//// 霍夫曼编码//#include <stdio.h>#include <stdlib.h>#include <string.h>/**思路：用一个有序链表（从大到小）来保存节点，然后通过链表来构造霍夫曼树, 再由霍夫曼树得到霍夫曼编码**/typedef struct huffman_tree_node{int weight;//权重char c;//字符 非叶子节点为0struct huffman_tree_node * nextHuffmanTreeNode;//链表下一个节点struct huffman_tree_node * leftHuffmanTreeNode;//左节点struct huffman_tree_node * rightHuffmanTreeNode;//右节点}HuffmanTreeNode; //霍夫曼树节点typedef struct huffman_code{char *s;//编码 如 010， 00， ....int len;//编码长度char c;//字符}HuffmanCode; //霍夫曼编码（可以用来保存结果）/*** 创建一个节点* @param c 字符* @param weight 权重* @return*/HuffmanTreeNode * createHuffmanTreeNode(char c, int weight){HuffmanTreeNode * node = (HuffmanTreeNode *)calloc(1, sizeof(HuffmanTreeNode));node->c = c;node->weight = weight;node->nextHuffmanTreeNode = NULL;node->leftHuffmanTreeNode = NULL;node->rightHuffmanTreeNode = NULL;return node;}/*** [insert 插入节点到有序链表中]* @param h [头节点指针]* @param s [要插入的节点]* @return [头节点]*/static HuffmanTreeNode * insert(HuffmanTreeNode * h, HuffmanTreeNode * s){if(h == NULL){ //插入第一个节点时 没有头节点return s;//s作为头节点}if(s->weight > h->weight){s->nextHuffmanTreeNode = h; //s作为头节点return s;}HuffmanTreeNode * tempHuffmanTreeNode = h; //中间变量 用于遍历HuffmanTreeNode * preHuffmanTreeNode = tempHuffmanTreeNode;//中间变量的前一个节点while(tempHuffmanTreeNode != NULL){if(s->weight < tempHuffmanTreeNode->weight){ //要插入的节点的学号比当前节点小preHuffmanTreeNode = tempHuffmanTreeNode;tempHuffmanTreeNode = tempHuffmanTreeNode->nextHuffmanTreeNode;continue;}//插入到中间preHuffmanTreeNode->nextHuffmanTreeNode = s;s->nextHuffmanTreeNode = tempHuffmanTreeNode;break;}if(tempHuffmanTreeNode == NULL){ //插入的节点比已有的节点都小preHuffmanTreeNode->nextHuffmanTreeNode = s;}return h;}/*** 移除最后一个节点（最小的那个） 并返回* @param node* @return*/HuffmanTreeNode * removeLastHuffmanTreeNode(HuffmanTreeNode * h){HuffmanTreeNode * tempHuffmanTreeNode = h; //中间变量 用于遍历HuffmanTreeNode * preHuffmanTreeNode = tempHuffmanTreeNode;//中间变量的前一个节点while(tempHuffmanTreeNode->nextHuffmanTreeNode != NULL){preHuffmanTreeNode = tempHuffmanTreeNode;tempHuffmanTreeNode = tempHuffmanTreeNode->nextHuffmanTreeNode;}preHuffmanTreeNode->nextHuffmanTreeNode = NULL;return tempHuffmanTreeNode;}/*** 链表转霍夫曼树* @param head* @return*/HuffmanTreeNode * createTree(HuffmanTreeNode * head){if(head == NULL){return NULL;}while (1){//获取最小的两个节点HuffmanTreeNode * node1 = removeLastHuffmanTreeNode(head);if(node1 == head){ //只有一个节点了 完成return node1;}HuffmanTreeNode * node2 = removeLastHuffmanTreeNode(head);if(node2 == head){ //最后一个节点head = NULL; //头节点置为NULL}//创建一个新的节点HuffmanTreeNode * newNode = createHuffmanTreeNode(0, node1->weight+node2->weight);//设置左节点newNode->leftHuffmanTreeNode = node1->weight <= node2->weight ? node1 : node2;//设置右节点newNode->rightHuffmanTreeNode = node1->weight <= node2->weight ? node2 : node1;//新节点插入到链表中，再次循环 直到链表中只有一个节点head = insert(head, newNode);}}/*** 字符串拷贝* @param s* @param len* @param dest*/void str_copy(char *s,int len ,char *dest){for(int i = 0; i < len; i++){dest[i] = s[i];}}/*** 霍夫曼编码* @param node 节点* @param s 编码的字符串 如 001,00,01...* @param len 编码字符串的长度*/void showCode(HuffmanTreeNode * node, char *s, int len){if(node->c != 0){ //到叶子节点了//打印编码结果（或保存到结构体中）：printf("%c->%s\n", node->c, s);free(s);return;}//遍历左节点 编码增加一个0char * leftS = (char *)calloc(len+1, sizeof(char));str_copy(s, len, leftS);leftS[len] = '0';showCode(node->leftHuffmanTreeNode, leftS, len+1);//遍历右节点 编码增加一个1char * rightS = (char *)calloc(len+1, sizeof(char));str_copy(s, len, rightS);rightS[len] = '1';showCode(node->rightHuffmanTreeNode, rightS, len+1);free(s);}int main(){//创建节点HuffmanTreeNode * head = NULL;HuffmanTreeNode * node_a = createHuffmanTreeNode('A', 5);HuffmanTreeNode * node_b = createHuffmanTreeNode('B', 4);HuffmanTreeNode * node_c = createHuffmanTreeNode('C', 3);HuffmanTreeNode * node_d = createHuffmanTreeNode('D', 2);HuffmanTreeNode * node_e = createHuffmanTreeNode('E', 1);//插入到有序链表中head = insert(head,node_a);head = insert(head,node_b);head = insert(head,node_c);head = insert(head,node_d);head = insert(head,node_e);//转霍夫曼树HuffmanTreeNode *tree = createTree(head);printf("huffman encode:\n");//获取编码char * s = (char*)malloc(0);showCode(tree, s, 0);}
