在一般的数据结构的书中，树的那章后面，著者一般都会介绍一下哈夫曼(HUFFMAN)

树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如

JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，

是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点

的权值乘上其到根结点的 路径长度（若根结点为0层，叶结点到根结点的路径长度

为叶结点的层数）。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln)

，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径

长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。

哈夫曼编码步骤：

一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算 法，一般还要求以Ti的权值Wi的升序排列。）

二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。

三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。

四、重复二和三两步，直到集合F中只有一棵二叉树为止。

简易的理解就是，假如我有A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树，即取1，2构成新树，其结点为1+2=3，如图：



虚线为新生成的结点，第二步再把新生成的权值为3的结点放到剩下的集合中，所以集合变成{5,4,3,3}，再根据第二步，取最小的两个权值构成新树，如图：



再依次建立哈夫曼树，如下图：



其中各个权值替换对应的字符即为下图：



所以各字符对应的编码为：A->11,B->10,C->00,D->011,E->010

霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合。

哈夫曼树（最优二叉树）

百度百科：https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91/2305769?fr=aladdin

一. 目的：

找出存放一串字符所需的最少的二进制编码

二. 构造方法：

首先统计出每种字符出现的频率！（也可以是概率）//权值

------------------------------------------------------------------------------------------------

           例如：频率表 A：60,    B:45,   C:13   D:69   E:14   F:5  G:3

第一步：找出字符中最小的两个，小的在左边，大的在右边，组成二叉树。在频率表中删除此次找到的两个数，并加入此次最小两个数的频率和。

F和G最小，因此如图，从字符串频率计数中删除F与G，并返回G与F的和 8给频率表



 重复第一步：

-------------------------------------------------------------------------------------------------

频率表 A：60,    B:45,   C:13   D:69   E:14   FG:8

最小的是 FG：8与C：13，因此如图，并返回FGC的和：21给频率表。



---------------------------------------------------------------------------------------------------

重复第一步：

---------------------------------------------------------------------------------------------------

频率表 A：60    B: 45   D: 69   E: 14   FGC: 21

如图



-----------------------------------------------------------------------------------------------------

重复第一步

-----------------------------------------------------------------------------------------------------

频率表 A：60    B: 45   D: 69  FGCE: 35



-----------------------------------------------------------------------------------------------------

重复第一步

-----------------------------------------------------------------------------------------------------

频率表 A：60   D: 69  FGCEB: 80



-----------------------------------------------------------------------------------------------------

重复第一步

-----------------------------------------------------------------------------------------------------

频率表 AD：129  FGCEB: 80



添加 0 和 1，规则左0 右1



 

频率表 A：60,    B:45,   C:13   D:69   E:14   F:5  G:3

每个 字符 的 二进制编码 为（从根节点 数到对应的叶子节点，路径上的值拼接起来就是叶子节点字母的应该的编码）

字符
			
编码
		
A
			
10
		
B
			
01
		
C
			
0011
		
D
			
11
		
E
			
000
		
F
			
00101
		
G
			
00100
		
 

 

 

 

 

 

 

 

 

那么当我想传送 ABC时，编码为 10 01 0011

思考：

大家观察 出现得越多的字母，他的编码越短 ，出现频率越少的字母，他的编码越长。

在信息传输过程中，如果这个字母越多，那么我们希望他越瘦小（编码短）这样占用的编码越少，其实编码长的字母也是让频率比它多的字母把编码短的位子都占用后，他才去占用当前最短的编码。至此让总的编码长度最短。

且要保证长编码的不与短编码的字母冲突：

比如 不能出现 读码 读到 01  还有长编码的 字母为011，如果短编码为一个长编码的左起子串，这就是冲突，意思就是说读到当前位置已经能确定是什么字母时不能因为再读取一位或几位让这个编码能表示另外的字母，

但哈夫曼树（最优二叉树）在构造的时候就避免了这个问题。为什么能避免呢，因为哈夫曼树的它的字母都在叶子节点上，因此不会出现一个字母的编码为另一个字母编码左起子串的情况。

 

提问：

1.为什么要保证长编码不与短编码冲突？

