在C中实现链接列表优先级队列(implement a Linked List Priority Queue in 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 （按照优先顺序排列，以及添加的顺序，而不是标准先进先出方法，不考虑优先级）。 
 
 这是我所拥有的，但它不具备优先权。 你将如何去实施优先队列？ 
 
 http://codepad.org/BMeuSgNBxd 
 
 一种方法是使用排序/优先级算法。 除了算法之外，对于我来说，一些主要的未知/困惑是如何以及在哪里存储优先级，它是否在实际元素内，例如： 
 
 （Linked List | Head）---->（a | 1 | Next）---->（b | 2 | Next）---->空 
 
 要么 
 
  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?
 
http://codepad.org/BMeuSgNBxd
 
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.

原文：https://stackoverflow.com/questions/7383747