fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. #include <map>
  5. #include <string>
  6. #include <fstream>
  7. using namespace std;
  8.  
  9.  
  10.  
  11. class Node {
  12.     public:
  13.     int a;
  14.     char c;
  15.     Node *left, *right;
  16.     Node() {}
  17.     Node(Node *L, Node *R){
  18.         left=L;
  19.         right =R;
  20.         a=L->a + R->a;
  21.     }
  22. };
  23.  
  24. struct MyCompare {
  25.     bool operator() (Node *l, Node *r) const
  26.     { return l->a < r->a;}
  27. };
  28. void BuildTable(Node *root, vector<bool> &code, map<char, vector<bool> > &table) 
  29. {
  30. 	if (root->left){
  31. 		code.push_back(0);
  32. 		BuildTable(root->left, code, table);
  33. 	}
  34. 	if (root->right){
  35. 		code.push_back(1); 
  36. 		BuildTable(root->right, code, table);
  37. 	}
  38. 	if (root->c)
  39. 		table[root->c] = code;
  40. 	if (code.size())
  41. 		code.pop_back();
  42. }
  43.  
  44. int main()
  45. {
  46.  
  47.    ifstream f("l.txt") ;
  48.    map <char, int> m;
  49.    while(!f.eof()) {
  50.        char c=f.get();
  51.        m[c]++;
  52.    }
  53.  
  54.    list<Node*> t;
  55.    map <char, int> :: iterator i;
  56.    for(i=m.begin(); i!=m.end(); i++){
  57.        Node *p=new Node;
  58.        p->c=i->first;
  59.        p->a=i->second;
  60.        t.push_back(p);
  61.    }
  62.    while (t.size()!=1){
  63.        t.sort(MyCompare());
  64.        Node *SonL=t.front();
  65.        t.pop_front();
  66.        Node *SonR=t.front();
  67.        t.pop_front();
  68.        Node *parent= new Node(SonL, SonR);
  69.        t.push_back(parent);
  70.    }
  71.    Node *root=t.front();
  72.  
  73.    vector <bool> code;
  74. map <char, vector<bool> > table;
  75.    BuildTable(root, code, table);
  76.    for (i = m.begin(); i != m.end(); i++)
  77. 	{
  78. 		if((int (i->first))==10) cout<<"\n" << "-" << i->second;
  79. 		cout << i->first << " - "<< i->second<< " ";
  80. 		for (int j = 0; j < table[i->first].size(); j++)
  81. 			cout << table[i->first][j];
  82. 		cout << endl;
  83. 	}
  84. 	while(!f.eof()){
  85.           char c=f.get();
  86.           for (int j = 0; j < table[c].size(); j++){
  87. 			cout << table[c][j];
  88. 		   }
  89.         }
  90.         cout <<endl;
  91.         f.close();
  92.  
  93.  
  94.     return 0;
  95. }
  96.  
Success #stdin #stdout 0s 4408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4xz1nk
language:
C++14 (gcc 8.3)
created:
4 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!