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应该检查新元素是否将成为列表的新头部，而实际上它检查列表的头部是否是我们元素之前的元素。你应该检查 ifitem < head->data而不是这个检查。

同样在中间情况下，您应该使用ptr->next它的链接而不是使用ptr->previous. 试着在纸上画出几个简单的案例——例如你在主要案例中尝试的那个，我认为你应该能够弄清楚发生了什么。

于 2013-09-26T12:02:25.743 回答
1

澄清一下，既然你说只有头部和尾部是有序的，你是在试图让它们从最大到最小插入吗？如果是这种情况，它会立即出错。查看问题的最简单方法是手动运行您的代码和您的数字。只需按照您的代码输入 11，然后输入 1。1 在 11 之前插入，因为您只在 while 循环中执行 item < ptr->data 检查，而不会在 if 和 else 中再次执行此操作。

插入 11 后，尝试插入 1 时，ptr->next 为空，因此 while 循环不运行，您直接进入

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

请注意，没有检查是否在之前或之后插入它，您只需在它之前插入 1。您需要在 if 中进行额外检查以检查 item < ptr->data 是否。

于 2013-09-26T12:16:33.763 回答
0

我认为您的“插入中间不太正确...

else {//middle of the list insertion
        (ptr -> previous) -> next = newNode;
         newNode -> previous = ptr -> previous;
         newNode -> next = ptr;
         ptr -> previous = newNode;
         ++count;
      }

这会在指向元素之前插入新元素。我相信你想在它之后插入它，类似于：

else {//middle of the list insertion
         newNode->next = ptr->next;
         newNode->next->previous = newNode;
         newNode->previous= ptr;
         ptr->next = newNode;
         ++count;
      }
于 2013-09-26T12:11:39.423 回答