hafman.txt

一个哈夫曼树的构建的算法

#include <string> 
#include <vector> 
#include <map> 
using namespace std; 

template<class TData, class TWeight = double> 
class THuffmanTree 
{ 
protected: // tpye define 
class THuffmanNode 
{ 
public: 
bool isdata; 
TData data; 
TWeight weight; 
THuffmanNode *Left, *Right; 

THuffmanNode( TData d, TWeight w ) 
{ isdata = true; data = d; weight = w; 
Left = Right = 0; 
} 

THuffmanNode( THuffmanNode* node1, THuffmanNode* node2 ) 
{ isdata = false; 
weight = node1->weight + node2->weight; 
Left = node1; Right = node2; 
} 

THuffmanNode( THuffmanNode& node1, THuffmanNode& node2 ) 
{ isdata = false; 
weight = node1.weight + node2.weight; 
Left = &node1; Right = &node2; 
} 

bool operator < ( THuffmanNode& rop ) const 
{ return weight < rop.weight; } 

bool operator == ( THuffmanNode& rop ) const 
{ return weight == rop.weight; } 

bool operator != ( THuffmanNode& rop ) const 
{ return ! ( *this == rop ); } 

bool operator > ( THuffmanNode& rop ) const 
{ return rop < *this; } 

bool operator <= ( THuffmanNode& rop ) const 
{ return ! ( *this > rop ); } 

bool operator >= ( THuffmanNode& rop ) const 
{ return ! ( *this < rop ); } 

TWeight 
Weight( const TData& d, int n ) 
{ 
if( data == d && isdata ) 
return n*weight; 
else 
{ 
TWeight w = 0; 
n++; 
if( Left != 0 ) 
w = Left->Weight( d, n ); 
if( w == 0 && Right != 0 ) 
w = Right->Weight( d, n ); 
return w; 
} 
} 

THuffmanNode* 
Child( char c ) 
{ 
if( c == '0' ) 
return Left; 
else 
return Right; 
} 

}; // THuffmanNode 

protected: // variable define 
THuffmanNode* root; 
map<TData, string> code; 
map<TData, TWeight> weight; 
int _size; 

void add_code( THuffmanNode* node, int l_r ) 
{ if( node->isdata ) 
code[node->data].insert( code[node->data].begin(), 1, char(48+l_r) ); 
else 
{ add_code( node->Left, l_r ); add_code( node->Right, l_r ); } 
} 

void Clear( THuffmanNode* node ) 
{ if( node->Left != 0 ) Clear( node->Left ); 
if( node->Right != 0 ) Clear( node->Right ); 
delete( node ); 
} 

template<class StringPtr> 
bool 
GetVal( StringPtr& ptr, const StringPtr& end, TData& d ) 
{ 
if( ptr == end ) 
return false; 
THuffmanNode* p = root; 
while( ( ptr != end ) && ( p->Child( *ptr ) != 0 ) ) 
p = p->Child( *( ptr++ ) ); 
if( p->isdata ) 
{ 
if( p == root ) 
ptr++; 
d = p->data; 
return true; 
} 
else 
return false; 
} 

public: // functions 
THuffmanTree( TData d[], TWeight w[], int n ) 
{ Create( d, w, n ); } 

THuffmanTree( const vector<TData>& d, const vector<TWeight>& w ) 
{ Create( d, w, d.size() ); } 

~THuffmanTree() { Clear(); } 

template<class TDataArray, class TWeightArray> 
TWeight 
Create( const TDataArray& d, const TWeightArray& w, int n ); 

template<class TDataArray> 
bool 
Trans( const TDataArray& d, int n, string& bi_code ) 
{ 
bi_code.erase( bi_code.begin(), bi_code.end() ); 
if( n <= 0 ) 
return false; 
for( int i = 0; i < n; i++ ) 
bi_code += code[d[i]]; 
return true; 
} 

int 
Length( const string& r ); 

template<class TDataArray> 
int 
Trans( const string& r, TDataArray& d ); 

const string& 
GetCode( TData d ) 
{ return code[d]; } 

TWeight 
Weight() 
{ 
typename map<TData, string>::iterator p_code; 
TWeight w = 0; 
for( p_code = code.begin(); p_code != code.end(); p_code++ ) 
w += root->Weight( p_code->first, 0 ); 
return w; 
} 

int Clear() 
{ Clear( root ); root = 0; 
_size = 0; code.clear(); 
} 
}; 

