#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

unsigned char saveChar = 0; //用来保存二进制文件，因为char类型是1个字节，所以每8位储存一次 ,而且用unsigned无符号型，避免符号位干扰
typedef struct
{
    int value;
    int p,l,r;
}HTNode,*HuffTree;         //哈夫曼树

struct fact                   //因为不是每一篇文章中所有字符都会出现
{                            //所以结构体数组存储数组下标真正对应的字符ch以及权值weight
    char ch;//字符
    int weight;//权重
};

typedef char * * HuffCode;   //  字符指针数组用于存储各个字符对应的编码
typedef char * CHAR;

void select(HuffTree &HT,int n,int &s1,int &s2);                         //查找HT中未被使用的权值最小的两个点的下标
void CREATEHUFFTREE(HuffTree &HT,fact *ww,int n,HuffCode &HC);                //建树函数，附带完成每一个字符对应的编码
void BecomeCode(HuffCode &HC,int n,CHAR &Code,char *Text,int *match);  //由已知的各个字符的编码完成全文的编码

void Code_ToBe_Artical(CHAR &Code,HuffTree &HT,fact *Fact,int n);     //由全文的编码，用已经建立的哈弗曼树完成解码
int main()
{
    HuffTree HT=NULL;
    HuffCode  HC; //字符指针数组
    printf("请输入需要编码的文章\n");
    char Text[20000];
    CHAR Code = NULL;               //指针用于存储文章最终的编码
    gets(Text);  //写入编码
    int len=strlen(Text);//求出长度
    //写入文件
    FILE *fp=fopen("E:\\demo.txt", "w");
    //printf("15555555");
    if(fputs(Text, fp)!=EOF)
    {
        printf("写入E:\\demo.txt文件成功,大小为 %dk",len/1024+1);
        //printf("%d",len);
    }
    fclose(fp);
    int codeweight[54];//频率数组
    int match[54];
    memset(codeweight,0,sizeof(codeweight));//置0
    for(int i=0;i<len;i++)          // 统计频率  空格下标为0 ，（A~Z）下标分别为（1~26） （a~z）下标分别为（27~52）
    {
        if(Text[i]==' ')
            codeweight[0]++;
        else if(isupper(Text[i]))//若是大写字母
            codeweight[Text[i]-'A'+1]++;
        else
            codeweight[Text[i]-'a'+27]++;
    }

    int n=0;
    fact Fact[54];                  // 由于不是每一个字符都出现在文章中，将codeweight数组录入Fact结构体数组中
    for(int i=0;i<=52;i++)
    {
        if(codeweight[i]!=0)
        {
            if(i==0)
                Fact[n].ch=' ';
            else if(i<=26)  //转为相应的大写字母
                Fact[n].ch=i+'A'-1;
            else
                Fact[n].ch=i+'a'-27;//转为相应的小写字母
            match[i]=n;
            Fact[n++].weight=codeweight[i];
        }
    }
    CREATEHUFFTREE(HT,Fact,n,HC);                //建树函数，附带完成每一个字符对应的编码
    BecomeCode(HC,n,Code,Text,match);     //由已知的各个字符的编码完成全文的编码
    Code_ToBe_Artical(Code,HT,Fact,n);   //由全文的编码，用已经建立的哈弗曼树完成解码
    return 0;
}

void select(HuffTree &HT,int n,int &s1,int &s2)  //查找HT中未被使用的权值最小的两个点的下标
{
    s1=s2=0;
    HT[0].value=0x7fffffff;
    for(int i=1;i<=n;i++)
    {
        if(HT[i].p!=0)
            continue;
        if(HT[i].value<HT[s1].value)//比较权值
        {
            s2=s1;
            s1=i;
        }
        else if(HT[i].value<HT[s2].value)
            s2=i;
    }
}

void CREATEHUFFTREE(HuffTree &HT,fact *ww,int n,HuffCode &HC) //由已知的各个字符的编码完成全文的编码
{
    int m=n*2-1;
    HT = (HuffTree)malloc((m+1)*sizeof(HTNode));  //分配m+1个内存，是因为要存储m个数据，但是要从HT数组下标1开始
    int i,j,f;
    fact *w=ww;
    HuffTree p;
    for(p =HT,p++,i=1;i<=n;i++,p++,w++)          //对HT （1~n）赋值语句
    {
        (*p).value=(*w).weight,(*p).p=0,(*p).l=0,(*p).r=0;
    }
    for(;i<=m;i++,p++)                          //对HT （n+1~m）赋值语句
    {
        (*p).value=0,(*p).p=0,(*p).l=0,(*p).r=0;
    }

    int s1,s2;
    for(i=n+1;i<=m;i++)
    {
        select(HT,i-1,s1,s2);//查找最小的两个
        HT[s1].p=i,HT[s2].p=i;
        HT[i].l=s1,HT[i].r=s2;
        HT[i].value=HT[s1].value+HT[s2].value;
    }

    HC = (HuffCode)malloc((n+1)*sizeof(char *));    // 为字符指针数组分配内存
    char *temp=(char *)malloc(n*sizeof(char));
    temp[n-1]='\0';
    for(i=1;i<=n;i++)
    {
        int start=n-2;
        for(j=i,f=HT[i].p;f!=0;j=f,f=HT[f].p)
        {
            if(HT[f].l==j)
                temp[start--]='0';
            else
                temp[start--]='1';
        }
        HC[i]=(char *)malloc((n-start)*sizeof(char));
        strcpy(HC[i],&temp[++start]);
    }
    delete temp;

    printf("\n各个字符对应的编码\n");
    for(i=1;i<=n;i++)
    {
        if(ww[i-1].ch==' ')
            printf("空格 --> ");
        else
            printf("%c --> ",ww[i-1].ch);
        puts(HC[i]);
    }
}

