如何在C语言编程中实现优先队列

Question

我需要在C编程中使用单链表实现优先级队列。

我不清楚什么是优先队列。我用谷歌搜索了一下，但不完全明白我找到了什么。我的理解是，优先队列是其元素按优先级排序的队列。插入到列表中的元素根据元素的优先级在列表中定位。

假设，我们有以下场景。(注意:我认为，更高的值具有更高的优先级):

Element-->2 (priority=2)  (Now in position 0)

如果需要插入另一个元素，例如具有更高优先级的Element-->3 (priority=3)。

我可以移动前一个元素Element-->2 (priority=2)，并将这个新的Element-->3 (priority=3)插入到位置0,Element-->2 (priority=2)移动到列表中的位置1。

现在列表变成

Element-->3 (priority=3) followed by Element-->2 (priority=2)

同样，在插入的基础上，我是否必须移动列表中的所有元素?

正确吗?

Answer 1

你不需要"移位"列表，相反，当你插入时，你做这样的事情(伪代码):

if new_node.priority > list.head.priority:
    new_node.next = list.head
    list.head = new_node
else:
    previous = null
    for current = list.head:
        if current.priority < node.priority:
            previous.next = node
            node.next = current
            break loop
        previous = current

如果你的列表有一个指向结束的指针，你可以添加一个特殊的检查优先级低于结束

Answer 2

我认为你遇到了麻烦，因为优先级队列应该用堆树来实现，而不是一个单一的链表。

堆让一切变得简单——所有的操作都非常便宜:在堆中更新、删除和插入都是O(log n)。

Answer 3

您可以使用优先级队列。但是…

链表不是一个简单的数组。

链表中的每一项都有对下一项的引用。您可以通过更改这两个项的引用来在另一个项之后插入一个项。

+--------+
| item A |                           +--------+
+--------+     +--------+            | item C |
|ref to B|---->| item B |            +--------+
+--------+     +--------+            |  NULL  |
               |  NULL  |            +--------+
               +--------+

在A和B之间插入C通过:

1. 用ref to B改变C中的NULL
2. 通过ref to C改变A中的ref to B

Answer 4

优先级队列是一种抽象数据类型，它基本上按照所选键的排序顺序(升序或降序)保存其中的项。正如Anthony Blake所提到的，堆实现是最直接的，你使用的底层结构只是一个数组，你执行一些以数组索引为中心的操作。

如果出于某种原因您想使用单链表实现，下面是一个演示代码，以就地方式执行排序插入:

void sortedInsert(struct node **headRef,int data){
struct node *newnode=(struct node *)malloc(sizeof(struct node));
assert(newnode);
newnode->value=data;
newnode->next=NULL;
if(!(*headRef) || data<(*headRef)->value){
    newnode->next=*headRef;
    *headRef=newnode;
}else{
    struct node *prev=*headRef;
    while(prev->next && prev->next->value<data)
        prev=prev->next;
    struct node *temp=prev->next;
    prev->next=newnode;
    newnode->next=temp;
}

}

Answer 5

好吧，我不知道为什么在C中需要它。在c++ STL中它是可用的。

但你想这里是链接到源代码的问题。

http://matrixsust.blogspot.com/2011/11/basic-priority-queue-in-c.html

或

http://www.indiastudychannel.com/projects/4870-Priority-queue-using-array.aspx

希望能有所帮助。