哪位高手来拯救小弟我？基于STL堆排序的哈弗曼编码出现异常，求指教

谁来拯救我？基于STL堆排序的哈弗曼编码出现错误，求指教
主程序中定义一个string 类，放几个字符，统计每个字符出现的次数，然后用STL的堆排序建立哈弗曼树，输出树的大小判断是否完成（不一定准确，只能保证已经建立预期数量的结点）。运行后发现，有时候是对的，比如那个string是“abc"但是如果是”abcde"就错了。求指教额，，，，我很烦恼，，，，很烦恼，谁来拯救我。！？

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <string>
#include <string.h>

using namespace std;

typedef struct //Designed by GX
{
    char Alpha='0';
    int Tax=-1;
    int PParent=-1;
    int PLChild=-1;
    int PRChild=-1;
}TNode;

typedef struct
{
    char code[26];
}CodeChart;  //用于存储某一个字符的编码


bool TNodeCmp(const TNode &Cmp1,const  TNode &Cmp2)  //GX
{
    return Cmp1.Tax>=Cmp2.Tax;
}

vector<TNode> BuildHaffmanTree(vector<TNode>ToHaff)//GX
{
    int Size=ToHaff.size();
    int HClk=(2*Size)-1;
    vector<TNode>::iterator Head=ToHaff.begin();
    int LChild=0;
    int RChild=1;
    while(Size<HClk)
    {
        make_heap(Head,ToHaff.end(),TNodeCmp);
        Head=Head+1;
        make_heap(Head,ToHaff.end(),TNodeCmp);
        Head=Head+1;
        TNode Father;
        Father.Tax=ToHaff[LChild].Tax+ToHaff[RChild].Tax;
        Father.PLChild=LChild;
        Father.PRChild=RChild;
        ToHaff.push_back(Father);
        vector<TNode>::iterator HeapHead=ToHaff.begin();
        ToHaff[RChild].PParent=Size;
        ToHaff[LChild].PParent=Size;
        LChild=LChild+2;
        RChild=RChild+2;
        Size=Size+1;
    }
    return ToHaff;
}



int Search(char x,vector<TNode> ForSearch)
{
    int i; 
 
    for(i=0;i<int(ForSearch.size());i++)
        if(ForSearch[i].Alpha==x)
            return i;
    return -1;
}
vector<TNode> Counting(string Input)
{
    int Len,Position,i;
    vector<TNode> ToRet;
    Len=Input.size();
    for(i=0;i<Len;i++)
    {
        Position=Search(Input[i],ToRet);
        if(Search(Input[i],ToRet)>=0)
        {
            ToRet[Position].Tax++;
        }
        else
        {
            TNode x;
            x.Alpha=Input[i];
            x.Tax=1;
            ToRet.push_back(x);
        }
    }
    return ToRet;

}
int main()
{
    string source("abcdefghijk");
    vector<TNode>Haff=Counting(source);
    cout<<"<<<<<<<"<<int(Haff.size());
    Haff=BuildHaffmanTree(Haff);
    cout<<"<<<<<<<"<<int(Haff.size());

    cout<<"Completed.";
    return 0;
}

编码 STL 堆排序 String
[解决办法]
看不出来你的代码是如何验证结果的正确性的，不过有两个地方需要修改：

循环中size=size+1之前加一句：
Head = ToHaff.begin() + LChild;
因为push_back之后Head中保存的迭代器可能已经失效了。

此外,TNodeCmp函数顺的>=最好改为>

查看更多 下一篇