0

Merging two sortedlinked listへの回答を読んでいました。コード:

#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);

   // What does the following piece of code do ?
    *pnext = list1;  // ??
    pnext = &list1->next; // ??
    list1 = *pnext;     // ?? 
  }

  *pnext = list2;
  return list;
}

ここでダブルポインターがどのように機能しているか、値がどのように変更されているかを理解できませんか?

4

1 に答える 1

2

pnext は Node のポインターへのポインターでnextあり、最後のノードのフィールドのアドレスを保持するためのものです

そのため、最初の行はポインタを次のノード (リストまたは前のいずれかnode->next)に設定します。

next2 行目は、現在のノードのフィールドに pnext を設定します

3 行目は、list1 の再参照を回避するマイクロ最適化のために、割り当てられたばかりの pext を使用して、その先頭を処理した後に list1 を進めます。

node->next のように書くこともできます:

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

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

  if (list2 == NULL)
    return list1;

  if (list1->data > list2->data)
    SWAP_PTRS(list1, list2);

  node=list=list1;

  list1=list1->next;

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

    node->next = list1;  

    node = list1->next; 
    list1 = list1->next;     
  }

  node->next = list2;
  return list;
}
于 2013-06-04T11:38:11.967 に答える