求助,为什么用 new 来分配正确,用局部变量就错
用标准库优先队列实现实现哈夫曼树, 当优先队列里放指针时,结果正确,当直接放结点时错误,看了好久没发现原因,求教。是因为局部变量分配内存在栈上的原因吗?
优先队列放Hufcode:
cout<<(t.right)->left->freq<<endl; 应该输出的25
但是却输出45,
程序代码:
#include<iostream> #include<queue> #include<vector> using namespace std; class HufCode{ public: HufCode():key('0'),freq(0),left(NULL),right(NULL){ }; HufCode(char k,int f):key(k),freq(f),left(NULL),right(NULL){ } public: char key; int freq; HufCode* left; HufCode* right; }; class HufCodeSort{//函数对象, public: bool operator()(HufCode h1,HufCode h2){ return h1.freq>h2.freq; } }; void HuffMan(HufCode Q[],int n){ //利用标准库的 priority_queue 适配容器 typedef priority_queue<HufCode, vector< HufCode> , HufCodeSort > HuffTree; HuffTree Hf(Q, Q+n); // 初始化 for(int i=1;i!=n;++i){ HufCode Newcode; //这里用的是局部变量 HufCode t1=Hf.top(); Hf.pop(); Newcode.left=&(t1); //选出最小值 HufCode t2=Hf.top(); Hf.pop(); Newcode.right=&t2; //第二个最小值 cout<<t1.freq<<" "<<t2.freq<<endl; Newcode.freq=Newcode.left->freq+Newcode.right->freq; //两个最小值相加成为父节点的权值 Hf.push(Newcode); //插入 } HufCode t=Hf.top(); cout<<(t.right)->left->freq<<endl; } int main(){ char chu[]={'a', 'b', 'c', 'd', 'e', 'f'}; int freq[]={ 45, 13, 12, 16, 9, 5 }; int n=sizeof(chu)/sizeof(char); HufCode Q[n]; for(int i=0;i!=n;++i){ Q[i].key=chu[i]; Q[i].freq=freq[i]; } HuffMan(Q,n); return 0; }
优先队列放Hufcode* :
程序代码:
#include<iostream> #include<queue> #include<vector> using namespace std; class HufCode{ public: HufCode():key('0'),freq(0),left(NULL),right(NULL){ }; HufCode(char k,int f):key(k),freq(f),left(NULL),right(NULL){ } public: char key; int freq; HufCode* left; HufCode* right; }; class HufCodeSort{//函数对象, public: bool operator()(HufCode *h1,HufCode *h2){ return h1->freq >h2->freq; } }; void HuffMan(HufCode *Q[],int n){ //利用标准库的 priority_queue 适配容器 typedef priority_queue<HufCode*, vector< HufCode*> , HufCodeSort > HuffTree; HuffTree Hf(Q, Q+n); // 初始化 for(int i=1;i!=n;++i){ HufCode *Newcode=new HufCode; //这里用new Newcode->left=Hf.top(); //选出最小值 Hf.pop(); Newcode->right=Hf.top(); //第二个最小值 Hf.pop(); Newcode->freq=Newcode->left->freq+Newcode->right->freq; Hf.push(Newcode); //插入 } HufCode *t=Hf.top(); cout<<(t->right)->left->freq<<endl; } int main(){ char chu[]={'a', 'b', 'c', 'd', 'e', 'f'}; int freq[]={ 45, 13, 12, 16, 9, 5 }; int n=sizeof(chu)/sizeof(char); HufCode *Q[n]; for(int i=0;i!=n;++i){ Q[i]=new HufCode; Q[i]->key=chu[i]; Q[i]->freq=freq[i]; } HuffMan(Q,n); return 0; }
输出25正确
[ 本帖最后由 未未来 于 2014-11-3 20:15 编辑 ]