实验五：树及其应用——哈夫曼树

【实验目的】

通过本次实验使学生了解哈夫曼树的结构特性及其基本操作的实现过程，同时掌握在实际问题背景下的应用开发能力。

【实验内容】

1. 问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编／译码系统。试为这样的信息收发站写一个哈夫曼码的编／译码系统。
2. 基本要求：
   　　一个完整的系统应具有以下功能：
   （１）、Ｉ：初始化（Initialization）。从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
   （２）、Ｅ：编码（Encoding）。利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
   （３）、Ｄ：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
   （４）、Ｐ：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。
   （５）、Ｔ：印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
3. 测试数据：见上机指导书Ｐ149测试数据。（此处测试数据写在代码的首部）
4. 实现提示：
   　（1）、用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Ｑ”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Ｑ”为止。
   　（2）、在程序的一次执行过程中，第一次执行I,D或Ｃ命令之后，哈夫曼树已经在内存了，不必读入。每次执行中不一定执行Ｉ命令，因为文件hfmTree可能早已建好。

【实验代码】

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>

#define MAXVALUE 2147483647
using namespace std;

/*
 * 27
 * 空格(需要你打一个真的空格，然后再输入后面的英文字母)ABCDEFGHIJKLMNOPQRSTUVWXYZ
 * 186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1
 *
*/

typedef struct {
    char data; // 数据
    int weight; // 权值
    int parent, lChild, rChild; // 双亲位置，左孩子位置，右孩子位置
    string code; // 哈夫曼编码
} HTNode, *HuffmanTree;

void Initialization(HuffmanTree &HT, int &n); // 初始化哈夫曼树
void StorageToHfmTree(HuffmanTree HT, int m); // 存储哈夫曼树到hfmtree文件中
void HfmTreeToHuffmanTree(HuffmanTree &HT,int &n); // 从文件中读取哈夫曼树
void HuffmanCoding(HuffmanTree &HT, int n); // 为字符编码
void GetMinValue(HuffmanTree HT, int n, int &s1, int &s2); // 获取此时结点中最小的两个

void Encoding(HuffmanTree HT, int n); // 将文本编码
void Decoding(HuffmanTree HT, int m); // 将文本译码
bool IsLeaf(HTNode HN); // 判断结点是否为叶子结点

void Print(); // 输出编码后的文件
void TreePrinting(HuffmanTree HT,int count, int index); // 打印哈夫曼树
void PrintT(HuffmanTree HT, int count, int index); // 打印哈夫曼树

int main() {
    int N = 0;
    HuffmanTree HT;

    char ch;
    while(true)
    {
        cout << "\n菜单：" << endl;
        cout << "I：初始化哈夫曼树，将其存储在文件hfmTree中。         E：对文件ToBeTran中的文本进行编码，将结果储存在文件CodeFile中" << endl;
        cout << "D：将文件CodeFile中的数据进行译码，储存在文件TextFile中                     P：将文件CodeFile中的数据输出在终端上" << endl;
        cout << "T：将内存中的哈夫曼树按树形结果输出在终端上，同时将此树储存在文件TreePrint中   Q：退出程序" << endl;
        cout << "请选择你要使用的功能：" << endl;
        cin >> ch;
        if(ch == 'Q')
        {
            cout << "退出程序成功！" << endl;
            break;
        }
        switch(ch)
        {
            case 'I':
                cout << "开始初始化哈夫曼树!" << endl;
                Initialization(HT, N);
                cout << "初始化完成!" << endl;
                break;
            case 'E':
                if(N == 0)
                {
                    HfmTreeToHuffmanTree(HT,N); //如果内存中没有哈夫曼树，就从文件中读取
                }
                cout << "开始编码! " << endl;
                Encoding(HT, N);
                cout << "编码成功！" << endl;
                break;
            case 'D':
                cout << "开始译码! " << endl;
                Decoding(HT, 2 * N - 1);
                cout << "译码成功！" << endl;
                break;
            case 'P':
                cout << "编码文件为! " << endl;
                Print();
                cout << "\n编码文件打印完毕！" << endl;
                break;
            case 'T':
                cout << "凹入表打印：" << endl;
                TreePrinting(HT,0,2*N-1);
                cout << "打印完成！" << endl;
                break;
            default:
                cout << "操作编码异常，请重新输入！" << endl;
        }
    }

    return 0;
}

void Initialization(HuffmanTree &HT, int &n) // 初始化哈夫曼树
{
    cout << "请输入字符集大小：" << endl;
    cin >> n;
    getchar();
    if (n <= 1) {
        cout << "字符集过小，初始化失败！" << endl;
        return;
    }
    int m = 2 * n - 1; // 哈夫曼树总结点数
    HT = new HTNode[m + 1];
    cout << "请依次输入你的字符集的字符：" << endl;
    for (int i = 1; i <= n; i++) {
        char ch;
        ch = getchar();
        if(ch == ' ')
        {
            ch = '@';
        } else if(ch == '\n')
        {
            ch = getchar();
        }
        HT[i].data = ch;
    }

    cout << "请依次输入你的字符集的各个字符所对应的权值：" << endl;
    for (int i = 1; i <= n; i++) {
        int wei;
        cin >> wei;
        HT[i].weight = wei;
        HT[i].parent = 0;
        HT[i].lChild = 0;
        HT[i].rChild = 0;
    }

    for (int i = n + 1; i <= m; i++) {
        HT[i].weight = 0;
        HT[i].parent = 0;
        HT[i].lChild = 0;
        HT[i].rChild = 0;
        HT[i].data = '#';
    }

    for (int i = n + 1; i <= m; i++) {
        int s1, s2;
        GetMinValue(HT, i - 1, s1, s2);
        HT[s1].parent = i;
        HT[s2].parent = i;
        HT[i].lChild = s1;
        HT[i].rChild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }

    HuffmanCoding(HT, n); // 为字符编码
    StorageToHfmTree(HT, m); // 将哈夫曼树存进文件中

}

