首页 🏳️‍🌈CTF

完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

// 哈夫曼树结点
typedef struct {
    int parent, lchild, rchild;     //双亲,左右孩子
    unsigned char uch;                //8bits字符,处理单元
    unsigned long weight;            //权值--字频 
    char *code;                        //字符->Hufcode 
} HufNode, *HufTree;

// FeqNode临时存放字符频度的统计
typedef struct {
    unsigned char uch;            
    unsigned long weight;        
} FeqNode;


// 选择最小和次小的两个结点,建立哈夫曼树调用
void selectMinTwo(HufNode *huffmantree, unsigned int n, int *left, int *right)
{
    /*找最小节点*/
    unsigned int i;
    unsigned long min = ULONG_MAX;
    for(i = 0; i < n; ++i)           
        if(huffmantree[i].parent == 0 && huffmantree[i].weight < min)
        {
            //循环时查看是否访问过标记
            min = huffmantree[i].weight;
            *left = i;
        }
        /*此节点已被访问过标记1*/
        huffmantree[*left].parent=1;   

    /*找次小节点*/
    min=ULONG_MAX;
    for(i = 0; i < n; ++i)            
        if(huffmantree[i].parent == 0 && huffmantree[i].weight < min)
        {
            min = huffmantree[i].weight;
            *right = i;
        }
} 

// 创建哈夫曼树
void createhufTree(HufNode *huffmantree, unsigned int classi, unsigned int node_num)
{
    unsigned int i;
    int left, right;
    for(i = classi; i < node_num; ++i)  
    { 
        /*选择最小两节点*/
        selectMinTwo(huffmantree, i, &left, &right);        
        /*建立双亲节点i*/
        huffmantree[left].parent = huffmantree[right].parent = i; 
        huffmantree[i].lchild = left; 
        huffmantree[i].rchild = right; 
        huffmantree[i].weight = huffmantree[left].weight + huffmantree[right].weight; 
    } 
}

// 生成哈夫曼编码
void generatehufCode(HufNode *huffmantree, unsigned classi)
{
    unsigned int i;
    int now, next, index;
    /*动态分配256个叶子节点的字符编码*/
    char *code_temp = (char *)malloc(256*sizeof(char));        
    code_temp[255] = '\0';  //编码结束符 

    for(i = 0; i < classi; ++i) 
    {
        index = 255;    //索引初始化,从叶子节点开始
        /*从叶子节点出发,向根节点遍历,当前位置i,下一位置i的双亲节点,循环条件next不为空*/
        for(now = i, next = huffmantree[i].parent; next != 0; 
            now = next, next = huffmantree[next].parent) 
            /*左0右1*/ 
            if(huffmantree[next].lchild == now) 
                code_temp[--index] = '0';    
            else 
                code_temp[--index] = '1';    
                /*为第i个节点的字符编码动态分配内存空间*/
        huffmantree[i].code = (char *)malloc((256-index)*sizeof(char));     //为第i个字符编码分配空间    
        strcpy(huffmantree[i].code, &code_temp[index]);     //从code_temp复制编码到huffmantree[i] 
        printf("%3d  %3c  length:%2d  code:%s\n",huffmantree[i].uch,huffmantree[i].uch,255-index,&code_temp[index]);
    } 
    //释放暂存编码空间
    free(code_temp);        
}

