首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >用C++实现链表优先级队列

问用C++实现链表优先级队列
EN

Stack Overflow用户
提问于 2011-09-12 13:45:47
回答 3查看 3.8K关注 0票数 1

如何在C中使用链表实现优先级队列?

典型的链表由指向一个元素的head组成,该元素指向另一个元素,该元素最终以NULL或链表的尾部结束。示例:

代码语言:javascript
复制
(Linked List | Head) ----> (Element | Next) ----> (Element | Next) ----> Null

在基本场景中,通过使用先进先出(添加到列表末尾,从列表前面删除) FIFO方法将新元素添加到列表中。

然而,在我的例子中,必须考虑优先级值。更具体地说,可以为每个元素分配优先级1、2或3。优先级最高的元素被添加到列表的前面,而优先级较低的元素被添加到列表的后面。列表中的插入操作会保持每个优先级的FIFO顺序。

因此,如果要将以下元素一次排入一个队列:

代码语言:javascript
复制
a 3, b 1, c 2, d 3, e 2

输出应该是:a 3, d 3, c 2, e 2, b 1 (按优先级和添加顺序排序,而不是忽略优先级的标准先入先出方法)。

这就是我所拥有的,但它并不具有优先级。您将如何实现优先级队列?

http://codepad.org/BMeuSgNBxd

一种方法是使用排序/优先级算法。除了算法之外,对我来说,一些主要的未知/混乱是如何以及在哪里存储优先级,它是否在实际元素中,例如:

(链表|头)-> (a |1|下一步)-> (b |2|下一步)->空

或

代码语言:javascript
复制
  q_enqueue(&q, "a", "1");
  q_enqueue(&q, "b", "2");

在使用指针创建排序算法时,如何比较优先级。

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2011-09-12 14:11:19

如果您只有三个优先级值(或者在更一般的固定优先级范围内),为什么不能实现三个单独的队列,并编写一个包装器函数,根据优先级向特定队列添加/删除元素?

票数 6
EN

Stack Overflow用户

发布于 2011-09-12 13:55:51

无论何时在列表中添加/移动元素,都会使用排序算法根据元素的优先级对列表中的元素进行重新排序。它可能很慢,但它是有效的。

票数 0
EN

Stack Overflow用户

发布于 2011-09-12 14:03:33

您应该考虑实现一个双向链表。

这基本上类似于一个简单的链表,但也有一个指向列表末尾的尾节点,列表中的每个元素在列表中都有一个向前和向后的指针。

因此,高优先级节点被添加到前端,低优先级节点被添加到末尾。对于这种数据结构,这两种操作都非常有效。

我不确定在哪里添加了优先级2节点:)

正常链表之上的开销应该可以忽略不计。

Doubly linked list - Wikipedia

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/7383747

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档