void BecomeCode(HuffCode &HC,int n,CHAR &Code,char *Text,int *match)  //由已知的各个字符的编码完成全文的编码
{
    int len,i;                           //纯粹是用已知的文本Text和HC将文本转化为编码
    len=strlen(Text);
    Code = (char *)malloc((len*n+1)*sizeof(char));//初始化字符数组
    Code[0]='\0';  //置空
    for(i=0;i<len;i++)
    {
        if(Text[i]==' ')
            strcat(Code,HC[1]);
        else if(Text[i]<='Z'&&Text[i]>='A')
            strcat(Code,HC[ match[Text[i]-'A'+1]+1 ]);
        else
            strcat(Code,HC[ match[Text[i]-'a'+27]+1 ]);
    }
    printf("\n文章编码为\n");
    puts(Code);
    FILE *fp=fopen("E:\\test.txt", "w");
    if(fputs(Code, fp)!=EOF)
    {
        printf("文章编码写入E:\\test.txt文件成功\n");
    }
    fclose(fp);
    //进行压缩
    FILE *fp2=fopen("E:\\test.txt", "r");
    FILE *fpw = fopen("E:\\Huffman","wb");//2进制写入文件
    char reder;
    int Hufflength=0;//压缩长度
    int num=0;//计数
    //int  t=0;
    //printf("len=%d\n",strlen(Code));
   // while ((reder=fgetc(fp2))!=EOF)//一个一个读入字符
    {
        //t++;

        for(int i=0;i<strlen(Code);i++)
        {
            //saveChar || = (code[i]-'0');
            //printf("%c",Code[i]);
            saveChar  = ((Code[i]-'0')|saveChar);//让saveChar和编码中的每一位进行或操作
            num++;
            if(num==8)
            {
                fwrite(&saveChar,sizeof(char),1,fpw);//每8位写入一次文件
                Hufflength++;
                saveChar = 0;//重新置0
                num = 0;
            }
            else{
                    saveChar = saveChar << 1; //每做完一步，左移一位

            }
        }
    }
    //printf("t=%d",t);
    //最后不到8位，移到最左端
    if(num != 8)
    {
        saveChar = saveChar<<(7-num);//移到最左端
        fwrite(&saveChar,sizeof(char),1,fpw);
        Hufflength++;
    }
    printf("加密文件写入E:\\Huffman 成功,大小为 %dk",Hufflength/1024+1);
    //printf("%d",Hufflength);
    fclose(fp2);
    fclose(fpw);

}

void  Code_ToBe_Artical(CHAR &Code,HuffTree &HT,fact *Fact,int n)  //根据哈夫曼编码解压缩,主要思想是根据编码遍历哈夫曼树
{

    printf("\n将编码解码\n");
    for(int i=0;Code[i]!='\0';i++)//遍历哈夫曼编码
    {
        int m=n*2-1,ok=1;
        while(1)
        {
            if(Code[i]=='0')
            {
                m=HT[m].l;
                if(HT[m].l==0)
                {
                    printf("%c",Fact[m-1].ch);
                    break;
                }
            }
            else if(Code[i]=='1')
            {
                m=HT[m].r;
                if(HT[m].r==0)
                {
                    printf("%c",Fact[m-1].ch);
                    ok=0;
                }
            }
            if(!ok)
                break;
            i++;
        }
    }
    printf("\n");
    return ;
}

原理就是统计带压缩文件字符频率，构建哈夫曼树，然后求哈夫曼编码，将字符频率(解压的时候通过字符频率建树)和哈夫曼编码写入文件，完成压缩。

压缩代码：

//获取一个文件的每个字符的频率
void get_frequency(string filename, int frequency[256])
{
    ifstream fin(filename);
    
    if (!fin.is_open())
    {
        return ;
    }
    
    memset(frequency, 0, sizeof(int) * 256);
    
    while (!fin.eof())
    {
        unsigned char temp = fin.get();
        if (fin.eof())
        {
            break;
        }
        frequency[temp]++;
    }

    fin.close();
}


//哈夫曼树的节点
struct node
{
    unsigned char ch;
    int w;
    node *rch, *lch;
};
//获取一个行自定义属性的节点
node* new_node(unsigned char ch, int w, node* lch = NULL, node* rch = NULL)
{
    node* temp = (node*)malloc(sizeof(node));
    temp->ch = ch;
    temp->w = w;
    temp->rch = rch;
    temp->lch = lch;
    return temp;
}
//优先级队列比较大小的方法
struct cmp
{
    bool operator () (node* x, node* y)
    {
        return x->w > y->w;
    }
};
//建树，返回根节点
node* build_haffman(int frequency[256])
{
    priority_queue<node*, vector<node*>, cmp> q;
    for (int i = 0; i < 256; i++)
    {
        if (frequency[i] != 0)
        {
            node* temp = new_node((unsigned char)i, frequency[i]);
            q.push(temp);
        }
    }
    while (q.size() > 1)
    {
        node* x = q.top();
        q.pop();
        node* y = q.top();
        q.pop();
        
        node* temp = new_node(0, x->w + y->w, x, y);
        q.push(temp);
    }
    return q.top();
}


//后跟遍历销毁树
void destory_haffman(node **root)
{
    if (*root)
    {
        destory_haffman(&(*root)->lch);
        destory_haffman(&(*root)->rch);
        free(*root);
    }
}