/*压缩函数
**包含文件字频统计
**根据哈夫曼树的结构--num_node=num_leaf*2-1
*num_leaf->字符种类总数*/
int compression(char *in_name, char *out_name)
{
    unsigned int i, j;            //排序控制
    unsigned int classi;          //字符种数
    unsigned char char_temp;      //暂存8bits字符
    unsigned long file_len = 0;   //文件初始长度
    unsigned long after_len = 0;  //编码后文件长度
    unsigned int node_num;        //节点数
    unsigned int code_len;        //编码长度
    char buff[256] = "\0";          //待存编码缓冲区
    FILE *in_file, *out_file;
    FeqNode nodestore;
    HufTree huffmantree;
    /*动态分配256个节点,暂存字频,统计拷贝到树节点后再释放*/
    FeqNode *tmp_node =(FeqNode *)malloc(256*sizeof(FeqNode));        

    //初始化,字符数组下标与字符对应
    for(i = 0; i < 256; ++i)
    {
        tmp_node[i].weight = 0;
        tmp_node[i].uch = (unsigned char)i;        // 数组的256个下标与256种字符对应
    }

    /**关键部分**/
    //读取文件,获取字频
    in_file = fopen(in_name, "rb");
    //在开始扫描前,先判断文件是否存在
    if (in_file == NULL)
        return -1;
    fread((char *)&char_temp, sizeof(unsigned char), 1, in_file);        //开始读入一个字符
    while(!feof(in_file))
    {
        ++tmp_node[char_temp].weight;        //利用字符数组下表为索引
        ++file_len;
        /*printf("%d",file_len);*/
        fread((char *)&char_temp, sizeof(unsigned char), 1, in_file);        //每次循环完成前再读入一个字符
    }
    fclose(in_file);

    // 排序
    for(i = 0; i < 255; ++i)           
        for(j = i+1; j < 256; ++j)
            if(tmp_node[i].weight < tmp_node[j].weight)
            {
                nodestore = tmp_node[i];
                tmp_node[i] = tmp_node[j];
                tmp_node[j] = nodestore;
            }

    //统计出现频率不为0的字符种类数
    for(i = 0; i < 256; ++i)
        if(tmp_node[i].weight == 0) 
            break;
    classi = i;

    if (classi == 1) /*只有一种字符的情况*/
    {
        out_file = fopen(out_name, "wb");                    //打开待写入的文件
        //引用
        fwrite((char *)&classi, sizeof(unsigned int), 1, out_file);        //写入种类数
        fwrite((char *)&tmp_node[0].uch, sizeof(unsigned char), 1, out_file);        //写入字符
        fwrite((char *)&tmp_node[0].weight, sizeof(unsigned long), 1, out_file);       //写入权值--字符频度--文件长度
        /*释放用来统计字频的暂存空间*/
        free(tmp_node);
        fclose(out_file);
    }
    else
    {
        /*如果字符种类大于1,根据它算出建立哈夫曼树所需的节点数,节约动态分配的空间*/
        node_num = 2 * classi - 1;         
        huffmantree = (HufNode *)malloc(node_num*sizeof(HufNode));        //哈夫曼树节点分配  

        /*循环遍历所有字符种类,将字频暂存节点存入树节点*/
        for(i = 0; i < classi; ++i) 
        { 
            // 将暂存结点的字符和频度拷贝到树结点
            huffmantree[i].uch = tmp_node[i].uch; 
            huffmantree[i].weight = tmp_node[i].weight;
            huffmantree[i].parent = 0;  //初始化叶子节点
        }    
        /*释放用来统计字频的暂存空间*/
        free(tmp_node); 

        /*初始化非叶子节点*/
        for(; i < node_num; ++i) 
            huffmantree[i].parent = 0; 

        /*创建哈夫曼树*/
        createhufTree(huffmantree, classi, node_num);        
        /*生成对应的哈夫曼编码*/
        generatehufCode(huffmantree, classi);        

        /*将字符种类 字符 权值写入压缩文件,供下一步解压使用*/
        out_file = fopen(out_name, "wb");                    //打开待写入的文件
        fwrite((char *)&classi, sizeof(unsigned int), 1, out_file);        //写入种类数
        for(i = 0; i < classi; ++i)
        {
            fwrite((char *)&huffmantree[i].uch, sizeof(unsigned char), 1, out_file);            //写入该类别所对应的字符
            fwrite((char *)&huffmantree[i].weight, sizeof(unsigned long), 1, out_file);        //写入该类别所对应的权值
        }

        /**关键部分**/
        /*写入信息文件长度和字符编码*/
        fwrite((char *)&file_len, sizeof(unsigned long), 1, out_file);        //写入文件长度
        in_file = fopen(in_name, "rb");        //二进制 允许读写 打开待压缩的文件
        fread((char *)&char_temp, sizeof(unsigned char), 1, in_file);     //先读8bits 
        while(!feof(in_file))
        {
            /*字符->编码*/
            for(i = 0; i < classi; ++i){
                if(char_temp == huffmantree[i].uch)
                    strcat(buff, huffmantree[i].code);
                /*printf("%s",buff);*/
            }
            /*以8bits为一个处理单元*/
            while(strlen(buff) >= 8)
            {
                /*清空字符的暂存空间*/
                char_temp = '\0';        
                /*存编码*/
                for(i = 0; i < 8; ++i)
                {
                    char_temp <<= 1;        //补0
                    if(buff[i] == '1')
                        char_temp |= 1;        //如果编码为1,添加到最低位
                }
                /*写入字节->编码*/
                fwrite((char *)&char_temp, sizeof(unsigned char), 1, out_file);        
                /*strcat(buff+8, buff);?*/
                strcpy(buff, buff+8);    //回收缓存
                after_len++;  //文件长度递加1
            }
            fread((char *)&char_temp, sizeof(unsigned char), 1, in_file);     //再读8bits
        }
        //最后一组不满8bits的编码
        code_len = strlen(buff);
        if(code_len > 0)
        {
            char_temp = '\0';        
            for(i = 0; i < code_len; ++i)
            {
                char_temp <<= 1;        
                if(buff[i] == '1')
                    char_temp |= 1;
            }
            after_len++;
            char_temp <<= 8-code_len;       //左移
            /*将最后这一部分写入*/
            fwrite((char *)&char_temp, sizeof(unsigned char), 1, out_file);     
            after_len+=12+node_num;
            printf("\nCompression rate:%.2lf%c\n",(double)((file_len -after_len) / (double)file_len) * 100.0, '%');
        }

        //close
        fclose(in_file);
        fclose(out_file);

        //free
        for(i = 0; i < classi; ++i)
            free(huffmantree[i].code);
        free(huffmantree);
    }
}



