打印树信息时,树被垃圾值替换

Tree being replaced by junk values, when printing tree info

这是我在做的一个小项目中发现的一个问题,我不知道发生了什么,也不知道要搜索什么来修复它,所以我写了这个小程序来重现这个问题.我已经有几年没有使用 C++ 了,所以如果这是一个非常明显的问题,我深表歉意。

#include <iostream>
#include <vector>
using namespace std;
class Cell{
    int score;
    Cell* next_l;
    Cell* next_r;
    public:
    Cell(int s = 0, Cell *r = nullptr, Cell *l = nullptr){
        this -> score = s;
        this -> next_l = l;
        this -> next_r = r;
    }
    int getScore(){
        return this -> score;
    }
    void disp(){
        cout << "Score: " << this -> score << endl;  //Problem Line
        if(this -> next_r != nullptr){
            this -> next_r -> disp();
        }
        if(this -> next_l != nullptr){
            this -> next_l -> disp();
        }
    }
};
// returns a cell that's the head of a binary tree 
// formed by replacing last two cells in the vector
// with a Cell pointing to those two cells instead,
// and then calling this function on that new vector of cells.
Cell make_tree(vector<Cell> &cells){  
    if(cells.size() == 1){
        return cells[0];
    }else{
        Cell c1 = *(cells.end() - 1);
        cells.pop_back();
        Cell c2 = *(cells.end() - 1);
        cells.pop_back();
        Cell cell = Cell(c1.getScore() + c2.getScore(), &c1, &c2);
        cells.push_back(cell);
        return make_tree(cells);
    }
}
int main(){
    vector<Cell> cells;
    for(int i = 0; i < 3; i++){
        Cell *ptr{new Cell(i)};
        cells.push_back(*ptr);
    }
    Cell head = make_tree(cells);
    head.disp();
    return 0;
}

所以我标记为 //Problem Line 的行是我在调试时遇到的困惑。打印分数后,出于某种原因,一定深度后树中的所有值都被随机垃圾替换。这最终会导致分段错误。我不知道如何继续解决这个问题。

问题是您在这一行中使用了指向局部变量的指针:

  Cell cell = Cell(c1.getScore() + c2.getScore(), &c1, &c2);

成员 next_l 和 next_r 指向堆栈上的变量 c1c2,这是不正确的。这些值在函数终止时无效,并在之后进行其他函数调用时被覆盖。

尝试更改代码,以便将单元格放置在 vector<Cell*> cells 中。那么您的代码将如下所示:

Cell* make_tree(vector<Cell*> &cells) {  
   ...
   Cell* c1 = *(cells.end() - 1);
   cells.pop_back();
   Cell* c2 = *(cells.end() - 1);
   cells.pop_back();
   Cell* cell = new Cell(c1->getScore() + c2->getScore(), c1, c2);
   cells.push_back( cell );
   return make_tree( cells );
   ...
}

您必须在程序结束时删除生成的单元格 (delete head;),您还必须为 Cell 编写一个析构函数,以删除其左右子项。您可以通过使用共享指针 (std::shared_ptr) 而不是原始指针来避免这种情况:

  • std::shared_ptr<Cell> next_l, next_r
  • vector<std::shared_ptr<Cell>> cells;
  • std::shared_ptr<Cell> make_tree(vector<std::shared_ptr<Cell>> &cells)
  • std::shared_ptr<Cell> c1, c2
  • auto cell = std::make_shared<Cell>(c1->getScore() + c2->getScore(), c1, c2)

因为 std::make_shared 你还需要默认构造函数:

class Cell{
   ...
   Cell() = default;
   ...
};