0

ノードが順番に表示されるようにリストにノードを挿入する際に問題があります。ノードをリストに挿入するための私の関数は次のとおりです。

void LinkedList::insert(const int item)
{
   Node *newNode = new Node;
   newNode -> data = item;

   if(head == NULL)
   {//in case of empty list
      head = tail = newNode;
      newNode -> next = NULL;
      newNode -> previous = NULL;
      ++count;
   } else {

      Node *ptr = head;

      while((ptr && (ptr -> next) != NULL) && (item < (ptr -> data)))
      {//traversing the list to find the correct insertion point
         ptr = ptr -> next;
      }

      if((ptr -> previous) == NULL)
      {//the insertion point is before the head of the list
         newNode -> previous = NULL;
         newNode -> next = ptr;
         ptr -> previous = newNode;
         head = newNode;
         ++count;
      }
      else if((ptr -> next) == NULL) 
      {//end of list insertion
         newNode -> next = NULL;
         newNode -> previous = ptr;
         ptr -> next = newNode;
         tail = newNode;
         ++count;
      } else {//middle of the list insertion
        (ptr -> previous) -> next = newNode;
         newNode -> previous = ptr -> previous;
         newNode -> next = ptr;
         ptr -> previous = newNode;
         ++count;
      }
   }
}

順序付けられているノードは、リストの先頭または末尾に挿入されたノードのみです。ノードをリストの途中に挿入する必要がある場合、ノードの順序は違反します。main() から結果を出力すると、次のようになります。

int main()
{
    LinkedList database;

    cout<<"The count is: "<< database.lenght() << endl;

    database.insert(11);
    database.insert(1);
    database.insert(8);
    database.insert(62);
    database.insert(55);
    database.insert(100);
    database.insert(00);
    cout<< endl;

    cout<<"The count is: "<< database.lenght() << endl;

    cout<< endl;
    database.print_forwards();

return 0;
}

出力：

The count is : 0

the count is : 7

 100
 62
 55
 8
 1
 11
 0

誰かが挿入機能の何が問題なのか説明できますか? ありがとうございました、

4

4 に答える 4

1

これで修正されるはずです： 

if((ptr -> previous) == NULL && item > (ptr -> data))
      {//the insertion point is before the head of the list if value is greater
         newNode -> previous = NULL;
         newNode -> next = ptr;
         ptr -> previous = newNode;
         head = newNode;
         ++count;
      }
else if((ptr -> previous) == NULL && item < (ptr -> data))
      {//the insertion point is after the head of the list if value is smaller
         newNode -> next = NULL;
         newNode -> previous = ptr;
         ptr -> next = newNode;
         ++count;
      }

「if((ptr -> next) == NULL)」ブロックにも同様のバグがあります。数字が小さい場合にのみ最後に挿入する必要があります。それ以外の場合は、中間に挿入します。

else if((ptr -> next) == NULL && item < (ptr -> data)) 
      {//end of list insertion
         newNode -> next = NULL;
         newNode -> previous = ptr;
         ptr -> next = newNode;
         tail = newNode;
         ++count;
      }
于 2013-09-26T12:32:58.740 に答える
1

上記のサイクルは、ptr がリスト内の挿入する項目の前の場所を指すように記述されています(少なくとも、サイクル条件からはそう思われます)。ただし、(ptr -> previous) == NULL新しい要素がリストの新しい先頭になるかどうかを確認する必要がある場合は、実際にはリストの先頭が要素の前の要素であるかどうかを確認します。item < head->dataこのチェックの代わりにかどうかをチェックする必要があります。

また、中間のケースでは、で作業する必要がptr->nextあり、そのリンクは ではありませんptr->previous。いくつかの単純なケースを紙に描いてみてください。たとえば、メインで試してみると、何が起こっているのかを理解できるはずです。

于 2013-09-26T12:02:25.743 に答える