#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct node
{
node *left;
node *right;
int data;
int weight;
node()
{
left=0;
right=0;
}
};
class Cmp
{
public:
bool operator() (const node * a, const node * b) const
{
return a->weight>b->weight; // 从小到大 ，weight小的优先级别高
}
};
void coding(node *t,string *a,string code)
{//遍历编码
if(t)
{
if(t->data!=27)
a[t->data]=code;
coding(t->left,a,code+"0");
coding(t->right,a,code+"1");
}
}
struct huffnode
{
int count;
char c;
};
bool great(huffnode a,huffnode b)
{
return a.count>b.count;
}
int change(char c)
{
return (c-'A');
}
int main()
{
int N;
char c;
cin>>N;
while(cin)
{
huffnode count[28];
string codes[28];
vector<huffnode> sortweight;
string a;
priority_queue<node*,vector<node*>,Cmp> que;
node* p;
for(int i=0;i<28;i++)
count[i].count=0;
for(int i=0;i<N;i++)
{
cin>>c;
count[change(c)].count++;
count[change(c)].c=c;
}
for(int i=0;i<28;i++)
{
if(count[i].count!=0)
{
p=new node();
p->weight=count[i].count;
sortweight.push_back(count[i]);
p->data=i;
que.push(p);
}
}
int num=que.size();
node *x,*y,*z;
for(int i=1;i<num;i++)
{//每次从那些树中拿出两个最小的，合成一棵，再放回去
x=que.top();
que.pop();
y=que.top();
que.pop();
z=new node();
z->left=x;
z->right=y;
z->weight=x->weight+y->weight;
z->data=27;
que.push(z);
}
x=que.top();
// cout<<x->left->data<<endl;
coding(x,codes,"");
sort(sortweight.begin(),sortweight.end(),great);
for(vector<huffnode>::iterator it=sortweight.begin();it!=sortweight.end();it++)
{
char c=it->c;
cout<<c<<" "<<it->count<<" "<<codes[change(c)]<<endl;
}
cin>>N;
}
return 0;
}

技术贴

http://read.pudn.com/downloads166/sourcecode/others/763432/hafuman.cpp__.htm