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

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

最近的数据结构大作业…
其中涉及到了很多，像一些哈夫曼树的编码、译码，以及树的二叉树形式的存储及恢复。。
[基本要求]
一个完整的系统应具有以下功能：
（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中。

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

参考:

哈夫曼编码C++实现
二叉树的文件存储和读取
c++按行读取文件的方式
c++ofstream与c风格fwrite的一个小区别
c++字符串按空格分割
这里是用了头文件<sstream>处理的，相对简单一些，但是限于以空格分割，更复杂的请搜索split函数。
上面的空格分割字符串存在只能处理一行的问题，我在其进行了改进
c++ string类型与基本数值类型的互相转换
c++ 头文件中stringstream流的用法的一些补充
access函数：检测文件是否存在/是否具有读/写权限
string 与const char*、char*、char[]之间相互转换
一次读入整个txt文件到一个string中
在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->r