void HfmTreeToHuffmanTree(HuffmanTree &HT, int &n) // 从文件中读取哈夫曼树
{
    ifstream infile("file/hfmTree.txt", ios::in);
    infile >> n;
    HT = new HTNode[2 * n];
    for (int i = 1; i <= 2 * n - 1; i++) {

        infile >> HT[i].weight >> HT[i].parent >> HT[i].lChild >> HT[i].rChild;
        if (i <= n) {
            infile >> HT[i].data;
        } else
        {
            HT[i].data = '#';
        }
    }
    infile.close();
    HuffmanCoding(HT, n);
}

void StorageToHfmTree(HuffmanTree HT, int m) // 存储哈夫曼树到hfmtree文件中
{
    ofstream outfile("file/hfmTree.txt", ios::out);
    outfile << (m + 1) / 2 << endl;
    for (int i = 1; i <= m; i++) {
        outfile << HT[i].weight << " " << HT[i].parent << " " << HT[i].lChild << " " << HT[i].rChild;
        if (i <= (m + 1) / 2) {
            outfile << " " << HT[i].data;
        }
        outfile << endl;
    }
    outfile.close();
}

void HuffmanCoding(HuffmanTree &HT, int n) // 为字符编码
{
    for (int i = 1; i <= n; i++) {
        for (int j = i, f = HT[i].parent; f != 0; j = f, f = HT[f].parent) {
            if (HT[f].lChild == j) {
                HT[i].code = '0' + HT[i].code;
            } else {
                HT[i].code = '1' + HT[i].code;
            }
        }
    }
}

void GetMinValue(HuffmanTree HT, int n, int &s1, int &s2) // 获取此时结点中最小的两个
{
    s1 = s2 = MAXVALUE;
    for (int i = 1; i <= n; i++) {
        if (HT[i].parent != 0) {
            continue;
        }
        if (s1 <= n) {
            if (HT[i].weight < HT[s1].weight) {
                s1 = i;
            }
        } else {
            if (HT[i].weight < s1) {
                s1 = i;
            }
        }

    }

    for (int i = 1; i <= n; i++) {
        if (HT[i].parent != 0 || i == s1) {
            continue;
        }
        if (s2 <= n) {
            if (HT[i].weight < HT[s2].weight && HT[i].weight > HT[s1].weight) {
                s2 = i;
            }
        } else {
            if (HT[i].weight < s2 && HT[i].weight >= HT[s1].weight) {
                s2 = i;
            }
        }
    }
}

void Encoding(HuffmanTree HT, int n) // 将文本编码
{
    string str1, str2 = "";
    ifstream infile("file/ToBeTran.txt", ios::in);

    ostringstream buf;
    char ch;
    while(buf && infile.get(ch))
    {
        buf.put(ch);
    }

    str1 = buf.str();
    infile.close();

    for (int i = 0; i < str1.size(); i++) {
        if(str1[i] == ' ')
        {
            str1[i] = '@';
        }

        for (int j = 1; j <= n; j++) {
            if (str1[i] == HT[j].data) {
                str2 += HT[j].code;
                break;
            }
        }
    }
    ofstream outfile("file/CodeFile.txt", ios::out);
    outfile << str2;
    outfile.close();
}

void Decoding(HuffmanTree HT, int m) // 将哈夫曼编码译码
{
    string code = "", str = "";
    ifstream infile("file/CodeFile.txt", ios::in);
    infile >> code;
    infile.close();

    int cur = m;
    for (int i = 0; i <= code.size(); i++) {

        if (IsLeaf(HT[cur])) {
            char ch = HT[cur].data;
            if(ch == '@')
            {
                ch = ' ';
            }
            str += ch;
            cur = m;
        }

        if (code[i] == '0') {
            cur = HT[cur].lChild;
        } else {
            cur = HT[cur].rChild;
        }
    }

    ofstream outfile("file/TextFile.txt", ios::out);
    outfile << str;
    outfile.close();
}

bool IsLeaf(HTNode HN) // 判断结点是否为叶子结点
{
    return (HN.lChild == 0 && HN.rChild == 0);
}

void Print() // 输出编码后的文件
{
    string str = "";
    ifstream infile("file/CodeFile.txt", ios::in);
    infile >> str;
    infile.close();

    ofstream outfile("file/CodePrin.txt", ios::out);
    for (int i = 0; i < str.size(); i++) {
        cout << str[i];
        outfile << str[i];
        if ((i + 1) % 50 == 0) {
            cout << endl;
            outfile << endl;
        }
    }
}

ofstream outTree("file/TreePrint.txt",ios::out);
void TreePrinting(HuffmanTree HT, int count, int index) // 打印存储哈夫曼树
{
    PrintT(HT,count,index);
    outTree.close();
}

void PrintT(HuffmanTree HT, int count, int index) // 打印哈夫曼树
{
    if (index > 0) {
        PrintT(HT, count + 1, HT[index].rChild);

        for (int i = 0; i < count; i++) {
            cout << "  ";
            outTree << "    ";
        }

        cout << HT[index].data << endl;
        outTree << HT[index].data << endl;
        PrintT(HT, count + 1, HT[index].lChild);

    }
}

【最终效果】