Циклическая проблема с зависимостями LinkedList

Введение в проблему: я делаю программу для отслеживания маршрутов полетов в аэропортах с использованием связанных списков. Например, если набор данных

(Austin - Dallas, Dallas - Houston)

и вы пытаетесь найти рейс

(Austin - Houston)

он рассчитает, что вам нужно выбрать маршрут полета:

(Austin - Dallas - Houston)

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

struct OuterNode {
    InnerList flights;
    int name;
    OuterNode* next;
};

struct InnerNode {
    OuterNode* dest;
    int price;
    InnerNode* next;
};
class InnerList
{
public:
    InnerList();
    ~InnerList();
    void add(InnerNode*);
private:
    InnerNode* innerhead;
};

Итак, в основном:

OuterNode – требуется InnerList (пока нет определения)

InnerNode – нуждается OuterNode

InnerList – нуждается InnerNode

И в настоящее время ошибка заключается в том, что InnerList не существует, когда OuterNode нужно его создать. Как я могу это исправить, чтобы все нашло то, что ему нужно? Есть ли какое-то творческое использование шаблонов или что-то, что я мог бы использовать, чтобы исправить это?


c++ nodes circular-dependency linked-list
person Jd Francis    schedule 10.11.2014    source источник

Ответы (2)


arrow_upward
0
arrow_downward

"Могу ли я использовать какие-то творческие шаблоны или что-то, что можно исправить?"

Нет необходимости в использовании шаблонов, вы можете просто немного реструктурировать свой код и ввести предварительное объявление для struct InnerNode;

struct InnerNode;  // << forward declaration 

// Declare class InnerList first
class InnerList {
public:
    InnerList();
    ~InnerList();
    void add(InnerNode*);
private:
    InnerNode* innerhead;
};

struct OuterNode {
    InnerList flights;
    int name;
    OuterNode* next;
};

// Finally declare InnerNode completely
struct InnerNode {
    OuterNode* dest;
    int price;
    InnerNode* next;
};

РЕАЛЬНАЯ ДЕМО

ВНИМАНИЕ:

Вместо создания собственной структуры связанного списка вы также можете использовать std::list<InnerNode*> flights; или даже элемент std::vector<InnerNode*> flights; в вашей структуре OuterNode.
Хотя эти решения должны правильно обрабатывать экземпляры InnerNode с помощью управления памятью, std::list<std::shared_ptr<InnerNode>> или std::vector<std::shared_ptr<InnerNode>> выглядит правильным путем.

person πάντα ῥεῖ    schedule 10.11.2014

arrow_upward
0
arrow_downward

Вам нужно использовать предварительные объявления.

Когда компилятору нужно только знать, что тип существует, но ему не нужно ничего знать о его определении (как в случае, когда вы объявляете указатель), вы можете использовать предварительное объявление, чтобы сообщить компилятору «тип с это имя существует':

class InnerNode;
class InnerList
{
public:
    InnerList();
    ~InnerList();
    void add(InnerNode*);
private:
    InnerNode* innerhead;
};

Это скомпилируется, потому что InnerList не нужно ничего знать о InnerNode; ему просто нужно знать, что тип с именем InnerNode существует.

Если у вас есть фактический экземпляр типа в вашем классе, как в случае с OuterNode, предварительное объявление не будет работать. Класс должен знать, сколько памяти выделить для типа, поэтому ему требуется полное определение.

Вы можете использовать предварительные объявления для компиляции InnerList и InnerNode, но вам нужно переместить определение OuterNode после InnerList, так как оно зависит от его определения.

person Collin Dauphinee    schedule 10.11.2014