哈夫曼编码系统 C++实现

最近的数据结构大作业…
其中涉及到了很多，像一些哈夫曼树的编码、译码，以及树的二叉树形式的存储及恢复。。
[基本要求]
一个完整的系统应具有以下功能：
（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
（2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
（3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
（4）P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。
（5）T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

注释很详细了，也花了不少时间。这些我当时也是参考了许多他人的资料，希望我这篇博客能够在总结前人的基础上，让大家更好、更综合地理解这一个实现过程。
我自认为我的编码风格还是比较容易懂的，函数名字也都是有意义的，如果看下来的话其实不会太吃力，同时很多地方的参考我也在前面列举了，如果有疑问或者是有问题，欢迎在评论区留言。

参考:

1. 哈夫曼编码C++实现
2. 二叉树的文件存储和读取
3. c++按行读取文件的方式
4. c++ofstream与c风格fwrite的一个小区别
5. c++字符串按空格分割
   这里是用了头文件<sstream>处理的，相对简单一些，但是限于以空格分割， 更复杂的请搜索split函数。
6. 上面的空格分割字符串存在只能处理一行的问题，我在其进行了改进
7. c++ string类型与基本数值类型 的互相转换
8. c++ 头文件中stringstream流的用法的一些补充
9. access函数：检测文件是否存在/是否具有读/写权限
10. string 与const char*、char*、char[]之间相互转换
11. 一次读入整个txt文件到一个string中
12. 在fstream流中新手可能把模式ios::a|ios::b中的"|“写成”||"，会导致文件无法打开

注：此代码是在VS2019下运行，因有一些函数可能与标准库不一样，如下面的_access函数，如果你在你编译器上报错，请把这些带有"_"的函数的前缀“_”去掉即可。

// 赫夫曼编码系统.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include<iostream>
#include<fstream>
#include<string>
#include<sstream>
#include <vector>
#include <map>
#include <algorithm>
#include<io.h> //调用access函数确认文件是否存在
#include<windows.h>
using namespace std;

const string hfmTree = "hfmTree.txt";
const string tobeEncoding = "ToBeTran.txt";
const string EncodingResult = "CodeFile.txt";
const string DecodingResult = "TextFile.txt";
const string CodePrin = "CodePrin.txt";
const string TreePrin = "TreePrin.txt";

