符号表结构体：

struct node{    // 字符串形式存储的Huffman编码    char code[MAX_CODE_LENGTH];    // 这个字符在文件中出现的次数    long count;    // 在生成Huffman树的时候是否已经被当作叶子节点    int checked;    // 符号    char sym;    // left和right只在生成Huffman树的时候有用    struct node* next,*left,*right;};

全局变量：

const int BIT_WIDTH_CHAR = 8;const int END_SYM_FLAG = 200;// 符号的范围是-127~128int gl_total_node_num = 0;// 符号表的总长度int gl_source_file_length = 0;// 源文件的总长度

辅助函数：

// 在链表中查找指定的字符// 参数：符号表// 参数：字符// 返回值：找到的节点的指针struct node* content_char(struct node*,char);// 在链表中查找指定编码// 参数：符号表// 参数：编码// 返回值：找到的节点的指针struct node* content_code(struct node* list,const char* ch);// 根据字符创建一个新的节点// 参数：字符// 参数：计数// 返回值：新节点指针struct node* create_new_node(char ch,int count);// 插入新节点到符号表的最前面// 参数list：目标链表// 参数new_node：新节点// 返回值：插入后的链表struct node* insert_node(struct node *list,struct node *new_node);// 输出链表// 参数list：目标链表void print_list(struct node *list);// 获取到最小的未被检查的count的节点，返回它的指针，并将其设置为检查过的// 参数list_addr：链表头// 返回值：第一个未检查的最少出现次数的结点指针struct node* get_smallest_node(struct node *list_addr);

压缩：

第一步：建立符号表

在main函数中：获取文件的总长度，用于生成进度条

// 获取文件长度，以实现进度条fseek(source_file,0,SEEK_END);gl_source_file_length = ftell(source_file);fseek(source_file,0,SEEK_SET);

扫描源文件，按字符读取，建立符号表，统计每个字符出现的次数

首先提示进度条，10个'.'为结束

将读取到的字符在已有的符号表中查找，如果已存在就将该节点的count+1，否则就创建新节点并插入到符号表中

统计符号表中总节点数

// 生成符号链表（含频率）// 参数：源文件// 参数：目标链表// 返回值：符号链表struct node* generate_count(FILE* f,struct node*list){    printf("counting");    int count=0;        char ch;    struct node *content_node;    while(fread(&ch,sizeof(char),1,f)==1)    {        // 进度条        count++;        if(count%(gl_source_file_length/10+1)==0)            printf(".");                // 插入符号表        content_node = content_char(list,ch);        if(content_node)            content_node->count++;        else         {            gl_total_node_num++;            list=insert_node(list,create_new_node(ch,1));        }    }    printf("\n");    return list;}

第二步：生成Huffman树

生成Huffman树

使用先前统计的符号表总数进行计数循环，因为生成树的所有非叶子节点共有叶子节点-1个

首先输出进度条

视初始时所有的符号表中的节点为只有一个节点的子树，获取两个最小的count的子树根节点指针，这是通过节点的checked属性实现的，如果使用了两个子树根节点生成新的子树，那么这两个子树根节点的checked将会设为1，在寻找最小节点的时候将会跳过

将新的树的中间节点插入到符号表中

最终的效果是符号表中只有最前面的一个节点的checked为0

// 生成Huffman树// 参数：符号链表// 返回值：含有Huffman树的链表，非叶节点将插入到链表前面，并有左右孩子属性，叶节点没有左右孩子属性struct node* generate_tree(struct node* list){    printf("generate_tree");    // 生成树    for(int i=1;i
    
     count+sm_right->count);        new_node->left=sm_left;        new_node->right=sm_right;        list = insert_node(list,new_node);    }    printf("\n");    return list;}
    

第三步：生成编码

从Huffman树中生成符号表的编码属性

因为这是一棵树，所以用递归的方式进行

某节点的左孩子的编码将在继承其父节点编码的基础上扩展'0'，右孩子将在继承其父节点的编码的基础上扩展'1'

最终所有叶子节点的编码就是Huffman编码

// 递归的生成Huffman编码于符号链表// 参数：Huffman树void generate_code(struct node*list){    // 生成Huffman编码    if(!list)return;    // 左子树扩展'0'    if(list->left)    {        strcat(list->left->code,list->code);        strcat(list->left->code,"0");        generate_code(list->left);    }    // 右子树'1'    if(list->right)    {        strcat(list->right->code,list->code);        strcat(list->right->code,"1");        generate_code(list->right);    }}

因为之后树就没什么用了，只有叶子节点有用，所以将其他节点释放掉

// 释放Huffman树的非叶子节点，只留下符号链表// 参数：Huffman树// 返回值：不含Huffman树的符号链表struct node* free_tree(struct node*list){    struct node*free_node=list;    while(list->left && list->right)// 左右子树不为空的节点都是需要释放的    {        free_node=list;        list=list->next;        free(free_node);    }    return list;}

第四步：生成目标文件

首先将符号表写入到目标文件头部，再次扫描源文件，将每个字符转换为对应的编码，并以二进制的形式存储在目标文件中

// 生成目标文件// 参数：源文件// 参数：目标文件// 参数：符号链表void generate_des_file(FILE* sf,FILE* df,struct node*list)

首先，为了解压，要把符号表的内容写入到目标文件前面

其中符号和编码时两两配对的，最后通过一个符号表不可能取到的值标记结束

标识符之间是通过空格隔开，最终结束时以换行符结尾。这里的规则将在解压的时候需要严格遵守

// 符号表以文本形式写入到目标文件的前端，解压时需要的信息struct node* index=list;while(index){    fprintf(df,"%d %s ",index->sym,index->code);    index=index->next;}// 指示结尾，"END"实际上没有用到，只用于和END_SYM_FLAG配对fprintf(df,"%d %s\n",END_SYM_FLAG,"END");

变量：

// 实际文件内容（二进制形式）// 前者是从源文件中读取的字符，后置是对Huffman编码进行二进制形式转换后取8位形成的字符char ch,des_ch='\0';// 目标字符知否足够8位可以进行写入？int des_ch_length=0;// 因为之前进行了读取，所以这里回到文件头fseek(sf,0,SEEK_SET);int count=0;// 程序执行进度提示

while循环读文件：

while(fread(&ch,sizeof(char),1,sf)==1)

输出进度条，并根据从源文件中读取的字符找符号表中对应的节点

// 进度条count++;if(count%(gl_source_file_length/10+1)==0)    printf(".");// 在符号表中找这个字符// 没有找到一定是出错了struct node *content_node = content_char(list,ch);if(!content_node){    printf("error:cannot match with sym list\n");    exit(0);}

现在需要将符号对应的字符串Huffman编码转化为一个个8位char类型，其中每一位代表一位Huffman编码

对这个编码每一位循环处理：将已经部分生成的目标字符左移一位，如果当前的编码位为1就用掩码0000 0001和目标字符按位或，那么最后一位将为1，其余不变，当前编码位为0就不做操作，因为本来左移就补0

当记录的长度达到8的时候就将这个字符写入到目标文件，将记录长度清零，继续对编码的每一位循环

// 对这个符号对应的Huffman编码进行二进制转化char* current_code=content_node->code;for(int i=0;i

但是最后一位不一定够8位，这需要额外的说明

将剩下的这个字符左对齐，并在目标文件的最后一个字符说明前一个字符有几位有效

// 最后一个字符，没有满足8位if(des_ch_length!=0){    des_ch=des_ch<

 

解压：

第一步：从目标文件读取符号表

首先从源文件头读取并创建符号表

值得注意的是读取字符串的时候用fscanf将会在遇到空格的时候结束，而用其他的方式将会在换行符时结束，但是我们在生成的时候全都生成在一行

在读取结束的时候需要将换行符读掉，否则接下来将会读到换行符并解析

// 获取文件头的符号表// 参数：源文件// 返回值：符号表struct node* de_get_sym_list(FILE* f){    printf("getting sym list...\n");        char code[MAX_CODE_LENGTH];    int ch_int;    struct node* list=NULL;        fscanf(f,"%d %s",&ch_int,code);    // 如果没有读到结束标志    while(ch_int!=END_SYM_FLAG)    {        // 创建新节点并插入符号表        struct node* new_node=create_new_node((char)ch_int,0);        strcpy(new_node->code,code);        list=insert_node(list,new_node);        fscanf(f,"%d %s",&ch_int,code);    }    fgetc(f);// 将换行符读掉，按照生成的规则，最后是一个换行符    return list;}

第二步：解析压缩内容

// 生成解压后的文件// 参数：源文件// 参数：目标文件// 参数：符号链表void de_generate_des_file(FILE* sf,FILE* df,struct node* list)

变量：

// 存储未形成一个有效的Huffman编码的字符串char temp_code[MAX_CODE_LENGTH] = {'\0'};int last_length;// 最后一个字符的有效位长度// 分别指向实际的压缩内容（去除头部的符号表）的头和尾long current_file_index,file_length;// 位操作的掩码，首位为1其余为0char mask=((char)1)<

