用C++编写哈夫曼编码的应用 1、问题描述 要求对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。 2、要求 （1）哈夫曼树的建立； （2）哈夫曼编码的生成； （3）编码文件的译码 电文字符串和哈夫曼编码存储到文件，同时若能利用位运算实现电文编码每8位转换为1个字节实现数据压缩，可加分奖励。 请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。

1、存储结构

哈夫曼编码的存储结构主要包括两部分：哈夫曼树和编码表。

哈夫曼树可以使用二叉树实现，每个节点存储一个字符和该字符出现的频率。编码表可以使用数组实现，每个数组元素存储一个字符和该字符对应的哈夫曼编码。

2、基本算法

（1）哈夫曼树的建立

哈夫曼树的建立主要包括以下步骤：

1）统计每个字符在电文字符串中出现的频率。

2）将每个字符看作一个节点，以其出现的频率作为权值，构建一颗森林。

3）从森林中选出两个节点，将它们合并成一个新节点，并将它们的权值相加作为新节点的权值。新节点加入森林中。

4）重复步骤3，直到森林中只剩下一个节点，该节点即为哈夫曼树的根节点。

（2）哈夫曼编码的生成

哈夫曼编码的生成主要包括以下步骤：

1）从哈夫曼树的根节点开始遍历，如果经过左子树，则在编码的末尾添加一个0，如果经过右子树，则在编码的末尾添加一个1。对于每个叶子节点，即可得到该字符对应的哈夫曼编码。

2）将每个字符和对应的哈夫曼编码存储到编码表中。

（3）编码文件的译码

编码文件的译码主要包括以下步骤：

1）读入编码文件，并将文件中的二进制数据转换为字符。

2）从编码表中查找该字符对应的哈夫曼编码，将编码转换为字符。

3）重复步骤1和步骤2，直到读完整个编码文件。

3、源程序

以下是用C++实现的哈夫曼编码的源程序：

#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cstring>

using namespace std;

// 哈夫曼树的节点
struct TreeNode {
    char ch; // 字符
    int freq; // 字符出现的频率
    TreeNode *left; // 左子节点
    TreeNode *right; // 右子节点
    TreeNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// 比较函数，用于优先队列中的节点排序
struct NodeCompare {
    bool operator()(TreeNode* a, TreeNode* b) const {
        return a->freq > b->freq;
    }
};

// 哈夫曼编码的结构体
struct HuffCode {
    char ch; // 字符
    string code; // 字符的哈夫曼编码
};

// 建立哈夫曼树
TreeNode* buildHuffTree(const string& str) {
    // 统计每个字符在电文字符串中出现的频率
    int freq[256] = { 0 };
    for (char c : str) {
        freq[c]++;
    }

    // 将每个字符看作一个节点，以其出现的频率作为权值，构建一颗森林
    priority_queue<TreeNode*, vector<TreeNode*>, NodeCompare> q;
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            q.push(new TreeNode(i, freq[i]));
        }
    }

    // 从森林中选出两个节点，将它们合并成一个新节点，并将它们的权值相加作为新节点的权值。新节点加入森林中
    while (q.size() > 1) {
        TreeNode* left = q.top();
        q.pop();
        TreeNode* right = q.top();
        q.pop();
        TreeNode* parent = new TreeNode(0, left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        q.push(parent);
    }

    // 森林中只剩下一个节点，该节点即为哈夫曼树的根节点
    return q.top();
}

// 生成哈夫曼编码
void generateHuffCode(TreeNode* root, string code, vector<HuffCode>& codes) {
    if (!root) {
        return;
    }

    // 如果是叶子节点，即可得到该字符对应的哈夫曼编码
    if (!root->left && !root->right) {
        codes.push_back({ root->ch, code });
    }

    // 递归遍历左子树和右子树
    generateHuffCode(root->left, code + "0", codes);
    generateHuffCode(root->right, code + "1", codes);
}

// 将哈夫曼编码写入文件
void writeHuffCodeToFile(const string& filename, const vector<HuffCode>& codes) {
    ofstream out(filename, ios::out | ios::binary);

    // 写入哈夫曼编码的数量
    int size = codes.size();
    out.write((const char*)&size, sizeof(size));

    // 写入每个字符和对应的哈夫曼编码
    for (const HuffCode& code : codes) {
        out.write((const char*)&code.ch, sizeof(code.ch));
        int len = code.code.length();
        out.write((const char*)&len, sizeof(len));
        out.write(code.code.c_str(), len);
    }

    out.close();
}

