哈夫曼编码

先构建哈夫曼树，再用哈夫曼树进行编码。

0、哈夫曼树的存储结构

在这哈夫曼树不使用链表存储，而是使用数组下标方式的存储结构，即lchild、rchild、parent中存储的是相应元素对应的下标值。 而编码结果用数组存储，一维数组中存储的是对应编码字符串的首地址，这样可以实现边长的存储。

typedef struct HTNode{ int weight; int lchild, rchild, parent; }HTNode,*HuffmanTree; typedef char** HuffmanCode;

1、构建哈夫曼树

哈夫曼树不是满二叉树（每一层都是满的），也不是完全二叉树（深度为n，n-1层是满的，剩余的先左再右）。其叶子结点数n与结点树总和m的关系m=2*n-1，因为哈夫曼树的所有结点的度都为0或者2，从分叉数来看，一共有(n-1)*2个分叉，分叉数+1等于结点数，所以m=(n-1)*2+1=2*n-1个。 接下来，前n个结点的weight初始化为权重值，剩余lchild、rchild和parent初始化为-1，n-m个结点全初始化为-1。 构建哈夫曼树的时候，对于第n-m个结点，每次从前面parent为-1的结点中选取最小的两个结点，求和，并设置结点的parent，与设置当前结点的值。

int m = 2 * n - 1; HT = (HuffmanTree)malloc(sizeof(HTNode)*m); HuffmanTree p = HT; for (int i = 0; i < n; i++, p++){ *p = { weight[i], -1, -1, -1 }; } for (int i = n; i < m; i++, p++){ *p = { -1, -1, -1, -1 }; } p = HT + n; int h1, h2; for (int i = n; i < m; i++, p++){ SelectTwo(HT, h1, h2, i); HT[h1].parent = i; HT[h2].parent = i; *p = { HT[h1].weight + HT[h2].weight, h1, h2, -1 }; }

从parent != -1 的所有结点中选出两个最小的：

void SelectTwo(HuffmanTree HT, int &p1, int &p2, int length){ int min1 = 999; int min2 = 999; int index = 0; for (int i = 0; i < length; i++){ if (HT[i].parent== -1 && HT[i].weight < min1){ p1 = i; min1 = HT[i].weight; } } for (int i = 0; i < length; i++){ if (i == p1){ continue; } if (HT[i].parent == -1 && HT[i].weight < min2){ p2 = i; min2 = HT[i].weight; } } }

2、哈夫曼编码

编码需要注意的是，从叶子结点向根结点，反向寻找编码，因为这样方便判断到底是左结点的0还是右结点的1编码。 同时，字符串的结尾为’\0’，不要忘记了！！

HC = (HuffmanCode)malloc(sizeof(char*)*n); char *str = (char*)malloc(sizeof(char)*(n + 1)); str[n] = '\0'; for (int i = 0; i < n; i++){ int index = n; for (int j = HT[i].parent, last = i; j != -1; last = j, j = HT[j].parent){ if (HT[j].lchild == last){ str[--index] = '0'; } else{ str[--index] = '1'; } } HC[i] = (char*)malloc(sizeof(char)*n - index); strcpy(HC[i], &str[index]); }