2845 - 生成哈夫曼编码

#include<queue>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
struct tree
{
	int num;
	int val;
	char ch;
	int f;//父
	int l;//左
	int r;//右
	bool operator>(const tree x)const
	{
		return val>x.val;
	}
}t[501];
struct node
{
	int n;
	char c;
	operator>(const node x)const
	{
		return n>x.n;
	}
};
void no()
{
	return;
}
bool cmp(node x,node y)
{
	if(x.n==y.n)
		return x.c<y.c;
	return x.n>y.n;
}
string num(int x)
{
	if(t[x].f==0)
	{
		return "";
	}
	else
	{
		return num(t[x].f)+(t[t[x].f].l==x?"0":"1"); 

	}
}
int main()
{
	int k,n,m;tree tr1,tr2,tr3;
	tree trN={0,0,'\0',0,0,0};
	priority_queue<tree,vector<tree>,greater<tree> > q;
	map<char,string> m1;
	string str;
	int x;
	cin>>str;
	node a[26]={};
	for(int i=0;i<str.size();i++)
	{
		a[str[i]-'a'].n++;a[str[i]-'a'].c=str[i];
		//cout<<a[str[i]-'a'].c<<endl;
	}
	sort(a,a+26,cmp);
	//cout<<a[0].c<<a[0].n<<endl;
	//cout<<a[25].c<<a[25].n<<endl;
	n=0;
	while(a[n].n>0)
	{
		q.push({n+1,a[n].n,a[n].c,0,0,0});
		n++;
	}
	tr3.ch='\0';
	while(q.size()>1)
	{
		tr3.num=++n;
		tr3.f=0;
		tr1=q.top();
		q.pop();
		tr2=q.top();
		q.pop();
		tr1>tr2?( tr1.num > tr2.num ?swap(tr1,tr2):no()):no();
		tr3.l=tr1.num;
		tr3.r=tr2.num;
		tr3.val=tr1.val+tr2.val;
		tr2.f=tr1.f=tr3.num;
		q.push(tr3);
		t[tr1.num]=tr1;
		t[tr2.num]=tr2;
		//cout<<n<<endl;
	}
	t[n]=q.top();
	for(int j=1;j<=n;j++)
	{
		m1[t[j].ch]=num(j);
	}
	for(int j=0;j<str.size();j++)
	{
		cout<<m1[t[j].ch];
	}
	cout<<endl;
	for(int i=1;i<=n;i++)
	{
		cout<<t[i].num<<" "<<t[i].val<<" "<<t[i].ch<<" "<<t[i].f<<" "<<t[i].l<<" "<<t[i].r<<endl;
	}
}

奇遇编程