/*解压缩*/
int Decompression(char *in_name, char *out_name)
{
    unsigned int i;
    unsigned int classi;          //存储字符种类
    unsigned char store;          //暂存8bits编码
    unsigned long file_len;       //文件初始长度
    unsigned long length = 0;      //文件写入长度
    unsigned int node_num;        //节点个数
    unsigned int root;              //根节点索引
    FILE *in_file, *out_file;
    HufTree huffmantree;
    /*二进制 读写 打开压缩文件*/
    in_file = fopen(in_name, "rb");        
    //在开始扫描前,先判断文件是否存在
    if (in_file == NULL)
        return -1;

    //读取上一步操作中写入的字符种类
    fread((char *)&classi, sizeof(unsigned int), 1, in_file);     /*跟压缩时的思路一样,先判断字符种类个数,提高执行效率*/
    if (classi == 1)
    {
        fread((char *)&store, sizeof(unsigned char), 1, in_file);     // 读取唯一种的字符
        fread((char *)&file_len, sizeof(unsigned long), 1, in_file);     // 读取文件长度
        out_file = fopen(out_name, "wb");                    // 打开解压后将生成的文件
        while (file_len--)
            fwrite((char *)&store, sizeof(unsigned char), 1, out_file);    
        fclose(in_file);
        fclose(out_file);
    }
    else
    {
        node_num = 2 * classi - 1;        //根据字符种类计算节点总数
        huffmantree = (HufNode *)malloc(node_num*sizeof(HufNode)); //哈夫曼树节点分配    

        //初始化节点
        /*前classi个*/
        for(i = 0; i < classi; ++i)     
        {
            fread((char *)&huffmantree[i].uch, sizeof(unsigned char), 1, in_file);        // 读入字符
            fread((char *)&huffmantree[i].weight, sizeof(unsigned long), 1, in_file);    // 读入字符对应权重
            huffmantree[i].parent = 0;
        }
        /*后node_num-classi个*/
        for(; i < node_num; ++i) 
            huffmantree[i].parent = 0;

        //重新创建哈夫曼树
        createhufTree(huffmantree, classi, node_num);        

        //读取文件长度
        fread((char *)&file_len, sizeof(unsigned long), 1, in_file);
        out_file = fopen(out_name, "wb");        // 打开压缩后将生成的文件
        root = node_num-1;
        while(1)
        {
            fread((char *)&store, sizeof(unsigned char), 1, in_file);        // 读取一个字符长度的编码

            /*以8bits为一个处理单元*/
            for(i = 0; i < 8; ++i)
            {
                // 由根向下直至叶节点正向匹配编码对应字符
                if(store & 128)
                    root = huffmantree[root].rchild;
                else
                    root = huffmantree[root].lchild;

                if(root < classi)
                {
                    fwrite((char *)&huffmantree[root].uch, sizeof(unsigned char), 1, out_file);
                    ++length;
                    if (length == file_len) break;        // 控制文件长度,跳出内层循环
                    root = node_num-1;        // 复位为根索引,匹配下一个字符
                }
                store <<= 1;        // 将编码缓存的下一位移到最高位,供匹配
            }
            if (length == file_len) break;        // 控制文件长度,跳出外层循环
        }

        //close
        fclose(in_file);
        fclose(out_file);

        //free
        free(huffmantree);
    }
}

int main()
{
    while(1)
    {
        int opt, flag  = 0;        // 每次进入循环都要初始化flag为0
        char in_name[256], out_name[256];        // 保存输入输出文件名
        // 输入所选择操作类型的数字代号:1:压缩,2:解压,3:退出
        printf("--------------------------------------------\n");
        printf("    1: Compression\n\n    2: Decompression\n\n    3: Quit\n");
        printf("--------------------------------------------\n");
        printf("Input:");
        scanf("%d", &opt);
        if (opt == 3)
            break;
        else
        {
            printf("\nFilename to be compressed: ");
            fflush(stdin);        // 清空标准输入流,防止干扰gets函数读取文件名
            gets(in_name);
            printf("\nFilename after compressed: ");
            fflush(stdin);
            gets(out_name);
        }
        switch(opt)
        {
        case 1: printf("--------------------------------------------\n");
                printf("Compressioning……\n");
                flag = compression(in_name, out_name);    // 压缩,返回值用于判断是否文件名不存在
                break;        
        case 2: printf("--------------------------------------------\n");
                printf("Decompressioning……\n");
                flag = Decompression(in_name, out_name);        // 解压,返回值用于判断是否文件名不存在
                break;        
        }
        if (flag == -1)
            printf("\nSorry, in_file \"%s\" doesn't exist!\n", in_name);        // 如果标志为‘-1’则输入文件不存在
        else
            printf("\nOperation is done!\n");        // 操作完成
    }

    return 0;
}



扫描二维码,在手机阅读!
文章评论