双向链表插入问题

我在列表中插入节点以便它们按顺序显示时遇到问题。这是我将节点插入列表的函数：

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

有人可以解释一下我的插入功能出了什么问题吗？谢谢，

这应该可以解决它：

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

您编写上述循环的方式是 ptr 指向列表中应插入的项目之前的位置（至少从循环条件来看是这样）。但是，当(ptr -> previous) == NULL应该检查新元素是否会成为列表的新标题时，实际上它会检查列表的头部是否是我们元素之前的元素。您应该检查是否item < head->data而不是此检查。

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

澄清一下，既然你说只有头部和尾部是有序的，你是在尝试将它们从大到小插入？如果是这种情况，它会立即出错。查看问题所在最简单的方法是手动使用数字运行代码。只需按照您的代码输入 11，然后输入 1。1 在 11 之前插入，因为您只在 while 循环中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 中进行额外的检查，以检查该项目是否data。

我认为

您的"插入中间不太正确......

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

相关内容

最新更新

热门标签：