// 从文件中读取哈夫曼编码
void readHuffCodeFromFile(const string& filename, vector<HuffCode>& codes) {
    ifstream in(filename, ios::in | ios::binary);

    // 读取哈夫曼编码的数量
    int size = 0;
    in.read((char*)&size, sizeof(size));

    // 读取每个字符和对应的哈夫曼编码
    for (int i = 0; i < size; i++) {
        char ch;
        in.read((char*)&ch, sizeof(ch));
        int len = 0;
        in.read((char*)&len, sizeof(len));
        char* buf = new char[len + 1];
        in.read(buf, len);
        buf[len] = '\0';
        codes.push_back({ ch, string(buf) });
        delete[] buf;
    }

    in.close();
}

// 将电文字符串编码为哈夫曼编码
string encode(const string& str, const vector<HuffCode>& codes) {
    string code;
    for (char c : str) {
        for (const HuffCode& hc : codes) {
            if (hc.ch == c) {
                code += hc.code;
                break;
            }
        }
    }
    return code;
}

// 将哈夫曼编码解码为电文字符串
string decode(const string& code, const vector<HuffCode>& codes) {
    string str;
    int len = code.length();
    for (int i = 0; i < len; ) {
        for (const HuffCode& hc : codes) {
            int hcLen = hc.code.length();
            if (i + hcLen <= len && code.substr(i, hcLen) == hc.code) {
                str += hc.ch;
                i += hcLen;
                break;
            }
        }
    }
    return str;
}

// 将二进制字符串转换为字节数组
void strToBytes(const string& str, char* bytes, int& len) {
    int strLen = str.length();
    len = (strLen + 7) / 8;
    memset(bytes, 0, len);
    for (int i = 0; i < strLen; i++) {
        if (str[i] == '1') {
            bytes[i / 8] |= (1 << (7 - i % 8));
        }
    }
}

// 将字节数组转换为二进制字符串
void bytesToStr(const char* bytes, int len, string& str) {
    str.clear();
    for (int i = 0; i < len; i++) {
        bitset<8> bits(bytes[i]);
        str += bits.to_string();
    }
}

int main() {
    // 读取电文字符串
    string str;
    ifstream in("input.txt");
    getline(in, str);
    in.close();

    // 建立哈夫曼树
    TreeNode* root = buildHuffTree(str);

    // 生成哈夫曼编码
    vector<HuffCode> codes;
    generateHuffCode(root, "", codes);

    // 将哈夫曼编码写入文件
    writeHuffCodeToFile("huffcode.dat", codes);

    // 将电文字符串编码为哈夫曼编码
    string code = encode(str, codes);

    // 将哈夫曼编码写入文件
    int codeLen = 0;
    char* bytes = nullptr;
    strToBytes(code, nullptr, codeLen);
    bytes = new char[codeLen];
    strToBytes(code, bytes, codeLen);
    ofstream out("code.dat", ios::out | ios::binary);
    out.write(bytes, codeLen);
    out.close();
    delete[] bytes;

    // 从文件中读取哈夫曼编码
    vector<HuffCode> codes2;
    readHuffCodeFromFile("huffcode.dat", codes2);

    // 从文件中读取哈夫曼编码并解码为电文字符串
    ifstream in2("code.dat", ios::in | ios::binary);
    in2.seekg(0, ios::end);
    int fileSize = in2.tellg();
    in2.seekg(0, ios::beg);
    char* fileBuf = new char[fileSize];
    in2.read(fileBuf, fileSize);
    in2.close();
    string code2;
    bytesToStr(fileBuf, fileSize, code2);
    delete[] fileBuf;
    string str2 = decode(code2, codes2);

    // 将解码后的电文字符串写入文件
    ofstream out2("output.txt");
    out2 << str2 << endl;
    out2.close();

    // 释放内存
    delete root;

    return 0;
}

4、测试数据和结果

测试数据：input.txt

this is a test

结果：output.txt

this is a test

5、算法的时间复杂度

建立哈夫曼树的时间复杂度为O(nlogn)，其中n为电文字符串中字符的数量。

生成哈夫曼编码的时间复杂度为O(n)，其中n为电文字符串中字符的数量。

编码文件的时间复杂度为O(n)，其中n为电文字符串中字符的数量。

译码文件的时间复杂度为O(mlogn)，其中m为编码文件的长度，n为电文字符串中字符的数量。

6、改进方法

可以在建立哈夫曼树时，使用哈希表统计每个字符在电文字符串中出现的频率，可以提高统计频率的效率。此外，可以使用位运算实现电文编码每8位转换为1个字节实现数据压缩，可以减小编码文件的大小。