1 
#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;
}

这段代码来自这里，这个问题的选择答案。

我在这里无法理解 3 行：

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

任何人都可以帮助我吗？给我解释一下？

编辑：我可以改变这两行：

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

至

 list = list-> next;
4

4 回答 4

3

从一开始：您有两个列表和一个新的列表头，您将返回它们。pnext 最初指出了这一点。

该代码旨在尽可能少地重新分配指针，因此尝试保持输入列表的初始“下一个”指针完好无损。

list1          pnext->list->Null
|
V
o->o->o...

list2
|
V
o->o->o...

交换是为了确保较小的元素是 list1 的第一个元素。这些行的作用是：

一步一步来：

*pnext = list1;

获取 *pnext（它是第一次迭代之前的列表）以指向包含最小元素的节点：

list1
|
V
o->o->o...
^
|
list<-pnext

list2
|
V
o->o->o...

.

pnext = &list1->next;

是棘手的部分，如前所述， & 运算符的优先级较低。它也很难以图形方式显示，因为它实际上是查看 Node 构造的一部分。像这样的东西：

list1
|
V
o---->o->o...
^     ^
|     |
list  x<-pnext

list2
|
V
o->o->o...

其中 x 是 list1 指向的 o 的下一个指针。

list1 = *pnext;

推进 list1 头，因为它的第一个元素被处理。

   list1<-pnext
   |
   V
o->o->o->...
^
|
list

list2
|
V
o->o->o->...

从这里开始，您与列表无关，因为您想将其作为合并列表的头部返回。

不变量 pnext 指向最后处理元素的 next 指向的位置，这是 list1-2 中最小元素应该去的位置。有趣的事情发生在交换中，尝试自己制定确切的程序（很难像这样画，并且很好的练习来理解 ** 做了什么）。如果我找到一个好的方法来绘制它，我可能会添加它。

你不能使用list = list-> next;它会做这样的事情：

   list1
   |
   V
o->o->o->...
   ^
   |
   list

list2
|
V
o->o->o->...

这意味着你会失去那个孤独的 o（以及随着循环的进行而最终失去的一切）。

编辑：*pnext = list2;最后这样做：

循环终止（上述语句之前的状态）：

         list1<-pnext
         |
         V
o->o->o->null
^
|
list

      o->o->o->...
      ^
      |
      list2

声明后：

         list1
         |
         V              
o->o->o  Null
^     |
|     |
list  |
      V
      o->o->o->...
      ^
      |
      list2<-pnext

该语句将剩余的列表附加到列表的末尾。然后返回 Node* 列表，指向合并列表的头部。

编辑2：

一路走来，pnext 会更好地表示为：

         list1
         |
         V              
o->o->o  Null
^     |
|     |<-pnext
list  |
      V
      o->o->o->...
      ^
      |
      list2

这意味着它指向最后处理节点的下一个指针。

于 2011-03-21T10:18:00.220 回答
2

pnext是指向 a 的指针的指针Node。

" *pnext" 表示您正在使用 所指向的值pnext。因此：

*pnext = list1;

意味着无论指针pnext指向什么，现在都指向与 . 相同的东西list1。

为了清楚起见，下一行应加括号：

pnext = &(list1->next);

list1->next意味着您也正在访问指向的next属性，以及获取该元素地址的方法。本质上意味着您正在指向指向下一个元素的指针。list1&pnext

最后一行：

list1 = *pnext;

意味着您获取指向的值pnext并将其分配给list1.

于 2011-03-21T09:23:56.403 回答
1

list1is of typeNode*并且 pnextis of typeNode**意味着它应该保存类型为 的变量的地址Node*。

*pnext = list1;

当您取消引用时pnext，您会得到Node*. 所以，这个任务是正确的。

pnext = &list1->next;

这里->的优先级高于&. 因此，它返回一个指针的地址（即 Node* 类型的地址）

list1 = *pnext;

这与第一种说法正好相反。取消引用pnext给出了Node*可以分配给list1.

是的，你可以改变这一点（即，从逻辑上讲，它们做同样的事情）-

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

至

list1 = list1->next ;

但是，你有一个声明 -

 *pnext = list2;

如果pnext没有像两步序列中那样初始化，取消引用未初始化的指针（即*pnext）将导致分段错误。这就是原因。

于 2011-03-21T09:29:57.877 回答
0

尝试安装visual studio express版。在 VS-2012 中调试程序后，只需将鼠标悬停在指针上，它就会通过取消引用地址向您显示内容。

于 2012-12-30T11:17:38.953 回答