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;

誰かが親切に私を助けてくれますか？説明してくれませんか？

編集済み：これらの2行を変更できますか：

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

に

 list = list-> next;
4

4 に答える 4

3

最初から：2つのリストと、返される新しいリストヘッドがあります。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ポイントがあります。これは、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*リストが返されます。

edit2：

そして、ずっと、pnextは次のように表現する方が適切です。

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

これは、最後に処理されたノードの次のポインターを指していることを意味します。

于 2011-03-21T10:18:00.220 に答える
2

pnextへのポインタへのポインタ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

list1は型Node*で pnextありNode**、型は、型が。である変数のアドレスを保持する必要があることを意味しますNode*。

*pnext = list1;

間接参照するpnextと、が得られNode*ます。したがって、この割り当ては正しいです。

pnext = &list1->next;

ここで->は、よりも優先順位が高くなり&ます。したがって、ポインタのアドレス（つまり、Node *タイプのアドレス）を返します。

list1 = *pnext;

これは最初のステートメントの正反対です。間接参照は、に割り当てることができるものをpnext与えます。Node*list1

はい、これを変更できます（つまり、論理的には同じことをします）-

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

に

list1 = list1->next ;

しかし、あなたは声明を持っています-

 *pnext = list2;

2ステップシーケンスのように初期化されなかった場合pnext、初期化されていないポインタ（つまり、*pnext）を逆参照すると、セグメンテーション違反が発生します。それが理由です。

于 2011-03-21T09:29:57.877 に答える
0

Visual StudioExpressEditionをインストールしてみてください。VS-2012でプログラムをデバッグしたら、ポインタにマウスを合わせるだけで、アドレスを逆参照して内容が表示されます。

于 2012-12-30T11:17:38.953 に答える