如何在C編程中實現優先隊列？

我需要在C編程中使用單向鏈表實現一個優先級隊列。如何在C編程中實現優先隊列？

我對優先級隊列沒有清晰的認識。我用Google搜索，但沒有完全理解我發現的內容。我的理解是，優先級隊列是一個隊列，其元素按優先級排序。根據元素優先級將列表中的插入定位在列表中。

假設我們有以下情況。（注：我假設，更高的價值遠遠具有較高優先級）：

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

如果另一個元素需要插入，說Element-->3 (priority=3)具有更高的優先級。

我可以移動上一個元素Element-->2 (priority=2)，並在位置0處插入此新的Element-->3 (priority=3)，並將Element-->2 (priority=2)移動到列表中的位置1。

現在名單成爲，

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

同樣，插入的基礎上，我必須在列表中的所有元素轉變？

這是正確的嗎？

來源

2011-11-24 Dinesh

到目前爲止好 - 你是否被你的實現困住了？ – sarnold

簡而言之，當它必須在列表上操作時，它需要具有最高優先級的項目來操作......如何實現這一點取決於您是將最高優先級的元素放在列表正面還是將其放在堆棧前面（如果你使用堆）... – nikel

插入，當你做這樣的事情（僞代碼）你不必「移動」列表中，而不是對優先級低於結束的特殊檢查也是如此。

來源

2011-11-24 08:18:33

我認爲你遇到了麻煩，因爲優先隊列應該用堆樹來實現，而不是一個單獨的鏈表。

堆使一切都變得簡單 - 所有操作都非常便宜：更新，刪除和插入堆都是O（log n）。

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

如果您的列表中有一個指針到最後，你可以添加：

來源

2011-11-24 08:15:43

好的，我不知道你爲什麼需要它在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

希望它能幫助。

來源

2011-11-24 08:21:56

您對優先級隊列沒問題。但是...

鏈表不是一個簡單的數組。

鏈接列表中的每個項目都有對下一個項目的引用。您可以通過更改這兩個項目的引用來將項目插入另一個項目。

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

插入A與B之間C被執行：

通過ref to B
更改A ref to B改變NULL用C由ref to C

來源

2011-11-24 08:23:14 mouviciel

優先級隊列是一個抽象數據類型基本上保持項目在排序順序（升序或降序）在某些選定的關鍵。正如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; 
}

}

來源

2011-11-24 08:39:23

如何在C編程中實現優先隊列？

回答

相關問題