3834 Problem D Haffman编码

45 阅读 0 评论 30 点赞

我是靠谱客的博主曾经纸鹤，最近开发中收集的这篇文章主要介绍3834 Problem D Haffman编码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题 D: Haffman编码
时间限制: 1 Sec 内存限制: 128 MB
献花: 12 解决: 11
[献花][花圈][TK题库]
题目描述
哈弗曼编码大家一定很熟悉吧（不熟悉也没关系，自己查去。。。）。现在给你一串字符以及它们所对应的权值，让你构造哈弗曼树，从而确定每个字符的哈弗曼编码。当然，这里有一些小规定：
1.规定哈弗曼树的左子树编码为0，右子树编码为1；
2.若两个字符权值相同，则ASCII码值小的字符为左孩子，大的为右孩子；
3.创建的新节点所代表的字符与它的做孩子的字符相同；
4.所有字符为ASCII码表上32-96之间的字符（即“ ”到“`”之间的字符）。
输入
输入包含多组数据（不超过100组）
每组数据第一行一个整数n，表示字符个数。接下来n行，每行有一个字符ch和一个整数weight，表示字符ch所对应的权值，中间用空格隔开。
输入数据保证每组测试数据的字符不会重复。
输出
对于每组测试数据，按照输入顺序输出相应的字符以及它们的哈弗曼编码结果，具体格式见样例。
样例输入
3
a 10
b 5
c 8
4
a 1
b 1
c 1
d 1
样例输出
a:0
b:10
c:11
a:00
b:01
c:10
d:11

#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <iostream>
#include <queue>
#include <cfloat>
#include <cstring>
using namespace std;
const int MaxN = 110;
int w[MaxN];
typedef struct data
{
int weight;
char val;
}Key;
typedef struct
{
Key key;
int parent, lchild, rchild;
}HuffmanNode, *HuffmanTree;
typedef char *HuffmanCode;
void seletTMin(HuffmanTree HT, int n, int &m1, int &m2)
{
int min = INT32_MAX;
for (int i = 1; i <= n; ++i)
{
if (HT[i].parent == 0 && min >= HT[i].key.weight)
{
if (min > HT[i].key.weight)
{
min = HT[i].key.weight;
m1 = i;
}
else
{
if (HT[m1].key.val > HT[i].key.val)
m1 = i;
}
}
}
min = INT32_MAX;
for (int i = 1; i <= n; ++i)
{
if (HT[i].parent == 0 && min >= HT[i].key.weight && i != m1)
{
if (min > HT[i].key.weight)
{
min = HT[i].key.weight;
m2 = i;
}
else
{
if (HT[m2].key.val > HT[i].key.val)
m2 = i;
}
}
}
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode *&HC,Key w[], int n)
{
if (n <= 1) return;
int m = 2 * n - 1;
HT = new HuffmanNode[m + 1];
for (int i = 1; i <= n; ++i)
{
HT[i].key = w[i];
HT[i].lchild = HT[i].rchild = HT[i].parent = 0;
}
for (int i = n + 1; i <= m; ++i)
HT[i].lchild = HT[i].rchild = HT[i].parent = 0;
for (int i = n + 1; i <= m; ++i)
{
int m1, m2;
seletTMin(HT, i - 1, m1, m2);
HT[i].lchild = m1;
HT[i].rchild = m2;
HT[m1].parent = HT[m2].parent = i;
HT[i].key.weight = HT[m1].key.weight + HT[m2].key.weight;
}
HC = new HuffmanCode[n + 1];
char * cd = new char[n];
cd[n - 1] = 0;
for (int i = 1; i <= n; ++i)
{
int start = n - 1;
for (int c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
{
if (HT[f].lchild == c)
cd[--start] = '0';
else
cd[--start] = '1';
}
HC[i] = new char[n - start];
strcpy(HC[i], cd + start);
}
delete cd;
}
int main()
{
#ifdef _DEBUG
freopen("data.txt", "r+", stdin);
#endif // _DEBUG
std::ios::sync_with_stdio(false);
HuffmanTree HT;
HuffmanCode *HC;
int n;
Key data[MaxN];
while (cin >> n)
{
for (int i = 1; i <= n; ++i)
cin >> data[i].val >> data[i].weight;
HuffmanCoding(HT, HC, data, n);
for (int i = 1; i <= n; ++i)
cout << data[i].val << ":" << HC[i] << endl;
delete HC;
delete HT;
}
return 0;
}
/**************************************************************
Problem: 3834
User: Sharwen
Language: C++
Result: 升仙
Time:1 ms
Memory:1700 kb
****************************************************************/