C中的双向链表排序函数

Question

我正在使用冒泡排序来更改节点位置。我知道有几种情况需要注意节点 1 是否在列表的开头。如果节点 2 在列表的末尾。如果node1在开头，node2在结尾。所以我相信问题是当我交换作为邻居的节点时，如 node1->next_ = node2;因为如果我进行常规交换，我最终会得到 node2->next_ = node2。

我想知道我是否走上正轨，因为我尝试了类似于我写的东西并最终无限循环。我觉得有些事情我不明白，就像我在某处丢失了一个指针。

我相信这是正确的，除非这两个节点在链表中是邻居。

编辑澄清的链接命名。恢复原状。

void swap(struct student_record_node** node1, struct student_record_node** node2)
{

  struct student_record_node *p1, *x1, *n1, *p2,*x2,*n2, *temp;

  p1 = (*node1)->prev_;
  x1 = *node1;
  n1 = (*node1)->next_;

  p2 = (*node2)->prev_;
  x2 = *node2;
  n2 = (*node2)->next_;

  /* swap next_  */

  if (p1 == NULL && n2 == NULL)
  {



  /* step one swap nodes */
    temp = *node1;
    *node1 = *node2;
    *node2 = temp; 
    /* step two swap node1 prev to be node2 prev */
    (*node2)->prev_ = NULL;
    /* step three swap node1 next to be node 2 next */
    (*node2)->next_ = n1;
    /* step four swap node1 next prev to be node2 next prev */
    (*node2)->next_->prev_ = x2;

    /* step 5 swap node2 next to be node1 next */
    (*node1)->next_ = NULL;
    /* step 6 swap node2 prev to be node1 prev */
    (*node1)->prev_ = n2;
    /* step 7 swap node2 prev next to be node1 prev next */
    (*node1)->prev_->next_ = x1;


  }
  else if (p1 == NULL)
  {
   /* step one swap nodes */
    temp = *node1;
    *node1 = *node2;
    *node2 = temp; 
     /* step two swap node1 prev to be node2 prev */
    (*node2)->prev_ = NULL;
    /* step three swap node1 next to be node 2 next */
    (*node2)->next_ = n1;
    /* step four swap node1 next prev to be node2 next prev */
    (*node2)->next_->prev_ = x2;

    /* step 5 swap node2 next to be node1 next */
    (*node1)->next_ = n2;
    /* step 6 swap node2 prev to be node1 prev */
    (*node1)->prev_ = p2;
    /* step 7 swap node2 prev next to be node1 prev next */
    (*node1)->prev_->next_ = x1;
    /* step 8 swap node2 next prev to be node1 next prev */
    (*node1)->next_->prev_ = x1;



  }
  else if(n2 == NULL)
  {
     /* step one swap nodes */
    temp = *node1;
    *node1 = *node2;
    *node2 = temp; 
     /* step two swap node1 prev to be node2 prev */
    (*node2)->prev_ = p1;
    /* step three swap node1 next to be node 2 next */
    (*node2)->next_ = n1;
    /* step four swap node1 next prev to be node2 next prev */
    (*node2)->next_->prev_ = x2;
        /* step 5 node1 prev next swapped with node2 prev next */
    (*node2)->prev_->next_ = x2;


    /* step 6 swap node2 next to be node1 next */
    (*node1)->next_ = NULL;
    /* step 7 swap node2 prev to be node1 prev */
    (*node1)->prev_ = p2;
    /* step 8 swap node2 prev next to be node1 prev next */
    (*node1)->prev_->next_ = x1;


  }
  else
  {
       /* step one swap nodes */
    temp = *node1;
    *node1 = *node2;
    *node2 = temp; 
     /* step two swap node1 prev to be node2 prev */
    (*node2)->prev_ = p1;
    /* step three swap node1 next to be node 2 next */
    (*node2)->next_ = n1;
    /* step four swap node1 next prev to be node2 next prev */
    (*node2)->next_->prev_ = x2;
        /* step 5 node1 prev next swapped with node2 prev next */
    (*node2)->prev_->next_ = x2;


    /* step 6 swap node2 next to be node1 next */
    (*node1)->next_ = n2;
    /* step 7 swap node2 prev to be node1 prev */
    (*node1)->prev_ = p2;
    /* step 8 swap node2 prev next to be node1 prev next */
    (*node1)->prev_->next_ = x1;
    /* step 9 swap node2 next prev to be node1 next prev */
    (*node1)->next_->prev_ = x1;


  }
  /* swap surrounding */

}

