Проблема со вставкой в ​​двусвязный список по возрастанию

Мне нужно создать функцию для суммирования 2 кусочно-линейных функций (как убывающих, так и возрастающих) и вставить их в третий список в порядке возрастания на основе координат оси x каждой точки. Итак, я создал несколько функций, все вроде проверяются, кроме этой, но я не знаю, в чем проблема. Он вообще ничего не вводит.

struct coords имеет двойные x, y;
dList has: 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