读书人

小弟我写的建哈夫曼的程序帮小弟我看

发布时间: 2013-07-04 11:45:33 作者: rapoo

我写的建哈夫曼的程序,帮我看下哪里错了呢
我的程序采用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不影响老迭代器使用的容器。

读书人网 >C++

热点推荐