All pastes #53291 Raw Edit

Someone

public cpp v1 · immutable
#53291 ·published 2006-05-03 19:56 UTC
rendered paste body
#include <iostream>#include <iomanip>#include <vector>#include <string>#include "heap.h"using namespace std;class node{    int freq;    char symbol;    const node *left;    const node *right;public:		    node(char c = 0, int i = 0)	{        symbol = c;        freq = i;        left = 0;        right = 0;    }    node(const node* l, const node *r)	{        symbol = 0;        freq = l->freq + r->freq;        left = l;        right = r;    }		bool operator>(const node &n) const	{        return freq > n.freq;    }	    void traverse(string code = "")  const;};void node::traverse(string code) const{    if (left)	{        left -> traverse(code + "0");        right -> traverse(code + "1");    }	else	{        if (symbol == '\n')			cout << "<nl>" << "\t";		else if (symbol == ' ')			cout << "<space>" << "\t";		else			cout << symbol << "\t";        cout << setw( 9 ) << freq;        cout << "\t" << code << endl;    }}int main(){    char c;	int freq[256];		// populate frequency table from standard input	for (int i = 0 ; i < 256 ; i++)        freq[ i ] = 0;	while(cin.get(c))	{			freq[ c ]++;	}		minHeap<node> q();    for (int i = 0 ; i < 256 ; i++)        if (freq[ i ] )            {            q.push(node( i, freq[i] ));            }	    while (q.size > 1)	{		// extract first two nodes from prorioty queue		node *left = new node( q.top() );        q.pop();        node *right = new node( q.top() );        q.pop();        		// combine the nodes and the resulting subtree back on the priority queue		q.push( node( left, right ) );    }    	// output codes	cout << "Symbol\tFrequency\tCode" << endl;	cout << "------\t---------\t----" << endl;    q.top().traverse();    	return 0;}