C语言中的优先队列实现

Question

C语言中的优先队列实现

c

6

有没有可靠且简单的优先队列（最好是链表，但不是必须）C语言实现？

更一般地说，你使用哪些C标准库？

- Yuval Adam

1

你说的“什么标准库”是什么意思？ - WhirlWind

2

我喜欢在二项堆的基础上实现我的优先队列。 - Heath Hunnicutt

4个回答

5

Robert Sedgewick的C语言算法基础：数据结构、排序、搜索（第1-4部分）附带的源代码包含基于堆和基于列表的实现。请参阅第9章-优先队列和堆排序。

- AShelly

3

我有一个使用C语言编写的优先队列，托管在Google Code上。采用MIT许可证。 https://code.google.com/p/pqueue-heap-c/source/browse/trunk/pqueue.cpp 这段代码已经被用在几个项目中，所以它是稳定的，但我是在'98年编写的，所以我不记得如何使用它了。不要被cpp扩展名误导，它是纯C代码。

- justinhj

有哪些项目使用了你的代码？感谢你的制作和分享！ - Darakian

不客气，@Darakian。我在90年代末的某个视频游戏中使用了这个路径查找代码。 - justinhj

你不能分享哪个游戏呢？ - Darakian

这段代码或者类似的版本被用在Playstation游戏《蝙蝠侠和罗宾》中，我也在A*算法实现中使用过它，但后来我将其重写为C++并使用STL内置的优先队列。 - justinhj

-2

请查看PQLib。

我使用标准的C标准库。 ;)

- WhirlWind

12

请务必非常仔细地阅读PQLib中的LICENSE文件。它重新引入了一种全新的广告条款（甚至比原始的BSD广告条款更糟），并且与GPL/LGPL（所有版本）不兼容。基本上，您无法合法地链接glibc和PQLib并分发最终产品。该库显然不是开源的，更不是自由软件。 - Tim Post

1

@Tim 我没意识到...它写着BSD，但他们一定是指特殊的BSD。+1 - WhirlWind

1

请勿使用PQLIB。它不完整且无法正常工作。 - Mark

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dsh · Accepted Answer

PQLib（当前接受的答案）不完整，功能与此帖子发布时的文档不匹配。例如，pq_dequeue文档说它返回一个值，但实现返回NULL。代码中有许多“待办事项”注释，例如“从其堆中删除包含最高优先级条目的节点”。关键逻辑缺失。

对于任何寻找优先队列的人：我建议找到一些拥有良好的、通过单元测试的代码。我不建议使用PQLib，除非它更新并包含测试。

对于PQLib的所有者或任何推荐它的人：我认为这段代码已经完成，并花费了相当长的时间进行调试，直到我意识到它没有完成，这很令人沮丧。请不要推荐你没有尝试过或知道是正在进行的工作的代码。