wywwzjj's Blog

优雅实现哈夫曼编码

字数统计: 321阅读时长: 1 min
2018/12/22 Share
#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;
}
CATALOG