#include<bits/stdc++.h>
using namespace std;
struct node{
int weight;
int parent;
int left;
int right;
};
class Huffman{
public:
Huffman(int n, const int w[]);
void HuffmanCode(int n);
void Decode(int m, char *s);
~Huffman();
private:
node *root;
char **code;
int getMin(int n);
void select(int n, int &s1, int &s2);
};
Huffman:: Huffman(int n, const int w[]) {
int m = 2*n-1, i;
int s1, s2;
if(n <= 1) {
cout << "Size error!" << endl;
return;
}
root = new node[m+5];
if(!root) {
cout << "Malloc error!" << endl;
exit(-1);
}
// 初始化
node *p = root+1;
for (i = 1; i <= n; ++i, ++(p)) {
p->weight = w[i];
p->parent = 0;
p->right = 0;
p->left = 0;
}
while(i <= m) {
p->parent = 0;
p++;
i++;
}
for (i = n+1; i <= m; ++i) {
select(i-1, s1, s2);
root[s1].parent = root[s2].parent = i;
root[i].left = s1;
root[i].right = s2;
root[i].weight = root[s1].weight+root[s2].weight;
}
}
void Huffman:: HuffmanCode(int n) {
code = new char*[n+5];
if(!*code) {
cout << "Malloc error1" << endl;
exit(-1);
}
char *tmp = new char[n+5];
//char debug[100], dd;
if(!tmp) {
cout << "Malloc error2";
exit(-1);
}
tmp[n-1] = 0;
int st;
for (int i = 1; i <= n; ++i) {
st = n-1;
for (int j = i, f = root[j].parent; f; j = f, f = root[f].parent) {
if(root[f].left == j)
tmp[--st] = '0';
else if(root[f].right == j)
tmp[--st] = '1';
//dd = tmp[st+1]; // debug
//cout << "dd: " << dd << endl;
}
code[i] = new char[n-st];
//strcpy(debug, tmp+st);
//cout << "debug: " << debug << endl;
strcpy(code[i], tmp+st);
}
delete []tmp;
for (int i = 1; i <= n; ++i) {
cout << "The Huffmancode is " << root[i].weight << " : " << code[i] << endl;
}
}
void Huffman:: Decode(int n, char *s) {
int len = strlen(s), pt = 2*n-1;
for (int i = 0; i < len; ++i) {
if(s[i] == '0') {
pt = root[pt].left;
if(pt <= n) {
cout << root[pt].weight << " ";
pt = 2*n-1;
}
} else if(s[i] == '1') {
pt = root[pt].right;
if(pt <= n) {
cout << root[pt].weight << " ";
pt = 2*n-1;
}
}
}
cout << endl;
}
Huffman:: ~Huffman() {
delete []root;
delete []code;
cout << "The Huffmantree has been destroyed." << endl;
}
int Huffman:: getMin(int n) {
int Min = 100;
int flag = 0; //用来记录已遍历过的结点
for(int i = 1; i <= n; ++i) {
if ((root + i)->weight < Min && (root + i)->parent == 0) {
Min = (root + i)->weight;
flag = i;
}
}
//给选中的结点置 1, 下次不需要再遍历
(root + flag)->parent = 1;
return flag;
}
void Huffman:: select(int n, int &s1, int &s2) {
s1 = getMin(n);
s2 = getMin(n);
//目的是 s1 的权值要不大于 s2 的权值
if ((root + s1)->weight > (root + s2)->weight) {
swap(s1, s2);
}
}
int main() {
int n;
cin >> n;
int w[5];
for (int i = 1; i <= n; ++i) {
cin >> w[i];
}
Huffman h_test(n, w);
h_test.HuffmanCode(n);
h_test.Decode(n, "10011");
return 0;
}