1.实现字符串的哈夫曼编码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
using namespace std;
int n;
int name[500];
vector<char> alls;
bool cmp1(char a,char b) {
return name[a]<name[b];
}
struct HTNode{
int na;//包含的字符
int weight;//权值
int p;//是否有效
int sons;//子树大小
bool operator < (const HTNode& a) const{//降序 小根堆
if (weight!=a.weight) return weight>a.weight;
//return p
}
}HT[2020];
const int N = 1e5+10;
HTNode e[N];
int ne[N],h[N],idx;
int cnt;
map <int,string> mp;
bool st[N];
void add(HTNode a,HTNode b){//所有索引均为idx 节点存在了e中
e[idx]=b;
ne[idx]=h[a.na],h[a.na]=idx++;
}
void dfs(int u,string now){//建好树后 遍历,赋予编码
printf ("%c ",e[u].na);
int res=0;
for (int i=h[e[u].na];~i;i=ne[i]){
HTNode j=e[i];
char tt=('0'+res);//左0 右1
dfs(i,now+tt);
res++;
}
if (!res) {//叶子节点就是要编码的点
mp[e[u].na]=now;
}
return ;
}
int main () {
string s;
getline(cin,s);
n=s.size();
memset(h, -1, sizeof h);//初始化
cout<<s<<'\n';
for (int i=0;i<n;i++) {//统计个数
name[s[i]]++;
if (name[s[i]]==1) alls.push_back(s[i]);
}
sort(alls.begin(),alls.end(),cmp1);
for (auto x:alls) {
printf ("%c %d\n",x,name[x]);
}//到此 统计出权值
priority_queue<HTNode> q;
for (auto x:alls) {
q.push({(int)x,name[x],1,1});
}
while (q.size()>1) {//取出权值最小的两个点 造一个父节点指向他们
cnt++;
HTNode a=q.top();
q.pop();
HTNode b=q.top();
q.pop();
HTNode x={500+cnt,a.weight+b.weight,0,a.sons+b.sons+1};
q.push(x);
add(x,a),add(x,b);
//add(x,a)
}
cnt++;
HTNode x={500+cnt,-1,0,0};
add(x,q.top());//最后一个父节点也需要被指一下hh
puts("");
printf ("idx=%d cnt=%d\n",idx,cnt);
dfs(idx-1,"");
puts("");
// for (int i=0;i<idx;i++) {
// printf ("%c ha=%d\n",e[i].na,h[e[i].na]);
// for (int j=h[e[i].na];~j;j=ne[j]){
// printf("%c ",e[j].na);
// }
// if (~h[e[i].na]) puts("");
// }
for (int x:alls) {
printf ("%c ",x);
cout<<mp[x]<<'\n';
}
puts("-----");
for (int i=0;i<n;i++) {
cout<<mp[s[i]];
}
return 0;
}