基于哈夫曼编码的文件压缩解压程序的C语言实现

利用无失真信源编码方法中的哈夫曼编码进行程序设计实践，实现对文件的压缩与解压操作。

#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 < n; ++i）           
        if（huf_tree[i].parent == 0 && huf_tree[i].weight < min）{
            min = huf_tree[i].weight;
            *s1 = i;
        }
        huf_tree[*s1].parent=1;   // 标记此结点已被选中
    // 找次小
    min=ULONG_MAX;
    for（i = 0; i < n; ++i）            
        if（huf_tree[i].parent == 0 && huf_tree[i].weight < min）{
            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 < node_num; ++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 < char_kinds; ++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 < 256; ++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