上学期数据结构课的练习，觉得对学弟学妹们有点帮助，就拿出来了(～￣▽￣)～

实现功能

1.文件输入输出

1)从用户输入指定位置读取文件
2)从文件中按行单词和该单词词频
3)将按照哈夫曼树生成的单词和对应编码输出到文件

2.生成哈夫曼树

1)根据单词权重生成哈夫曼树
2)权重越小的节点越靠下，权重越大的节点越靠上

3.为各节点编码

1)根节点编码为空字符串
2)左子树编码在父节点基础上后缀一个“0”，右节点编码在父节点编码基础上后追一个“1”
3)权重越大的节点编码越短，权重越小的节点编码越长

算法简述

存储结构

1.使用类作为基础结构

为保证良好的封装性和对数据便于操作，我在本次实验中使用类作为基础结构。定义treeNode类作为哈夫曼树节点（以及未暂时未编码进树的孤立节点），每个treeNode对象包含单词、权重、编码以及指向左右子树的指针。

1)对象的创建初始化

treeNode类对象可以以两种方式创建。一种方式是将单词和权重作为参数，编码初始化为空字符串，指向左右子树的指针为空，这样创建的节点在最终建立的哈夫曼树中会成为叶节点；另一种方式是将左右子树作为参数建立父节点，编码初也始化为空字符串，指向子树的指针指向输入的参数，单词初始化为空字符串，权重为左右子树之和。

2)类的函数

除了构造函数和重载运算符，该类还有重要函数，分别是编码和输出函数。这两个函数都需要递归调用，他们在完成建树过程后从根节点递归调用遍历全树。其算法将在后文算法图中详细呈现。

2.使用元素为指针的vector作为抽象的树

使用类treeNode解决了每一个节点数据类型的问题，但整个哈夫曼树也需要一个结构存储。这个存储结构需要满足以下特性：

1)含有的元素需要能够随意增减。

在哈夫曼树构建过程中，需要随时用最小的两个节点生成新的父节点加入树中，这实质上是删除两个元素再加入一个元素的过程，因此整个树的结构应该在数据加入和删除方面较为灵活。

2)被删除的元素应该仍能以其他方式被访问。

哈夫曼树中所有已经拥有父节点的子节点都应该被“删除”，不再参与权重比较和建树过程；但是它们应该仍能被访问，因为建树完成后任何节点都不应该丢失，最终的输出和应用仍需要使用它们。

3)整个树中所有元素应该能够较为方便迅速地找到最小元素或执行排序。

哈夫曼树涉及到寻找权重最小节点的过程，而且这个过程需要反复执行，因此寻找排序或最小节点应该能够被迅速方便地操作。

所以，最终我决定使用一个vector来保存哈夫曼树，vector中的元素为指向treeNodo类对象的指针。首先，vector类能够方便地进行元素加入和删除，并且STL中提供了sort()函数可以方便地进行排序。另外，由于保存在这个vector内的元素都是通过new操作符创建的对象，只要新创建并压入vector的父节点仍保留了指向子节点的指针，那么删除vector中的子节点的指针对子节点这个对象本身并没有影响，也即就是说删除vector中元素后该元素还可以其他方式被访问。

整体算法图

编码函数算法图

关键算法简述

1.寻找最小孤立节点

在我的算法中，哈夫曼树的构建每一步都需要找到当前权重最小的两个节点，将它们作为参数构造一个新的treeNode对象作为父节点，然后删除子节点。这里，我使用的是STL中的sort()排序。通过重载比较函数，实现以vector中元素指向对象的权重为关键字将vector中元素从大到小排序的功能。

完成排序后，指向权重最小的两个的指针节点即在vector末尾。将它们保存在临时变量中，之后使用pop_up()函数删除，最后以临时变量中的两个指针作为参数构造父节点并用push_back()函数压入vector，完成一次操作。

2.使用递归函数编码节点

构建完哈夫曼树后，可以直接访问的节点只有根节点，所有其他节点都需要从根节点通过指针一层层访问，无法直接遍历。这种情况，可以通过函数递归调一层层遍历。

编码函数的参数是该对象的编码，由调用它的函数（上一层递归）赋值。函数会先检查该节点是否为叶节点，判断依据是数据域中的单词字符串是否为空，只有叶节点单词字符串非空。如果是叶节点就可以将编码赋值给数据域中的编码字符串并跳出递归。如果不是叶节点就分别调用左子树和右子树的编码函数，左子树参数为自身参数字符串后缀“0”，右子树参数为自身参数字符串后缀“1”，这样进入下一轮递归。

源代码

Main.cpp（程序入口）

#include <fstream>;
#include <vector>;
#include <string>;
#include <iostream>;
#include <algorithm>;
#include "treeNode.h"
#include "globle.h"

using namespace std;

