哈夫曼树加密解密

哈夫曼数

1.哈夫曼树为何能压缩数据？

这个问题在上课时一直没弄懂，感觉老师表述的不太清楚。下课后上网查了一下，感觉豁然开朗。
假设原编码每个字符占4bits（其实ASCII编码每个占8bits），为什么一定要固定为4bits呢？
因为计算机储存是连续的且只能储存0和1。一大段字符串对应一大段二进制编码。只有每个固定为四位，才能把每个字符分割开来。
例如，把a=010，b=01，c=00，d=10。那么01001010，可以是aad，也可以是bcdd也可以是aba。
那么为什么哈夫曼树能够实现编码长度不固定呢？4
由于haffman树是唯一确定的，将哈夫曼树理解为一种编码对应表，便能实现压缩。

2.具体实现

先贴代码

//采用部分C++11特性，在VisualStudio2017下已通过编译
#include<iostream>
#include<string>
#include<vector>
using namespace std;
struct node {
    int ascii,times;
    node *lchild, *rchild;
};

node* Hafman(vector<node*> a) {
    node* min1 = new node, *min2 = new node; node *p = new node;
    int t = a.size();//第二个坑
    for (int i = 0; i < t-1; i++) {
        min1 = new node;
        min1 = a[0]; 
        int j, k, j1 = 0, k1 = 0;
        for (j = 0; j < a.size(); j++) {
            if (a[j]->times < min1->times) { min1 = a[j]; j1 = j; }
        }
        a.erase(a.begin() + j1);//从vector中释放最小值


        min2 = a[0]; 
        for (k = 0; k < a.size(); k++) {
            if (a[k]->times < min2->times) { min2 = a[k]; k1 = k; }
        }
        a.erase(a.begin() + k1);//从vector中释放次小值

        p = new node;//第一个坑
         p->lchild = min1; p->rchild = min2;
         p->times = min1->times + min2->times;

        a.push_back(p);

    }
    return p;
}
void preorder(node *&T,int &WPL) {
    if (T != NULL) {
        if(T->lchild!=NULL && T->rchild!=NULL)
        WPL = WPL + T->times;
        preorder(T->lchild,WPL);
        preorder(T->rchild,WPL);
    }
}
void recode(node *&T, int x,string code) {
    if (T != NULL) {
        if (T->lchild == NULL && T->rchild == NULL &&T->ascii == x)
            cout << code;
        recode(T->lchild, x,code+"0");
        recode(T->rchild,  x,code +"1");
    }
}
int main()
{
    string text; int mark[128]; vector<node*> tab;
    for (int i = 0; i < 128; i++) mark[i] = 0;
    cin >> text;
    cout <<"原字符串编码占:"<< text.length() * 4<<"bits"<<endl;
    cout << "各个字符出现的频次为：" << endl;
    for (int i = 0; i < text.length(); i++) {
        int k = text[i];
        mark[k] ++;
    }
    for (int i = 0; i < 128; i++) {
        if (mark[i] != 0) {
            cout << char(i) << ":" << mark[i]<<endl;
            node *a=new node;
            a->ascii = i;
            a->times = mark[i];
            a->lchild = NULL;
            a->rchild = NULL;
            tab.push_back(a);
        }
    }
    node *root=Hafman(tab);
    int x=0;
    preorder(root, x);
    cout << endl;
    cout << "WPL="<<x<<endl<<endl;
    string code;
    cout << "压缩编码如下：" << endl;
    for (auto a : tab)
    {
        cout << char(a->ascii) << "…………";
        recode(root, a->ascii, code);
        cout << endl;
    }
    cout << "压缩比为" << (double)x / (text.length() * 4) * 100 << "%" << endl;
    cin >> text;
}

哈夫曼树的构建原理不再赘述。
由于哈夫曼树的原始数据需要带权重，所以定义哈夫曼树节点如下：

struct node {
    int ascii,times;//times即权重，ascii为编码
    node *lchild, *rchild;
};

3.测试

为了更方便的组织数据，需要一个vector容器，将所有原始节点都置于该容器内。
1.找出权重最小的两个节点。
利用经典的找最小值方法，可以找出第一个最小值。难点是找次小值。
我的思路是利用vector的功能函数，将最小值从vector中释放后，再找一次最小值。从而找到次小值。将次小值再次释放。
注意，由于使用了min1，min2记录两个值，并立即用于构建哈夫曼树，所以释放后，这两个值并没有丢失。
将min1，min2的权重相加，形成新的结点，，将min1，min2的父节点设置为新节点，并将新节点加入vector中。
不断循环上述过程，便可完成哈夫曼树的构建。

至此，大致思路就是这样。有一些坑我单独说：
1.万恶的指针
构建新节点时，需要new一个，并且把子节点设置为Null，不然指针错误，程序崩溃。
2.使用for循环时，注意控制条件的改变情况。
在上述程序中，很容易发现，n个初始元素，需要循环n-1次便可完成哈夫曼树的构建。
所以很显然，for（int i=0；i<原始vector长度；i++），错误就出在这里，最初直接使用size()函数置入for循环内，然而，由于删除了vector中的元素。size（）函数的大小是会减小的。应该在循环未开始前，将t=size（），t置于for循环内。
这两个坑抹杀了我几个小时的debug时间。
T T