#include<bits/stdc++.h> using namespace std;
struct Node { char data; int freq; Node *lChild, *rChild;
Node(char data, int freq) : data(data), freq(freq) { lChild = rChild = NULL; } };
struct cmp { bool operator() (const Node* a, const Node* b){ return a->freq > b->freq; } };
void print(Node* root, string str) { if(root == NULL) return;
if(root->data != '#') cout<<root->data<<": "<<str<<endl;
print(root->lChild, str + '0'); print(root->rChild, str + '1'); }
void Huffman(char* data, int* freq, int n) { priority_queue<Node*, vector<Node*>, cmp> pq;
for(int i = 0; i < n; i++) pq.push(new Node(data[i], freq[i]));
while(pq.size() > 1) { Node* left = pq.top(); pq.pop(); Node* right = pq.top(); pq.pop();
Node* top = new Node('#', left->freq + right->freq);
top->lChild = left; top->rChild = right;
pq.push(top); } print(pq.top(), ""); }
int main() { cout<<"请输入字符个数"<<endl; int n; cin>>n;
char* data = new char[n+5]; int* freq = new int[n+5];
for(int i = 0; i < n; i++) { cout<<"请输入字符及对应的权重:"<<endl; cin>>data[i]>>freq[i]; }
Huffman(data, freq, n);
delete(data); delete(freq); return 0; }
|
- By:wywwzjj.top
免责声明:文章中涉及的程序(方法)可能带有攻击性,仅供安全研究与教学之用,读者将其信息做其他用途,由读者承担全部法律及连带责任,本站不承担任何法律及连带责任;如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截,联系方式见首页),望知悉。
点赞
https://cn-sec.com/archives/2624244.html
复制链接
复制链接
-
左青龙
- 微信扫一扫
-
-
右白虎
- 微信扫一扫
-
评论