fork(29) download
copy 
  1. #include <queue>
  2. #include <iostream>
  3. #include <sstream> 
  4. using namespace std;
  5.  
  6. struct Node {
  7. 	string value, code;
  8. 	unsigned amount;
  9. 	Node * left;
  10. 	Node * right;
  11. 	// компаратор
  12. 	bool operator() (const Node& x, const Node& y) const {
  13. 		return x.amount > y.amount;
  14. 	}
  15. 	// конструктор по умолчанию нужен для создания объекта-компаратора
  16. 	Node (const string& value = "", unsigned amount = 0, Node * left = 0, Node * right = 0) {
  17. 		this->value = value; // множество символом узла
  18. 		this->code = ""; // строковое представление битового кода узла
  19. 		this->amount = amount; // сколько раз втретилось
  20. 		this->left = left; // левый ребенок
  21. 		this->right = right; // правый ребенок
  22. 	}
  23. 	// генерация DOT-описания полученного дерева 
  24. 	string to_str() {
  25. 		ostringstream x;
  26. 		if (left != 0 || right != 0) { // дерево таково, что либо есть оба ребенка либо нет ни одного
  27. 			x << "\t\"" << code << ": " << value << "[" << amount << "]\" -> \""  << left->code << ": " << left->value << "[" << left->amount << "]\";\n";
  28. 			x << left->to_str();
  29. 			x << "\t\"" << code << ": " << value << "[" << amount << "]\" -> \""  << right->code << ": " << right->value << "[" << right->amount << "]\";\n";
  30. 			x << right->to_str();
  31. 		} else {
  32. 			x << "\t\"" << code << ": " << value << "[" << amount << "]\" [shape=box, style=filled, fillcolor=green];\n";
  33. 		}
  34. 		return x.str();
  35. 	}
  36. 	//  объединение деревьев
  37. 	Node * join (Node x) {
  38. 		return new Node(x.value + value, x.amount + amount, new Node(x), this);
  39. 	}
  40. 	// проход по дереву с генерацией кода
  41. 	void traversal_code(string code) {
  42. 		this->code = code;
  43. 		if (left != 0 || right != 0) {
  44. 			left->traversal_code(code + "1");
  45. 			right->traversal_code(code + "0");
  46. 		}
  47. 	}
  48. 	// строим дерево по алгоритму Хаффмана
  49. 	static Node * builder(priority_queue<Node, vector<Node>, Node> graph) {
  50. 		while (graph.size() > 1) {
  51. 			Node *n = new Node(graph.top());
  52. 			graph.pop();
  53. 			graph.push(*n->join(*new Node(graph.top())));
  54. 			graph.pop();
  55. 		}
  56. 		return new Node(graph.top());
  57. 	}
  58. };
  59.  
  60. unsigned amounts[256]; // массив счетчиков встречаемости символов
  61. int main() {
  62. 	string s;
  63. 	getline (std::cin, s); // читаем строку вместе с пробелами
  64. 	for(auto i: s) amounts[i]++;
  65.     priority_queue<Node, vector<Node>, Node> graph;
  66. 	for(int i = 'a'; i <= 'z'; i++) // записываем в очередь с приоритетами 
  67. 		if (amounts[i] > 0) graph.emplace(s=(char)i, amounts[i]);
  68. 	Node *n = Node::builder(graph);
  69. 	n->traversal_code("");
  70. 	// генерируем ссылку на сервис Google для генерации изображений по описанию графа
  71. 	cout << "http://chart.apis.google.com/chart?cht=gv&chl=" << endl;
  72. 	// генерируем DOT-описание полученного дерева для отрисовки
  73. 	cout << "Digraph G {\n" << n->to_str() << "}";
  74. 	// Если вывод программы скопировать и вставить в адресную строку браузера, то увидим картинку.	
  75. }
Success #stdin #stdout 0s 16088KB
comments (?)
stdin
copy 
so many men, so many minds
stdout
copy 
http://chart.apis.google.com/chart?cht=gv&chl=
Digraph G {
	": noisedaym[20]" -> "1: noised[12]";
	"1: noised[12]" -> "11: noi[7]";
	"11: noi[7]" -> "111: n[4]";
	"111: n[4]" [shape=box, style=filled, fillcolor=green];
	"11: noi[7]" -> "110: oi[3]";
	"110: oi[3]" -> "1101: o[2]";
	"1101: o[2]" [shape=box, style=filled, fillcolor=green];
	"110: oi[3]" -> "1100: i[1]";
	"1100: i[1]" [shape=box, style=filled, fillcolor=green];
	"1: noised[12]" -> "10: sed[5]";
	"10: sed[5]" -> "101: s[3]";
	"101: s[3]" [shape=box, style=filled, fillcolor=green];
	"10: sed[5]" -> "100: ed[2]";
	"100: ed[2]" -> "1001: e[1]";
	"1001: e[1]" [shape=box, style=filled, fillcolor=green];
	"100: ed[2]" -> "1000: d[1]";
	"1000: d[1]" [shape=box, style=filled, fillcolor=green];
	": noisedaym[20]" -> "0: aym[8]";
	"0: aym[8]" -> "01: ay[4]";
	"01: ay[4]" -> "011: a[2]";
	"011: a[2]" [shape=box, style=filled, fillcolor=green];
	"01: ay[4]" -> "010: y[2]";
	"010: y[2]" [shape=box, style=filled, fillcolor=green];
	"0: aym[8]" -> "00: m[4]";
	"00: m[4]" [shape=box, style=filled, fillcolor=green];
}
https://ideone.com/nwA0BC
Алгоритм Хаффмана
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!