Реализация приоритетной очереди в C - PullRequest
7 голосов
/ 10 апреля 2010

Есть ли надежная и простая очередь с приоритетами (связанный список предпочтен, необязательный) для C?

В целом, какие стандартные библиотеки C вы используете?

Ответы [ 4 ]

6 голосов
/ 14 сентября 2014

PQLib (текущий принятый ответ) является неполным и функциональность не соответствует документации на момент публикации. Например, документация pq_dequeue сообщает, что возвращает запись. Реализация возвращает NULL. В коде есть много комментариев "TO DO", таких как "удалить узел, содержащий запись с наивысшим приоритетом, из своей кучи". Основная логика отсутствует.

Всем, кто ищет приоритетную очередь: я рекомендую найти код с хорошими проходными модульными тестами. Я не рекомендую PQLib, если он не обновлен и не содержит тестов.

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

5 голосов
/ 15 июня 2011

Исходный код , сопровождающий Роберт Седжвик Алгоритмы в C, части 1-4 (фундаментальные алгоритмы, структуры данных, сортировка, поиск) содержит оба реализация на основе кучи и на основе списка. См. Главу 9 - Приоритетные очереди и Heapsort.

3 голосов
/ 16 февраля 2011

У меня есть очередь с приоритетами, написанная на C, размещенная на коде Google. Лицензия MIT

https://code.google.com/p/pqueue-heap-c/source/browse/trunk/pqueue.cpp

Код использовался в нескольких проектах, поэтому он надежный, но я написал его в 98 году, поэтому не помню, как его использовать. Не вводите в заблуждение расширение cpp. Это прямо C.

0 голосов
/ 10 апреля 2010

Оформить PQLib .

Я использую стандартные стандартные библиотеки Си. ;)

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...