fork(4) download
  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
stdin
so many men, so many minds
stdout
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];
}