//获取字符的哈夫曼编码
void get_haffman_code(node* root, vector<char>& v, string code[256])
{
    if (root)
    {
        if (root->lch == NULL && root->rch == NULL)
        {
            string temp = "";
            for (int i = 0; i < v.size(); i++)
            {
                temp += v[i];
            }
            code[root->ch] = temp;
        }
        v.push_back('0');
        get_haffman_code(root->lch, v, code);
        v.pop_back();
        v.push_back('1');
        get_haffman_code(root->rch, v, code);
        v.pop_back();
    }
}


//将8位01码表示为一个unsigned char
unsigned char create_uchar(string haff_code, int index)
{
    unsigned char ch = 0;
    unsigned char flag = 128;
    for (int i = index; i < index + 8; i++)
    {
        ch += flag * (haff_code[i] - '0');
        flag /= 2;
    }
    return ch;
}
//压缩文件的流程
void compress_to_file(string src_file, string dst_file)
{
    ifstream fin(src_file);
    ofstream fout(dst_file, ios::binary);
    
    if (!fin.is_open() || !fout.is_open())
    {
        return;
    }
    
    int frequency[256];
    string code[256];
    vector<char> v;
    get_frequency("/Users/Rubik/Desktop/123.txt", frequency);
    node* root = build_haffman(frequency);
    get_haffman_code(root, v, code);
    
    string haff_code = "";
    unsigned char ch;
    while (!fin.eof())
    {
        ch = fin.get();
        if (fin.eof()) break;
        haff_code += code[ch];
    }
    int len = (int)haff_code.length();
    cout << len << endl;
    fout.write((const char*)frequency, sizeof(int) * 256);
    fout.write((const char*)&len, sizeof(int));
    
    while (haff_code.length() % 8 != 0)
    {
        haff_code += '0';
    }
    
    for (int i = 0; i < haff_code.length(); i += 8)
    {
        unsigned char temp = create_uchar(haff_code, i);
        fout.write((const char*)&temp, sizeof(char));
    }
    
    fout.close();
    fin.close();
    destory_haffman(&root);
}


解压部分比较简单，获取字符频率，建树，获取unsigned char，遍历树，遇到叶子节点就输出到解压文件

//通过一个unsigned char遍历haffman树，存到s[]里，s长度为slen， cnt为已走长度，len为有效长度
node* get_res(node* root, node* pos, unsigned char temp, char* s, int &slen, int &cnt, int len)
{
    slen = 0;
    for (int i = 128; i > 0 && cnt < len; i >>= 1)
    {
        if (i & temp)
        {
            pos = pos->rch;
        }
        else
        {
            pos = pos->lch;
        }
        cnt++;
        if (pos->lch == pos->rch && pos->lch == NULL)
        {
            s[slen++] = pos->ch;
            pos = root;
        }
    }
    return pos;
}

void decompress_to_file(string src_file, string dst_file)
{
    ifstream fin(src_file);
    ofstream fout(dst_file, ios::binary);
    
    int frequency[256];
    fin.read((char*)frequency, sizeof(int) * 256);
    
    node* root = build_haffman(frequency);
    
    vector<char> v;
    string code[256];
    get_haffman_code(root, v, code);
    
    for (int i = 0; i < 256; i++)
    {
        if (code[i].length() > 0)
        {
            cout << code[i] << endl;
        }
    }
    
    int len;
    fin.read((char*)&len, sizeof(int));
    
    unsigned char temp;
    node *pos = root;
    char s[8];
    int slen, cnt = 0;
    while (!fin.eof())
    {
        fin.read((char*)&temp, sizeof(char));
        pos = get_res(root, pos, temp, s, slen, cnt, len);
        for (int i = 0; i < slen; i++)
        {
            fout << s[i];
        }
    }
    
    destory_haffman(&root);
    
    fin.close();
    fout.close();
}


int main()
{
    compress_to_file("/Users/Rubik/Desktop/123.txt", "/Users/Rubik/Desktop/out.txt");
    decompress_to_file("/Users/Rubik/Desktop/out.txt", "/Users/Rubik/Desktop/456.txt");
    return 0;
}


效果如下

参考Crash Course的课程，做下笔记，原视频在这里 ↓

https://www.bilibili.com/video/BV1EW411u7th?p=21


我们要对如下一张 4像素 X 4像素的 图片进行压缩，



而在磁盘中图片是一串像素值的形式存储的，每个像素的颜色由RGB确定，这样一张图片需要 48（16*3） 个字节


为了能够压缩图片，我们需要减少冗余的信息或者用更紧凑的表示方法。可以发现，有很多相同的排列：白黄、黑黄、黄黄、白白，这个序列可以有这四种排列组成（当然也有其他不同的方式），我们为这四种排列生成紧凑代码，用更少的字节表示每对排列




我们会发现，这四对出现的频率并不相同



黄黄出现的次数最多，所以我们希望通过最紧凑的方式来表示，其次是白黄，黑黄和白白出现的次数最少，我们可以用长一点的来表示


为了实现以上的表示，我们需要构造哈夫曼树。

列出所有的块和频率，每轮选择两个最低的频率，将它们组成一个树。这里BY和WW频率最低,将其组成一个树，组成后的频率为2，这样就完成了一轮算法。




下一轮中重复这样的操作。现在白色的两个频率最低，合并！



合并之后的情况如下


第三轮同理



这样我们就完成了哈夫曼树，它是按照频率排序的，频率低的在下面，频率高的在上



完成了哈夫曼树，我们还需要生成字典，即如何访问各个节点。我们可以将所有的左子树的分支用0标示，右子树用1标示



这样我们就完成了字典



这样我们可以用0 标示YY,111标示 WW…

经过这样的压缩后，原本的字符可以表示为如下的形式



