如果有更好更短的代码能在评论取留言吗,这是我能想到的最简单的版本了
😭😭😭😭
判题OJ:NOJ
#include <iostream>
#include <unordered_map>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
// map_储存某字符的哈夫曼编码,编码使用string表示
unordered_map<char,string> map_;
struct TreeNode
{
string val;// 存该节点囊括的字符
TreeNode *left,*right;
TreeNode *parent;
// 用于创建叶节点
TreeNode(string v):val(v),left(nullptr),right(nullptr){}
// 用于创建两个叶子节点的合并节点
TreeNode(string v,TreeNode *l,TreeNode *r):val(v),left(l),right(r),parent(nullptr){}
};
// 用于创建权值&节点的复合数据类型
typedef pair<int,TreeNode*> IT;
// 储存权值的小根堆
priority_queue<IT,vector<IT>,greater<IT>> heap;
int main()
{
int n,x;n = 8;// OJ里的字符有8个
// 储存字符集
TreeNode *tmp;// 用于创建叶子节点和合并节点
string str = "ACIMNPTU",t;
// 只要heap还可以合并两个节点
for(int i = 0;i < n;i ++)
{
cin >> x;
t = str[i];
tmp = new TreeNode(t);
heap.push({x,tmp});
}
while(heap.size()>1)
{
auto x = heap.top();heap.pop();
auto y = heap.top();heap.pop();
// 合并最小的两个节点
// 左小右大
string res = x.second->val + y.second->val;// 存合并节点的val
if(x.first<y.first) tmp = new TreeNode(res,x.second,y.second);
else if(x.first == y.first)
{
if(x.second->val.size()<y.second->val.size()) tmp=new TreeNode(res,x.second,y.second);
else tmp = new TreeNode(res,y.second,x.second);
}
else tmp = new TreeNode(res,y.second,x.second);
heap.push({x.first+y.first,tmp});
// 储存路径左0右1
for(auto x:tmp->left->val) map_[x] += '0';
for(auto x:tmp->right->val) map_[x] += '1';
}
for(auto x:str)
{
reverse(map_[x].begin(),map_[x].end());
cout << x << ": " << map_[x] << endl;
}
// 字符转密码
string txt;cin >> txt;
for(auto x:txt) cout << map_[x];
puts("");
// 解密利用哈夫曼树
auto root = heap.top().second;
TreeNode *p = root;
cin >> txt;
for(int i = 0;i < txt.size();i ++)
{
if(txt[i] == '0') p = p->left;
else p = p->right;
if(!p->left && !p->right)
{
cout << p -> val;
p = root;
}
}
return 0;
}
好吧,还是很长。。。。。