Как эффективно пройтись по дереву с несколькими типами? - PullRequest
Новая
       4

Как эффективно пройтись по дереву с несколькими типами?

1 голос
/ 15 октября 2011

Мы все знаем, что мы должны использовать список, deque или другой объект вместо того, чтобы использовать классический список ссылок, как я думаю, это как список ссылок.

У меня есть тип, который я будупозвоните в ABC.У меня есть доступ ко всему через ABC root.Тип ABC может содержать 0 или несколько букв ABC.Он также может содержать тип DE, FGH, D, E, F, G, H. DE также может содержать тип D и E. FGH может содержать FG, F, G, H. FG содержит ... Вы понимаете.Эти объекты также могут содержать 0 или многие из этого типа и его подтипов.

Проблема, с которой я сталкиваюсь, заключается в том, как написать это так, что если я нахожусь в типе F, я могу вызвать parent () и пройтиОбратно к корневому типу ABC?Давайте на самом деле забудем о типах FOR NOW и предположим, что все это тип BASE.Как бы я написал это дерево на C ++?Я думал о том, чтобы сделать что-то вроде этого 

class Base{
    deque<Base*> children
    Base*parent;
}

Но это было похоже на список ссылок.Главным образом потому, что прогулка по дереву - это просто просмотр указателя за указателем, а это именно то, что делает список ссылок, а прогулка по дереву - указатель после удаления указателей.Есть ли какой-нибудь эффективный способ держать деревья и ходить по ним?Мое приложение связано с процессором и памятью, поэтому я не уверен, какой компромисс я хочу сделать.Как мне хранить эти данные?

1 Ответ

1 голос
/ 15 октября 2011

Мы все знаем, что мы должны использовать список или другой объект вместо использования классический список ссылок

Эх, wot?

Связанные списки не имеют наибольшего использования evar, но когда вам нужно что-то наподобие того, что у вас есть, например DAG, другого способа сделать это практически не существует.

Просто используйте указатели.

...