如何在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 (按优先级和添加顺序排序,而不是忽略优先级的标准先入先出方法)。
这就是我所拥有的,但它并不具有优先级。您将如何实现优先级队列?
一种方法是使用排序/优先级算法。除了算法之外,对我来说,一些主要的未知/混乱是如何以及在哪里存储优先级,它是否在实际元素中,例如:
(链表|头)-> (a |1|下一步)-> (b |2|下一步)->空
或
q_enqueue(&q, "a", "1");
q_enqueue(&q, "b", "2");在使用指针创建排序算法时,如何比较优先级。
发布于 2011-09-12 14:11:19
如果您只有三个优先级值(或者在更一般的固定优先级范围内),为什么不能实现三个单独的队列,并编写一个包装器函数,根据优先级向特定队列添加/删除元素?
发布于 2011-09-12 13:55:51
无论何时在列表中添加/移动元素,都会使用排序算法根据元素的优先级对列表中的元素进行重新排序。它可能很慢,但它是有效的。
发布于 2011-09-12 14:03:33
您应该考虑实现一个双向链表。
这基本上类似于一个简单的链表,但也有一个指向列表末尾的尾节点,列表中的每个元素在列表中都有一个向前和向后的指针。
因此,高优先级节点被添加到前端,低优先级节点被添加到末尾。对于这种数据结构,这两种操作都非常有效。
我不确定在哪里添加了优先级2节点:)
正常链表之上的开销应该可以忽略不计。
https://stackoverflow.com/questions/7383747
复制相似问题