哈夫曼编码中遇到的小问题
我以前写过一个计算哈夫曼编码的程序,是输入的字符和其出现次数,这次我要把他改成输入一连串字符串的形式,所以写了一个字符统计的功能,但是不知道为什么,出来的编码前面都是多一个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;
}