这样原来的48字节我们用14位就能表示了！！! (48字节=48 X 8位 = 384 位）


当然，只保存14位的数据是没有意义的，我们需要将字典也保存下来才能知道表示的信息



加上字典信息后我们需要30字节的空间，仍然比48字节好很多。

                                            利用哈夫曼编码压缩解压文件
1.     引言
本文为大一下学期C语言课程的期末大作业，经过修改后发布。文中要用到的测试文件1.lst见链接:  https://pan.baidu.com/s/1hs7XoIK  密码: wpru。              
编译环境：Ubuntu 16.04
本文主要考核如何以C实现集成电路测试向量文件的无损压缩。在通常的文件存储中，无论是二进制格式的文件还是文本文件，几乎都是等宽的编码。比如ASCII码格式的文本文件，每个字符由一个ASCII码表示，宽度为8bit。然而，从磁盘空间利用率的角度看，这并不是一种效率最高的存储方案。为了理解定长编码与变长编码的区别，假设某个文件纯粹由abcdef共6个字符组成，作为定长编码，至少需要3bit才能表示6个不同的字符，假设每个字符出现的频率以及两种编码方案如下表所示

下面我们计算一下上述两种编码方案的总编码长度。由于6个字符共出现了 100K次，对于定长编码，每个字符占用3bit，总共将占用300Kb的空间；对于变长编码，总计的编码长度为：45*1+(13+12+16)*3+(9+5)*4=224Kb，节省了76Kb的空间。这也正是本次大作业的基本的实现原理。上表中的变长编码有个特点，就是出现越频繁的字符，用越短的编码去表示；而且，每个字符的编码都不是另一个字符编码的前缀，从而简化了解码时的难度，因此又被称为前缀编码。哈夫曼编码就是这样一种编码。本作业要求以哈夫曼编码的原理，编写一个可以将给定的文件进行文件压缩，同时可以将压缩的文件进行解压的程序。比如假设编写的程序为huff，huff -c test.dat –o test.huff将test.dat文件压缩为test.huff；类似的，huff -d test.huff -o test.dat将压缩文件进行解压为原始的test.dat。现在问题的主要难点在于如何针对给定的文件由程序自己统计不同字符出现的频率并据此构造哈夫曼编码。
哈夫曼编码原理
此处以一个实例说明构造哈夫曼编码的过程。构造哈夫曼编码的过程可以等效为一个构造哈夫曼编码树的过程。以上节中的例子为例，首先需要统计各个字符出现的频率，如
上面表格中所示。 哈夫曼编码树的构造过程如下图所示。 


首先，创建 5 个叶子节点，如上图(a)所示，冒号后面是该节点字符出现的频率；接下来每次从当前结点中寻找两个出现频度最低的节点，出现频率最低的放在左边，如(b)的f，次低的放右边，如上图(b)的 e，然后将这两个出现频率最低的节点合并为一个节点，以两个节点出现的总频率为名字，如上图(b)的 14 节点， 14 节点和 f 与 e 分别用标记为 0/1的边连接，这时 f 和 e 两个节点已被删除并被合并为一个 14 节点，因此总的节点数少了一个；接下来继续寻找两个频率最低的节点，如上图(c)中的 c 和 b，二者合并为 25 节点，分别与 c 和 b 以边 0/1 连接；接下来 14 和 d 节点出现频率最低，分别为 14 和 16，合并为 30节点；继续此过程， 25 和 30 节点合并为 55 节点， 55 节点和 a 合并为最终的 100 节点。至此哈夫曼编码树构造完成，如上图(f)。观察上图(f)，所有表示真实字符的节点都放置于矩形框中，且都是叶子节点。从根节点到叶子节点的边的标签相连就是该叶子节点的编码，即 a: 0; b: 101; c: 100; d: 111; e: 1101;f: 1100，恰好是前面表中的变长编码方案。 

2.       基本原理/实现方法
以下是几个主要部分的编码解释，大家可以直接跳过，文件源代码贴在最后。 

由试验简介，根据哈夫曼编码的原理，可以实现文件的压缩与解压。压缩时读取字符转化而相应的哈夫曼二进制编码，解压即为其逆操作。接下来对完成的程序进行分析，具体的代码见huffman.c。
【程序及算法分析】
a)        哈夫曼树建立预备步骤
void initialize(struct node *HuffmanTreeNodeTemp,int count[]) 函数
/***********压缩文件的准备工作*************/
void initialize(struct node *HuffmanTreeNodeTemp,int count[])
{
	int i,j;
	struct node temp;
	for (i=0;i<256;i++)                      //给每一个临时的节点赋值
    {
        HuffmanTreeNodeTemp[i].value=count[i];
        HuffmanTreeNodeTemp[i].ch=(char)i;
    }
    for (i=0;i<256;i++)                      //筛选出现过的字符
    {
        for (j=i+1;j<256;j++)
        {
            if (HuffmanTreeNodeTemp[i].value<HuffmanTreeNodeTemp[j].value)
            {
                temp=HuffmanTreeNodeTemp[i];
                HuffmanTreeNodeTemp[i]=HuffmanTreeNodeTemp[j];
                HuffmanTreeNodeTemp[j]=temp;
            }
        }
    }
}


根据main()函数中统计的256个各个不同字符所重复出现的次数，来创建出256个临时结点结构。又由于实际哈夫曼树的建立并不需要考虑未出现过的字符，所以将这256个节点根据出现的次数(value值)进行排序，将有用的部分放在前面，为下一步建立正式哈夫曼结点准备。
 