冲突情况：如果我们已经确定D，E，F，G 用 01 ，010 ，10，001的2进制编码来传输了。那么想传送FED时，我需要传送     1001001，接收方可以把它解析为FDG（10 01 001），当然也能解析为FED（10 010 01），他两编码一样的，这就是编码冲突，（这里编码冲突的原因，也是因为编码时，D的编码是E的编码的左起子串了）显然这是不行的，就像我说压脉带，你如果是日本人会理解为 （你懂得），这就是发出同一种语，得出不同的意的情况。所以不能让一个字母的二进制代表数，为另一个字母的二进制代表数的子串。但为什么实际情况只要求编码时，一个编码不是另一编码的左起子串呢而不是绝对意义上的非子串呢，因为计算机从数字串的左边开始读，如果从右边读，那么可以要求是非右起（无奈）。你又可以问了为什么编码要求是非左起或非右起不直接规定不能是子串呢（也行，不过=>），比如说原文中B就是C，F，G的子串，那这不就不符合规则了么。这里是为了哈夫曼的根本目的，优化编码位占用问题，如果完全不能有任何子串那么编码将会非常庞大。但这里计算机是一位一位的·读取编码的，只需要保证计算机在读取中不会误判就行。并且编码占用最少。

code：0110101001110

左起子串：011

右起子串：110

绝对非子串：1110111  此串在code中完全找不到

2.那么哈夫曼树怎么避免左起子串问题呢？

因为哈夫曼是从叶子节点开始构造，构造到根节点的，而且构造时，都是计算两个权值的节点的和再与其他叶子节点再生成一个父节点来组成一个新的树。并且不允许任何带有权值的节点作为他们的父节点。这也保证了所有带有权值的节点都被构造为了叶子节点。然后最后编码的时候是从根节点开始走到叶子节点而得出的编码。在有权值的节点又不会出现在任何一条路的路途中的情况，只会出现在终点的情况下，因此不会出现01代表一个字母011又代表一个字母。

又如原文ABC编码为10010011的情况，当计算机读到10时，由于有左起子串不冲突的原则。那么计算机完全可以保证当前的10就是A字母，然后再往下读010011的部分，然后当读到01时，也完全能确定B，C同理，而不用说因为会出现冲突的编码而接着继续读取之后的编码来确定前面的编码。这样对信息的判断和效率是相当的不利的，也不是说不可以。即使你ABCD,分别用01,011,0111,01111来代替也行，传输后也能精确识别，但是数据量极大呢，想代替整个中文编码呢，那0后面得多少个1才能代表完。因此哈夫曼就是为了获得最少编码量代替最多字符串，并且不冲突，系统不会误判而产生的。

3.这里要提一下同权不同构

已经有朋友问起这个问题了。这里要说一下哈夫曼树的构造并不是唯一的。

考虑如下情况：

有权值分别为 5,29,7,8,14,23,3,11的情况，可以如下图一样构造。



带权路径长度：

(5+3+7+8)*4+

(11+14)*3+

(23+29)*2

=271

也可以如下图构造：



带权路径长度：

（3+5)*5+

7*4+

(8+11+14)*3+

(23+29)*2

=271

这两种不同的方式构造出来的哈夫曼树，得出的带权路径长度相等，那么选哪颗树都可以，这就叫同权不同构。

 

此问题由博主 https://me.csdn.net/weixin_43690959 昵称：叫我Tim就好了～ 提出，在这里对他表示感谢。

 

 

 

看懂的朋友留个赞，没看懂的留言我给你单独讲 _(:з」∠)_

写一个对文件进行压缩和解压缩的程序，功能如下：

① 可以对纯英文文档实现压缩和解压；

② 较好的界面程序运行的说明。

 

 

介绍哈夫曼：



 



效率最高的判别树即为哈夫曼树

在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明霍夫曼树的WPL是最小的。

 

文件压缩与解压

姓名：  范天祚 

1 程序说明

1.1数据结构

哈夫曼树

1.2函数功能说明

printfPercent界面

compress()读取文件内容并加以压缩，将压缩内容写入另一个文档

uncompress()解压缩文件，并将解压后的内容写入新文件

1.3 程序编写的思路及流程

压缩：统计字符出现次数、将节点按出现次数排序、构造哈夫曼树、设置字符编码、读文件字符、按设置好的编码替换字符、写入存储文件

