Определение параметра структуры с типом самой структуры

Я пытаюсь запустить алгоритм 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 {
             ^

Спасибо.


c c++ struct pointers forward-declaration
person kruspy    schedule 16.11.2015    source источник
comment
Вам нужно использовать указатель. Узел не может содержать другой объект узла, потому что сам этот узел будет содержать другой узел, который сам будет содержать другой узел, который сам будет содержать другой узел, который сам будет содержать другой узел, который сам будет содержать другой узел, который сам будет содержать другой узел. узел, который сам содержал бы другой узел, который сам содержал бы другой узел, который сам содержал бы другой узел, который сам содержал бы другой узел, который сам содержал бы другой узел, который сам содержал бы другой узел, и так далее.   -  person Neil Kirk    schedule 16.11.2015
comment
Если бы вы могли сделать это - иметь структуру, включающую саму себя - подумайте о том, как вы могли бы вычислить размер такой структуры и что это означает....   -  person Andrew Henle    schedule 16.11.2015
comment
Выберите один язык.   -  person Lightness Races in Orbit    schedule 16.11.2015

Ответы (2)


arrow_upward
1
arrow_downward

Это невозможно. Структура не может содержать экземпляр самой себя.

C++ (и C) имеют семантику значений. Возможно, вы используете ментальную модель другого языка, в которой parent означает ссылку на объект, хранящийся в другом месте.

Но в C++ node parent; означает объект с именем parent, который полностью хранится внутри внешнего объекта. Таким образом, ваш код приведет к бесконечной «глубине» объектов.

Судя по вашему описанию, вы, вероятно, имеете в виду ссылку на другой узел, который на самом деле хранится в другом месте. В C вы бы написали node *parent;, а затем были бы очень осторожны. В C++ у вас есть несколько вариантов, включая weak_ptr<node> parent; .

В обоих случаях ненавязчивый контейнер является еще одним вариантом (т. е. ваши узлы не содержат никаких ссылок на узлы, и у вас есть другая структура, которая содержит всю информацию о ссылках на узлы).

person M.M    schedule 16.11.2015

arrow_upward
0
arrow_downward

можно ли объявить элемент структуры с типом самой структуры?

No.

Вы не можете определить что-то в терминах самого себя.

Что, если бы автомобили всегда содержали в себе точную копию самих себя? Будет ли это работать? Нет! Это не подходит.

Насколько велика она будет? Размер автомобиля будет суммой размеров его колес, сидений, руля и, э-э, другой машины... с ее колесами, сиденьями, рулем и, э-э, еще одной машины... хм...

person Lightness Races in Orbit    schedule 16.11.2015