对文件的长度进行测量，并将最后一个字符有效位数读取进来，如果不记录长度，在之后的循环读取中想要跳过最后一个符号将会有些麻烦

记得要将文件的游标移动到合适的位置

// 记录此时符号表读取结束的位置current_file_index = ftell(sf);// 从文件尾获取最后一个字符的长度，以及文件的长度fseek(sf,-(sizeof(char)),SEEK_END);file_length = ftell(sf);last_length = fgetc(sf)-'0';// 回复当前位置到符号表结束的位置fseek(sf,current_file_index,SEEK_SET);

因为已知了长度，所以读文件的时候可以计数循环，而不是检测文件尾。跳过最后一个字符（当然，这里的最后一个不包括后面的那个表示它的有效位数的数字字符）

for(int i=current_file_index;i

首先时进度条，并进行读取：

// 进度条if(i%((file_length-current_file_index)/10+1)==0)    printf(".");// 读取是否成功if(fread(&ch,sizeof(char),1,sf)!=1){    if(ferror(sf))        printf("error:cannot read file.\n");    if(feof(sf))        printf("end of reading file.\n");    exit(0);}

对这个字符的每一位循环，将这个位转化为字符形式扩展到已有的字符串上，每扩展一位就检测一下符号表中有没有这个编码，有了就将对应的字符输出到文件中，并将字符串清空

位操作需要获取的是第一个位，所以掩码是第一位为1其余为0，按位与将获取第一个位：非0为1，0为0

// 将这一个字符的每一位扩展到未竟的Huffman编码上for(int j=0;j
    
     sym),sizeof(char),1,df)!=1)        {            printf("error:failed to write file.\n");            exit(0);        }        // 清零临时字符串        temp_code[0]='\0';    }// 如果在符号表中找到}// 对一个字符的每一位
    

最后一个字符，利用之前的长度进行循环，而不是8位

// 最后一个字符if(fread(&ch,sizeof(char),1,sf)!=1){    printf("error:cannot read file.\n");    exit(0);}for(int i=0;i
    
     sym),sizeof(char),1,df)!=1)        {            printf("error:failed to write file.\n");            exit(0);        }        // 清零临时字符串        temp_code[0]='\0';    }// 如果在符号表中找到}
    

辅助函数：

// 根据字符创建一个新的节点// 参数：字符// 参数：计数// 返回值：新节点指针struct node* create_new_node(char ch,int count){    struct node *new_node = (struct node*)malloc(sizeof *new_node);    if(!new_node)    {        printf("error:failed to malloc.\n");        exit(0);    }    new_node->code[0]='\0';    new_node->sym=ch;    new_node->count=count;    new_node->next=NULL;    new_node->checked=0;    new_node->left=NULL;    new_node->right=NULL;    return new_node;}

 

// 插入新节点// 参数list：目标链表// 参数new_node：新节点// 返回值：插入后的链表struct node* insert_node(struct node *list,struct node *new_node){    if(list)        new_node->next=list;    return new_node;}

 

// 获取到最小的未被检查的count的节点，返回它的指针，并将其设置为检查过的// 参数list_addr：链表头// 返回值：第一个未检查的最少出现次数的结点指针struct node* get_smallest_node(struct node *list){    while(list && list->checked)list=list->next;// 获取到首个未检查的节点    struct node *smallest=list;    // 获取到最小的count的节点    while(list)    {        if(!list->checked && (list->count < smallest->count))            smallest=list;        list=list->next;    }    if(smallest)smallest->checked++;    return smallest;}

执行程序：

我用的是Windows10下的gcc编译器，命令行执行，并通过命令行参数传递源文件名和目的文件名

编译：gcc Huffman.c -o Huffman.exe

执行：Huffman.exe sourcefile desfile

执行之后会询问是执行压缩还是解压还是结束程序

执行压缩会把源文件压缩另存为目的文件

解压会将源文件解压另存为目的文件

需要注意的问题：

文件打开的时候是要用二进制流的形式打开，因为要对其进行位操作。如果用文本模式打开，在解压非文本文件的时候在中途程序就可能会认为自己读到的是EOF而结束读取。

因为符号是char类型的字符，所以符号表最大是256，编码的长度最长为255

将char解释为int类型时其取值范围为-127~128，所以想要标记压缩文件中符号表内容的结束，需要用这个范围之外的数

源码地址：