b)        哈夫曼树的建立：void CreatHuffmanTree(int nodecount,int max,struct node *HuffmanTreeNodeTemp,structnode *HuffmanTreeNode)函数
/************构造哈夫曼树************/
void CreatHuffmanTree(int nodecount,int max,struct node *HuffmanTreeNodeTemp,struct node *HuffmanTreeNode)
{
    int i,j,k,m,n,value;
    int min;
    for (i=0;i<nodecount;i++)
    {
        HuffmanTreeNode[i]=HuffmanTreeNodeTemp[i];
    }
    for (i=0;i<2*nodecount-1;i++)
    {
        HuffmanTreeNode[i].tag=0;
        HuffmanTreeNode[i].parent=0;
    }
    for (i=nodecount;i<2*nodecount-1;i++)
    {
        min=INT_MAX;
        for (j=0;j<i;j++)       //查找最大值m
        {
            if ((HuffmanTreeNode[j].tag==0) && (HuffmanTreeNode[j].value<=min))
            {
                min=HuffmanTreeNode[j].value;
                m=j;              //m,n分别表示其为最大，次大值为第几个
            }
        }
        HuffmanTreeNode[m].tag=1;
        min=INT_MAX;
        for (j=0;j<i;j++)        //查找次大值n
        {
            if ((HuffmanTreeNode[j].tag==0)  &&( HuffmanTreeNode[j].value<=min))
            {
                min=HuffmanTreeNode[j].value;
                n=j;
            }
        }
        HuffmanTreeNode[n].tag=1;      			//被找过的值就标记1,下一次就不会再找了
        HuffmanTreeNode[i].lchild=m;
        HuffmanTreeNode[i].rchild=n;
        HuffmanTreeNode[m].parent=i;
        HuffmanTreeNode[n].parent=i;
        HuffmanTreeNode[i].value=HuffmanTreeNode[m].value+HuffmanTreeNode[n].value;
    }

    //生成哈夫曼编码
    int index,temp;

    for (i=0;i<nodecount;i++)
    {
        index=255;
        for (j=i;HuffmanTreeNode[j].parent!=0;)
        {
            temp=HuffmanTreeNode[j].parent;
            if (HuffmanTreeNode[temp].lchild==j)
            {
                HuffmanTreeNode[i].hufcodetemp[index]=1;
                index--;
            }
            else if (HuffmanTreeNode[temp].rchild==j)
            {
                HuffmanTreeNode[i].hufcodetemp[index]=0;
                index--;
            }
            j=temp;
        }

        int length=255-index;
        HuffmanTreeNode[i].hufcode=malloc(length*sizeof(int));
        HuffmanTreeNode[i].codelen=length;

        for (k=0;k<length;k++)
        {
            index++;
            HuffmanTreeNode[i].hufcode[k]=HuffmanTreeNode[i].hufcodetemp[index];
        }
    }
}


哈夫曼树的总节点个数为2*叶子个数-1，叶子个数n即为有效的字符个数，因此可以先分配出2n-1个的结点，其中，前n个为叶子结点，后n-1个为非叶子结点。根据哈夫曼树的建立原理，在建立哈夫曼树的过程中，先寻找已存在的结点中value值最大和次大的且tag值为0的结点，将这两个选择的结点tag值设置为1，这样下次搜索就会跳过它。同时，将其父亲结点加入下一次的搜索范围之内。记录相应的lchild、rchild、parent等必要数据值。如此循环，直到哈夫曼树建立完成。
 
c)        压缩文件核心部分：
void compressfile(struct node *HuffmanTreeNode,int wordcount,intnodecount,char FILE1[],char FILE2[]) 函数
/**********对文件进行压缩************/
void compressfile(struct node *HuffmanTreeNode,int wordcount,int nodecount,char FILE1[],char FILE2[])
{
	FILE *ptr=fopen(FILE1,"rb");
    FILE *ptw=fopen(FILE2,"wb");
    char readtemp;
    unsigned char codetemp;
    int wcount=0,i,j;
    int length,num;
    codetemp='\0';
    						//写入哈夫曼编码
    fwrite(&nodecount,sizeof(int),1,ptw);
    fwrite(&wordcount,sizeof(int),1,ptw);
    for (i=0;i<nodecount;i++)
    {
        fwrite(&(HuffmanTreeNode[i].ch),sizeof(char),1,ptw);
    }
    for (i=nodecount;i<nodecount*2-1;i++)
    {
        fwrite(&(HuffmanTreeNode[i].lchild),sizeof(int),1,ptw);
        fwrite(&(HuffmanTreeNode[i].rchild),sizeof(int),1,ptw);
    }

    while(!feof(ptr))
    {
        readtemp=getc(ptr);
        for (j=0;j<nodecount;j++)                    //找对应的字符
        {
            if (HuffmanTreeNode[j].ch==readtemp)
            {
                num=j;
                break;
            }
        }

        for (i=0;i<HuffmanTreeNode[num].codelen;i++)		//位操作来进行
        {
            codetemp<<=1;
            codetemp|=HuffmanTreeNode[num].hufcode[i];

            wcount++;
            if (wcount==8)						//满八位以后写入压缩文件
            {
                fwrite(&codetemp,sizeof(unsigned char),1,ptw);
                wcount=0;
                codetemp='\0';
            }
        }
       if (feof(ptr))
            break;
    }
    if (wcount>0)							//处理最后的未满八位的字节
    {
        for (i=0;i<8-wcount;i++)
            codetemp<<=1;

        fwrite(&codetemp,sizeof(unsigned char),1,ptw);
    }
    fclose(ptr);
    fclose(ptw);
}
根据建立的哈夫曼树，不妨假设父亲节点的左儿子编码为1，右儿子为0，这样就能从根结点开始得到每一个字符的哈夫曼编码。在进行压缩的时候，依次读取测试文件中的字符，根据该字符的哈夫曼编码通过位操作写入压缩文件中，在写入的过程中加入一个计数器wcount，当得到一位值，wcount就加一。当其值满8时及说明可以向压缩文件中写入一个字符，再将计数器归零。以此循环直到最后。最后可能出现为满8位的情况，这时要将其右端加0填满8位再写入文件。
需要说明的是，为了解压时候处理最后一个字符方便，需要将解压时所需要的相关信息在压缩之前写入文件。需要写入的重要信息有：所含有的有效字符种类，为了读取时分配大小、确定树叶节点个数；所含有的字符个数，输出最后一个字符时使用；叶子结点的字符值，非叶子结点的左儿子、右儿子值，为了从根节点一步一步得到叶子结点是使用。