Answer 1

交换双链表中的两个节点时，有8个指针需要修改。请参见下图中的 8 个箭头。

+---+    +---+    +---+        +---+    +---+    +---+
|   |--->| A |--->|   | ...... |   |--->| B |--->|   |
|   |<---|   |<---|   | ...... |   |<---|   |<---|   |
+---+    +---+    +---+        +---+    +---+    +---+

现在，A 或 B 中的任何一个都可能位于列表的开头或结尾。它们也可以紧挨着（我们稍后会讨论一种特殊情况）。

这里最简单的事情是首先存储指向那四个未标记节点的指针。这是全部您需要的信息：

struct node *a_prev = a->prev;
struct node *a_next = a->next;
struct node *b_prev = b->prev;
struct node *b_next = b->next;

现在，由于这些指针中的任何一个都可以为 NULL，您只需在对它们执行操作之前进行完整性测试即可：

if (a_prev) a_prev->next = b;  //(1)
if (a_next) a_next->prev = b;  //(2)
if (b_prev) b_prev->next = a;  //(3)
if (b_next) b_next->prev = a;  //(4)

然后您可以从实际节点更新链接：

a->prev = b_prev;  //(5)
a->next = b_next;  //(6)
b->prev = a_prev;  //(7)
b->next = a_next;  //(8)

现在，那个特例呢？有两个版本：

a_prev   b_prev   a_next   b_next
+---+    +---+    +---+    +---+
|   |--->| A |--->| B |--->|   |
|   |<---|   |<---|   |<---|   |
+---+    +---+    +---+    +---+

b_prev   a_prev   b_next   a_next
+---+    +---+    +---+    +---+
|   |--->| B |--->| A |--->|   |
|   |<---|   |<---|   |<---|   |
+---+    +---+    +---+    +---+

我们来看第一个。哪些代码行会破坏列表的结构？您可以看到，由于 b_prev == a 和 a_next == b，以下内容：

if (a_prev) a_prev->next = b;  //(1) OK
if (a_next) a_next->prev = b;  //(2) ERROR b->prev = b 
if (b_prev) b_prev->next = a;  //(3) ERROR a->next = a
if (b_next) b_next->prev = a;  //(4) OK
a->prev = b_prev;  //(5) ERROR a->prev = a
a->next = b_next;  //(6) OK and fixes 3
b->prev = a_prev;  //(7) OK and fixes 2
b->next = a_next;  //(8) ERROR b->next = b

所以有两个语句（5 和 8）中断了。首先，应该他们是什么？

a->prev = b;
b->prev = a;

你还可以看到，如果A和B颠倒了（第二种情况），那么就会出现相反的问题（5和8会坏；6和7会固定1和4；2和3会好的）。

如果你想要紧凑，你可以用三元运算符扩展这最后四个语句。不过，它可能会让您有点头疼：

a->prev = (b_prev == a ? b : b_prev);  //(5)
a->next = (b_next == a ? b : b_next);  //(6)
b->prev = (a_prev == b ? a : a_prev);  //(7)
b->next = (a_next == b ? a : a_next);  //(8)

要挤出最后一个分支，您可以在没有三元运算符的情况下重新排列这四个语句（因为一半的测试是多余的）。或者，您可以重写语句以使用两个测试（而不是我为对称性编写的四个测试）并依靠编译器进行优化。

我可能不会打扰，但你也可以展开整个事情：

if (a_next == b)
{
    a->prev = b;       //(5)
    a->next = b_next;  //(6)
    b->prev = a_prev;  //(7)
    b->next = a;       //(8)
}
else if (b_next == a)
{
    a->prev = b_prev;  //(5)
    a->next = b;       //(6)
    b->prev = a;       //(7)
    b->next = a_next;  //(8)
}
else
{
    a->prev = b_prev;  //(5)
    a->next = b_next;  //(6)
    b->prev = a_prev;  //(7)
    b->next = a_next;  //(8)
}

Answer 2

您的 swap() 中的问题是 x4 和 y4 ，它们都具有 NULL 值，并且您正试图取消对这两个指针的引用，这会导致分段错误。

C中的双向链表排序函数

Doubly Linked List sorting function in C

c

sorting

struct

pointers

doubly-linked-list