[南阳OJ]Haffman编码

题目: 哈弗曼编码大家一定很熟悉吧(不熟悉也没关系,自己查去。。。)。现在给你一串字符以及它们所对应的权值,让你构造哈弗曼树,从而确定每个字符的哈弗曼编码。当然,这里有一些小规定:

1.规定哈弗曼树的左子树编码为0,右子树编码为1;

2.若两个字符权值相同,则ASCII码值小的字符为左孩子,大的为右孩子;

3.创建的新节点所代表的字符与它的左孩子的字符相同;

4.所有字符为ASCII码表上32-96之间的字符(即“ ”到“`”之间的字符)。

输入包含多组数据(不超过100组) 每组数据第一行一个整数n,表示字符个数。接下来n行,每行有一个字符ch和一个整数weight,表示字符ch所对应的权值,中间用空格隔开。 输入数据保证每组测试数据的字符不会重复。

对于每组测试数据,按照输入顺序输出相应的字符以及它们的哈弗曼编码结果

这道题很坑,空格也能作为输入,坑了很长时间……

#include <stdio.h>
#include <math.h>

#include <algorithm>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef struct BiTNode{  
    char data;
    int weight;
    BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

bool compareBiTNode(BiTNode *a, BiTNode *b)  
{
    if(a->weight == b->weight) { // 根据题目要求,如果权重一样,那么ascii码小的是左孩子 
        return a->data > b->data;
    }

    return a->weight > b->weight;
}

void insertIntoVector(vector<BiTNode*> &a, BiTNode *node) // 这里的a一定要用引用,不然加入没有用  
{
    int i;

    // 这句的逻辑表达式有点复杂
    // 是为了保证如果权重一样,那么ascii码小的是左孩子 
    for(i = 0;
            i < a.size()
            && (a[i]->weight > node->weight || (a[i]->weight == node->weight && a[i]->data > node->data));
                i++);
    a.insert(a.begin() + i, node);
}

// 如果用&a,而不是a,那么a是引用,调用完这个函数后会破坏原来vector里的内容 
BiTree constructHaffmanTree(vector<BiTNode*> a)  
{
    BiTNode *l, *r;
    BiTNode *f;

    if(a.size() == 0) {
        return NULL;
    }

    sort(a.begin(), a.end(), compareBiTNode); // 从大到小排列 

    while(a.size() > 1) {
        // 顺序不能乱,保证如果权重一样,ascii码小的是左孩子 
        l = a[a.size() - 1];
        a.pop_back(); // 删除最后一个元素 
        r = a[a.size() - 1];
        a.pop_back(); // 删除最后一个元素 

        f = new BiTNode();
        f->lchild = l;
        f->rchild = r;
        f->data = l->data;
        f->weight = l->weight + r->weight;

        insertIntoVector(a, f);
    }

    return a[0];
}

void traversalHaffmanTree(BiTree t, string code, map<BiTNode*, string> &m)  
{
    if(t == NULL) {
        return;
    }

    if(t->lchild == NULL && t->rchild == NULL) { // 遇到叶子节点,保存code 
        m.insert(pair<BiTNode*, string>(t, code));
        return;
    } else {
        traversalHaffmanTree(t->lchild, code + "0", m);
        traversalHaffmanTree(t->rchild, code + "1", m);
    }
}

int main() {  
    vector<BiTNode*> a;
    BiTNode *p;
    BiTree t;
    map<BiTNode*, string> m;

    int n, w;
    char c;

    while(scanf("%d", &n) != EOF) {
        while(n--) {
            getchar(); // 读取换行符,不保存 
            c = getchar(); // 读取真正要计算的字符,因为可能有空格,所以不能用scanf 

            scanf("%d", &w);

            p = new BiTNode();

            p -> data = c;
            p -> weight = w;

            a.push_back(p);
        }

        // printf("constructing\n");
        t = constructHaffmanTree(a);
        // printf("constructed, t = %d\n", t->weight);

        traversalHaffmanTree(t, "", m);

        for(int i = 0; i < a.size(); i++) {
            printf("%c:%s\n", a[i]->data, m[a[i]].c_str());
        }

        a.clear(); // 每次要记得清空 
    }

    return 0;
}