d)        解压文件部分：void extract(charFILE2[],char FILE3[])函数
/************解压文件正式程序************/
void extract(char FILE2[],char FILE3[])
{
    int i,j;
    FILE *ptr=fopen(FILE2,"rb");
    int countch;
    int curwordcount=0;
    int wordcount;

    fread(&countch,sizeof(int),1,ptr);                          //从文件中获取构建哈夫曼树的相关信息
    fread(&wordcount,sizeof(int),1,ptr);
	struct node *extractHuffmanTreeNode = malloc((countch*2-1)*sizeof(struct node));
	for (i=0;i<countch;i++)
    {
        extractHuffmanTreeNode[i].rchild=-1;
        extractHuffmanTreeNode[i].lchild=-1;
    }
    for (i=0;i<countch;i++)
    {
        fread(&(extractHuffmanTreeNode[i].ch),sizeof(char),1,ptr);
    }

    for (i=countch;i<2*countch-1;i++)
    {
        fread(&(extractHuffmanTreeNode[i].lchild),sizeof(int),1,ptr);
        fread(&(extractHuffmanTreeNode[i].rchild),sizeof(int),1,ptr);
    }

    int nextnode=2*countch-2;
    int pose;
    unsigned char chtemp;

    FILE *ptw=fopen(FILE3,"wb");
    while (!feof(ptr))							//读取文件进行解码
    {
        fread(&chtemp,sizeof(unsigned char),1,ptr);
        for (i=0;i<8;i++)
        {
            if (curwordcount>=wordcount)	//让打印的字符数与原文件相同，这个是由于用huffman编码压缩时，最后不满8位的都被进行移位处理了，当解压时无法判断最后的0是不是移位造成的
                break;
            if (((int)chtemp&128)==128)				//采用掩码来判断该位上为0还是1
                pose=1;
            else
                pose=0;
            chtemp<<=1;
            if (nextnode>=countch)     //非叶子节点，继续
            {
                if (pose==1)
                {
                    nextnode=extractHuffmanTreeNode[nextnode].lchild;
                }
                else
                {
                    nextnode=extractHuffmanTreeNode[nextnode].rchild;

                }
                if (nextnode<countch)      //到达叶子节点，将解压的字符输出
                {
                    fwrite(&(extractHuffmanTreeNode[nextnode].ch),sizeof(char),1,ptw);
                    curwordcount++;
                    nextnode=2*countch-2;
                }
            }
        }
    }
    free(extractHuffmanTreeNode);
    fclose(ptw);
    fclose(ptr);
}


解压文件即为压缩文件的逆过程。首先读取解压缩所需的相关信息，根据其建立哈夫曼树。进行解压文件时，依次读取文件的一个字符，一位字符占八位字节，可以通过掩码（mask）来确定某一位上的值。确定一位值就在哈夫曼树上由跟节点移动一步，得到相应的解码后的字符值。其中和压缩时设置的一样，左儿子为1，右儿子为0。每读到一个字符就向解压文件中写入该字符，再从头开始重新求下一个字符。
由于压缩时最后一位的处理比较特殊，通过移动往后增加了几个0，而解压时很难判断这几个0是哈夫曼编码还是移动得到的。因此在之前压缩时已经写入了该文件应包含几个字符，解压时即可用计数器统计解压产生的字符个数，当其值到达要求值时就退出循环。
 
3.       实现过程/实验数据
a)       函数运行结果分析：

时间：
压缩文件（包括写压缩文件&构造哈夫曼树）用时约25.2s，解压缩（包括重构哈夫曼树&写解压缩文件）用时约22.6s。
1.lst为原文件（即老师提供的文件，改了一下名字，方便输入），生成的2.lst为压缩文件，3.lst为解压后的文件。三个文件见附件。通过ubuntu下的diff命令操作，比较1.lst和3.lst是否相同，当不返回任何内容时，两个文件即为相同的，否则则返回两文件不同的部分。由截图可以看出，该程序解压得到的文件和原文件相同。即说明压缩与解压程序可以正确运行。
 
b)        压缩率分析：

查看两个文件大小：原文件1.lst大小为849,646,229字节，压缩后的文件2.lst为123,313,632 字节，压缩率为 
 
c)   内存泄漏分析：
通过valgrind工具可以分析该程序的内存泄漏情况：

可以看到，该程序所有需要释放的内存都已经被释放，内存无泄漏。
 

****************************下面是源码***************************
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

struct node{
    int value;                  //权重
    int parent,lchild,rchild;
    char ch;
    int tag;
    int hufcodetemp[256];
    int *hufcode;
    int codelen;
    };

