реализовать приоритетную очередь связанного списка в C

Question

Как бы вы реализовали приоритетную очередь, используя связанный список в C?

Типичный связанный список состоит из head, указывающего на элемент, который указывает на другой элемент (ы), который в конце концов заканчиваетсяNULL или хвостом связанного списка.Пример:

(Linked List | Head) ----> (Element | Next) ----> (Element | Next) ----> Null

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

В моем случае, однако, значение приоритета должно быть принято во внимание.Более конкретно, каждому элементу может быть назначен приоритет 1, 2 или 3. Элементы с наивысшим приоритетом добавляются в начало списка, а элементы с более низким приоритетом добавляются в конец.Вставки в список поддерживают порядок FIFO каждого приоритета.

Итак, если нужно ставить в очередь следующие элементы по одному:

a 3, b 1, c 2, d 3, e 2

Выходные данные должны быть: a 3, d 3, c 2, e 2, b 1(упорядочено по приоритету, а также по порядку добавления вместо стандартного подхода «первым пришел - первым обслужен», который игнорирует приоритет).

Вот то, что у меня есть, но оно НЕ имеет приоритета.Как бы вы реализовали приоритетную очередь?

http://codepad.org/BMeuSgNBxd

Одним из способов было бы использование алгоритма сортировки / приоритета.Помимо алгоритма, некоторые из основных неизвестных / путаницы для меня - это то, как и где будет храниться приоритет, будет ли он находиться внутри фактического элемента, такого как:

(Linked List | Head) ---->(a | 1 | Next) ----> (b | 2 | Next) ----> Null

или

  q_enqueue(&q, "a", "1");
  q_enqueue(&q, "b", "2");

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

Answer 1

Если у вас есть только три значения приоритета (или в более общем - фиксированный диапазон приоритетов), почему вы не можете реализовать три отдельные очереди и написать функции-оболочки, которые в зависимости от приоритета добавляют / удаляют элемент в определенной очереди?

Answer 2

Вы должны рассмотреть возможность реализации двойного связанного списка.

По сути, это похоже на простой связанный список, но есть также хвостовой узел, указывающий на конец списка, и каждый элемент в списке имеет указатель вперед и назад в списке.

Таким образом, узлы с высоким приоритетом добавляются вперед, а узлы с низким приоритетом добавляются в конец. Обе эти операции очень эффективны с этой структурой данных.

Я не уверен, куда добавляются узлы с приоритетом 2:)

Издержки над обычным связанным списком должны быть незначительными.

Двусвязный список - Википедия

Answer 3

Каждый раз, когда вы добавляете / перемещаете элемент в списке, используйте алгоритм сортировки, чтобы изменить порядок элементов в списке на основе их приоритета.Это может быть медленно, но это работает.