[code]
\n\/\/Originally FOUND in Internet
\n\/\/by RIT2009061 vikesh iiita<\/p>\n
\/\/Author: Ujjal Suttra DHar [CSE’08,RUET]<\/p>\n
#include <iostream>
\n#include <fstream>
\n#include <vector>
\n#include <string>
\n#include <queue>
\n#include <algorithm><\/p>\n
using namespace std;<\/p>\n
struct node {
\n\tint weight;
\n\tchar value;
\n\tconst node *child0;
\n\tconst node *child1;<\/p>\n
\tnode( int c, int i ) {
\n\t\tvalue = c;
\n\t\tweight = i;
\n\t\tchild0 = 0;
\n\t\tchild1 = 0;
\n\t}<\/p>\n
\tnode( const node* c0, const node* c1 ) {
\n\t\tvalue = 0;
\n\t\tweight = c0->weight + c1->weight;
\n\t\tchild0 = c0;
\n\t\tchild1 = c1;
\n\t}<\/p>\n
\tbool operator<( const node &a ) const {
\n\t\tif(weight ==a.weight)
\n\t\t return value>a.value;
\n else
\n\t\t return weight >a.weight;
\n\t}<\/p>\n
void traverse(string code="") const{<\/p>\n
\tif ( child0 ) {
\n\t\tchild0->traverse( code + ‘0’ );
\n\t\tchild1->traverse( code + ‘1’ );
\n\t} else {
\n\t\tcout <<" " <<value <<"\t ";
\n\t\tcout <<weight;
\n\t\tcout <<"\t " <<code <<endl;
\n\t}
\n}<\/p>\n
};<\/p>\n
\/*
\nvoid count_chars( int *counts )
\n{
\n\tfor ( int i = 0 ; i <256 ; i++ )
\n\t\tcounts[ i ] = 0;<\/p>\n
freopen("input.dat","r",stdin);<\/p>\n
char c;
\nwhile((c=getchar())!=EOF)
\n counts[c]++;
\n}<\/p>\n
*\/<\/p>\n
int main()
\n{<\/p>\n
freopen("input.dat","r",stdin);<\/p>\n
\tint counts[ 256 ];
\n\tchar a[1000];<\/p>\n
gets(a);<\/p>\n
for ( int i = 0 ; i <256 ; i++ )
\n\t\tcounts[ i ] = 0;<\/p>\n
for(int i=0;i<strlen(a);i++)
\n\tcounts[a[i]]++;<\/p>\n
\tpriority_queue < node > q;<\/p>\n
\tfor (int i = 0 ; i <256 ; i++ )
\n\t\tif ( counts[ i ] )
\n\t\t\tq.push( node( i, counts[ i ] ) );<\/p>\n
\/\/if you wanna show the queue
\n\/*while(!q.empty()){
\n cout<<q.top().value<<endl;
\n q.pop();
\n }
\n*\/<\/p>\n
\twhile ( q.size() >1 ) {
\n\t\tnode *child0 = new node( q.top() );
\n\t\tq.pop();
\n\t\tnode *child1 = new node( q.top() );
\n\t\tq.pop();
\n\t\tq.push( node( child0, child1 ) );
\n\t}<\/p>\n
\tcout <<"CHAR FREQUENCY HOFFMAN-CODE" <<endl;
\n\tq.top().traverse();
\n\treturn 0;
\n}<\/p>\n
[\/code]<\/p>\n","protected":false},"excerpt":{"rendered":"
[code] \/\/Originally FOUND in Internet \/\/by RIT2009061 vikesh iiita \/\/Author: Ujjal Suttra DHar [CSE’08,RUET] #include <iostream> #include <fstream> #include <vector> #include <string> #include <queue> #include <algorithm> using namespace std; struct node { int weight; char value; const node *child0; const node *child1; node( int c, int i ) { value = c; weight = i; … <\/p>\n