Проблем с вмъкване в двойно свързан списък във възходящ ред

Трябва да направя функция за сумиране на 2 линейни функции на части (и двете намаляващи или нарастващи) и да ги вмъкна в трети списък във възходящ ред въз основа на координатите на оста x на всяка точка. Така че създадох множество функции, изглежда, че всички работят, освен тази, но не знам какъв е проблемът. Изобщо не въвежда нищо.

struct coords има двойно x,y;
dList има: coords pt;
node има: node *head, *tail ;
възел *предишен, *следващ;

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

c++ sorting doubly-linked-list
person TheAfterLife    schedule 30.12.2019    source източник
comment
Бихте ли добавили как се дефинират node и dList? Не се събира. Изглежда, че node има coords pt, а не dList, както ни казвате.   -  person PajLe    schedule 31.12.2019
comment
Това е маркирано C++ и не посочвате никакви ограничения или причини за тях. Така че използвайте std::list и забравете всички хакерски действия в персонализирания списък.   -  person Zan Lynx    schedule 31.12.2019
comment
Също така, какво трябва да прави тази точна функция, за която питате? Вмъкване на coords елемент в съществуващ списък?   -  person PajLe    schedule 31.12.2019
comment
Имате проблем с вашата вложка. С първия възел задавате L.head=temp; и L.tail=temp; (което е добре, списъкът е просто саморефериращ или кръгъл в този момент). Проблемът идва, когато поставите втория възел. Вие не обработвате случая, когато L.head == L.tail, за да знаете дали да зададете L.head->next = L.tail = temp. Вместо това за втория възел просто сравнявате point за head и tail, които са един и същ възел по това време.   -  person David C. Rankin    schedule 31.12.2019

Отговори (1)


arrow_upward
0
arrow_downward

Случаят, в който възелът, който трябва да се вмъкне, е в средата, е проблемът. Трябва да гледате един възел напред, вместо да гледате текущия. Опитайте да го разработите на хартия и ще видите как това има значение:

  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)

Надявам се, че това ви помага.

person bhristov    schedule 31.12.2019
comment
Няма проблем. Радвам се, че можах да помогна. - person bhristov; 31.12.2019