* 对给定的一组权值，实现HuffMan编码，时间复杂度1/2n^2
* 第一步：由已知的n个权值形成哈夫曼的初态
* 第二步：建立哈夫曼结点数组。依次对前面已建立的结点作如下处理
* 1. 选择两个权值最小且无双亲的权
* 2. 根据选出来的两个权构造新的哈夫曼结点，修改两个点父亲结点为新建的节点
* 第三步：对哈夫曼树进行哈夫曼编码：从权结点逆序到根节点写出01编码，
然后再次逆序（正序）存储到哈夫曼编码数组中
1
#include<iostream>
2#include<iomanip>
3
4using std::endl;
5using std::cout;
6using std::setw;
7
8const int maxlen = 10; //HuffMan编码最大长度
9const int MAX = 100; //比任何权重大的一个数
10
11struct HuffNode
12
{
13
int weight;
14 int parent;
15 int lchild;
16 int rchild;
17
};
18
19struct HuffCode
20{
21 int bit[maxlen]; //HuffMan 编码
22 int length; //HuffMan 编码长度
23 int weight;
24};
25
26void Huffman(int weight[], int n, HuffNode hn[], HuffCode hc[])
27{
28 int i,j,l,r; //l,r分别代表新建的节点所用到的两个结点
29 int min1,min2; //存储每次选择的最小的两个权
30
31 for(i = 0; i != 2*n - 1; ++i) //create Huffman Node,step 1
32
{
33 if(i < n) hn[i].weight= weight[i];
34 else hn[i].weight = 0;
35 hn[i].parent = 0;
36 hn[i].lchild = hn[i].rchild = -1;
37
}
38 for(i = 0; i != n-1; ++i) //create Huffman Node, step 2
39 {
40 min1 = min2 = MAX;
41 l = r = 0;
42 /**//* 下面的一段程序本来是想直接通过输入值确定min1,min2的初始值的，因为像上面那个MAX，不知如何给。
43 但是这个代码错了，因为n+i-1,n+i-2不能保证其parent=0，还没想到其他方法
44 min1 = hn[n+i-1].weight;
45 min2 = hn[n+i-2].weight;
46 l = n+i-1;
47 r = n+i-2;
48 if(min1 > min2)
49 {
50 int temp = min1;
51 min1 = min2;
52 min2 = temp;
53 int t = l;
54 l = r;
55 r = t;
56 }
57 */
58 //find two minimum data
59 for(j = 0; j != n+i; j++)
60 {
61 if(hn[j].weight < min1 && hn[j].parent == 0)
62 {
63 min2 = min1;
64 min1 = hn[j].weight;
65 r = l;
66 l = j;
67 }
68 else if(hn[j].weight < min2 && hn[j].parent == 0)
69 {
70 min2 = hn[j].weight;
71 r = j;
72 }
73 else ;
74 }
75
76 //create a new Huffman Node
77 hn[n+i].weight = min1+min2;
78 hn[l].parent = n+i;
79 hn[r].parent = n+i;
80 hn[n+i].lchild = l;
81 hn[n+i].rchild = r;
82 }
83
84 int temp[maxlen]; //在此逆序存储Huffman编码
85
86 for(i = 0; i != n; ++i)
87 {
88 j = 0;
89 int child = i;
90 int parent = hn[i].parent;
91 while(hn[child].parent != 0) //逆序存储
92 {
93 if(hn[parent].lchild == child) temp[j++] = 0;
94 else temp[j++] = 1;
95 child = parent;
96 parent = hn[parent].parent;
97 }
98
99 //正序存储到HuffCode中
100 int k=0;
101 hc[i].length = j;
102 hc[i].weight = weight[i];
103 while(j) hc[i].bit[k++] = temp[--j];
104 }
105
106}
107
108const int N = 7;
109
110int main()
111{
112 int a[N] = {4,2,6,8,3,2,1};
113 HuffNode *hn = new HuffNode[2*N-1];
114 HuffCode *hc = new HuffCode[N];
115
116 Huffman(a,N,hn,hc);
117
118 for(int i=0; i < 2*N -1; ++i)
119 {
120 cout << setw(3) << hn[i].weight << setw(3) << hn[i].parent << setw(3) << hn[i].lchild << setw(3) << hn[i].rchild <<endl;
121 }
122 for(int j=0; j != N; ++j)
123 {
124 cout << "weight = " << hc[j].weight << ", code = ";
125 for(int k = 0; k != hc[j].length; ++k) cout << hc[j].bit[k];
126 cout << endl;
127 }
128 return 0;
129}