解压：读取文件各参数、转换成二进制码、按码求对应字符、写入存储文件

#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct head
{
    int b;						  //字符
    long count;                   //文件中该字符出现的次数
    long parent, lch, rch;        //make a tree
    char bits[256];               //the huffuman code
};

struct head header[512], tmp;  //节点树

void printfPercent(int per)
{
	int i = 0;
	printf("|");
	for(i = 0; i < 10; i++)
	{
		if(i < per/10)
			printf(">");
		else
			printf("-");
	}
	printf("|已完成%d%%\n",per);
}

//函数：compress()
//作用：读取文件内容并加以压缩
//将压缩内容写入另一个文档
int compress(const char *filename,const char *outputfile)
{
    char buf[512];
    unsigned char c;
    long i, j, m, n, f;
    long min1, pt1, flength;
    FILE *ifp, *ofp;
	int per = 10;
    ifp = fopen(filename, "rb");                  //打开原始文件
    if (ifp == NULL)
    {
        printf("打开文件失败:%s\n",filename);
        return 0;                             //如果打开失败，则输出错误信息
    }
    ofp = fopen(outputfile,"wb");                 //打开压缩后存储信息的文件
    if (ofp == NULL)
    {
        printf("打开文件失败:%s\n",outputfile);
        return 0;
    }
    flength = 0;
    while (!feof(ifp))
    {
        fread(&c, 1, 1, ifp);
        header[c].count ++;                       //读文件，统计字符出现次数
        flength ++;                               //记录文件的字符总数
    }
    flength --;
    header[c].count --;
    for (i = 0; i < 512; i ++)                    //HUFFMAN算法中初始节点的设置
    {
        if (header[i].count != 0)
            header[i].b = (unsigned char) i;
        else
            header[i].b = -1;
        header[i].parent = -1;
        header[i].lch = header[i].rch = -1;
    }

    for (i = 0; i < 256; i ++)                    //将节点按出现次数排序
    {
        for (j = i + 1; j < 256; j ++)
        {
            if (header[i].count < header[j].count)
            {
                tmp = header[i];
                header[i] = header[j];
                header[j] = tmp;
            }
        }
    }


    for (i = 0; i < 256; i ++)                    //统计不同字符的数量
	{
        if (header[i].count == 0)
            break;
	}

    n = i;
    m = 2 * n - 1;
    for (i = n; i < m; i ++)
    {
        min1 = 999999999;
        for (j = 0; j < i; j ++)
        {
            if (header[j].parent != -1) continue;
            if (min1 > header[j].count)
            {
                pt1 = j;
                min1 = header[j].count;
                continue;
            }
        }
        header[i].count = header[pt1].count;
        header[pt1].parent = i;
        header[i].lch = pt1;
        min1 = 999999999;
        for (j = 0; j < i; j ++)
        {
            if (header[j].parent != -1) continue;
            if (min1 > header[j].count)
            {
                pt1 = j;
                min1 = header[j].count;
                continue;
            }
        }
        header[i].count += header[pt1].count;
        header[i].rch = pt1;
        header[pt1].parent = i;
    }

    for (i = 0; i < n; i ++)                        //构造HUFFMAN树，设置字符的编码
    {
        f = i;
        header[i].bits[0] = 0;
        while (header[f].parent != -1)
        {
            j = f;
            f = header[f].parent;
            if (header[f].lch == j)
            {
                j = strlen(header[i].bits);
                memmove(header[i].bits + 1, header[i].bits, j + 1);
                header[i].bits[0] = '0';
            }
            else
            {
                j = strlen(header[i].bits);
                memmove(header[i].bits + 1, header[i].bits, j + 1);
                header[i].bits[0] = '1';
            }
        }
    }

    //下面的就是读原文件的每一个字符，按照设置好的编码替换文件中的字符
    fseek(ifp, 0, SEEK_SET);                                                //将指针定在文件起始位置
    fseek(ofp, 8, SEEK_SET);                                //以8位二进制数为单位进行读取
    buf[0] = 0;
    f = 0;
    pt1 = 8;

	printf("读取将要压缩的文件:%s\n",filename);
	printf("当前文件有:%d字符\n",flength);
	printf("正在压缩\n");

    while (!feof(ifp))
    {
        c = fgetc(ifp);
        f ++;
        for (i = 0; i < n; i ++)
        {
            if (c == header[i].b) break;
        }
        strcat(buf, header[i].bits);
        j = strlen(buf);
        c = 0;
        while (j >= 8)                                             //当剩余字符数量不小于8个时
        {
            for (i = 0; i < 8; i ++)                               //按照八位二进制数转化成十进制ASCII码写入文件一次进行压缩
            {
                if (buf[i] == '1') c = (c << 1) | 1;
                else c = c << 1;
            }
            fwrite(&c, 1, 1, ofp);
            pt1 ++;
            strcpy(buf, buf + 8);
            j = strlen(buf);
        }
		if(100 * f/flength > per)
		{
			printfPercent(per);
			per += 10;
		}
        if (f == flength)
			break;
    }
	printfPercent(100);

    if (j > 0)                                                      //当剩余字符数量少于8个时
    {
        strcat(buf, "00000000");
        for (i = 0; i < 8; i ++)
        {
            if (buf[i] == '1') c = (c << 1) | 1;
            else c = c << 1;                                        //对不足的位数进行补零
        }
        fwrite(&c, 1, 1, ofp);
        pt1 ++;
    }
    fseek(ofp, 0, SEEK_SET);                                        //将编码信息写入存储文件
	fwrite(&flength,1,sizeof(flength),ofp);
    fwrite(&pt1, sizeof(long), 1, ofp);
    fseek(ofp, pt1, SEEK_SET);
    fwrite(&n, sizeof(long), 1, ofp);
    for (i = 0; i < n; i ++)
    {
		tmp = header[i];

        fwrite(&(header[i].b), 1, 1, ofp);
		pt1++;
        c = strlen(header[i].bits);
        fwrite(&c, 1, 1, ofp);
		pt1++;
        j = strlen(header[i].bits);

        if (j % 8 != 0)                                             //当位数不满8时，对该数进行补零操作
        {
            for (f = j % 8; f < 8; f ++)
                strcat(header[i].bits, "0");
        }

        while (header[i].bits[0] != 0)
        {
            c = 0;
            for (j = 0; j < 8; j ++)
            {
                if (header[i].bits[j] == '1') c = (c << 1) | 1;
                else c = c << 1;
            }
            strcpy(header[i].bits, header[i].bits + 8);
            fwrite(&c, 1, 1, ofp);                                            //将所得的编码信息写入文件
			pt1++;
        }

		header[i] = tmp;
    }
    fclose(ifp);
    fclose(ofp);                                                              //关闭文件

	printf("压缩后文件为:%s\n",outputfile);
    printf("压缩后文件有:%d字符\n",pt1 + 4);

    return 1;                                       //返回压缩成功信息
}


