算法设计与分析王晓东哈夫曼编码c++实现代码

王晓东的《算法设计与分析》是一本经典的算法教材，而哈夫曼编码是其中的一种重要算法。哈夫曼编码是一种前缀编码方式，可以将字符集中的每个字符映射成唯一的二进制编码，并且保证编码长度最短，从而实现压缩数据的目的。

下面是哈夫曼编码的C++实现代码，代码注释中有详细的说明：

#include<iostream>
#include<queue>
#include<vector>
#include<string>
#include<fstream>
#include<sstream>
using namespace std;

//节点类
class Node{
public:
    char ch;
    int freq;
    Node* left;
    Node* right;
    Node(char c, int f){
        ch = c;
        freq = f;
        left = nullptr;
        right = nullptr;
    }
    //定义比较函数，用于优先队列中节点的排序
    bool operator<(const Node& node) const{
        return freq > node.freq;
    }
};

//哈夫曼树类
class HuffmanTree{
public:
    Node* root;
    HuffmanTree(){
        root = nullptr;
    }
    //创建哈夫曼树
    void createHuffmanTree(vector<Node*>& nodes){
        priority_queue<Node> pq;
        for(int i=0; i<nodes.size(); i++){
            pq.push(*nodes[i]);
        }
        while(pq.size() > 1){
            Node* left = new Node(pq.top().ch, pq.top().freq);
            pq.pop();
            Node* right = new Node(pq.top().ch, pq.top().freq);
            pq.pop();
            Node* parent = new Node('#', left->freq+right->freq);
            parent->left = left;
            parent->right = right;
            pq.push(*parent);
        }
        root = new Node(pq.top().ch, pq.top().freq);
    }
    //生成哈夫曼编码
    void generateHuffmanCode(Node* node, string code, vector<pair<char,string>>& codeTable){
        if(!node->left && !node->right){
            codeTable.push_back(make_pair(node->ch, code));
            return;
        }
        generateHuffmanCode(node->left, code+"0", codeTable);
        generateHuffmanCode(node->right, code+"1", codeTable);
    }
};

//读取文件内容，并统计每个字符出现的次数
void readData(string fileName, vector<Node*>& nodes){
    ifstream file(fileName);
    if(file.is_open()){
        stringstream buffer;
        buffer << file.rdbuf();
        string contents(buffer.str());
        int count[256] = {0};
        for(int i=0; i<contents.size(); i++){
            count[contents[i]]++;
        }
        for(int i=0; i<256; i++){
            if(count[i] > 0){
                char ch = (char)i;
                int freq = count[i];
                Node* node = new Node(ch, freq);
                nodes.push_back(node);
            }
        }
        file.close();
    }
}

int main(){
    string fileName = "test.txt";
    vector<Node*> nodes;
    readData(fileName, nodes);

    HuffmanTree huffmanTree;
    huffmanTree.createHuffmanTree(nodes);

    vector<pair<char,string>> codeTable;
    huffmanTree.generateHuffmanCode(huffmanTree.root, "", codeTable);

    cout << "Huffman coding table:" << endl;
    for(int i=0; i<codeTable.size(); i++){
        cout << codeTable[i].first << ": " << codeTable[i].second << endl;
    }

    return 0;
}