2014-11-27 11:01:23

# 哈夫曼编码

## 编码方式

`abbcccdddde`这个是一个字符串，一共有5个字符。每个字符的权值就是出现的频率，那么`a`就是1`b`权值为2`c`的权值为3`d`的权值为4`e`的权值为1。在普通的编码方式中，表示5个字母最少要3位，也就是3bit.那么这串字符就需要1*3+2*3+3*3+4*3+1*3=33 bits。而使用哈夫曼的编码呢？

``````       2
/ \
1   1``````

``````           4
/   \
2     2
/  \
1    1``````

``      ...省略ing``

``````                     11
/       \
7         4
/  \       / \
3    4     2   2
/ \
1   1``````

`c`的就是`00`, `d`的就是`01`,`a`的是`100`,`b`=`11`,`e`=`101`.这样就成功了。

## 代码实现

```//
//  main.cpp
//  HuffmanCode
//
//  Created by Alps on 14/11/22.
//

#include
using namespace std;
typedef struct HTNode{
int weight;
int parent;
int lchild;
int rchild;
}HTNode, *HuffmanTree;
typedef char** HuffmanCode;

void Select(HuffmanTree HT, int num, int &child1, int &child2);

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){
//
int m,i;
int child1,child2;
if (n <= 1) {
return;
}
m = n*2-1;//整棵树的节点数
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));//申请足够空间
for (i = 1; i <= n; i++,w++) {
HT[i] = {*w, 0, 0, 0};
}
for (; i <= m; i++) {
HT[i] = {0, 0, 0, 0};
}
for (i = n+1; i <= m; i++) {
Select(HT,i-1,child1,child2);
HT[child1].parent = i;
HT[child2].parent = i;
HT[i].lchild = child1;
HT[i].rchild = child2;
HT[i].weight = HT[child1].weight + HT[child2].weight;
printf("%d==%d\n",child1,child2);
}

HC = (char**)malloc((n+1)*sizeof(char *));

char *cd = (char*)malloc(n*sizeof(char));
//    memset(cd, '\0', n*sizeof(char));
int c = 0;

int tempParent,count;
for (i = 1; i <= n; i++) {
count = 0;
for (c = i,tempParent = HT[i].parent; tempParent != 0;c=tempParent, tempParent = HT[tempParent].parent) {
if (HT[tempParent].lchild == c) {
cd[count++] = '0';
}else{
cd[count++] = '1';
}
}
cd[count]='\0';
printf("%s~%d\n",cd,i);
HC[i] = (char *)malloc((count)*sizeof(char));

strcpy(HC[i], cd);
//        memset(cd,'\0', n*sizeof(char));//error
}
}

void Select(HuffmanTree HT, int num, int &child1, int &child2){
child1 = 0;
child2 = 0;
int w1 = 0;
int w2 = 0;
for (int i = 1; i <= num; i++) {
if (HT[i].parent == 0) {
if (child1 == 0) {
child1 = i;
w1 = HT[i].weight;
continue;
}
if (child2 == 0) {
child2 = i;
w2 = HT[i].weight;
continue;
}
if (w1 > w2 && w1 > HT[i].weight) {
w1 = HT[i].weight;
child1 = i;
continue;
}
if (w2 > w1 && w2 > HT[i].weight) {
w2 = HT[i].weight;
child2 = i;
continue;
}
}
}
}

int main(int argc, const char * argv[]) {
char a[] = "abcaab";
int i = (int)strlen(a);
printf("%d\n",i);

int b[]={1,2,3,4};
HuffmanTree HT;
HuffmanCode HC;
HuffmanCoding(HT, HC, b, 4);
for (i = 1; i <= 7; i++) {
printf("%d-%d\n",HT[i].weight,HT[i].parent);
}
for (i = 1; i <=4; i++) {
printf("%s\n",HC[i]);
}
return 0;
}
```