Я не знаю многого о топологическом роде, но я думаю, что знаю достаточно, чтобы оставить разумный комментарий. Любой человек должен отредактировать этот ответ.
Я вижу несколько вопросов с этой реализацией. Некоторые связаны с C, другие связаны с алгоритмом, поэтому позвольте мне пройти через них по одному.
Определение проблемы. Topological sort действительно определяется как приоритет элементов в ориентированном графе. Однако это предложение само по себе не определяет проблему полностью. В частности, топологическая сортировка является приоритетом элементов графа , начиная с заданной вершины источника. В качестве примера предположим, что следующий ориентированный граф:
a -> b
b -> c
c -> a
Если вы начинаете с вершины a, ваша топологическое упорядочение должно быть {a, b, c}. Если вы начинаете с вершины c, ваш топологический заказ должен быть {c, a, b}. Поэтому определение проблемы не имеет смысла без исходной вершины. Одним из вариантов для такой вершины может быть некоторая вершина графа, которая не имеет кромки, указывающей на нее, т. Е. Каждое падающее ребро является исходящим ребром.
Еще одна вещь, которую следует иметь в виду - это график connectedness. Не всегда можно добраться до любой вершины из любой другой вершины. Поэтому при реализации таких алгоритмов стоит иметь в виду.
Хорошие структуры данных являются ключом к хорошим алгоритмам. Если вы хотите отсортировать объекты в ориентированном графике, лучше всего создать структуру данных ориентированного графа, которая сама будет включать создание структуры данных Node и структуры данных Edge. Предлагаю посмотреть adjacency lists. Как только у вас будет такая структура данных, на графике будет работать breadth first search, и вы получите свой топологический приоритет как аккуратное следствие.
При реализации списка смежности вам все равно нужно хранить все свои элементы в одном месте. Связанный список, как правило, не лучший способ сделать это, потому что требуется постоянное время для вставки в одно (при условии сортировки по данным), для поиска по нему требуется линейное время. Это путь неоптимальный. Как и @David RF, Red-Black trees и AVL trees - это путь. Однако я бы не стал с этой оптимизации. До тех пор, пока у вас есть алгоритм обработки звука, вы всегда можете улучшить структуру данных хранилища. В конце концов, интерфейс для связанных списков и деревьев поиска одинаковый.
Алгоритм может быть быстрым, учитывая, что вы используете правильный алгоритм. На практике я не занимался топологическими сортами, поэтому я не знаю всех сложностей и каждого случая кромки. Но! Если вы сделаете это с широким первым поиском, используя обычные структуры данных с узкими краями (обратите внимание, что ребра могут быть неявно определены в узлах), ваш поиск сам по себе должен взять линейное время, используя поиск по ширине.
Я прочитал ваш алгоритм, и я должен признать, что я не совсем понимаю вашу концепцию большого списка и небольшого списка. Неоднозначные имена действительно не помогают. Возможно, это работает с одной крошечной ошибкой, где-то скрывается, но она не слишком читаема. Возможно, кто-то еще может прокомментировать вашу текущую реализацию.
Вы должны прочитать о [минимальных рабочих примерах] (http://www.minimalbeispiel.de/mini-en.html) и взять то, что вы читаете близко к сердцу. Отправьте свой код _entire_ здесь и ожидайте, что кто-то прочитает его, поймет его, а затем скажет вам, что не так, на самом деле это не тот сайт. – Richard
спасибо. Я буду держать это в виду. – user1476263
Спасибо, @ user1476263. Существует ли ряд возможных возможностей для вашей проблемы? Работа с числами может быть намного проще, чем буквы или строки. Поэтому, если у вас есть 'a-z' в качестве ввода, я бы конвертировал его в' 0-25'. – Richard