雙鏈表維護排序列表

-2

如何維護沒有排序功能的排序列表。當我添加節點時，我想維護排序的列表。還刪除節點時。雙鏈表維護排序列表

#include <iostream> 
    #include <cstdlib> 
    #include <string> 
    using namespace std; 


struct Node 
{ 
//node declare 
    double value; 
    Node *next; 
    Node *prev; 
    Node(double y) 
    { 
     value = y; 
     next = prev = NULL; 
    } 
}; 

class DLinkedList 
{ 
    Node *front; 
    Node *back; 
    public: 
    DLinkedList() 
    { 
       front = NULL; back = NULL; 
    } 
    //declare function 
    void NodeFront(double x); 
    void NodeBack(double x); 
    void dispForward(); 
    void dispReverse(); 
}; 
void DLinkedList::NodeFront(double x) 
    { 
     Node *n = new Node(x); 

     if(front == NULL) 
     { 
      front = n; 
      back = n; 
     } 
     else 
     { 
      front->prev = n; 
      n->next = front; 
      front = n;} 

    } 
    void DLinkedList::NodeBack(double x) 
    { 
     Node *n = new Node(x); 
     if(back == NULL) 
     { 
      front = n; 
      back = n; 
     } 
     else 
     { 
      back->next = n; 
      n->prev = back; 
      back = n; 

     } 

} 
//forward nodes 
    void DLinkedList::dispForward() 
    { 
     Node *temp = front; 
     cout << "forward order:" << endl; 
     while(temp != NULL) 
     { 
     cout << temp->value << " " ; 
     cout<<endl; 
     temp = temp->next; 
     } 
    } 
    //reverse list 
    void DLinkedList::dispReverse() 
    { 
     Node *temp = back; 
     cout << "reverse order :" << endl; 
     while(temp != NULL) 
     { 
     cout << temp->value << " " ; 
     cout<<endl; 
     temp = temp->prev; 
     } 
    } 

int main() 
{ 
    DLinkedList *list = new DLinkedList(); 
    //front of the list 
    list->NodeFront(45.0); 
    list->NodeFront(49.0); 
    list->NodeFront(42.0); 
    list->NodeFront(48.0); 
    list->NodeFront(48.0); 
    list->NodeFront(52.0); 
    list->NodeFront(12.0); 
    list->NodeFront(100.0); 

    list->dispForward(); 
    list->dispReverse(); 
    cin.get(); 
    return 0; 
}

來源

2013-02-23 user2102787

如果你想維護排序後的關鍵字，鏈接列表實際上是錯誤的數據結構 – 2013-02-23 17:46:57

聞起來像是作業或者不知道'std :: list'的人。 – 2013-02-23 18:04:56

這聽起來像你想有一個新的功能：

void DLinkedList::NodeSorted(double x) 
    { 
     Node *n = new Node(x); 

     // Step 1: Find the first node "x" that should be AFTER n. 

     // Step 2: Make the node before "x" link to n 

     // Step 2: Make "x" link to n 

    }

來源

2013-02-23 17:54:36

保持它排序很容易。添加另一個方法NodeSorted（錯誤的名稱，我只是遵循慣例，它們應該是insertFront，insertBack，insertSorted）。這個方法應該做什麼 - 將節點插入正確的位置，這樣你就可以瀏覽你的列表，並且一旦發現元素大於你需要插入的元素，就在它之前插入節點。注意這樣的NodeSorted工作正常，你需要維護列表排序，即避免使用NodeFront和NodeFront。當然，如果實施正確，NodeSorted本身會將列表保持在排序狀態。

來源

2013-02-23 17:55:49 Slava

雙鏈表維護排序列表

回答

相關問題