《趣学算法》学习打卡：Day2

神秘电报密码——哈夫曼编码（哈夫曼树）

哈夫曼编码 ：

（一）：编码尽可能的短：根据字符使用频率不同（权值不同），当进行编码储存时，频率高的编码短，频率低的编码长（不定长编码），从而节省储存空间。

注： 如果字符使用的频率是相同的，固定长度编码时空间效率最高的办法

（二）：消除二义性（前缀码特性）；一个高频字符（编码短的）不能是其他低频字符的前缀。

例如： a=0,b=1,c=01,d=11 ,a是c的前缀，b是d的前缀，用来储存时就会产生二义性

哈夫曼编码的思路是以字符的使用频率作为权来构建一棵哈夫曼树，利用哈夫曼树对字符进行编码。

哈夫曼算法采取的贪心策略是每次从树的集合中取出没有双亲且权值最小的两棵树作为左右子树，构造一个新树，新树根结点的权值为其左右孩子结点的权值之和，将新树插入到树的集合中。

先来捋一捋思路再看代码吧，下面都是书上给的伪码，一下子看有点串

首先我们清楚完成哈夫曼编码是有两个步骤的：

1. 构建哈夫曼树

关于数据：假设我们有n个字符，那么我们最后的到的哈夫曼树一共有多少个结点呢？答案是2*n-1个，恰好是每个字符中间插入一个结点来组成树插入的结点数（n-1）；

那么怎么去表示这些结点呢？这时候就需要设计一个结点结构体了，（见下文：节点结构体）

在设计好结构体以后，就只要简单的初始化结点的数据和录入n个字符及其权值就okk了；

在数据都准备好了的现在；按照哈夫曼贪心策略，选择结点（有权值的）中权值最小的两个结点，把他们的权值之和赋给下一个权值为空的结点的权值，把他们的ID按照左小右大计入左右子树中（下标）。

重复上面的步骤到2*（n-1）中的权值不为0；

这里应该要配图的，不然太抽象了,ppt演示这种需要动态变化的一定会更直观

假设n=6={a=5,b=32,c=18,d=7,e=25,f=13};则

哈夫曼结点数组：

i	weight	parent	lchild	rchild	value
0	5	-1->6	-1	-1	a
1	32	-1	-1	-1	b
2	18	-1	-1	-1	c
3	7	-1->6	-1	-1	d
4	25	-1	-1	-1	e
5	13	-1	-1	-1	f
6	0—>12	-1->7	-1->0	-1->3
7	0->25	-1	-1->6	-1->5
8	0	-1	-1	-1
9	0	-1	-1	-1
10	0	-1	-1	-1

好了，这个画图有点浪费时间，下面的自己脑补一下吧

2. 输出哈夫曼编码

ok，到这里你应该知道，我们是怎样构建哈夫曼树的了，如果你还不会，那么请仔细阅读上面的部分。或者直接参考课本的相应章节。

重点在于怎么借助哈夫曼树构建编码

对于字母符的结点，他是一定有双亲的，我们从当前（字符）叶子结点出发，去找到双亲，判断自己是双亲的左子树还是右子树，左子树记为0，右子树记为1，写在编码结构体的HCodeType.bit[]中（从后面往前面记，输出的时候正着输出就是这个字符的编码）；然后找双亲的双亲（祖父母？？），判断……，直到结点没双亲。

1. 数据结构：

结点结构体：

typedef struct
{
    double weight;//权值
    int parent;   //双亲
    int lchild;   //左孩子
    int rchild;   //右孩子
    char value;   //代表的字符
}HNodeType

注：-1表示没有**

编码结构体：

typedef struct
{
    int bit[MAXBIT];//储存编码的数组
    int start;      //编码开始的下标
}HcodeType

? 2.初始化

结点初始化

for(int i=0;i<2*n-1;i++)
{
	HuffNode[i].weight=0;
	HuffNode[i].parent=-1;
	HuffNode[i].lchild=-1;
	HuffNode[i].rchild=-1;
}
/*输入n个叶子结点的字符及权值*/
for(i=0;i>HuffNode[i].value>>HuffNode[i].weight;
}

输入n个叶子结点的字符及权值

? 3.循环构造Huffman树

所有的结点都放在一个集合T中表示

s从树集合中取出两个权值最小的树t_i，t_j，把他们合成一棵新树z_k，新树的左儿子为t_i，右孩子为t_j，Z_k的权值为t_i和t_j的权值之和。

int i,j,x1,x2;//x1、x2为最小权值结点的序号。
double m1,m2;//m1、m2为最小权值结点的权值。
for(i=0;i

void HuffmanCode(HCodeType Huffcode[MAXLEAF],int n)
{
    /*定义一个临时变量来存放求解编码时的信息*/
	HCodeType cd;  
    int i,j,c,p;
    for(i=0;i