哈夫曼编码的设计与实现

基本思路

将每个符号看作一棵二叉树,将这些树依权重合并,形成新的树,最后形成一棵树。每棵树的信息存于其根节点,包含符号信息、权值、父结点指针,编码,高度等,用于比较合并。

数据结构

Tree:
- weight : float
- symbol : char
- parent : Tree*
- code : int
- height : int

基本操作
Tree* merge(Tree* t1, Tree* t2)    两树合并,同时指定编码
Traverse(Tree* t, vector<int> * res) 从叶子向根遍历
Tree* createTree(char sysmbol, float weight);    用符号和权重生城一棵单节点树

比较规则:
1. 比较权重(权重小者优先)
2. 权重相同时比较高度(高度小者优先)
bool TreeCompare(Tree* t1, Tree* t2);

构建哈夫曼树
void genHuffTree(vector<char> syms, vector<float> weight)

构建哈夫曼树操作

  1. 读入符号和权重向量;

  2. 对每一个符号生成一个单节点树,高度为1,把节点指针存入 symtrees 容器;

  3. 拷贝 symtreescurtrees(生成树过程中需动态改变),当 curtrees 长度大于1时,循环 [4 - 6]:

  4. 按升序排列,选取最小的两个合并

  5. 删除 curtrees 中最小两棵树

  6. 将合并结果放入 curtrees 中;

  7. 哈夫曼树构建完毕

树的所有叶子节点地址都记录在 symtrees 中,从 symtrees 中的每个叶子节点开始遍历到树根,获取编码序列,翻转即得符号对应的哈夫曼编码。

源代码

huffman.h

#pragma once
#include <vector>

typedef struct Tree Tree;
typedef struct Tree* TreePtr;

struct Tree {
    float weight;
    char symbol;
    int code;
    int height;
    Tree* parent;
};

TreePtr merge(TreePtr t1, TreePtr t2);

std::vector<int> Traverse(TreePtr t);

TreePtr createTree(char sysmbol, float weight);

bool TreeCompare(TreePtr t1, TreePtr t2);

void genHuffCode(std::vector<char> syms, std::vector<float> weight);

huffman.cpp

#include "huffman.h"
#include 
#include 
#include 
#include 
using namespace std;

TreePtr merge(TreePtr t1, TreePtr t2)
{
    TreePtr newTree = (TreePtr)malloc(sizeof(Tree));
    if (newTree == NULL) return NULL;
    t1->parent = newTree;
    t2->parent = newTree;
    t1->code = 1;
    t2->code = 0;
    newTree->code = 999;
    newTree->height = t1->height + 1;
    newTree->weight = t1->weight + t2->weight;
    newTree->parent = NULL;
    return newTree;
}

vector Traverse(TreePtr t)
{
    TreePtr p = t;
    vector res;
    while (p != NULL) {
        if (p->code == 999) break;
        res.push_back(p->code);
        p = p->parent;
    }
    return res;
}

TreePtr createTree(char symbol, float weight)
{
    TreePtr newTree = (TreePtr)malloc(sizeof(Tree));
    if (newTree == NULL) return NULL;
    newTree->weight = weight;
    newTree->height = 1;
    newTree->symbol = symbol;
    newTree->code = 1;
    newTree->parent = NULL;
    return newTree;
}

bool TreeCompare(TreePtr t1, TreePtr t2)
{
    if (t1->weight < t2->weight) {
        return true;
    }
    else if (t1->weight == t2->weight) {
        if (t1->height < t2->height) {
            return true;
        }
    }
    return false;
}

void genHuffCode(vector syms, vector weight) {
    /*char syms[] = { 'a', 'b', 'c', 'd', 'e' };
    float weight[] = { 2,1,2,1,3 };
    vector symtrees;
    int i;*/

    //for (int i = 0; i < weight.size(); i++) {
    //    cout << weight[i]<<' '; } cout << endl; assert(syms.size()="=" weight.size()); vector symtrees;
    for (int i = 0; i < syms.size(); i++) {
        TreePtr t = createTree(syms[i], weight[i]);
        if (t != NULL)
            symtrees.push_back(t);
        else
            cout << "ERROR!\n";
    }

    vector alltrees;
    alltrees.assign(symtrees.begin(), symtrees.end());



    while (alltrees.size() > 1) {
        sort(alltrees.begin(), alltrees.end(), TreeCompare);    // 从小到大排序
        TreePtr t = merge(alltrees[0], alltrees[1]);            // 合并最小两棵树
        alltrees.erase(alltrees.begin(), alltrees.begin() + 2);    // 删除最小两棵树
        alltrees.push_back(t);                                    // 加入合并后的树
    }

    for (int i = 0; i < symtrees.size(); i++) {
        vector codes = Traverse(symtrees[i]);
        reverse(codes.begin(), codes.end());
        cout << symtrees[i]->symbol << "的编码为:";
        for (int j = 0; j < codes.size(); j++)
            cout << codes[j];
        cout << "\n------------------\n" << endl;
    }
}

main.cpp

![huffman](C:\Users\ouyang\Desktop\queny.coding.me\source\asserts\postimgs\huffman.png)
#include "huffman.h"
#include 
#include 
#include 
using namespace std;

int main() {
    /*vector syms = {'a','b','c'};
    vector weight = {0.2, 0.3, 0.5};*/
    vector syms;
    vector weight;
    string line;
    fstream fs = fstream("in.txt");
    cout << "请输入符号序列(用空格隔开)" << endl;
    getline(cin, line);
    istringstream iss1(line);
    for (char c; iss1 >> c; syms.push_back(c));

    cout << "请输入符号的权重(用空格隔开)" << endl;
    getline(cin, line);
    istringstream iss2(line);
    for (float f; iss2 >> f; weight.push_back(f)) {}

    genHuffCode(syms, weight);
    return 0;
}


附:运行结果

huffman