双链表维护排序列表

-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

双链表维护排序列表

回答

相关问题