Huffman Coding_final

 avatar
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]] ;
}