# Huffman Coding_final

user_3763047219
c_cpp
2 years ago
1.6 kB
4
Indexable
Never
```#include <iostream>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <map>
using namespace std;

struct Node {
int value;
Node* left;
Node* right;
};

void huffman(Node* node, map<int, string>& HC_bin, string text) {
if (node->left == NULL && node->right == NULL) {
HC_bin[node->value] = text;
//45 13 12 16 9 5
// 下次過來時 int 45 對到的 string="0"
}
else {
// 100會到這 得到 binaryStr="0"
huffman(node->left, HC_bin, text + "0");
huffman(node->right, HC_bin, text + "1");
}
}

bool sortlist(Node* f1, Node* f2) {
return f1->value < f2->value;
}

int main() {
int n;
cin >> n;

int f[n] = { 0 };
deque<Node*> tree;

Node* tmp;
for (int i = 0; i < n; i++) {
cin >> f[i];
tmp = new Node;
tmp->value = f[i];
tmp->left = NULL;
tmp->right = NULL;
tree.push_back(tmp);
}

for (int i = 0; i < n - 1; i++) {
sort(tree.begin(), tree.end(), sortlist);
//new 自行配置一個記憶體給tmp
tmp = new Node;
//tmp指到的地方的value=最小的兩個相加
tmp->value = tree[0]->value + tree[1]->value;
tmp->left = tree[0];
tmp->right = tree[1];
//移除前兩個元素
tree.pop_front();
tree.pop_front();
//把tmp塞到柱列裡
tree.push_back(tmp);
}
// 除了100 其他都刪光光了(有被指到)
Node* root = tree.front();

// 做出一個空的map (叫做 HC_bin)
map<int, string> HC_bin;
huffman(root, HC_bin, "");

cout << n;
cout << "\n";
for (int i = 0; i < n-1; i++) {
cout << HC_bin[f[i]] << " ";
}
cout << HC_bin[f[n]] ;
}```