| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1608 人关注过本帖
标题:哈夫曼编码中遇到的小问题
只看楼主 加入收藏
EMMMM
Rank: 1
等 级:新手上路
帖 子:32
专家分:0
注 册:2017-9-16
结帖率:75%
收藏
 问题点数:0 回复次数:0 
哈夫曼编码中遇到的小问题
我以前写过一个计算哈夫曼编码的程序,是输入的字符和其出现次数,这次我要把他改成输入一连串字符串的形式,所以写了一个字符统计的功能,但是不知道为什么,出来的编码前面都是多一个0,比如我输入aaabbc,应该a是0,b是10(或者11),但是现在他显示的是a是00,b是011或者010,这是为什么?我直接输入字符和次数又不会出现这种情况?
代码如下:主要改动加粗
#include<iostream>
#include<vector>
#include<string>
#include<map>
#define NUM 200
using namespace std;

/* Huffman树的节点 */
struct Node
{
    Node(int frequency, char ch, Node* left, Node* right)
{
    this->frequency = frequency;
    this->ch = ch;
    this->left = left;
    this->right = right;
}
int frequency;
char ch;
Node* left;
Node* right;
};
/*哈夫曼树的类*/
class HuffmanCode
{
public:
    ~HuffmanCode()//析构函数
    {
        if (nod.size() > 0)
            clear(nod[0]);
    }

    /* 建树 */
    void buildTree(const char* ch, const int* fq, const int&size)
    {
        for (int i = 0; i<size; i++)
        {
            Node* node = new Node(fq[i], ch[i], NULL, NULL);
            nod.push_back(node);
        }
        while (nod.size() != 1)
        {
            Node* x = getMinNode();
            Node* y = getMinNode();
            Node* z = new Node(x->frequency + y->frequency, '\0', x, y);//合并,父节点为x+y
            nod.push_back(z);
        }
    }
    /* 编码 */
    void buildCode()
    {
        huff_code(nod[0], "");
    }
    /* 获取字符的编码 */
    string getCode(char ch)
    {
        return code[ch];
    }
private:
    /* 清空Huffman树 */
    void clear(Node* root)
    {
        if (root != NULL)
        {
            clear(root->left);
            clear(root->right);
            delete root;
        }
    }
    /* 获取结点中频率最小的结点并将其移出 */
    Node* getMinNode()
    {
        int min = 0;
        for (int i = 1; i<nod.size(); i++)
        {
            if (nod[i]->frequency < nod[min]->frequency)
            {
                min = i;
            }
        }
        Node* temp = nod[nod.size() - 1];
        nod[nod.size() - 1] = nod[min];
        nod[min] = temp;
        temp = nod[nod.size() - 1];
        nod.pop_back();
        return temp;
    }
    /* 遍历Huffman树编码,左0右1 */
    void huff_code(Node* r, string str)
    {
        if (r->left == NULL&&r->right == NULL)
            code[r->ch] = str;
        if (r->left != NULL)
            huff_code(r->left, str + "0");
        if (r->right != NULL)
            huff_code(r->right, str + "1");
    }
    vector<Node*> nod; // 结点集
    map<char, string> code; // 字符
};
int main()
{
    char ch[NUM];
    int fr[NUM], size;
    string code;

    int i, n, a[26];
    for (i = 0; i<26; i++)
        a[i] = 0;
    char str[100];
    gets_s(str);
    n = strlen(str);
    for (i = 0; i<n; i++)
        if (str[i] >= 'A'&&str[i] <= 'Z') a[str[i] - 'A']++;
        else if (str[i] >= 'a'&&str[i] <= 'z') a[str[i] - 'a']++;
        for (i = 0; i<26; i++)
            if (a[i])
            {
                printf("%c:%d\n", i + 'a', a[i]);
                ch[i] = i + 'a';
                fr[i] = a[i];
            }

    HuffmanCode huff_tree;
    huff_tree.buildTree(ch, fr, n);
    huff_tree.buildCode();
    for (int i = 0; i< n; ++i)
    {
        code = huff_tree.getCode(ch[i]);
        cout << ch[i] << ": " << code << endl;
    }
    return 0;
}
搜索更多相关主题的帖子: str Node int left size 
2018-07-04 22:54
快速回复:哈夫曼编码中遇到的小问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.013298 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved