优雅实现哈夫曼编码 admin 102737文章 87评论 2024年4月3日10:25:14评论4 views字数 1031阅读3分26秒阅读模式 #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; // 左0右1 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 点赞 http://cn-sec.com/archives/2624244.html 复制链接 复制链接 左青龙 微信扫一扫 右白虎 微信扫一扫
评论