哈夫曼编码 译码
作者:
TyjCj
,
2022-11-29 22:07:30
,
所有人可见
,
阅读 207
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
unordered_map<char, string> mp; // 储存某字符的哈夫曼编码,编码使用string表示
int n = 8;
string str;
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;
void Create()
{
str = "ACIMNPTU";
string c;
TreeNode *tmp;
for(int i = 0; i < n; i ++ )
{
int a;
cin >> a;
c = str[i];
tmp = new TreeNode(c);
heap.push({a, tmp});
}
while(heap.size() > 1)
{
auto a = heap.top(); heap.pop();
auto b = heap.top(); heap.pop();
// 合并最小的两个节点
// 左小右大
string res = a.y -> val + b.y -> val; // 存合并节点的val
// 如果权值相等 看哪个合并的val的size小就是哪个在左边
if(a.x == b.x)
{
if(a.y -> val.size() < b.y -> val.size()) tmp = new TreeNode(res, a.y, b.y);
else tmp = new TreeNode(res, b.y, a.y);
}
else tmp = new TreeNode(res, a.y, b.y);
heap.push({a.x + b.x, tmp});
for(auto t : tmp -> left -> val) mp[t] += '0';
for(auto t : tmp -> right -> val) mp[t] += '1';
}
}
void Getcode()
{
for(auto t : str)
{
reverse(mp[t].begin(), mp[t].end());
cout << t << ": " << mp[t] << endl;
}
}
// 字符转编码
void Encode()
{
string code = "";
string s;
cin >> s;
for(auto t : s) cout << mp[t];
cout << endl;
}
//编码转字符
void Decode()
{
string s;
cin >> s;
auto a = heap.top().y;
TreeNode *p = a;
for(int i = 0; i < s.size(); i ++ )
{
if(s[i] == '0') p = p -> left;
else p = p -> right;
if(! p -> left && !p -> right)
{
cout << p -> val;
p = a;
}
}
cout << endl;
}
int main()
{
Create();
Getcode();
Encode();
Decode();
return 0;
}