//函数：uncompress()
//作用：解压缩文件，并将解压后的内容写入新文件
int uncompress(const char *filename,const char *outputfile)
{
    char buf[255], bx[255];
    unsigned char c;
	char out_filename[512];
    long i, j, m, n, f, p, l;
    long flength;
	int per = 10;
	int len = 0;
    FILE *ifp, *ofp;
	char c_name[512] = {0};
    ifp = fopen(filename, "rb");                                              //打开文件
    if (ifp == NULL)
    {
        return 0;     //若打开失败，则输出错误信息
    }

													  //读取原文件长
	if(outputfile)
		strcpy(out_filename,outputfile);
	else
		strcpy(out_filename,c_name);

    ofp = fopen(out_filename, "wb");                                            //打开文件
    if (ofp == NULL)
    {
        return 0;
    }

	fseek(ifp,0,SEEK_END);
	len = ftell(ifp);
	fseek(ifp,0,SEEK_SET);

	printf("将要读取解压的文件:%s\n",filename);
	printf("当前文件有:%d字符\n",len);
	printf("正在解压\n");

    fread(&flength, sizeof(long), 1, ifp);                                    //读取原文件长
    fread(&f, sizeof(long), 1, ifp);
    fseek(ifp, f, SEEK_SET);
    fread(&n, sizeof(long), 1, ifp);                                          //读取原文件各参数
    for (i = 0; i < n; i ++)                                                  //读取压缩文件内容并转换成二进制码
    {
        fread(&header[i].b, 1, 1, ifp);
        fread(&c, 1, 1, ifp);
        p = (long) c;
        header[i].count = p;
        header[i].bits[0] = 0;
        if (p % 8 > 0) m = p / 8 + 1;
        else m = p / 8;
        for (j = 0; j < m; j ++)
        {
            fread(&c, 1 , 1 , ifp);
            f = c;
            _itoa(f, buf, 2);
            f = strlen(buf);
            for (l = 8; l > f; l --)
            {
                strcat(header[i].bits, "0");                                  //位数不足，执行补零操作
            }
            strcat(header[i].bits, buf);
        }
        header[i].bits[p] = 0;
    }

    for (i = 0; i < n; i ++)
    {
        for (j = i + 1; j < n; j ++)
        {
            if (strlen(header[i].bits) > strlen(header[j].bits))
            {
                tmp = header[i];
                header[i] = header[j];
                header[j] = tmp;
            }
        }
    }

    p = strlen(header[n-1].bits);
    fseek(ifp, 8, SEEK_SET);
    m = 0;
    bx[0] = 0;


    while (1)
    {
        while (strlen(bx) < (unsigned int)p)
        {
            fread(&c, 1, 1, ifp);
            f = c;
            _itoa(f, buf, 2);
            f = strlen(buf);
            for (l = 8; l > f; l --)
            {
                strcat(bx, "0");
            }
            strcat(bx, buf);
        }
        for (i = 0; i < n; i ++)
        {
            if (memcmp(header[i].bits, bx, header[i].count) == 0) break;
        }
        strcpy(bx, bx + header[i].count);
        c = header[i].b;
        fwrite(&c, 1, 1, ofp);
        m ++;

		if(100 *  m/flength > per)
		{
			printfPercent(per);
			per += 10;
		}
        if (m == flength) break;
    }
	printfPercent(100);

    fclose(ifp);
    fclose(ofp);

	printf("解压后文件为:%s\n",out_filename);
    printf("解压后文件有:%d字符\n",flength);

    return 1;                   //输出成功信息
}

