-1

我在其中一篇文章中看到下面的代码作为在 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;
}

任何人都可以将其作为伪代码文本向我解释吗？无法在相同的答案下发表评论，因此发布为新问题。

4

1 回答 1

0

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

#define SWAP_PTRS(a, b) do { void *t = (a); (a) = (b); (b) = t; } while (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循环中。这是一个细分：

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

开始时，*pNext指向list1具有较小数据值的 this。第一次通过循环，因为*pNext也是list（合并的列表），list现在也将指向同一个地方。

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

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

然后循环使用这个新的 list1 进入下一次迭代。

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

希望这是有道理的！这是一个相当不错的解决方案，老实说，绘制起来比用文字解释要容易得多。

于 2013-08-15T07:45:37.587 回答