c++ - 使用结构本身的类型定义结构参数

Question

我正在尝试将 BFS 算法启动到矩阵中，以获取从我的位置到 BFS 找到的第一个可访问元素的最短路径。矩阵由定义如下的节点组成:

    struct node {
    int distance = -1;
    node parent;
    Pos position;
    //Direction to get into the actual node from the parent's position.
    Dir direction;
    Cell cell;
 };

我需要有一个父节点的实例(之前访问过的那个，并且到初始节点的距离小于实际节点的距离)，以便在找到所需项目后追踪最快的路径回到原始节点。但是似乎 node parent; 声明会抛出错误，所以可以用结构本身的类型声明结构的元素吗？还是必须将其声明为指向元素的指针？

这里有错误:

error: field has incomplete type 'node' 
       node parent;
            ^
note: definition of 'node' is not complete until the closing '} 
      struct node {
             ^

谢谢。

Answer 1

这是不可能的。结构不能包含其自身的实例。

C++(和 C)具有值语义。也许您正在使用另一种语言的心智模型，其中 parent将意味着对存储在别处的对象的引用。

但是在 C++ 中，node parent;表示一个名为 parent 的对象它完全存储在外部对象中。因此，您的代码将导致无限“深度”的对象。

根据您的描述，您的意思可能是引用另一个实际存储在别处的节点。在 C 中你会写 node *parent; ，然后非常小心。在 C++ 中，您有几个选项，包括 weak_ptr<node> parent; .

在这两种语言的情况下，非侵入式容器是另一种选择(即您的节点不包含任何节点引用；并且您有另一个结构来保存有关节点链接的所有信息)。