int main(int argc,const char *argv[])
{
	memset(&header,0,sizeof(header));
    memset(&tmp,0,sizeof(tmp));

	compress("测试文档.txt","测试文档.txt.zip");
	uncompress("测试文档.txt.zip","测试文档.txt 解压后.txt");
	system("pause");

	return 0;
}


 

2 功能展示

2.1 控制台显示



2.2 文件效果

开始时只有一个文件《测试文档.txt》：



打开《测试文档.txt》



《测试文档.txt》文件大小：



程序运行结束后多了两个文件：



以文本形式打开压缩二进制文件《测试文档.txt.zip》：



《测试文档.txt.zip》文件属性：

参考书籍：数据结构（C语言版）严蔚敏吴伟民编著清华大学出版社

本文中的代码可从这里下载：https://github.com/qingyujean/data-structure

1.哈夫曼树

    假设有n个权值{w1, w2, ..., wn}，试构造一棵含有n个叶子结点的二叉树，每个叶子节点带权威wi，则其中带权路径长度WPL最小的二叉树叫做最优二叉树或者哈夫曼树。

    特点：哈夫曼树中没有度为1的结点，故由n0 = n2+1以及m= n0+n1+n2，n1=0可推出m=2*n0-1，即一棵有n个叶子节点的哈夫曼树共有2n-1个节点。

2.哈夫曼编码

    通信传送的目标是使总码长尽可能的短。

    变长编码的原则：

    1.使用频率高的字符用尽可能短的编码（这样可以减少数据传输量）；

    2.任一字符的编码都不能作为另一个字符编码的开始部分（这样就使得在两个字符的编码之间不需要添加分隔符号）。这种编码称为前缀编码。

    根据每种字符在电文中出现的次数构造哈夫曼树，将哈夫曼树中每个分支结点的左分支标上0，右分支标上1，把从根结点到每个叶子结点的路径上的标号连接起来，作为叶结点所代表的字符的编码。这样得到的编码称为哈夫曼编码。

    思考：为什么哈夫曼编码符合变长编码的原则？哈夫曼树所构造出的编码的长度是不是最短的？

     哈夫曼树求得编码为最优前缀码的原因： 在构造哈夫曼树的过程中：

    1.权值大的在上层，权值小的在下层。满足出现频率高的码长短。

