C++ 指针和数据位置 : Data Always Being Placed at Same Memory Location

Question

我正在尝试用 C++ 实现迭代加深深度优先搜索算法。搜索成功找到问题的解决方案，但我无法将子节点链接回根节点。

struct Node
{
    std::vector<int> config;
    int depth;
    int action; //0 up 1 down 2 left 3 right
    Node * parent;
    bool operator<(const Node& rhs) const
    {
        return depth < rhs.depth;
    }
};

正如您在我的结构中看到的，我有一个指向父节点的指针。然而，在我的 DFS 代码中，我遇到了在循环的每次迭代中更新节点的父指针的问题。所有节点的父指针始终指向相同的数据位置 0xfffffffd2b0。换句话说，名为 Next 的新节点总是在这里创建。

我相信我在名为 Next 的代码中拥有的节点总是放置在同一数据位置，因此每个 Next 的引用位置始终相同。我怎样才能防止它总是出现在同一个位置？这意味着子节点没有链接到它们的父节点，而是链接到它们自己。我用星号标记了错误的来源。

 //IDDFS Logic:
int Current_Max_Depth = 0;
while(Current_Max_Depth < 20) 
{
    struct Node initial = {orig_config, 0, 0, NULL}; //config, depth, action, parent.
    visited.clear();
    priority_queue<Node> frontier;
    frontier.push(initial);
    while(frontier.size()>0)
    {
        struct Node Next = frontier.top();
        visited.push_back(Next.config);
        frontier.pop();
        if(Next.depth < Current_Max_Depth)
        {
            int pos_of_hole = Find_Position_of_Hole(Next.config);
            if(pos_of_hole==0) 
            {
                 std::vector<int> Down_Child = Move_Down(Next.config);
                 struct Node Down_Node = {Down_Child,Next.depth+1,1,&Next};  //****
                 if(!(std::find(visited.begin(), visited.end(), Down_Child)!=visited.end()))
                 {
                      if(Goal_Test(Down_Child))
                      {
                           goal_node = Down_Node;
                           goal_reached = true;
                           break;
                      }
                 frontier.push(Down_Node);
                 }

                std::vector<int> Right_Child = Move_Right(Next.config);
                struct Node Right_Node = {Right_Child,Next.depth+1,3,&Next}; //*******Passing next by reference here is not working since Next is always at the same data location.  The nodes one layer up from the leaf nodes end up all pointing to themselves.
                if(!(std::find(visited.begin(), visited.end(), Right_Child)!=visited.end()))
                {
                    if(Goal_Test(Right_Child))
                    {
                        goal_node = Right_Node;
                        goal_reached = true;
                        break;
                    }
                 frontier.push(Right_Node);
                 }      
         }
    if(pos_of_hole==1)
    ... does very similar for pos 1 through 8, not related to bug ...
        } //End of if(Next.Depth < Max_Depth)
} //End of while(frontier.size()>0)
if(goal_reached)
{
    break;
} 
Current_Max_Depth++;
}

Answer 1

struct Node initial = {orig_config, 0, 0, NULL};

在堆栈上创建一个节点。当你创建下一个 child 时

struct Node Down_Node = {Down_Child,Next.depth+1,1,&Next};

您正在获取该本地堆栈对象的地址。当循环结束时，Next 被销毁，然后在 while 循环的下一次迭代开始时再次构造它。如果节点需要保留，那么您需要使用 new 分配它们，然后在完成后使用 delete 分配它们。

请注意，C++ 中的变量声明不需要 struct 关键字。参见 Why does C need “struct” keyword and not C++?获取更多信息。