#include?
#include?
#include?
#include?
//?字符頻度結點
typedef?struct?{
????unsigned?char?uch;??????????
????unsigned?long?weight;???????
}?TmpNode;
//?哈夫曼樹結點
typedef?struct?{
????unsigned?char?uch;??????????????
????unsigned?long?weight;???????????
????char?*code;?????????????????????
????int?parent?lchild?rchild;?????
}?HufNode?*HufTree;
//?選擇最小和次小的兩個結點的函數
void?SelectMinTwo（HufNode?*huf_tree?unsigned?int?n?int?*s1?int?*s2）{
????//?找最小
????unsigned?int?i;
????unsigned?long?min?=?ULONG_MAX;
????for（i?=?0;?i?????????if（huf_tree[i].parent?==?0?&&?huf_tree[i].weight?????????????min?=?huf_tree[i].weight;
????????????*s1?=?i;
????????}
????????huf_tree[*s1].parent=1;???//?標記此結點已被選中
????//?找次小
????min=ULONG_MAX;
????for（i?=?0;?i?????????if（huf_tree[i].parent?==?0?&&?huf_tree[i].weight?????????????min?=?huf_tree[i].weight;
????????????*s2?=?i;
????????}
}?
//?建立哈夫曼樹
void?CreateTree（HufNode?*huf_tree?unsigned?int?char_kinds?unsigned?int?node_num）{
????unsigned?int?i;
????int?s1?s2;
????for（i?=?char_kinds;?i?????????SelectMinTwo（huf_tree?i?&s1?&s2）;????????//?選擇最小的兩個結點
????????huf_tree[s1].parent?=?huf_tree[s2].parent?=?i;?
????????huf_tree[i].lchild?=?s1;?
????????huf_tree[i].rchild?=?s2;?
????????huf_tree[i].weight?=?huf_tree[s1].weight?+?huf_tree[s2].weight;?
????}?
}
//?生成哈夫曼編碼
void?HufCode（HufNode?*huf_tree?unsigned?char_kinds）{
????unsigned?int?i;
????int?cur?next?index;
????char?*code_tmp?=?（char?*）malloc（256*sizeof（char））;
????code_tmp[256-1]?=?‘\0‘;?
????for（i?=?0;?i?????????index?=?256-1;
????????for（cur?=?i?next?=?huf_tree[i].parent;?next?!=?0;?
????????????cur?=?next?next?=?huf_tree[next].parent）??
????????????if（huf_tree[next].lchild?==?cur）?
????????????????code_tmp[--index]?=?‘0‘;????//?左‘0’
????????????else?
????????????????code_tmp[--index]?=?‘1‘;????//?右‘1’
????????huf_tree[i].code?=?（char?*）malloc（（256-index）*sizeof（char））;????????
????????strcpy（huf_tree[i].code?&code_tmp[index]）;?
????}?
????free（code_tmp）;?
}
//?壓縮函數
int?compress（char?*ifname?char?*ofname）{
????unsigned?int?i?j;
????unsigned?int?char_kinds;????????
????unsigned?char?char_temp;??//?暫存8bits字符
????unsigned?long?file_len?=?0;
????FILE?*infile?*outfile;
????TmpNode?node_temp;
????unsigned?int?node_num;
????HufTree?huf_tree;
????char?code_buf[256]?=?“\0“;??????
????unsigned?int?code_len;
????TmpNode?*tmp_nodes?=（TmpNode?*）malloc（256*sizeof（TmpNode））;?????
????//?初始化暫存結點
????for（i?=?0;?i?????????tmp_nodes[i].weight?=?0;
????????tmp_nodes[i].uch?=?（unsigned?char）i;??//?數組的256個下標與256種字符對應
????}
????infile?=?fopen（ifname?“rb“）;
????if?（infile?==?NULL）
????????return?-1;
????fread（（char?*）&char_temp?sizeof（unsigned?char）?1?infile）;????????//?讀入一個字符
????while（!feof（infile））{
????????++tmp_nodes[char_temp].weight;??//?統計下標

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件???????10535??2018-06-01?23:26??huffman.c