哈夫曼编码

传送门

OJ小作业 很久以前第一次听说哈夫曼树问了一下煞笔室友 听他很不屑地说 只是一个贪心而已 我也就没怎么在意

最近李总上课点名不得不去上一下 可惜也只是到那里发了一下呆 点了一下到就过去了 他在讲哈夫曼编码的时候我也没去听

搞得我刚开始看到这题的时候有点小蒙蔽 还好数据比较水 不然估计要卡很长时间 （因为完全是我根据以前的知识xjb搞的 还好还好是一A

下面是源码+注解 （因为完全是自己看了远离后搞得 可能有点烦……..

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>

#define root tree[id]
#define leson tree[ldir]
#define rison tree[rdir]

using namespace std;
const int maxn = 104;
int len, all_time;
int tree_root;//根节点
char to_c[maxn];//由节点的值转化为字符
char tar[maxn * 100];
char tar_ch;//当前目标字符
char output[maxn];//输出数组
bool flag;//标记  如果已经输出就直接返回

struct node {
    int lson, rson;
    int tim;//结点生成时间  所有原结点初始化为0
    int order;//节点编号
    int val;//结点的值
    bool operator<(const node& a) const
    {
        if (val != a.val)
            return val > a.val;
        if (tim != a.tim)
            return tim > a.tim;
        return order > a.order;
    }//按照题意出队
};

priority_queue<node> que;
node tree[maxn << 2];

int CreatTree()
{
    node ta, tb;
    int id;
    while (que.size() > 1) {
        ta = que.top();
        que.pop();
        tb = que.top();
        que.pop();
        id = len + all_time;
        root.lson = ta.order;
        root.rson = tb.order;
        root.val = ta.val + tb.val;
        root.order = id;
        root.tim = all_time++;
        que.push(root);
        // printf("%d %d\n",ta.order,tb.order);
    }//取出两个节点并合并再入队   最后剩余的便是根节点
    ta = que.top();
    que.pop();
    return ta.order;
}

void lock(int id, int dep)
{
    if (flag)//若已经输出过了   就直接返回
        return;
    int ldir = root.lson, rdir = root.rson;
    if (ldir) {
        output[dep] = '0';
        lock(ldir, dep + 1);
    }
    if (rdir) {
        output[dep] = '1';
        lock(rdir, dep + 1);
    }
    if (!ldir && !rdir && to_c[root.order] == tar_ch) {  //确保该结点为叶子结点也可以省点时间
        for (int i = 0; i < dep; i++)
            putchar(output[i]);
        flag = true;//标记为true
    }
}

int unlock(int index)
{
    int id = tree_root;
    while (root.lson || root.rson) {
        if (tar[index] == '0')  // 0 向左 1向右
            id = root.lson;
        else
            id = root.rson;
        index++;
    }
    putchar(to_c[root.order]);
    return index;//返回转化后的index
}

int main()
{
    while (scanf("%s", to_c + 1) != EOF) {
        len = strlen(to_c + 1);
        for (int id = 1; id <= len; id++) {
            scanf("%d", &root.val);
            root.order = id;
            root.tim = 0;
            root.lson = root.rson = 0;
            que.push(root);
        }
        all_time = 1;
        tree_root = CreatTree();
        // printf("root: %d\n",tree_root);
        // for(int id=1;id<=tree_root;id++)
        //    printf("order: %d  val: %d  lson: %d  rson:%d\n",root.order,root.val,root.lson,root.rson); //可取消注释查看建树是否正确
        scanf("%s", tar);
        int tar_len = strlen(tar);
        for (int i = 0; i < tar_len; i++) {
            tar_ch = tar[i];
            flag = false;
            lock(tree_root, 0);
        }
        puts("");
        scanf("%s", tar);
        tar_len = strlen(tar);
        int i = 0;
        while (i < tar_len)
            i = unlock(i);
        puts("");
    }
    return 0;
}