void CreatHuffmanTree(int nodecount,int max,struct node *huffmanTreeNodeTemp,struct node *huffmanTreeNode);
void initialize(struct node *HuffmanTreeNodeTemp,int count[]);
void compressfile(struct node *HuffmanTreeNode,int wordcount,int nodecount,char FILE1[],char FILE2[]);
void compress(int count[],int wordcount,char FILE1[],char FILE2[]);
void extract(char FILE1[],char FILE2[]);

/************解压文件正式程序************/
void extract(char FILE2[],char FILE3[])
{
    int i,j;
    FILE *ptr=fopen(FILE2,"rb");
    int countch;
    int curwordcount=0;
    int wordcount;

    fread(&countch,sizeof(int),1,ptr);                          //从文件中获取构建哈夫曼树的相关信息
    fread(&wordcount,sizeof(int),1,ptr);
	struct node *extractHuffmanTreeNode = malloc((countch*2-1)*sizeof(struct node));
	for (i=0;i<countch;i++)
    {
        extractHuffmanTreeNode[i].rchild=-1;
        extractHuffmanTreeNode[i].lchild=-1;
    }
    for (i=0;i<countch;i++)
    {
        fread(&(extractHuffmanTreeNode[i].ch),sizeof(char),1,ptr);
    }

    for (i=countch;i<2*countch-1;i++)
    {
        fread(&(extractHuffmanTreeNode[i].lchild),sizeof(int),1,ptr);
        fread(&(extractHuffmanTreeNode[i].rchild),sizeof(int),1,ptr);
    }

    int nextnode=2*countch-2;
    int pose;
    unsigned char chtemp;

    FILE *ptw=fopen(FILE3,"wb");
    while (!feof(ptr))							//读取文件进行解码
    {
        fread(&chtemp,sizeof(unsigned char),1,ptr);
        for (i=0;i<8;i++)
        {
            if (curwordcount>=wordcount)	//让打印的字符数与原文件相同，这个是由于用huffman编码压缩时，最后不满8位的都被进行移位处理了，当解压时无法判断最后的0是不是移位造成的
                break;
            if (((int)chtemp&128)==128)				//采用掩码来判断该位上为0还是1
                pose=1;
            else
                pose=0;
            chtemp<<=1;
            if (nextnode>=countch)     //非叶子节点，继续
            {
                if (pose==1)
                {
                    nextnode=extractHuffmanTreeNode[nextnode].lchild;
                }
                else
                {
                    nextnode=extractHuffmanTreeNode[nextnode].rchild;

                }
                if (nextnode<countch)      //到达叶子节点，将解压的字符输出
                {
                    fwrite(&(extractHuffmanTreeNode[nextnode].ch),sizeof(char),1,ptw);
                    curwordcount++;
                    nextnode=2*countch-2;
                }
            }
        }
    }
    free(extractHuffmanTreeNode);
    fclose(ptw);
    fclose(ptr);
}

/************构造哈夫曼树************/
void CreatHuffmanTree(int nodecount,int max,struct node *HuffmanTreeNodeTemp,struct node *HuffmanTreeNode)
{
    int i,j,k,m,n,value;
    int min;
    for (i=0;i<nodecount;i++)
    {
        HuffmanTreeNode[i]=HuffmanTreeNodeTemp[i];
    }
    for (i=0;i<2*nodecount-1;i++)
    {
        HuffmanTreeNode[i].tag=0;
        HuffmanTreeNode[i].parent=0;
    }
    for (i=nodecount;i<2*nodecount-1;i++)
    {
        min=INT_MAX;
        for (j=0;j<i;j++)       //查找最大值m
        {
            if ((HuffmanTreeNode[j].tag==0) && (HuffmanTreeNode[j].value<=min))
            {
                min=HuffmanTreeNode[j].value;
                m=j;              //m,n分别表示其为最大，次大值为第几个
            }
        }
        HuffmanTreeNode[m].tag=1;
        min=INT_MAX;
        for (j=0;j<i;j++)        //查找次大值n
        {
            if ((HuffmanTreeNode[j].tag==0)  &&( HuffmanTreeNode[j].value<=min))
            {
                min=HuffmanTreeNode[j].value;
                n=j;
            }
        }
        HuffmanTreeNode[n].tag=1;      			//被找过的值就标记1,下一次就不会再找了
        HuffmanTreeNode[i].lchild=m;
        HuffmanTreeNode[i].rchild=n;
        HuffmanTreeNode[m].parent=i;
        HuffmanTreeNode[n].parent=i;
        HuffmanTreeNode[i].value=HuffmanTreeNode[m].value+HuffmanTreeNode[n].value;
    }

    //生成哈夫曼编码
    int index,temp;

    for (i=0;i<nodecount;i++)
    {
        index=255;
        for (j=i;HuffmanTreeNode[j].parent!=0;)
        {
            temp=HuffmanTreeNode[j].parent;
            if (HuffmanTreeNode[temp].lchild==j)
            {
                HuffmanTreeNode[i].hufcodetemp[index]=1;
                index--;
            }
            else if (HuffmanTreeNode[temp].rchild==j)
            {
                HuffmanTreeNode[i].hufcodetemp[index]=0;
                index--;
            }
            j=temp;
        }

        int length=255-index;
        HuffmanTreeNode[i].hufcode=malloc(length*sizeof(int));
        HuffmanTreeNode[i].codelen=length;

        for (k=0;k<length;k++)
        {
            index++;
            HuffmanTreeNode[i].hufcode[k]=HuffmanTreeNode[i].hufcodetemp[index];
        }
    }
}

