HC4
user_3763047219
c_cpp
3 years ago
1.6 kB
3
Indexable
#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; int f[n] = { 0 }; deque<Node*> tree; cin >> n; 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]] ; }
Editor is loading...