排序隊列鏈表C++

-1

我需要做一個隊列鏈表中的第一個節點總是具有最小的值，因此需要進行排序，我寫了這個代碼：排序隊列鏈表C++

#include <iostream> 
using namespace std; 

struct Node 
{ 
    int key; 
    Node *link; 
}; 

class qlinkedlist 
{ 
private: 
    Node *head; 
    Node *tail; 
    Node *curr; 
    Node *prev; 
    int count; 

public: 
    void Enqueue(int value) 
    { 
     Node *newnode = new Node; 
     newnode -> key = value; 
     newnode -> link = NULL; 
     if(head==NULL) 
     { 
      head=tail=newnode; 
      count++; 
     } 
     else if(newnode->key < head->key) 
     { 
      newnode -> link = head; 
      head = newnode; 
      count++; 

     } 
     else 
     { 
      prev=head; 
      curr=head->link; 
      while(curr != NULL) 
      { 
       if(newnode->key < curr->key) 
       { 
        prev->link = newnode; 
        newnode->link = curr; 
        count++; 
       } 
       else 
       { 
        prev = curr; 
        curr = curr ->link; 
       } 
      } 
     } 
    } 


    void Dequeue() 
    { 
     if(head==NULL) 
     { 
      cout<< "Queue is empty" << endl; 
     } 
     else 
     { 
      curr = head; 
      head = head -> link; 
      delete curr; 
      count--; 
     } 
    } 

    void print() 
    { 
     curr = head; 
     while (curr!=NULL) 
     { 
      cout << curr -> key << endl; 
      curr = curr -> link; 
     } 
    } 

}; 


void main() 
{ 
    qlinkedlist obj; 
    obj.Enqueue(5); 
    obj.Enqueue(4); 
    obj.Enqueue(3); 
    obj.Enqueue(2); 
    obj.Enqueue(1); 

    obj.print(); 
}

問題是它只有當我按照上面的順序添加節點時才起作用，例如，如果我嘗試添加3然後2然後5不起作用，那麼代碼有什麼問題？謝謝

來源

2014-05-01 Computerphile

與人們在標點或雙方空間周圍沒有空格是什麼？ – crashmstr

你想要做什麼是一個優先級隊列，有更好的方法來使用二叉搜索樹來做到這一點。 – Guilherme

因爲如果您嘗試添加比列表中所有內容更大的元素，它永遠不會通過您唯一的條件來添加節點：if(newnode->key < curr->key)。試試這個：

while(curr != NULL && newnode->key > curr->key) 
{ 
    prev = curr; 
    curr = curr ->link;   
} 
prev->link = newnode; 
newnode->link = curr; 
count++;

這樣，你通過鏈表，直到找到正確的位置，然後再添加即使你到最後（CURR == NULL）的新節點。

來源

2014-05-01 18:04:33

排序隊列鏈表C++

回答

相關問題