typedef double weighttype;
//string对象转换为数值类型
template <class Type>
Type stringToNum(const string& str) {
    istringstream iss(str);
    Type num;
    iss >> num;
    return num;
}
struct HFMNode
{
    char key;
    weighttype weight;
    HFMNode* left, * right;
    HFMNode(char k, weighttype w) :key(k), weight(w), left(nullptr), right(nullptr) {};
    HFMNode(weighttype w) :key('/0'), weight(w), left(nullptr), right(nullptr) {};
    //第二个构造函数用于存储合并两个树的父节点，这时其key应该是被禁用，这里用'\0'
};
typedef HFMNode* HFMNodeP;
typedef map<int, HFMNodeP> NodeMap;//节点的位置为key,节点的指针为值
typedef int Position;
//把树存储在文件中
struct HFMNodeFile {
    char key; //节点值
    weighttype weight;
    Position p; //节点在完全二叉树中的位置
};
bool compare(HFMNode* e1, HFMNode* e2) {
    return e1->weight < e2->weight;
}//构建小顶堆，方便每次取两个最小值
class HFMTree {
public:
    HFMTree() {
        root = nullptr;
        count = 0;
    }
    ~HFMTree() {
        ClearDecodeTree();
    }
    //建立哈夫曼树
    HFMNode* BuildHFMTree(const map<char, double>& KVmap) {
        vector<HFMNode*> HFMNodes;
        for (auto itr = KVmap.begin(); itr != KVmap.end(); ++itr) {
            HFMNodes.push_back(new HFMNode(itr->first, itr->second));
            ++count;
        }

        make_heap(HFMNodes.begin(), HFMNodes.end(), compare);

        while (HFMNodes.size() > 1) {
            HFMNode* right = HFMNodes.front();
            pop_heap(HFMNodes.begin(), HFMNodes.end(), compare);
            HFMNodes.pop_back();

            HFMNode* left = HFMNodes.front();
            pop_heap(HFMNodes.begin(), HFMNodes.end(), compare);
            HFMNodes.pop_back();

            HFMNode* parent = new HFMNode(left->weight + right->weight);
            parent->left = left;
            parent->right = right;

            HFMNodes.push_back(parent);
            push_heap(HFMNodes.begin(), HFMNodes.end(), compare);
        }

        if (!HFMNodes.empty()) {
            root = HFMNodes.front();
        }

        return root;
    }
    //建立哈夫曼编码树,返回根指针
    HFMNode* BuildCodeTree() {
        //EncodingResults.resize(std::numeric_limits<char>().max());
        string code;//默认值为null,与string code=""  的区别见https://blog.csdn.net/yuanliang861/article/details/82893539
        //或者说，有点像vector里的reserve与resize方法；string code是预留空间，但不创建真正的对象；后者是创建真正的""的对象
        BuildCode(root, code);
        return root;
    };
    //得到整个字符集的哈夫曼编码
    void BuildCode(HFMNode* pNode, string& code) {
        if (pNode->left == NULL) {
            EncodingResults[pNode->key] = code;
            return;
        }

        code.push_back('0');
        BuildCode(pNode->left, code);
        code.pop_back();//去掉左边的0编码，走向右边
        code.push_back('1');
        BuildCode(pNode->right, code);
        code.pop_back();
    }
    //对待编码文件中的字符进行编码，输出到codeflie中
    void GetEncoding() {
        if (_access(tobeEncoding.c_str(), 00)) {
            cerr << tobeEncoding <<"该文件不存在!\n";
            exit(2);
        }
        ifstream fin(tobeEncoding);
        if (!fin.is_open()) {
            cerr << "文件" << tobeEncoding << "无法打开!\n";
            exit(1);
        }
        istreambuf_iterator<char> beg(fin), end;
        string strdata(beg, end);
        fin.close();
        ofstream fout(EncodingResult, ios::out | ios::trunc);
        if (!fout.is_open()) {
            cerr << "文件" << EncodingResult << "打开失败!\n";
            exit(1);
        }

        fout << this->GetCode(strdata);
    }
    //对编码文件codefile的编码进行译码，输出到TextFile中
    void GetText() {
        if (_access(EncodingResult.c_str(), 00)) {
            cerr << "该文件不存在!\n";
            exit(2);
        }
        ifstream fin(EncodingResult);
        if (!fin.is_open()) {
            cerr << "该文件无法打开!\n";
            exit(1);
        }
        istreambuf_iterator<char> beg(fin), end;
        string strdata(beg, end);
        string result = this->Decode(strdata);
        fin.close();
        ofstream fout(DecodingResult, ios::out | ios::trunc);
        if (!fout.is_open()) {
            cerr << "该文件无法打开!\n";
            exit(1);
        }
        fout << result << endl;
    }
    //清空编码树，释放内存
    void ClearDecodeTree() {
        ClearDecodeTree(root);
        root = nullptr;
    }
    //将哈夫曼编码树写入文件
    void writeBTree() {
        ofstream fout(hfmTree, ios::out | ios::trunc);
        if (!fout.is_open()) {
            cerr << "打开文件失败，将退出！\n";
            exit(1);
        }
        fout << count << endl;
        writeNode(root, 1); //写入节点
        fout.close();
    }
    //从哈夫曼编码树文件hfmTree中读取树并恢复到内存
    HFMTree* readBTree() {
        HFMTree* hfmtp = new HFMTree;
        NodeMap mapNode;
        HFMNode* nodep;
        string anode;//按行读取一条记录
        ifstream fin(hfmTree, ios::in);
        if (fin.is_open()) {
            fin >> hfmtp->count;//首先读取字符集的大小
            //接下来为count行字符的key与权重与位置
            stringstream input;
            vector<string> res;//存储分割的字符串
            string tmp;
            char tmpkey; double tmpweight; int tmpposition;
            getline(fin, tmp);
            int i = -1;
            while (getline(fin, anode)) {//getline丢掉了换行，不需再考虑
                input << anode;
                while (input >> anode)//按空格分割，分别得到char 型的key, int 型的weight, int型的 position
                {
                    res.push_back(anode);
                }
                input.clear(ios::goodbit);
                tmpkey = res[++i][0];//res[0]得到key的string，再用res[0][0]得到第一个字符即key
                tmpweight = stringToNum<weighttype>(res[++i]);
                tmpposition = stringToNum<int>(res[++i]);
                nodep = new HFMNode(tmpkey, tmpweight);
                mapNode.insert(NodeMap::value_type(tmpposition, nodep));
            }
            NodeMap::iterator iter;
            NodeMap::iterator iter_t;
            for (iter = mapNode.begin(); iter != mapNode.end(); iter++) {
                iter_t = mapNode.find(2 * iter->first);
                if (iter_t != mapNode.end()) { //找到左儿子
                    iter->second->left = iter_t->second;
                }
                else {	//未找到左儿子
                    iter->second->left = NULL;
                }
                iter_t = mapNode.find(2 * iter->first + 1);
                if (iter_t != mapNode.end()) { //找到右儿子
                    iter->second->right = iter_t->second;
                }
                else {	//未找到右儿子
                    iter->second->right = NULL;
                }
            }
            iter_t = mapNode.find(1); //找root节点
            if (iter_t != mapNode.end()) {
                hfmtp->root = iter_t->second;
            }
            fin.close();
        }
        return hfmtp;
    }

