2022.11.11 PM 09:00 by CBJ
來源 : https://drive.google.com/file/d/1CMnis82zw9hGQHW1pRv3LFXACoUGA90Y/view 出題者 : 108資訊學科能力競賽複賽-彰雲嘉 標籤 : 建樹(結構struct)、優先佇列+自定義排序、DFS(深度優先搜尋) 難易度 : 6
解題想法 : 實際建出一棵霍夫曼樹,再用dfs遍歷並編碼,最後將字串轉換成編碼,並計算壓縮率( (原字串bit數-壓縮後bit數) / 原字串bit數 )
//C++ language
//solution link(含註解): https://github.com/CBJ0519/CBJsProgramDiary.com/blob/main/%E8%B3%87%E8%A8%8A%E5%AD%B8%E7%A7%91%E8%83%BD%E5%8A%9B%E7%AB%B6%E8%B3%BD/108%E5%BD%B0%E9%9B%B2%E5%98%89/PJ-%E5%88%A9%E7%94%A8%E9%9C%8D%E5%A4%AB%E6%9B%BC%E6%A8%B9%E9%80%B2%E8%A1%8C%E8%B3%87%E6%96%99%E5%A3%93%E7%B8%AE.cpp
#include<iostream>
#include<map>
#include<string>
#include<unordered_set>
#include<queue>
using namespace std;
struct tree{
int cnt=0;
char elm='\0';
tree* left=nullptr;
tree* right=nullptr;
};
struct cmp{
bool operator()(tree *a, tree *b){
return a->cnt > b->cnt;
}
};
map<char,string>huffman;
void dfs(tree *now,string code){
if(now->elm!='\0'){
huffman[now->elm]=code;
return;
}
if(now->left){
dfs(now->left,code+"0");
}
if(now->right){
dfs(now->right,code+"1");
}
}
int main(){
string s;cin>>s;
unordered_set<char>st;
map<char,tree*>mp;
for(char c:s){
st.insert(c);
}
for(char c:st){
mp[c]=new tree;
mp[c]->elm=c;
}
for(char c:s){
mp[c]->cnt++;
}
priority_queue<tree*,vector<tree*>,cmp>pq;
for(char c:st){
pq.push(mp[c]);
}
while(pq.size()>1){
tree *a=pq.top(); pq.pop();
tree *b=pq.top(); pq.pop();
tree *c=new tree;
c->cnt=a->cnt+b->cnt;
c->left=a;
c->right=b;
pq.push(c);
}
dfs(pq.top(), "");
int bits=0;
for(char c:s){
bits+=huffman[c].length();
}
int before=s.length()*8;
cout<<before<<" "<<bits<<" "<<(before-bits)*100/before<<"%\n";
return 0;
}
發佈留言