程序是根据用户输入的一些列字符及其对应的权值,生成哈夫曼树,再根据生成的哈夫曼树进行编码,在测试时,发现输出每个元素对应的哈夫曼编码时,总会出现一些乱码的文字,知道原因的网友点拨一些,谢谢。程序如下:
#include <iostream>
#include<string>
using namespace std;
class HuffNode
{
public:
char c; // 结点的字符
int weight; // 权值
int parent, lChild, rChild; // 左右孩子指针
};
class HuffTree
{
private:
int Node_cnt=0;
HuffNode* huff=NULL;
string* HuffCode = NULL;
public:
HuffTree(int n, char* c, int* weights); // 创建Huffman树
~HuffTree(); // 析构函数
void setNode_cnt(int cnt){ Node_cnt = cnt; }
void select(int end, int& index1, int& index2); // 选出最小和次小叶子结点
void printHuffTree();
void setHuffCode();
void printHuffCode();
};
HuffTree::~HuffTree()
{
delete[] huff;
delete[] HuffCode;
}
void HuffTree::printHuffCode()
{
for (int i = 0; i < Node_cnt; i++)
{
cout << huff[i].c << "的哈夫曼编码为:" << HuffCode[i] << endl;
}
}
void HuffTree::setHuffCode() // 左孩子为0,右孩子为1
{
HuffCode = new string[Node_cnt];
for (int i = 0; i < Node_cnt; i++)
{
int son, father; // 孩子指针和双亲指针
int cnt = 0;
string str;
son = i;
father = huff[son].parent;
while (father != -1)
{
if (huff[father].lChild == son)
{
str.append("0");
}
else
{
str.append("1");
}
son = father; // 孩子指针为当前双亲指针
father = huff[father].parent; // 双亲指针为当前双亲指针的双亲
}
HuffCode[i] = new char[str.size()];
for (unsigned int j = 0; j < str.size(); j++) // 由于求哈夫曼编码时是从叶子结点一直找到树根,故编码为之前的逆序
{
HuffCode[i][j] = str[str.size() - 1-j];// 逆序
}
}
}
HuffTree::HuffTree(int n,char* ch,int* weights){
Node_cnt = n;
huff = new HuffNode[2 * Node_cnt - 1];
for (int i = 0; i < Node_cnt; i++) // 初始化
{
huff[i].c = ch[i];
huff[i].weight = weights[i];
huff[i].lChild = -1;
huff[i].rChild = -1;
huff[i].parent = -1;
}
for (int i = Node_cnt; i < Node_cnt * 2 - 1; i++)
{
int index1 = -1, index2 = -1;
select(i - 1, index1, index2);// 选出最小和次小中间树结点索引
huff[index1].parent = i;
huff[index2].parent = i;
huff[i].weight = huff[index1].weight + huff[index2].weight;
huff[i].lChild = index1;
huff[i].rChild = index2;
huff[i].parent = -1;
}
}
void HuffTree::printHuffTree()
{
cout << "所建哈夫曼静态链表示如下:" << endl;
cout << "位置\t" << "字符\t" << "权值\t" << "双亲\t" << "左孩子\t" << "右孩子\t" << endl;
for (int i = 0; i < Node_cnt*2-1; i++)
{
cout << i << "\t" << huff[i].c << "\t" << huff[i].weight << "\t" << huff[i].parent << "\t" << huff[i].lChild << "\t" << huff[i].rChild << endl;
}
}
void HuffTree::select(int end, int& index1, int& index2)
{
int min1=100000,min2 = 100000; // 设m1为最小值,m2为次小值
for (int j = 0; j <=end; j++)
{
if (huff[j].parent == -1)
{
if (huff[j].weight < min1) // 如果当前权值比最小值小
{
index2 = index1;
index1 = j;
min2 = min1;
min1 = huff[j].weight;
}
else if (huff[j].weight < min2) // 如果当前权值比次小值小
{
min2 = huff[j].weight;
index2 = j;
}
}
}
}
int main()
{
int n;
cout << "请输入树叶结点的个数(小于等于1结束):" << endl;
cin >> n;
if (n < 1) return 0;
char chs[256];
int weights[256];
for (int i = 0; i < n; i++){
cout << "请输入第" << i+1 << "个字符及权值" << endl;
cin >> chs[i] >> weights[i];
}
HuffTree tree(n,chs,weights);
tree.printHuffTree();
tree.setHuffCode();
tree.printHuffCode();
return 0;
}