2

「Programming Interviews Exposed」という本から、ツリーのようなリンクされたリストシステムを平坦化する次のアルゴリズムを見ています。

void flattenList( Node *head, Node **tail)
    Node *curNode =  head;
    while( curNode ){
        /* The current node has a child */
        if( curNode->child ){
            append( curNode->child, tail );
        }
        curNode = curNode->next;
    }
}

/* Appends the child list to the end of the tail and updates
 * the tail.
 */
void append( Node *child, Node **tail ){
    Node *curNode;

    /* Append the child child list to the end */
    (*tail)->next = child;
    child->prev = *tail;

    /*Find the new tail, which is the end of the child child
     *list.
     */
    for( curNode = child; curNode->next;
         curNode = curNode->next )
        ; /* Body intentionally empty */

    /* Update the tail pointer now that curNode is the new
     * tail.
     */
    *tail = curNode;
}

変更が持続することを確認するために関数に渡す**tail代わりに渡していることは理解していますが、私が理解できないのは、子に対して同じことをしない理由です (つまり、の代わりに渡さないのはなぜですか)?*tailappend*tail**child*child

4

4 に答える 4

1

Cは、セマンティクスを渡す「値による呼び出し」パラメーターを使用します。つまり、のような関数を呼び出すと、変数自体ではf(x)なく、の値のみがx関数に渡されます。x関数内のパラメーターに値を割り当てても、関数のx呼び出しに使用される値は変更されません。

変数自体を変更できるようにする場合は、変数を変更した関数内にf(&x)割り当てを行う場合は、この呼び出しのようにアドレスを渡す必要があります。*xx

は値によって渡される（変更されない）flattenListため、そのまま宣言されますが、関数が変更する必要があるため、アドレスとともに渡されます。headtail

これはappend関数に似ています。最初のパラメーターは変更されませんが、2番目のパラメーターは関数内で変更する必要があります。

于 2012-12-27T16:59:43.560 に答える
1

あなたの質問にすぐに答えるために。aのchildメンバーはNode更新されません。それらは、基になる子リストをウォークするためにのみ使用されます。

そして正直なところ、パラメーター名 ( child) の選択は、これほど恐ろしいものではありませんでした (それを呼び出すか、parentまたはそのようなものを除いて)。以下が少しでも明確かどうかを確認してください。これは、C が byval-call システムであるという事実を利用しており、実際にはパラメーターの 1 つ (ノード ポインター) を使用して、一時ポインターを使用せずに、特定のノードで始まるリストの末尾を見つけます (ノード ポインター自体を使用して、 byvalなので歩く）：

void append( Node *node, Node **tail )
{
    /* Append the child child list to the end */
    (*tail)->next = node;
    node->prev = *tail;

    /*Find the new tail, which is the end of the child child
     *list.
     */
    while (node->next)
        node = node->next;

    /* Update the tail pointer now that curNode is the new
     * tail.
     */
    *tail = node;
}

とにかく、これはあまり良いコードではありません。パラメータなどの NULL に対してチェックを行いません。これは大幅に強化する必要があります。エラー チェックと null 以外の検証を省略することにしたのは、元のコードでそれらがすべて除外されていたためです。大幅に堅牢なバージョンが必要な場合はお知らせください。

于 2012-12-27T17:03:47.297 に答える
0

コメントはappendそれを非常に明確に述べています

/* Update the tail pointer now that curNode is the new
 * tail.
 */
*tail = curNode;

テールポインタ自体（およびそれが参照するノードだけでなく）をpointer to a pointer更新しているため、更新を関数の外部に表示するには、パスする必要があります。

ポインタについてはchild、ポインタ自体ではなく、参照するノードのみを更新しています。したがって、別のレベルの間接参照を追加することによってコードをさらに複雑にする理由はありません。

于 2012-12-27T16:51:43.687 に答える