Liu Zhian
2017-11-02 13:49
采纳率: 60%
浏览 1.2k

哈夫曼树构造过程中出现乱码?

程序是根据用户输入的一些列字符及其对应的权值,生成哈夫曼树,再根据生成的哈夫曼树进行编码,在测试时,发现输出每个元素对应的哈夫曼编码时,总会出现一些乱码的文字,知道原因的网友点拨一些,谢谢。程序如下:

 #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;
}
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • Carrie_zzz 2017-11-02 23:28
    已采纳

    在动态创建的过程中,总是出现未利用的空间出现乱码。通过专门建立一个变量来统计用到的数组长度,可以解决了这个问题。

    打赏 评论
  • Liu Zhian 2017-11-03 05:39

    正如楼上所言,我在每次保存编码时固定了一个char【50】的数组(也许这么干肯定不是最好的解决办法),算法功能已经实现。

    打赏 评论
  • 七七不是七七七七 2017-11-03 06:51

    同受教了,谢谢楼上。

    打赏 评论