题目：输入：

第一行为一个整数，表示输入数据中有n种字符

第2~n+1行为n个整数，表示每个字符出现的次数

输出：Huffman编码的平均长度（保留两位小数）

代码：

#include

#include

#include

using namespace std;

struct HuffmanNode {

    int weight; // 权重，出现的次数或者频率

    char ch; // 存储符号

    string code; // 存储该符号对应的编码

    int leftChild, rightChild, parent; // 左、右孩子，父结点

};

class HuffmanCode {

public:

    HuffmanCode(string str); // 构造函数

    ~HuffmanCode(); // 析构函数

    void getMin(int& first, int& second, int parent); // 选取两个较小的元素

    void Merge(int first, int second, int parent); // 合并

    void Encode(); // 编码:利用哈夫曼编码原理对数据进行加密

private:

    HuffmanNode* HuffmanTree; // 数组

    int leafSize; // 统计不同字符的个数

    double average;//记录编码平均长度

};

// 构造函数

HuffmanCode::HuffmanCode(string str) {

    int len = (int)str.size(); // 字符串的长度

    int arr[256], i; // 存储字符串各个字符的个数

    HuffmanTree = new HuffmanNode[256]; // 动态分配空间

    // 1.初始化HuffmanTree数组

    for (i = 0; i < (2 * len - 1); i++) { // 叶子结点为len,则树最多有2*len-1个结点

        HuffmanTree[i].leftChild = HuffmanTree[i].rightChild = HuffmanTree[i].parent = -1;

        HuffmanTree[i].code = "";

    }

    // 2.统计输入的字符串的各个字符出现的个数

    memset(arr, 0, sizeof(arr)); // 清零

    for (i = 0; i < len; i++) // 统计次数

        arr[str[i]]++; // str[i] -> 转成对应的ASCII码，如'0'->48

    leafSize = 0; // 出现不同字符的个数

    for (i = 0; i < 256; i++) {

        if (arr[i] != 0) { // 有出现的字符

            // cout