//

// 霍夫曼编码

//

#include 

#include 

#include 

/**思路：用一个有序链表（从大到小）来保存节点，然后通过链表来构造霍夫曼树, 再由霍夫曼树得到霍夫曼编码**/

typedef struct huffman_tree_node{

int weight;//权重

char c;//字符 非叶子节点为0

struct 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;

}

//遍历左节点 编码增加一个0

char * leftS = (char *)calloc(len+1, sizeof(char));

str_copy(s, len, leftS);

leftS[len] = '0';

showCode(node->leftHuffmanTreeNode, leftS, len+1);

//遍历右节点 编码增加一个1

char * 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);

}