Huffman編碼是一種壓縮編碼柳爽，我們可以借助Huffman樹來完成這個(gè)任務(wù)渠抹。
算法的內(nèi)容可以參考網(wǎng)上的介紹息罗，這里只是使用C++的方式實(shí)現(xiàn)這個(gè)算法芋齿，并且給出了一個(gè)簡單的例子進(jìn)行測(cè)試啸如。

本文涉及到了STL庫的最新知識(shí)侍匙，比如auto關(guān)鍵字，智能指針等等叮雳，總之想暗，最新的STL11庫讓我更愛C++這么語言（C語言雖然簡單，但是C語言還是停留在最初的設(shè)計(jì)的方法上帘不，并沒有提供其他的更方便的方式说莫，比如相關(guān)的容器，不過還好我們有了C++寞焙，不過C++太大了储狭，不太容易學(xué)）

代碼如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <memory>
using namespace std;

struct s_symbol_info
{
    char ch;
    int  w;

    s_symbol_info(char c, int n) :  ch(c), w(n) {}
};

struct huffman_node
{
    typedef shared_ptr<huffman_node> sptr_huffman_node_in;

    // pos
    sptr_huffman_node_in lchild;
    sptr_huffman_node_in rchild;

    // value
    char ch;

    huffman_node() : ch('\0')    { InitPos(); }
    huffman_node(char c) : ch(c) { InitPos(); }
    ~huffman_node() {}

    void InitPos() {
        lchild.reset();
        rchild.reset();
    }
};
typedef shared_ptr<huffman_node> sptr_huffman_node;
typedef shared_ptr<huffman_node> huffman_tree;

struct heap_node
{
    // weight
    int weight;

    // value
    sptr_huffman_node pNode;

    heap_node(int w, sptr_huffman_node p) : weight(w), pNode(p){}
};
typedef shared_ptr<heap_node> sptr_heap_node;
struct s_comp_sptr_heap_node
{
    bool operator() (sptr_heap_node e1, sptr_heap_node e2) {
        return e1->weight > e2->weight;
    }
}CompSPtrHeapNode;

huffman_tree create_huffman_tree(const vector<s_symbol_info> & vecSymbolInfo)
{
    huffman_tree tree;

    vector<sptr_heap_node> vecHeapNode;
    for (auto itr=vecSymbolInfo.begin(); itr!=vecSymbolInfo.end(); ++itr) {
        vecHeapNode.push_back(make_shared<heap_node>(itr->w, make_shared<huffman_node>(itr->ch)));
    }
    make_heap(vecHeapNode.begin(), vecHeapNode.end(), CompSPtrHeapNode);

    while (vecHeapNode.size() > 1) {
        pop_heap(vecHeapNode.begin(), vecHeapNode.end(), CompSPtrHeapNode);
        auto & eTmp1 = vecHeapNode.back();
        auto e1 = eTmp1;
        vecHeapNode.pop_back();

        pop_heap(vecHeapNode.begin(), vecHeapNode.end(), CompSPtrHeapNode);
        auto & eTmp2 = vecHeapNode.back();
        auto e2 = eTmp2;
        vecHeapNode.pop_back();

        auto e = make_shared<heap_node>(e1->weight+e2->weight, make_shared<huffman_node>());

        vecHeapNode.push_back(e);
        push_heap(vecHeapNode.begin(), vecHeapNode.end(), CompSPtrHeapNode);

        e->pNode->lchild  = e1->pNode;
        e->pNode->rchild  = e2->pNode;
    }

    if (!vecHeapNode.empty()) {
        tree = vecHeapNode[0]->pNode;
    }

    return tree;
}

void build_huffman_code(sptr_huffman_node pNode, string & strHuffCode, map<char, string> & mapHuffCode)
{
    sptr_huffman_node lchild = pNode->lchild;
    sptr_huffman_node rchild = pNode->rchild;

    if (lchild == nullptr && rchild == nullptr) {
        mapHuffCode[pNode->ch] = strHuffCode;
        return ;
    }

    strHuffCode += "0";
    build_huffman_code(lchild, strHuffCode, mapHuffCode);
    strHuffCode.pop_back();

    strHuffCode += "1";
    build_huffman_code(rchild, strHuffCode, mapHuffCode);
    strHuffCode.pop_back();

}

map<char, string> build_huffman_code(huffman_tree root)
{
    map<char, string> mapHuffCode;

    string strHuffCode;

    build_huffman_code(root, strHuffCode, mapHuffCode);

    return mapHuffCode;
}

string huffman_code(string str, const map<char, string> & mapHuffCode)
{
    string rt;

    for(int i=0; i<str.size(); ++i) {
        rt += mapHuffCode.at(str[i]);
    }

    return rt;
}

string huffman_decode(string str, huffman_tree root)
{
    string rt;
    auto pNode = root;
    for (int i=0; i<str.size(); ++i) {
        if (str[i] == '0') {
            pNode = pNode->lchild;
        } else {
            pNode = pNode->rchild;
        }

        if (pNode->ch != '\0') {
            rt.push_back(pNode->ch);
            pNode = root;
        }
    }
    return rt;
}

int main()
{
    vector<s_symbol_info> vecSymbolInfo = {
            s_symbol_info( 'a' , 45 ),
            s_symbol_info( 'b' , 13 ),
            s_symbol_info( 'c' , 12 ),
            s_symbol_info( 'd' , 16 ),
            s_symbol_info( 'e' , 9  ),
            s_symbol_info( 'f' , 5  ),
    };

    cout << "Input:";
    for (auto itr=vecSymbolInfo.begin(); itr!=vecSymbolInfo.end(); ++itr) {
        cout << itr->ch << ":" << itr->w << " ";
    }
    cout << endl;

    auto huffTree = create_huffman_tree(vecSymbolInfo);

    auto mapHuffCode = build_huffman_code(huffTree);

    cout << "Output Huffman Code:" << endl;
    for (auto itr=mapHuffCode.begin(); itr!=mapHuffCode.end(); ++itr) {
        cout << "\t" << itr->first << ":" << itr->second << endl;
    }

    string strTest = "abaadcef";
    cout << "Input Test String:" << strTest << endl;

    string strHuffCode = huffman_code(strTest, mapHuffCode);
    cout << "OutHuffmanCode:";
    cout << strHuffCode << endl;
    cout << "OutHuffmanDecode:" << huffman_decode(strHuffCode, huffTree) << endl;
    return 0;
}

輸出如下：

Input:a:45 b:13 c:12 d:16 e:9 f:5 
Output Huffman Code:
    a:0
    b:101
    c:100
    d:111
    e:1101
    f:1100
Input Test String:abaadcef
OutHuffmanCode:01010011110011011100
OutHuffmanDecode:abaadcef