描述
已知电文包括的字符集为{A，C，I，M，N，P，T，U}，输入对应权值，对字符集合进行哈夫曼编码，完成电文的哈夫曼编码与译码工作。
输入
共三行：
第一行为对应字符集{A，C，I，M，N，P，T，U}的权值
第二行为一段字符串表示的电文(长度不超过1000）；
第三行为一段电文的哈夫曼编码。
输出
共十行：
前八行为各字符的编码；
第九行是与第二行输入对应的哈夫曼编码；
第十行是与第三行输入对应的电文。
样例输入
1 2 3 4 5 6 7 8
NUPTICPCACM
1111011111100
样例输出
A: 11110
C: 11111
I: 1110
M: 100
N: 101
P: 110
T: 00
U: 01
1010111000111011111110111111111011111100
ACM
#include<iostream>
#include<queue>
#include<string>
using namespace std;
#define MAX 10
char str[8]={'A','C','I','M','N','P','T','U'};
int temp[MAX*3];
int str2[256][MAX*3];
string str3;
class node
{
public:
int k;
char c;
node *l,*r;
node()
{
c='0';
k=0;r=l=NULL;
}
node(int a,char s)
{
k=a;r=l=NULL;
c=s;
}
friend node* uni(node *p,node *q)
{
node *temp=new node(p->k+q->k,'0');
temp->l=p;
temp->r=q;
return temp;
}
};
void prim(node *p,int L)
{
if(!p->r)
{
str2[p->c][0]=L;
for(int i=1;i<=L;i++)
{
str2[p->c][i]=temp[i-1];
}
}
else
{
temp[L]=0;
prim(p->l,L+1);
temp[L]=1;
prim(p->r,L+1);
}
}
class nodeCmp
{
public:
bool operator()(node* p1, node* p2) const
{
return p1->k > p2->k;
}
};
node *s[MAX*3];
priority_queue<node *,deque<node *>,nodeCmp> pro_queue;
int main()
{
//freopen("a.txt","r",stdin);
int i,a;
for(i=0;i<8;i++)
{
cin>>a;
node *p;
p=new node(a,str[i]);
s[i]=p;
pro_queue.push(s[i]);
}
while(pro_queue.size()>1)
{
node *p,*q,*k;
p=pro_queue.top();
pro_queue.pop();
q=pro_queue.top();
pro_queue.pop();
k=uni(p,q);
pro_queue.push(k);
}
node *p=pro_queue.top();
prim(p,0);
for(i=0;i<8;i++)
{
cout<<str[i]<<": ";
for(int j=1;j<=str2[str[i]][0];j++)
{
cout<<str2[str[i]][j];
}
cout<<endl;
}
cin>>str3;
int len=str3.length();
for(i=0;i<len;i++)
{
for(int j=1;j<=str2[str3[i]][0];j++)
{
cout<<str2[str3[i]][j];
}
}
cout<<endl;
cin>>str3;
len=str3.length();
node *q=pro_queue.top();
for(i=0;i<len;i++)
{
if(str3[i]=='1')
{
q=q->r;
}
else
{
q=q->l;
}
if(q->c!='0')
{
cout<<q->c;
q=pro_queue.top();
}
}
cout<<endl;
return 0;
}