Создание связанного списка в C#

Question

В настоящее время я пишу алгоритм построения цепочки объектов в C#. Порядок расположения объекта очень важен, поскольку он представляет собой последовательность событий в определенном порядке. Объект A выполняет действие и содержит ссылку на объект B, который выполняет и действие, и так далее. Проблема в том, что начальное состояние объектов не имеет порядка. У меня есть словарь, содержащий каждый объект и имя следующего объекта в серии. То, с чем я борюсь, - это разработать быстрый алгоритм для их сортировки. Мое первоначальное предположение состоит в том, чтобы перебирать словарь и для каждого значения, искать ключ, который соответствует ему, и добавлять оба этих объекта в другой список. Есть несколько проблем: 1. Определение первого объекта в цепочке. 2. Очень высокая сложность при использовании вложенных циклов. 3. Определение того, какие объекты C# использовать для размещения цепочки объектов.

Я надеялся, что у кого-то есть опыт работы с алгоритмом сортировки, чтобы выполнить это или сделал что-то подобное. Все комментарии и помощь приветствуются, спасибо.

Answer 1

Ваш последний комментарий к вашему сообщению важен - тот факт, что существует несколько цепей работы. Это не сортировка; это упражнение построения графа.

У вас уже есть хэш, содержащий каждый объект и его преемник (-ы). Я предполагаю, что объект может иметь несколько преемников, а также может иметь несколько предшественников (просто чтобы быть достаточно общим). Создайте другой хэш с каждым объектом и его предшественником (ами), и из них вы можете легко показать любую диаграмму или дерево отношений, которые вы хотите.

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

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

EDIT: обратите внимание, что если вы хотите знать, какие задания являются оригинальными (у них нет предшественников) или терминалом (нет преемников), для создания полного экрана вам нужно будет отслеживать их отдельно, скажем, два массива под названием «Оригиналы и терминалы». Вы можете создавать терминалы по мере того, как вы перебираете исходный хеш преемников, чтобы создавать предшественников, и создавать оригиналы с одним окончательным проходом через Предшественников, находя записи, у которых нет предшественника. Но если вы просто хотите удовлетворить конкретные запросы об отдельных объектах, это должны сделать преемники и предшественники.