小弟我写的建哈夫曼的程序，帮小弟我看下错哪了呢

我写的建哈夫曼的程序，帮我看下哪里错了呢
我的程序采用STL里的vector，动态存储树的节点（结构体），建树过程中采取了堆排序的办法来寻找权值最小的两个节点，找到后建立他们的父亲节点。但是运行的时候出现了段错误。这是为什么呢？

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct
{
    char Alpha='0';
    int Tax=65535;
    int PointerParent=65535;
    int PointerLChild=65535;
    int PointerRChild=65535;
}TNode;

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

vector<TNode> MakeHaff(vector<TNode>ToHaff,int AlphaSize)
{
    vector<TNode>::iterator HeapHead=ToHaff.begin();
    int LChild=0;
    int RChild=1;
    while(HeapHead!=ToHaff.end())
    {
        make_heap(HeapHead,ToHaff.end(),TNodeCmp);
        HeapHead++;
        make_heap(HeapHead,ToHaff.end(),TNodeCmp);
        HeapHead++;
        TNode newFather;
        newFather.Tax=ToHaff[LChild].Tax+ToHaff[RChild].Tax;
        newFather.PointerLChild=LChild;
        newFather.PointerRChild=RChild;
        ToHaff.push_back(newFather);
        ToHaff[RChild].PointerParent=AlphaSize+1;
        ToHaff[LChild].PointerParent=AlphaSize+1;
        LChild=LChild+2;
        RChild=RChild+2;
        AlphaSize=AlphaSize+1;
        vector<TNode>::iterator displayP=ToHaff.end();
        TNode DNode=*displayP;
        cout<<DNode.Tax<<" ";
    }
    return ToHaff;
}


int main()
{
    vector<TNode> Al;
    TNode a1;
    a1.Tax=2;
    TNode a2;
    a2.Tax=1;
    TNode a3;
    a3.Tax=100;
    Al.push_back(a1);
    Al.push_back(a2);
    Al.push_back(a3);
    int i=0;
    while(i<5)
    {
        cout<<Al[i].Tax<<" ";
        i++;
    }
    cout<<endl;
    Al=MakeHaff(Al,3);
    i=0;
    while(i<5)
    {
        cout<<"Result:";
        cout<<Al[i].Tax<<" ";
        i++;
    }
    cout<<endl;

    return 0; 
 
}

STL 堆排序 哈夫曼树
[解决办法]
还有43-45行：

        vector<TNode>::iterator displayP=ToHaff.end();
        TNode DNode=*displayP;
        cout<<DNode.Tax<<" ";

ToHaff.end()是不能问的，它的含义是“最后一个元素的后一个位置”。如果你是想要输出最后一个元素，应该：

  cout << ToHaff.back().Tax << " ";

还有第37行：

    ToHaff.push_back(newFather);

这句话执行之后，所有老的迭代器都有可能会失效，但你依然再使用HeapHead，也会出问题，解决方法就是改用整数索引代替迭代器，或者换一个push_back不影响老迭代器使用的容器。

查看更多 下一篇