C语言计算实现,字符串的编码值小于等于给定的值则输出yes,否则输出no

Problem Description
Javac++ 一天在看计算机的书籍的时候,看到了一个有趣的东西!每一串字符都可以被编码成一些数字来储存信息,但是不同的编码方式得到的储存空间是不一样的!并且当储存空间大于一定的值的时候是不安全的!所以Javac++ 就想是否有一种方式是可以得到字符编码最小的空间值!显然这是可以的,因为书上有这一块内容--哈夫曼编码(Huffman Coding);一个字母的权值等于该字母在字符串中出现的频率。所以Javac++ 想让你帮忙,给你安全数值和一串字符串,并让你判断这个字符串是否是安全的?

Input
输入有多组case,首先是一个数字n表示有n组数据,然后每一组数据是有一个数值m(integer),和一串字符串没有空格只有包含小写字母组成!

Output
如果字符串的编码值小于等于给定的值则输出yes,否则输出no。

Sample Input
2
12
helloworld
66
ithinkyoucandoit

Sample Output
no
yes

1个回答

#include
#include
#include
#include
#include

#pragma warning(disable:4996)
#define MAXLEN 110
using namespace std;

struct HuffmanTree {
int w;
int left, right, parent;
HuffmanTree()
{
w = left = right = parent = 0;
}
};

int w[MAXLEN];//权值
string huffmanCode[MAXLEN];//哈夫曼编码
HuffmanTree ht[MAXLEN*2];
map Hash;
int totalLength;
//初始化
void init()
{
for (int i = 1; i <= MAXLEN; ++i)
{
ht[i].left = ht[i].right = ht[i].parent = 0;
}
fill(w, w + MAXLEN, 0);
Hash.clear();
totalLength = 0;
}

//从哈夫曼树中选出没有父节点,权值最小的两个节点的下标
void select(HuffmanTree *ht,int n,int &s1,int &s2)
{
int min = INT_MAX;
int i;
for (i = 1; i <= n; ++i)
{
if (ht[i].parent == 0 && ht[i].w < min)
{
min = ht[i].w;
s1 = i;
}
}
min = INT_MAX;
for (i = 1; i <= n; ++i)
{
if (ht[i].parent == 0 && i!= s1 && ht[i].w < min)
{
min = ht[i].w;
s2 = i;
}
}
if (s1 > s2)
swap(s1, s2);
}

//建立哈夫曼树并编码
void HuffmanCoding(HuffmanTree * ht,string *hfCode,int *weight,int n)
{
if (n <= 1)
return;
//ht = new HuffmanTree[n * 2];//哈夫曼树节点个数为2*n-1个,这里数组0不用,所以分配2*n个
//为叶子节点赋上权值
int i,s1,s2;
for (i = 1; i <= n; ++i)
ht[i].w = weight[i];
for (i = n + 1; i <= 2 * n - 1; ++i)
{
select(ht, i - 1, s1, s2);
ht[i].w = ht[s1].w + ht[s2].w;
ht[s1].parent = ht[s2].parent = i;
ht[i].left = s1;
ht[i].right = s2;
}
//从每个叶子节点向上查找,直到找到根节点,
//如果当前节点是父节点的左孩子编码为0,否则为1
int c, p;
for (i = 1; i <= n; ++i)
{
c = i;
string temp;
while (ht[c].parent != 0)
{
p = ht[c].parent;
if (ht[p].left == c)
temp.insert(temp.begin(), '0');
else
temp.insert(temp.begin(), '1');
c = p;
}
hfCode[i] = temp;
totalLength += temp.size();
}
}
int setWeight(string &str)
{
char ch;
for (int i = 0; i < str.size(); ++i)
{
ch = str[i];
if (Hash.find(ch) == Hash.end())
{
Hash[ch] = 1;
}
else
{
++Hash[ch];
}
}
int index = 0;
for (auto it = Hash.begin(); it != Hash.end(); ++it)
{
w[++index] = it->second;
}
return index;//返回节点个数
}
int main()
{
int n,m,nodeNum;
string str;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
init();
cin >> m;
cin >> str;
nodeNum = setWeight(str);
HuffmanCoding(ht, huffmanCode, w, nodeNum);//哈夫曼编码
if (totalLength <= m)
cout << "yes" << endl;
else
cout << "no" << endl;
}
system("pause");
return 0;
}

qdv1100
qdv1100 这是c++写的,五个头文件没显示出来 分别是:iostream queue map string algorithm
一年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