　2.树中没有一片叶子是另一叶子的祖先，每片叶子对应的编码就不可能是其它叶子编码的前缀。即上述编码是二进制的前缀码。

    假设每种字符在电文中出现的次数为wi （出现频率即为权值），其码长为li，电文中只有n种字符，则编码后电文总码长为，而哈夫曼树是WPL最小的二叉树，因此哈夫曼编码的码长最小。

3.哈夫曼编码实例

四种字符以及他们的权值：a:30, b:5, c:10, d:20

第一步：构建哈夫曼树



第二步：为哈夫曼树的每一条边编码



第三步：生成哈夫曼编码表



4.代码实现

4.1哈夫曼树定义

哈夫曼树的存储结构：采用静态三叉链表

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

#define N 4//带权值的叶子节点数或者是需要编码的字符数
#define M 2*N-1//n个叶子节点构造的哈夫曼树有2n-1个结点
#define MAX 10000
typedef char TElemType;
//静态三叉链表存储结构
typedef struct{
	//TElemType data;
	unsigned int weight;//权值只能是正数
	int parent;
	int lchild;
	int rchild;
}HTNode;//, *HuffmanTree;
typedef HTNode HuffmanTree[M+1];//0号单元不使用

typedef char * HuffmanCode[N+1];//存储每个字符的哈夫曼编码表，是一个字符指针数组，每个数组元素是指向字符指针的指针

 

4.2构造哈夫曼树

//构造哈夫曼树
void createHuffmanTree(HuffmanTree &HT, int *w, int n){
	if(n <= 1)
		return;
	//对树赋初值
	for(int i = 1; i <= n; i++){//HT前n个分量存储叶子节点，他们均带有权值
		HT[i].weight = w[i];
		HT[i].lchild = 0;
		HT[i].parent = 0;
		HT[i].rchild = 0;
	}
	for(int i=n+1; i <=M; i++){//HT后m-n个分量存储中间结点，最后一个分量显然是整棵树的根节点
		HT[i].weight = 0;
		HT[i].lchild = 0;
		HT[i].parent = 0;
		HT[i].rchild = 0;
	}
	//开始构建哈夫曼树，即创建HT的后m-n个结点的过程，直至创建出根节点。用哈夫曼算法
	for(int i = n+1; i <= M; i++){
		int s1, s2;
		select(HT, i-1, s1, s2);//在HT[1...i-1]里选择parent为0的且权值最小的2结点，其序号分别为s1,s2，parent不为0说明该结点已经参与构造了，故不许再考虑
		HT[s1].parent = i;
		HT[s2].parent = i;
		HT[i].lchild = s1;
		HT[i].rchild = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}
}

 

//在HT[1...k]里选择parent为0的且权值最小的2结点，其序号分别为s1,s2，parent不为0说明该结点已经参与构造了，故不许再考虑
void select(HuffmanTree HT, int k, int &s1, int &s2){
	//假设s1对应的权值总是<=s2对应的权值
	unsigned int tmp = MAX, tmpi = 0;
	for(int i = 1; i <= k; i++){
		if(!HT[i].parent){//parent必须为0
			if(tmp > HT[i].weight){
				tmp = HT[i].weight;//tmp最后为最小的weight
				tmpi = i;
			}
		}
	}
	s1 = tmpi;
	
	tmp = MAX;
	tmpi = 0;
	for(int i = 1; i <= k; i++){
		if((!HT[i].parent) && i!=s1){//parent为0
			if(tmp > HT[i].weight){
				tmp = HT[i].weight;
				tmpi = i;
			}
		}
	}
	s2 = tmpi;
}

 

打印哈夫曼树

