利用哈弗曼树编码原理，对字符进行编码（C++,C语言都可）

Question

题目：输入任意字符串，str]=("a”，“b”，“c”，"d”，"e”，"f”，”g”，“h”；每种字符出现频率fnum，=0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.13，根据出现频率，利用哈夫曼编码原理，对每个字符进行(0.1)编码，并输出每种字符编码。

Answer 1

运行结果及代码如下：

#include <iostream>
#include <algorithm>

#include <iomanip>
using namespace std;
#define MAXLEN 30
#define MAXLEAF 130
#define MAXWEIGHT 1

//结点
struct HuffmanNode
{
    char node;      //结点字符
    double weight;  //结点权值
    int parent;     //父结点
    int lchild;     //左子节点
    int rchild;     //右子节点
    int no;         //节点编号
};
//每个结点的编码
struct HuffmanCode
{
    int bit[MAXLEN];  //存储哈夫曼编码
    int length;        //每个结点编码的长度
};
bool cmp1(HuffmanNode a, HuffmanNode b)
{
    return a.weight < b.weight;
}
bool cmp2(HuffmanNode a, HuffmanNode b)
{
    return a.no < b.no;
}

HuffmanNode HNode[2 * MAXLEAF - 1];
HuffmanCode HCode[MAXLEAF];




//构造哈夫曼树
void CreateHafman(char buf[], double w[], int n)
{
    //初始化结点
    for (int i = 0; i < 2 * n - 1; i++)
    {
        HNode[i].weight = MAXWEIGHT;
        HNode[i].parent = -1;
        HNode[i].lchild = -1;
        HNode[i].rchild = -1;
        HNode[i].no = 2 * n;
    }

    for (int i = 0; i < n; i++)
    {
        HNode[i].node = buf[i];
        HNode[i].weight = w[i];
        HNode[i].no = i;
    }


    for (int i = 0; i < n - 1; i++)
    {
        int min1 = 0, min2 = 1;
        sort(HNode, HNode + n + i, cmp1);
        for (int j = 0; j < n + i; j++)
        {
            if (HNode[min1].parent != -1)
            {
                min1++;
                min2 = min1 + 1;
                continue;
            }
            if (HNode[min2].parent != -1)
                min2++;
        }
        HNode[n + i].lchild = HNode[min1].no;
        HNode[n + i].rchild = HNode[min2].no;
        HNode[n + i].weight = HNode[min1].weight + HNode[min2].weight;
        HNode[n + i].no = n + i;
        HNode[min1].parent = HNode[n + i].no;
        HNode[min2].parent = HNode[n + i].no;

    }
    //cout << "哈夫曼树构建成功！" << endl;
}

//获取每个字符的哈夫曼编码
void Getcode(int n)
{
    int offset = 2 * n - 1, p, j;
    HuffmanCode hc;

    sort(HNode, HNode + offset, cmp2);
    for (int i = 0; i < n; i++)
    {
        hc.length = 0;
        j = i;
        p = HNode[j].parent;
        while (p != -1)
        {
            if (HNode[p].lchild == HNode[j].no)
                hc.bit[hc.length] = 0;
            else
                hc.bit[hc.length] = 1;
            hc.length++;
            j = HNode[p].no;
            p = HNode[j].parent;
        }
        for (int k = 0; k < hc.length; k++)
            HCode[i].bit[k] = hc.bit[hc.length - k - 1];
        HCode[i].length = hc.length;
    }
}
//显示哈夫曼编码
void showHafman(int n)
{
    //输出哈夫曼编码
    for (int i = 0; i < n; i++)
    {
        if (HNode[i].node == '\n')
            cout << "\\n" << ": Huffman code is: ";
        else if (HNode[i].node == '\r')
            cout << "\\r" << ": Huffman code is: ";
        else if (HNode[i].node == '\t')
            cout << "\\t" << ": Huffman code is: ";
        else
            cout << HNode[i].node << ": Huffman code is: ";
        for (int j = 0; j < HCode[i].length; j++)
            cout << HCode[i].bit[j];
        cout << endl;
    }
}



int main()
{
    int n = 8;
    char buf[MAXLEAF]={'a','b','c','d','e','f','g','h'};
    double w[MAXLEAF]={0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.13};

    
    CreateHafman(buf, w, n); //创建哈夫曼树
    Getcode(n);//获取每个字符的编码
    showHafman(n);
    return 0;
}