哈夫曼树的构造、编码和解码

被问了一天哈夫曼树=_= 于是迫不得已敲了一个...

首先是读字符，统计文章中n种字符每种出现的次数，然后降序排序。 然后把出现次数作为权值，建立n个叶子结点。把所有叶子结点插入小根堆中，每次取出两个，用二者权值之和构造新的节点，作为这二者的父亲节点，最后一个点作为根，记录下来。 虽然树是自底向上建的，但实际使用的时候只用从根往下跑，所以不必记录父节点。 树建完跑dfs就能得到所有叶子结点的huffman编码(左0右1)，跑到根的时候直接哈希表记录该字符对应的编码，对文章编码时直接调用哈希表即可。 解码时把01串放到huffman树上跑，跑到根就输出对应字符，并把当前位置重置为root。

#include <queue>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <unordered_map>

using namespace std;

void read(char text[])//读取文件信息,结果保存在text中
{
    FILE *fp = fopen("test.txt", "r");
    memset(text, 0, sizeof(text));
    char ch;
    int len = 0;
    fscanf(fp, "%c", &ch);
    while (!feof(fp))
    {
        text[len++] = ch;
        fscanf(fp, "%c", &ch);
    }
    fclose(fp);
}

typedef struct
{
    char c;//字符
    int cnt;//出现次数
    string code;
} ch;

bool cmp(ch a, ch b)
{
    return a.cnt > b.cnt;//排序规则
}

ch c[300];

int count(char text[])//统计词频并输出
{
    int len = strlen(text);

    for (int i = 0; i < 300; ++i)
        c[i].c = char(i);

    for (int i = 0; i < len; ++i)
        c[text[i]].cnt++;
    sort(c, c + 300, cmp);//按出现次数降序排序

    for (int i = 0; i < 300; ++i)
    {
        if (c[i].cnt == 0)
            return i;//返回出现次数大于0的词的数量(即种数)
        printf("%c: %d\n", c[i].c, c[i].cnt);
    }
}

struct node
{
    int w, id;
    int lson, rson;

    node()
    {
        lson = rson = 0;
    }

    bool operator<(const node b) const
    {
        return w > b.w;
    }
};

int buildHuffmanTree(int n, node huffNode[])
{
    int id = 0;//下一个未使用过的huffNode数组元素的下标
    priority_queue<node> que;
    for (int i = 0; i < n; ++i)//下标为0~n-1的huffNode是叶子
    {
        huffNode[id].w = c[i].cnt;
        huffNode[id].id = i;
        que.push(huffNode[id]);
        ++id;
    }
    node a, b;
    int root;
    while (true)
    {
        a = que.top();
        que.pop();
        b = que.top();//取出权值最小的两个点
        que.pop();
        huffNode[id].lson = a.id;
        huffNode[id].rson = b.id;
        huffNode[id].w = huffNode[a.id].w + huffNode[b.id].w;
        huffNode[id].id = id;
        if (que.empty())//当前点为根
        {
            root = id;
            break;
        }
        que.push(huffNode[id]);
        ++id;
    }
    return root;
}

unordered_map<char, string> mp;//建立字符到编码的映射关系

void dfs(int now, node huffmanNode[], string code)
{
    if (!huffmanNode[now].lson && !huffmanNode[now].rson)//没孩子节点，即叶子
    {
        mp[c[huffmanNode[now].id].c] = code;
        return;
    }
    dfs(huffmanNode[now].lson, huffmanNode, code + "0");
    dfs(huffmanNode[now].rson, huffmanNode, code + "1");
}

void print()
{
    for (int i = 0; i < 300; ++i)
    {
        if (!c[i].cnt)
            break;
        printf("%c的出现次数为%d, huffman编码为: %s\n", c[i].c, c[i].cnt, mp[c[i].c].c_str());
    }
}

void decode(char code[], node huffNode[], int root, int n)
{
    int len = strlen(code);
    int now = root;
    for (int i = 0; i < len; ++i)
    {

        if (code[i] == '0')
            now = huffNode[now].lson;
        else
            now = huffNode[now].rson;
        if (huffNode[now].id < n)
        {
            printf("%c", c[huffNode[now].id].c);
            now = root;
        }
    }
}

int main()
{
    char text[10000];
    read(text);
    int n = count(text);
    node *huffNode = new node[2 * n + 1];
    int root = buildHuffmanTree(n, huffNode);
    string code = "";
    dfs(root, huffNode, code);//dfs huffman树，获取字符的编码
    print();//输出字符的编码
    int len = strlen(text);
    char *encode = new char[50000];
    memset(encode, 0, sizeof(encode));
    for (int i = 0; i < len; ++i)
        strcat(encode, mp[text[i]].c_str());
    printf("%s\n", encode);
    puts("");
    printf("%s\n", text);
    decode(encode, huffNode, root, n);
    return 0;
}