template<class TData, class TWeight> 
template<class TDataArray, class TWeightArray> 
TWeight 
THuffmanTree<TData, TWeight>::Create( const TDataArray& d, 
const TWeightArray& w, 
int n ) 
{ 
if( n <= 0 ) 
{ 
_size = 0; 
return 0; 
} 
multimap<TWeight, THuffmanNode*> sort; 
vector<THuffmanNode*> node; 
typedef typename multimap<TWeight, THuffmanNode*>::value_type pair_type; 
typedef typename multimap<TWeight, THuffmanNode*>::iterator pointer; 
typedef typename map<TData, string>::value_type pair_type_code; 
int i; 
for( i = 0; i < n; i++ ) 
{ 
node.push_back( new THuffmanNode( d[i], w[i] ) ); 
code.insert( pair_type_code( d[i], "" ) ); 
sort.insert( pair_type( w[i], node[i] ) ); 
weight.insert( map<TData, TWeight>::value_type( d[i], w[i] ) ); 
} 
pointer p1, p2; 
THuffmanNode *n0, *n1, *n2; 
while( sort.size() >= 2 ) 
{ 
p1 = sort.begin(); 
n1 = p1->second; 
sort.erase( p1 ); 
p2 = sort.begin(); 
n2 = p2->second; 
sort.erase( p2 ); 
n0 = new THuffmanNode( n1, n2 ); 
sort.insert( pair_type( n0->weight, n0 ) ); 
add_code( n1, 0 ); 
add_code( n2, 1 ); 
} 
root = sort.begin()->second; 
if( root->isdata ) 
add_code( root, 0 ); 
_size = n; 
return Weight(); 
} 

template<class TData, class TWeight> 
int 
THuffmanTree<TData, TWeight> 
::Length( const string& r ) 
{ 
int l = 0; 
TData d; 
string::const_iterator ch_p = r.begin(); 
while( GetVal( ch_p, r.end(), d ) ) 
l++; 
if( ch_p != r.end() ) 
return 0; 
else 
return l; 
} 

template<class TData, class TWeight> 
template<class TDataArray> 
int 
THuffmanTree<TData, TWeight> 
::Trans( const string& r, TDataArray& d ) 
{ 
int l = 0; 
string::const_iterator ch_p = r.begin(); 
while( GetVal( ch_p, r.end(), d[l] ) ) 
l++; 
if( ch_p != r.end() ) 
return 0; 
else 
return l; 
} 

#include <iostream> 
#include <cstdlib> 
using namespace std; 
int main() 
{ 
int s, i; 
int t_w; 
char t_d; 
vector<char> a; 
vector<int> b; 

cout << "Please input the number of the datas:"; 
cin >> s; 
if( s <= 0 ) 
return 1; 
for( i = 0; i < s; i++ ) 
{ 
cout << "Please input a pair of data and its weight:"; 
cin >> t_d; 
a.push_back(t_d); 
cin >> t_w; 
b.push_back(t_w); 
} 

THuffmanTree<char, int> tree( a, b ); 
for( int i = 0; i < a.size(); i++ ) 
cout << "( " << a[i] << ", " << b[i] << " ) " 
<< "is " << tree.GetCode(a[i]) << endl; 
cout << "The weight of the tree is " << endl 
<< tree.Weight() << endl; 

cout << "Please input a string to translate it:"; 
string str; 
cin >> str; 
string str_out; 
tree.Trans( str, str.length(), str_out ); 
cout << "The result is:" << endl 
<< str_out << endl; 
cout << "The length is:" << endl 
<< tree.Length( str_out ) << endl 
<< "and" << endl 
<< str_out.length() << endl; 
string str2; 
str2.resize( tree.Length( str_out ) ); 
if( str2.length() != 0 ) 
{ 
tree.Trans( str_out, str2 ); 
if( str2 != str ) 
{ 
cout << "What??? It's wrong!!!" << endl; 
cout << str2 << endl; 
} 
else 
cout << "The result is:" << endl << str2 << endl; 
} 
system( "Pause" ); 
}