注册 登录
编程论坛 → C++教室

求助，为什么用 new 来分配正确，用局部变量就错

未未来 发布于 2014-11-03 20:13， 531 次点击
用标准库优先队列实现实现哈夫曼树， 当优先队列里放指针时，结果正确，当直接放结点时错误，看了好久没发现原因，求教。
是因为局部变量分配内存在栈上的原因吗?

优先队列放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 编辑 ]
4 回复
#2
沱游星空2014-11-03 21:01
用局部变量本身并没有错，真正报错是因为定义了一个没有指明大小的数组！将n用常数代替时就可以运行了即定义时用HufCode Q[100];
#3
未未来2014-11-04 10:31
回复 2 楼 沱游星空
我改了还是不对丫
#4
沱游星空2014-11-04 15:16
我认为  
1.这个与for循环有关，你在for循环内创建的对象名字相同，在第一次循环后，对象内存被分配，之后的每次均对这一片内存即这一个对象进行操作，因此会出现这种问题。
2.如果不用for循环，而是直接建立5个对象，结果输出不会错！！！
验证1的代码如下：
#include "stdafx.h"
#include "iostream"
using namespace std;
class A
{
public:
    A(int x){xx=x;}
    int xx;
    void output(){cout<<xx<<endl;}
};
void main()
{
    int i;
    A *pa=NULL;
    for (i=0;i<3;i++)
    {
        
        A a(i);
        if (0==i)
        {
            pa=&a;
        }
        a.output();
        pa->output();   
    }
}
#5
未未来2014-11-04 18:31
回复 4 楼 沱游星空
哈哈，c的代码我看得不是很懂，，，，但是你说的是正确的 我自己验证了。我创建了一个大的数组来存放，就正确了，所以我还是觉得指针是个好东西，虽然比较容易出错。
程序代码：
#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;
};

int result[100];
void printTree(HufCode* Q,int counts){ //网上 看来的，，自己想不到呀
    if(Q->key!='0'){
        cout<<Q->key<<"  "<<Q->freq<<"  ";
        for(int i=0;i!=counts;++i){
            cout<<result[i];
        }
        cout<<endl;
    }

    if(Q->left!=NULL){
    result[counts]=0;
    printTree(Q->left,counts+1);}
    if(Q->right!=NULL){
    result[counts]=1;
    printTree(Q->right,counts+1);
    }

}




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);  // 初始化

HufCode Newcode[100]; //创建了一个数组来存储。

    int mm=1;
for(int i=1;i!=n;++i){

    Newcode[mm]=Hf.top();

    Hf.pop();
    Newcode[mm+2].left=&(Newcode[mm]); //选出最小值


  Newcode[mm+1]=Hf.top();

     Hf.pop();
    Newcode[mm+2].right=&(Newcode[mm+1]); //第二个最小值


 Newcode[mm+2].freq= Newcode[mm+2].left->freq+ Newcode[mm+2].right->freq;
    Hf.push( Newcode[mm+2]); //插入

  mm+=3;
}

HufCode t=Hf.top();

cout<<(t.right)->left->freq<<endl;

printTree(&t,0);
}



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[111];

for(int i=0;i!=n;++i){
    Q[i].key=chu[i];
    Q[i].freq=freq[i];
}

HuffMan(Q,n);
return 0;

}
1
©2025, BC-CN.NET
电脑版