-3

如何在没有排序功能的情况下维护排序的列表。当我添加节点时，我想保持列表排序。删除节点时也是如此。

    #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;
}
4

2 回答 2

2

听起来你想要一个新功能：

  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-23T17:54:36.070 回答
0

维护它很容易排序。添加另一个方法 NodeSorted（名字不好，我只是按照你的约定，它们应该是 insertFront、insertBack、insertSorted）。这个方法应该做什么 - 将节点插入到适当的位置，所以你遍历你的列表，一旦找到大于你需要插入的元素，在它之前插入你的节点。请注意，要使此类 NodeSorted 正常工作，您需要维护列表排序，即避免使用 NodeFront 和 NodeFront。当然，如果实施得当，NodeSorted 本身将保持列表处于排序状态。

于 2013-02-23T17:55:49.063 回答