int main()
{
    string inputFileName;
    cout << "请输入完整文件名（包含路径和扩展名）：";
    cin >;>; inputFileName;
    ifstream inputFile;
    inputFile.open(inputFileName);
    string tmpWord;
    int tmpCount;
    vector <treeNode*>; nodeList;
    while (inputFile >;>; tmpWord&&inputFile >;>; tmpCount)
    {
        treeNode *newNode = new treeNode(tmpWord, tmpCount);
        nodeList.push_back(newNode);
    }
    while (nodeList.size()>; 1)
    {
        //将vector元素从大到小排序
        sort(nodeList.begin(), nodeList.end(), compare);
        //保存最小的两个元素到临时变量并从vector删除
        treeNode *leftTmp, *rightTmp;
        leftTmp = nodeList.back();
        nodeList.pop_back();
        rightTmp = nodeList.back();
        nodeList.pop_back();
        //构造父节点并压入vector
        treeNode *newNode = new treeNode(leftTmp, rightTmp);
        nodeList.push_back(newNode);
    }
    string outputFileName;
    cout << "请输入希望输出的完整文件名（包含路径和扩展名）：";
    cin >;>; outputFileName;
    ofstream outputFile;
    outputFile.open(outputFileName);
    //从根节点开始调用编码函数和输出函数（递归）
    nodeList[0]->;encode();
    nodeList[0]->;print(outputFile);
    system("pause");
}

globle.h（不在类内的全局函数声明）

#pragma once
#include "treeNode.h"

using namespace std;

//重载对自定义类treeNode的比较函数
bool compare(const treeNode *a, const treeNode *b);

globle.cpp（不在类内的全局函数定义）

#include "globle.h"
#include <vector>;

//重载对自定义类treeNode的比较函数
bool compare(const treeNode *a, const treeNode *b)
{
    return a->;getWeight()>; b->;getWeight();
}

treeNode.h（类的声明）

#pragma once
#include <string>;
#include <vector>;
#include <fstream>;

using namespace std;

class treeNode
{
    string word;
    string code;
    int weight;
    treeNode *leftChild;
    treeNode *rightChild;
public:
    treeNode(string inputWord,int inputWeight);
    treeNode(treeNode *left, treeNode *right);
    int getWeight()const;
    void encode(string code = "");
    void operator=(const treeNode &a);
    void print(ofstream &file);
};

treeNode.cpp（类的定义）

#include "treeNode.h"
#include <iostream>;

//构造叶节点
treeNode::treeNode(string inputWord,int inputWeight)
{
    word = inputWord;
    code = "";
    weight = inputWeight;
    leftChild = NULL;
    rightChild = NULL;
}

//从子节点构造父节点
treeNode::treeNode(treeNode * left, treeNode * right)
{
    word = "";
    leftChild = left;
    rightChild = right;
    weight = left->;weight + right->;weight;
}

//向类外函数返回权重
int treeNode::getWeight()const
{
    return weight;
}

//递归编码
void treeNode::encode(string oringinCode)
{
    //如果是叶节点就将编码存储到数据域并停止递归
    if (word != "")
    {
        code = oringinCode;
        return;
    }
    //调用子节点编码函数的参数为自身参数加后缀
    leftChild->;encode(oringinCode + "0");
    rightChild->;encode(oringinCode + "1");
}

//重载赋值操作符
void treeNode::operator=(const treeNode & a)
{
    word = a.word;
    code = a.code;
    weight = a.weight;
    leftChild = a.leftChild;
    rightChild = a.rightChild;
}

//输出函数，参数为文件输出流的引用
void treeNode::print(ofstream &file)
{
    //如果是叶节点就输出单词和编码
    if (word != "")
    {
        file << word << ' ' << code << endl;
    }
    //如果有子节点就继续递归
    if (leftChild != NULL)
    {
        leftChild->;print(file);
    }
    if (rightChild != NULL)
    {
        rightChild->;print(file);
    }
}

存在的不足

性能问题

1.反复排序

在建树过程中为了找到最小节点，反复使用了std::sort()函数。虽然该函数性能较好，但针对本实验中上万次的排序还是不够迅速，整个程序执行花了两分钟左右。

2.过多递归

递归虽然是很方便使用，但从空间复杂度的角度来说有其弊端。虽然在本实验中不到四万次递归效率很高，但是如果使用更多数据，可能出现内存不足方面的问题。

封装性不够好

1.数据类型限制

本程序只能针对有权重的字符串建立哈夫曼树，如果想兼容更多数据类型需要对类本身进行修改。其实从算法上来说，本程序可以完成任何带权重数据类型的建树，但其封装性和可移植性还是略有欠缺。

2.输出模块过于独立

输出模块是接受一个输出文件流作为参数并向该文件流输出。虽然可以通过重载函数实现向控制台打印或是进行其他操作，但无法实现直接向主调函数返回数据，独立性过强，不能与主函数或其他函数结合。