c - 需要有关伪代码/算法的帮助 - 链表合并

Question

这个问题已经有答案了:

How does indirection work in this code? (1 个回答)

已关闭 9 年前。

我在其中一篇文章中看到下面的代码作为合并 C 中两个排序列表的答案。

#define SWAP_PTRS(a, b) do { void *t = (a); (a) = (b); (b) = t; } while (0)

Node* MergeLists(Node* list1, Node* list2) 
{
  Node *list = NULL, **pnext = &list;

  if (list2 == NULL)
    return list1;

  while (list1 != NULL)
  {
    if (list1->data > list2->data)
      SWAP_PTRS(list1, list2);

    *pnext = list1;
    pnext = &list1->next;
    list1 = *pnext;
  }

  *pnext = list2;
  return list;
}

有人可以用伪代码文本向我解释一下吗？无法在同一答案下发表评论，因此作为新问题发布。

Answer 1

首先有一个预处理器指令:

#define SWAP_PTRS(a, b) do { void *t = (a); (a) = (b)； (b) = t； }而(0)

这意味着当预处理器准备翻译单元进行编译时，每当遇到 SWAP_PTRS(a, b) 时，它都会将其替换为

do { void *t = (a); (a) = (b); (b) = t; } while (0)

让我们来解压一下。它只是一个交换一对指针 a 和 b 的函数。

由于循环是一个 do ... while 循环，因此它将在测试循环条件之前执行。在循环内部，声明了一个新的 void 指针 t。这与任何类型的指针兼容，因此无论a和b是什么类型的指针，它们都与t兼容。

然后这是一个标准交换:

1. 将a分配给t
2. 将b分配给a
3. 将t赋值给b

交换后，检查循环条件。由于它是 0，因此条件计算结果为 false，并且 do ... while 循环结束。换句话说，它将被执行一次且仅执行一次，这正是所需要的，因为目标只是交换一对指针。

这是实际 MergeLists 函数的伪代码。

Algorithm MergeLists
Receives: pointer to head node of linked list list1
    pointer to head node of linked list list2
Returns: pointer to head node of merged list

1. Declare pointer list for merged list and initialize to NULL
2. Declare pointer to pointer pNext and initialize it to the address of the merged list
3. if (list2 is NULL)  // empty list
    3.1 return list1   // nothing to merge
4. loop while list1 is not NULL
    4.1 if (data in list1 is greater than data in list2)
        4.1.1 swap list1 and list2
    4.2 set dereferenced value of pNext to list1
    4.3 set pNext to the address of the next node in list1
    4.4 set list1 to the dereferenced value of pNext // same as list1 = list1->next
5. end loop for list1
6. set the dereferenced value of pNext to list2
7. return list

这是一个很难遵循的逻辑。繁重的工作都在 while 循环中。 segmentation 如下:

有两个指向链表节点的指针，list1和list2。 while循环的第一步将数据值较小的节点设置为list1，将另一个节点设置为list2。如果需要，可以使用 SWAP_PTRS 宏进行设置。

一开始，*pNext指向这个数据值较小的list1。第一次循环时，由于 *pNext 也是 list (合并列表)，list 现在将指向与出色地。

下一步将pNext重置为list1中下一个节点的地址。但是，这不会改变 list 指向的位置(pNext 是一个两级指针，在这一步中，我们将更改 pNext 指向的位置，即，不其中 *pNext 指向)。

然后list1被设置为*pNext，即list1->next。

然后循环进入新的 l​​ist1 的下一次迭代。

所以基本上它只是不断检查列表头部节点的数据值，并将数据值较小的节点添加到合并列表的末尾。当它到达任一列表的末尾时，循环将终止，另一个列表中的其余节点将附加到合并列表的末尾。

希望这是有道理的!这是一个非常漂亮的解决方案，老实说，绘制起来比用文字解释要容易得多。