//打印哈夫曼满树
void printHuffmanTree(HuffmanTree HT, char ch[]){
	printf("\n");
	printf("data, weight, parent, lchild, rchild\n");
	for(int i = 1; i <= M; i++){
		if(i > N){
			printf("  -, %5d, %5d, %5d, %5d\n", HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
		}else{
			printf("  %c, %5d, %5d, %5d, %5d\n", ch[i], HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
		}
	}
	printf("\n");
}

 

4.3编码

为哈夫曼树的每一条分支编码，并生成哈夫曼编码表HC

//为每个字符求解哈夫曼编码，从叶子到根逆向求解每个字符的哈夫曼编码
void encodingHuffmanCode(HuffmanTree HT, HuffmanCode &HC){
	//char *tmp = (char *)malloc(n * sizeof(char));//将每一个字符对应的编码放在临时工作空间tmp里，每个字符的编码长度不会超过n
	char tmp[N];
	tmp[N-1] = '\0';//编码的结束符
	int start, c, f;
	for(int i = 1; i <= N; i++){//对于第i个待编码字符即第i个带权值的叶子节点
		start = N-1;//编码生成以后，start将指向编码的起始位置
		c = i;
		f = HT[i].parent;

		while(f){//f!=0,即f不是根节点的父节点
			if(HT[f].lchild == c){
				tmp[--start] = '0';
			}else{//HT[f].rchild == c,注意:由于哈夫曼树中只存在叶子节点和度为2的节点，所以除开叶子节点，节点一定有左右2个分支
				tmp[--start] = '1';
			}
			c = f;
			f = HT[f].parent;
		}
		HC[i] = (char *)malloc((N-start)*sizeof(char));//每次tmp的后n-start个位置有编码存在
		strcpy(HC[i], &tmp[start]);//将tmp的后n-start个元素分给H[i]指向的的字符串
	}
}

打印哈夫曼编码表，当编码表生成以后，以后就可以对字符串进行编码了，只要对应编码表进行转换即可

//打印哈夫曼编码表
void printHuffmanCoding(HuffmanCode HC, char ch[]){
	printf("\n");
	for(int i = 1; i <= N; i++){
		printf("%c:%s\n", ch[i], HC[i]);
	}
	printf("\n");
}

 

4.4解码

//解码过程：从哈夫曼树的根节点出发，按字符'0'或'1'确定找其左孩子或右孩子，直至找到叶子节点即可，便求得该字串相应的字符
void decodingHuffmanCode(HuffmanTree HT, char *ch, char testDecodingStr[], int len, char *result){
	int p = M;//HT的最后一个节点是根节点，前n个节点是叶子节点
	int i = 0;//指示测试串中的第i个字符
	//char result[30];//存储解码以后的字符串
	int j = 0;//指示结果串中的第j个字符
	while(i<len){
		if(testDecodingStr[i] == '0'){
			p = HT[p].lchild;
		}
		if(testDecodingStr[i] == '1'){
			p = HT[p].rchild;
		}

		if(p <= N){//p<=N则表明p为叶子节点,因为在构造哈夫曼树HT时，HT的m个节点中前n个节点为叶子节点
			result[j] = ch[p];
			j++;
			p = M;//p重新指向根节点
		}
		i++;
	}
	result[j] = '\0';//结果串的结束符	
}

 

4.5演示

int main(){
	HuffmanTree HT;
	
	TElemType ch[N+1];//0号单元不使用，存储n个等待编码的字符
	int w[N+1];//0号单元不使用，存储n个字符对应的权值
	printf("请输入%d个字符以及该字符对应的权值(如:a,20):\n", N);
	for(int i = 1; i <= N; i++){
		scanf("%c,%d", &ch[i], &w[i]);
		getchar();//吃掉换行符
	}//即w里第i个权值对应的是ch里第i个字符元素


	createHuffmanTree(HT, w , N);//构建哈夫曼树
	printHuffmanTree(HT, ch);
	
	HuffmanCode HC;//HC有n个元素，每个元素是一个指向字符串的指针，即每个元素是一个char *的变量
	encodingHuffmanCode(HT, HC);//为每个字符求解哈夫曼编码
	printHuffmanCoding(HC, ch);

	//解码测试用例：abaccda----01000101101110
	char * testDecodingStr = "01000101101110";
	int testDecodingStrLen = 14;
	printf("编码%s对应的字符串是：", testDecodingStr);
	char result[30];//存储解码以后的字符串
	decodingHuffmanCode(HT, ch, testDecodingStr, testDecodingStrLen, result);//解码（译码），通过一段给定的编码翻译成对应的字符串
	printf("%s\n", result);

    return 0;
}




 

本文中的代码可从这里下载：https://github.com/qingyujean/data-structure