c++ - 以升序插入双向链表的问题

Question

我需要制作一个函数，将2个分段线性函数求和(减小或增大)，然后基于每个点的x轴坐标以升序将它们插入到第三列表中。因此，我创建了多个功能，除了该功能外，其他所有功能似乎都已 checkout ，但我不知道出了什么问题。它根本没有输入任何东西。

struct 坐标具有双倍x，y;
拥有:coords pt;
节点具有:节点* head，* tail;
节点* prev，* next;

dList insert(dList L, coords point) {
  node *temp;
  temp = new node;
  if (temp == NULL) {
    cout << "error";
    exit(1);
  }
  temp->next = NULL;
  temp->prev = NULL;
  temp->pt = point;
  if (L.head == NULL || L.tail == NULL) {
    L.head = temp;
    L.tail = temp;
    return L;
  }
  if (L.head->pt.x > temp->pt.x) {
    temp->next = L.head;
    L.head->prev = temp;
    L.head = temp;
    return L;
  }
  if (L.tail->pt.x < temp->pt.x) {
    temp->prev = L.tail;
    L.tail->next = temp;
    L.tail = temp;
    return L;
  }
  node *cur;
  cur = L.head->next;
  while (cur->pt.x < temp->pt.x)
    cur = cur->next;
  temp->next = cur->next;
  temp->prev = cur;
  cur->next->prev = temp;
  cur->next = temp;
  return L;
}

Answer 1

问题是要插入的节点在中间。您应该先看一个节点，而不要看当前节点。尝试在纸上解决问题，您会发现这有何不同:

  node * cur;
  // also start at head here
  cur=L.head;
  while(cur->next->pt.x<temp->pt.x)
    cur=cur->next;
  temp->next=cur->next;
  temp->prev=cur;
  cur->next->prev=temp;
  cur->next=temp;

您还应该考虑将dList L作为函数的指针传递，并将其作为指针返回:

// this way you won't be making a copy of it, you may run into trouble if you don't have your copy constructor implemented
dList* insert(dList* L,coords point)

希望对您有帮助。