-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 に答える