    void printBTreeToScreen(HFMTree* hfmt) {
        printSubBTreeToScreen(hfmt->root, 0);
    }
    void printBTreeToFile(HFMTree* hfmt,  string filename=TreePrin) {
        ofstream fout(filename, ios::out | ios::trunc);
        if (!fout.is_open()) {
            cerr << "打开文件失败，将退出！\n";
            exit(1);
        };
        printSubBTreeToFile(hfmt->root, 0,fout);
        fout.close();
    }
    HFMNode* root;
private:
    int count;
    map<char, string>EncodingResults;
    //vector<string> EncodingResults;
    //写入单个哈夫曼树节点
    void writeNode(const HFMNodeP hfm_nodep, Position p) {
        if (!hfm_nodep) {
            return;
        }
        ofstream fout(hfmTree, ios::out | ios::app);
        if (!fout.is_open()) {
            cerr << "打开文件失败，将退出！\n";
            exit(1);
        }
        HFMNodeFile node;
        node.key = hfm_nodep->key;
        node.weight = hfm_nodep->weight;
        node.p = p;
        //写入当前节点,按行写入字符，权重，在哈夫曼树中的位置
        fout << node.key << " " << node.weight << " " << node.p << endl;
        //写入左子树
        writeNode(hfm_nodep->left, 2 * p);
        //写入右子树
        writeNode(hfm_nodep->right, 2 * p + 1);
    }
    //带缩进地打印一个哈夫曼树节点,每层缩进量增加2个空格
    void printSubBTreeToScreen(HFMNodeP hfmnp, int indentation) {
        int i;
        if (!hfmnp)
            return;
        for (i = 0; i < indentation; i++)
            cout << " ";
        cout << hfmnp->key << " with " << hfmnp->weight << endl;
        printSubBTreeToScreen(hfmnp->left, indentation + 2);
        printSubBTreeToScreen(hfmnp->right, indentation + 2);
    }
    void printSubBTreeToFile(HFMNodeP hfmnp, int indentation,ofstream&fout) {
        int i;
        if (!hfmnp)
            return;
        for (i = 0; i < indentation; i++)
            fout << " ";
        fout << hfmnp->key << " with " << hfmnp->weight << endl;
        printSubBTreeToFile(hfmnp->left, indentation + 2,fout);
        printSubBTreeToFile(hfmnp->right, indentation + 2,fout);
    }
    //递归到叶子节点后再删除叶子节点
    void ClearDecodeTree(HFMNode* pNode) {
        if (pNode == nullptr) return;

        ClearDecodeTree(pNode->left);
        ClearDecodeTree(pNode->right);
        delete pNode;
    }
    //根据文本内容，遍历每一个字，连接每个字的编码得到文本的编码
    string GetCode(const string& Text) {
        string TextEncodingResult;
        for (int i = 0; i < Text.size(); ++i) {
            TextEncodingResult += EncodingResults[Text[i]];
        }

        return TextEncodingResult;
    }
    //根据一段文本的哈夫曼编码，得到对应的文本
    string Decode(const string& TextEncodingResult) {
        string Text;

        HFMNode* pNode = root;
        for (int i = 0; i < TextEncodingResult.size(); ++i) {
            if (TextEncodingResult[i] == '0') {
                pNode = pNode->left;
            }
            else {
                pNode = pNode->right;
            }

            if (pNode->left == NULL) {
                //哈夫曼树中只有度为0和度为2的节点
                //因此，只需判断左子树或右子树为空，就可以确定是叶子节点。
                //这时，把对应的字符压进文本，同时，从头开始遍历编码树
                Text.push_back(pNode->key);
                pNode = root;
            }
        }

        return Text;
    }
};
typedef HFMTree* HFMTreeP;
HFMTree* Initialization(int n);
int main()
{
    int flag = 0;
    int choice;
    HFMTree* hfmtp = nullptr;
    cout << "\n\n\t\t\t|**********************************************|\n";
    cout << "\t\t\t ______________________________________________|\n";
    cout << "\t\t\t|                 哈夫曼编码/译码系统          |\n";
    cout << "\t\t\t|                                              |\n";
    cout << "\t\t\t|   1.初始化           2.编码                  |\n";
    cout << "\t\t\t|                                              |\n";
    cout << "\t\t\t|   3.译码             4.印代码文件            |\n";
    cout << "\t\t\t|                                              |\n";
    cout << "\t\t\t|   5.印哈夫曼树      |\n\n";
    cout << "\t\t\t|   0.退出                                     |\n";
    cout << "\t\t\t|********************S**************************|\n";
    while (cout << "\n\t\t\t请选择功能（输入0-5任意一个数字）:\n" && cin >> choice)
    {
        switch (choice)
        {
        case 1: {
            int n;
            cout << "请输入字符集大小:\n";
            cin >> n;
            hfmtp = Initialization(n);
            flag = 1;
            cout << "初始化完成\n";
            break;
        }
        case 2: {
            if (flag == 1) {
                //内存中有哈夫曼树
                hfmtp->GetEncoding();
            }
            else {
                //内存中没有哈夫曼树，需要先从文件读取，并恢复哈夫曼树再进行操作
                hfmtp = hfmtp->readBTree();
                flag = 1;//经过恢复后，内存中已有哈夫曼树
                hfmtp->BuildCodeTree();
                hfmtp->GetEncoding();
            }
            cout << "编码完成\n";
            break;
        }
        case 3: {
            if (flag == 1) {
                hfmtp->GetText();
            }
            else {
                hfmtp = hfmtp->readBTree();
                flag = 1;//经过恢复后，内存中已有哈夫曼树
                hfmtp->GetText();
            }
            cout << "译码完成\n";
            break;
        }
        case 4: {
            ifstream fin(EncodingResult);
            istreambuf_iterator<char> beg(fin), end;
            string strdata(beg, end);
            fin.close();
            ofstream fout(CodePrin, ios::out | ios::trunc);
            if (!fout.is_open()) {
                cerr << "打开文件失败，将退出！\n";
                exit(1);
            }
            fout << strdata;
            for (int i = 1; i <= strdata.size(); ++i) {
                if (i % 50 == 0) cout << "\n";
                cout << strdata[i - 1];
            }
            break;
        }
        case 5: {
            if (flag == 0) {
                //内存中没有哈夫曼树，需要先从文件读取，并恢复哈夫曼树再进行操作
                hfmtp = hfmtp->readBTree();
                flag = 1;//经过恢复后，内存中已有哈夫曼树
            }
            ofstream fout(TreePrin, ios::out | ios::trunc);
            if (!fout.is_open()) {
                cerr << "打开文件失败，将退出！\n";
                exit(1);
            }
            hfmtp->printBTreeToScreen(hfmtp);
            hfmtp->printBTreeToFile(hfmtp);
            break;
        }
        case 0:{
            cout << "正在退出...\n";
            Sleep(1000);
            exit(0);
        }
        default:
            cout << "请输入0~5之间的输入!\n";
            break;
        }
    }
    return 0;
}
HFMTree* Initialization(int n) {

    map<char, double>tmp;
    char key;
    double weight;
    cout << "依次输入字符及其权重\n";
    for (int i = 0; i < n; ++i) {
        cin >> key >> weight;
        tmp.insert(pair<char,double>(key, weight));
    }
    HFMTree* hfmt = new HFMTree;
    hfmt->BuildHFMTree(tmp);

    ofstream fout(hfmTree, ios::out | ios::trunc);
    if (!fout.is_open()) {
        cerr << "打开文件失败" << endl;
        exit(1);
    }
    hfmt->writeBTree();
    return hfmt;
}
//我认为判断内存中是否存在哈夫曼树的方式，是看是否进行了Initialization或者readBTree，因此，我在该函数中设置了flag变量