用C实现链表优先级队列
您将如何使用 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（按优先级以及顺序排序）添加而不是忽略优先级的标准先进先出方法）。
这是我所拥有的，但它没有优先级。您将如何实现优先级队列？
一种方法是使用排序/优先级算法。除了算法之外，对我来说，一些主要的未知/困惑是如何以及在何处存储优先级，它是否在实际元素内，例如：（
链接列表 | Head）----> (a | 1 | 下一个) ----> (b | 2 | 下一个) ----> Null
或
q_enqueue(&q, "a", "1");
q_enqueue(&q, "b", "2");
，在使用指针创建排序算法时，我将如何比较优先级。
How would you go about implementing a priority queue using a linked list in C?
The typical linked list consists of head pointing to an element which points to another element(s), which eventually ends by NULL or the linked list's tail. Example:
(Linked List | Head) ----> (Element | Next) ----> (Element | Next) ----> Null
In the basic scenario, new elements are added to the list by using the First-In First-Out (add to the end of the list, remove from the front of the list) FIFO approach.
In my case however, a priority value must be taken into consideration. More specifically, each element can be assigned priority of 1, 2 or 3. Elements with the highest priority are added towards the front of the list while those with lower priority are added towards the back. Insertions into the list maintain the FIFO order of each priority.
So, if one is to enqueue the following elements one at a time:
a 3, b 1, c 2, d 3, e 2
The output should be: a 3, d 3, c 2, e 2, b 1 (ordered by priority as well as the order of being added instead of the standard First-In First-Out approach which disregards the priority).
Here is what I have, but it DOES NOT feature priority. How would you go about implementing a priority queue?
One way would be to use a sorting/priority algorithm. Besides the algorithm, some of the major unknowns/confusion for me is how and where the priority would be stored, would it be within the actual element such as:
(Linked List | Head) ----> (a | 1 | Next) ----> (b | 2 | Next) ----> Null
or
q_enqueue(&q, "a", "1");
q_enqueue(&q, "b", "2");
and how would I go about comparing the priorities while working with the pointers to create the sorting algorithm.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果您只有三个优先级值（或者更一般地说 - 固定的优先级范围），为什么您不能实现三个单独的队列并编写一个包装函数，根据优先级将元素添加/删除到某个队列？
If you have only three values of priority (or in more general - fixed range of priorities) why can't you implement three separate queues and write a wrapper functions that depending on the priority add/remove the element to certain queue?
每当您在列表中添加/移动元素时，请使用排序算法根据优先级对列表中的元素重新排序。它可能会很慢，但它确实有效。
Whenever you add/move an element within the list, using a sorting algorithm to reorder the elements in the list based on their priority. It may be slow, but it works.
您应该考虑实现双链表。
基本上这就像一个简单的链表，但还有一个尾节点指向列表的末尾，并且列表中的每个元素都有一个在列表中向前和向后的指针。
因此高优先级节点被添加到前面，低优先级节点被添加到最后。对于这种数据结构，这两种操作都非常有效。
我不确定优先级 2 的节点添加到哪里:)
普通链表之上的开销应该可以忽略不计。
双向链表 - 维基百科
You should consider implementing a double linked list.
Basically this is like a simple linked list, but there is also a tail node that points to the end of the list, and every element in the list has a pointer forwards and backwards in the list.
So high priority nodes get added to the front,and low priority nodes get added to the end. Both these operations are very efficient with this data structure.
I am not sure where priority 2 nodes get added :)
The overhead above a normal linked list should be negligible.
Doubly linked list - Wikipedia