递归回溯C++，内存地址更改，损坏指针

Question

我目前正在研究一种用于迷宫生成的递归回溯方法。目前我正在努力从

GetNeighbours()

函数中获取正确的值。在函数内，它返回正确的坐标，但是，当在另一个函数中引用它们时

RecursiveBacktracking()

，这些点不再有效并且包含不正确的值。

我已经尝试调试这个有一段时间了，但似乎无法弄清楚。

任何关于其原因的解释都会非常有帮助！

他克斯

#include <vector>
#include <cstdlib>
#include <stdlib.h> 
#include <algorithm>
#include <ctime>
#include <random>
#include <stack>

class Node{
    public:
        std::vector<Node*> GetNeighbours(Node* baseNode, std::vector<std::vector<Node>> mazeVector){
                
                std::vector<Node*> neighbours;
                //Get south neighbour
                if(baseNode->ypos + 1 < mazeVector.size()){

                    if(!mazeVector.at(baseNode->ypos+1).at(baseNode->xpos).isVisited){
                        neighbours.push_back(&mazeVector.at(baseNode->ypos+1).at(baseNode->xpos));
                    }
                }
                //Get north neighbour
                if(baseNode->ypos - 1 >= 0){

                    if(!mazeVector.at(baseNode->ypos-1).at(baseNode->xpos).isVisited){
                        neighbours.push_back(&mazeVector.at(baseNode->ypos-1).at(baseNode->xpos));
                       // std::cout << neighbours[0]->ypos << ", " << neighbours[0]->xpos;
                    }
                }
                //Get east neighbour
                if(baseNode->xpos + 1 < mazeVector.at(baseNode->ypos).size()){

                    if(!mazeVector.at(baseNode->ypos).at(baseNode->xpos+1).isVisited){
                        neighbours.push_back(&mazeVector.at(baseNode->ypos).at(baseNode->xpos+1));
                       // std::cout << neighbours[0]->ypos << ", " << neighbours[0]->xpos;
                    }
                }
                if(baseNode->xpos -1 >= 0){

                    if(!mazeVector.at(baseNode->ypos).at(baseNode->xpos-1).isVisited){
                        neighbours.push_back(&mazeVector.at(baseNode->ypos).at(baseNode->xpos-1));
                        //std::cout << neighbours[0]->ypos << ", " << neighbours[0]->xpos;
                    }
                }

                std::random_device rd;
                std::mt19937 g(rd());

                std::shuffle(neighbours.begin(), neighbours.end(), g);

                // for(int i = 0; i < neighbours.size(); i++){
                //     std::cout << "Neighbours[" << i << "] before return = (" << neighbours[i]->ypos << ", " << neighbours[i]->xpos << ")" << std::endl;
                //     std::cout << "Memory Address [" << i << "] within function = " << neighbours[i] << std::endl;
                //     std::cout << "Memory Address [" << i << "]within maze = " << &mazeVector[neighbours[i]->ypos][neighbours[i]->xpos] << std::endl;
                // }
                return neighbours;

            }

        bool isVisited = false;
        int ypos;
        int xpos;
      /*  Node(int y, int x, bool visited = false){
            this->ypos = y;
            this-> xpos = x;
            this-> isVisited = visited;
        }
        */


        
};
void PrintMaze(std::vector<std::vector<Node>>& mazeVector){
    for(int i = 0; i < mazeVector.size(); i++){ 
        for (int j = 0; j < mazeVector[i].size(); j++)
        {
            Node* currentNode = &mazeVector.at(i).at(j);
            if(currentNode->isVisited){
                std::cout << 'X';
            }else{
                std::cout << '.';
            }
           // std::cout << &currentNode <<" = (" << currentNode->ypos << ", " << currentNode->xpos <<")";
            
           // std::cout << currentNode.GetNeighbours(currentNode, i, j, mazeVector).size();
        }
        std::cout<<std::endl;
        
    }

} 

void RecursiveBacktracking(std::vector<std::vector<Node>>& maze, int x, int y){
    _sleep(500);
    std::cout<<"------GENERATING------" << std::endl;
    
    std::vector<Node*> stack;
    stack.emplace_back(&maze[0][0]);
    Node* currentNode = stack[0];
    currentNode->isVisited = true;
    while(stack.size() > 0){
        _sleep(3000);
        PrintMaze(maze);
        
        currentNode->isVisited = true;
        std::vector<Node*> neighbours = currentNode->GetNeighbours(currentNode, maze);
        PrintMaze(maze);
        // for(int i = 0; i < neighbours.size(); i++){
        //             std::cout << "Neighbours[" << i << "] after return = (" << neighbours[i]->ypos << ", " << neighbours[i]->xpos  << ")" << std::endl;
        //             std::cout << "Neighbours[" << i << "] Memory after return = (" << neighbours[i] << std::endl;
        //         }
        if(neighbours.size() > 0){
            stack.emplace_back(neighbours[0]);
            std::cout << "Selected neighbour = (" <<  stack[stack.size()-1]->ypos << ", " << stack[stack.size()-1]->xpos << ")" << std::endl;
            //std::cout<< "Selected Neighbour Coords: " << currentNode-> ypos<< ", " << currentNode-> xpos<< std::endl;
            currentNode = stack[stack.size()-1];
        }else{
           
            stack.pop_back();
            currentNode = stack[stack.size()-1];

        }
        for (size_t i = 0; i < stack.size(); i++)
        {
           
            /* code */
        }
        
         std::cout<< "Size while in loop: "<<stack.size() << std::endl;
   }
   std::cout<<stack.size() << std::endl;

}


int main(){
    int length;
    int width;
    std::cout << "Please enter and length and width: " << std::endl;
    std::cin >> length >> width;
    std::cout << "Please enter a seed for maze generation or enter '0' for a random seed: " << std::endl;
    int seed;
    std::cin >> seed;
    if(seed == 0){
        std::srand((unsigned) time(NULL));
    }else{
    std::srand(seed);
    }

    std::vector<std::vector<Node>> mazeVector(length, std::vector<Node>(width));

    for(int i = 0; i < length; i++){
        for (int j = 0; j < width; j++)
        {
            Node currentNode;/* = Node(i, j); */
            currentNode.ypos = i;
            currentNode.xpos = j;
            mazeVector.at(i).at(j) = currentNode;
        }
    }

   PrintMaze(mazeVector);
   RecursiveBacktracking(mazeVector, 0, 0);

   



return 1; 
}

Answer 1

这是按值传递，这意味着

mazeVector

是本地副本。

std::vector<std::vector<Node>> mazeVector

然后在函数本身中，您正在执行以下操作：

neighbours.push_back(&mazeVector.at(baseNode->ypos).at(baseNode->xpos+1));

您将临时地址存储在

neighbors

中，然后最终返回

neighbors

。当函数返回时，

mazeVector

不再有效，因此所有这些地址都不再有效。