优雅实现哈夫曼编码

算法

字数统计: 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;
}

原文作者：wywwzjj

原文链接：https://wywwzjj.top/2018/12/22/优雅实现哈夫曼编码/

发表日期：December 22nd 2018, 1:05:00 pm

更新日期：May 15th 2021, 11:53:20 am

Next Post

Code Breaking Writeup
Previous Post

Please don't stop rua 233333

CATALOG

