Менять местами узлы в связанном списке?

Question

Я написал эту функцию, чтобы поменять местами 2 узла в связанном списке, но в результате возникает ошибка сегментации.Вы можете проверить это?Благодарю.(Я сделал typedef для struct student * as punt)

void swap_node(punt node1, punt node2)
{

 node1->next=node2->next;
 node2->next=node1;
 node2->prev=node1->prev;
 node1->prev=node2;
 (node2->prev)->next=node2;

}

Answer 1

Когда это возможно, два узла легче заменить, только поменяв их содержимое.Результат идентичен.Это создаст проблему, если где-то еще в вашем коде вы держите указатель на один из замененных узлов и по-прежнему ожидаете, что это будет тот же самый узел.

В любом случае, вернемся к своему коду.Есть несколько вещей, которые требуют доработки.Во-первых, нам нужно проверить, не равны ли node1 и node2 значения NULL, и если нет, мы можем продолжить, в противном случае выйдите из функции, поскольку мы не можем поменять ее местами.Первые 4 строки вашего кода обмена в порядке, но есть две проблемы:

• Узел, который был до node1 (до замены), может быть нулевым, и, таким образом, доступ к его указателю nextточка на node2 может привести к неопределенному поведению и вероятному падению.Проверьте, существует ли он, а затем выполните присваивание.
• Вы забыли проверить, существует ли узел после node2 (до замены) и, если да, укажите prev указатель на node1

Answer 2

Обычно помогает визуализировать ссылки в двусвязном списке, просто нарисуйте его на листе бумаги.Вы заметите 4 ссылки на узел:

node->next
node->next->prev
node->prev
node->prev->next

Таким образом, чтобы поменять местами два несвязанных узла, вам нужно поменять 4 ссылки.

Следующее не будет работать:

node1->next=node2->next;

Это перезаписывает старое значение node1-> next.Вам нужно использовать временную переменную вместо этого.Примерно так:

#define SWAP_PTR(a,b) { void* tmp = b; b = a; a = tmp; }

void swap_node(punt node1, punt node2)
{
  SWAP_PTR(node1->next, node2->next);
  SWAP_PTR(node1->next->prev, node2->next->prev);
  SWAP_PTR(node1->prev, node2->prev);
  SWAP_PTR(node1->prev->next, node2->prev->next);
}

Примечание - в многопоточной среде вам понадобится некоторая форма блокировки.

Answer 3

Полагаю, этого было бы достаточно, в основном единственным отличием от вашего кода является последнее утверждение (без простоты):

void swap_node(punt node1, punt node2)
{

node1->next=node2->next;
node2->next=node1;
(node1->prev)->next=node2;
node2->prev=node1->prev;
node1->prev=node2;
(node1->next)->prev=node1;

}