shunfurh
编程介的小学生
采纳率92.7%
2019-03-07 14:21 阅读 544

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条回答 默认 最新

  • qdv1100 qdv1100 2019-03-09 22:33

    #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;
    }

    点赞 评论 复制链接分享

相关推荐