/***********压缩文件的准备工作*************/
void initialize(struct node *HuffmanTreeNodeTemp,int count[])
{
	int i,j;
	struct node temp;
	for (i=0;i<256;i++)                      //给每一个临时的节点赋值
    {
        HuffmanTreeNodeTemp[i].value=count[i];
        HuffmanTreeNodeTemp[i].ch=(char)i;
    }
    for (i=0;i<256;i++)                      //筛选出现过的字符
    {
        for (j=i+1;j<256;j++)
        {
            if (HuffmanTreeNodeTemp[i].value<HuffmanTreeNodeTemp[j].value)
            {
                temp=HuffmanTreeNodeTemp[i];
                HuffmanTreeNodeTemp[i]=HuffmanTreeNodeTemp[j];
                HuffmanTreeNodeTemp[j]=temp;
            }
        }
    }
}

/**********对文件进行压缩************/
void compressfile(struct node *HuffmanTreeNode,int wordcount,int nodecount,char FILE1[],char FILE2[])
{
	FILE *ptr=fopen(FILE1,"rb");
    FILE *ptw=fopen(FILE2,"wb");
    char readtemp;
    unsigned char codetemp;
    int wcount=0,i,j;
    int length,num;
    codetemp='\0';
    						//写入哈夫曼编码
    fwrite(&nodecount,sizeof(int),1,ptw);
    fwrite(&wordcount,sizeof(int),1,ptw);
    for (i=0;i<nodecount;i++)
    {
        fwrite(&(HuffmanTreeNode[i].ch),sizeof(char),1,ptw);
    }
    for (i=nodecount;i<nodecount*2-1;i++)
    {
        fwrite(&(HuffmanTreeNode[i].lchild),sizeof(int),1,ptw);
        fwrite(&(HuffmanTreeNode[i].rchild),sizeof(int),1,ptw);
    }

    while(!feof(ptr))
    {
        readtemp=getc(ptr);
        for (j=0;j<nodecount;j++)                    //找对应的字符
        {
            if (HuffmanTreeNode[j].ch==readtemp)
            {
                num=j;
                break;
            }
        }

        for (i=0;i<HuffmanTreeNode[num].codelen;i++)		//位操作来进行
        {
            codetemp<<=1;
            codetemp|=HuffmanTreeNode[num].hufcode[i];

            wcount++;
            if (wcount==8)						//满八位以后写入压缩文件
            {
                fwrite(&codetemp,sizeof(unsigned char),1,ptw);
                wcount=0;
                codetemp='\0';
            }
        }
       if (feof(ptr))
            break;
    }
    if (wcount>0)							//处理最后的未满八位的字节
    {
        for (i=0;i<8-wcount;i++)
            codetemp<<=1;

        fwrite(&codetemp,sizeof(unsigned char),1,ptw);
    }
    fclose(ptr);
    fclose(ptw);
}

/************压缩文件的正式程序***********/
void compress(int count[],int wordcount,char FILE1[],char FILE2[])
{
    int i,j,nodecount=0;
    struct node *HuffmanTreeNodeTemp=malloc(256*sizeof(struct node));      										//先给每一个可能的字符都初始化哈夫曼节点

    initialize(HuffmanTreeNodeTemp, count);		//处理这些节点，排序

    int max=HuffmanTreeNodeTemp[0].value;		//重新建立一棵包含有效的节点的哈夫曼树

    for (i=0;i<256;i++)
    {
        if (HuffmanTreeNodeTemp[i].value!=0)
                nodecount++;
        if (HuffmanTreeNodeTemp[i].value>max)
                max=HuffmanTreeNodeTemp[i].value;
    }
    struct node *HuffmanTreeNode=malloc((2*nodecount-1)*sizeof(struct node));
    for (i=0;i<nodecount;i++)
    {
        HuffmanTreeNode[i]=HuffmanTreeNodeTemp[i];
    }

    CreatHuffmanTree(nodecount,max,HuffmanTreeNodeTemp,HuffmanTreeNode);

    for (i=0;i<nodecount;i++)				//打印哈夫曼编码
    {
        printf("[%d]",i);
        printf(" %c ",HuffmanTreeNode[i].ch);
        for (j=0;j<HuffmanTreeNode[i].codelen;j++)
            {
                printf("%d",HuffmanTreeNode[i].hufcode[j]);
            }
        printf("\n");
    }

    compressfile(HuffmanTreeNode,wordcount,nodecount,FILE1,FILE2);   //压缩文件
    for (i=0;i<nodecount;i++)
    {
    	free(HuffmanTreeNode[i].hufcode);
    }
        free(HuffmanTreeNode);
        free(HuffmanTreeNodeTemp);
}

/*************主函数**************/
int main()
{
    int i;
    char ch;
    char FILE1[100],FILE2[100],FILE3[100];
    int wordcount=0;      //统计文件中的字符个数
    int count[256]={0};

    FILE *fp=fopen(FILE1,"rb");
    printf("Please enter the file name.\n");
    scanf("%s",FILE1);
    while ((fp=fopen(FILE1,"r"))==NULL)
    {
        printf("Sorry, can't open it.\nPlease enter the file name again.\n");
        scanf("%s",FILE1);
    }
    printf("Please enter the compressed file name.\n");
    scanf("%s",FILE2);
    printf("Please enter the extracted file name.\n");
    scanf("%s",FILE3);

    while((ch=getc(fp))!=EOF){
                count[(int)ch]+=1;
                wordcount++;
    }
    fclose(fp);
    int a,b;
    printf("compressing now\n");
    a=clock();
    compress(count,wordcount,FILE1,FILE2);
    b=clock();
    printf("\ncompress use time:   %dus\n",b-a);
    printf("extracting now\n");
    a=clock();
    extract(FILE2,FILE3);
    b=clock();
    printf("\nextract use time:   %dus\n",b-a);
    return 0;
}