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而不是传递*tail给append函数以确保更改*tail持续存在，但我不明白为什么我们不对孩子做同样的事情（意味着我们为什么不传递**child而不是传递*child）？

4

4 回答 4

1

C 使用“按值调用”参数传递语义。这意味着，如果您调用类似 的函数f(x)，则只会将 的值x传递给函数，而不是变量x本身。当您为函数内部的参数赋值时，x用于调用函数的参数不会改变。

如果您希望能够更改变量本身，则必须像在此调用中一样传递地址，f(&x)如果您随后对*x已更改变量的函数内部进行赋值x。

之所以flattenList按原样声明是因为它是head按值传递的（它不会改变），但是tail是用它的地址传递的，因为函数必须改变它。

这与append函数类似。第一个参数不会更改，而第二个参数必须在函数内部更改。

于 2012-12-27T16:59:43.560 回答
1

立即回答您的问题。a的child成员Node永远不会更新。它们仅用于遍历底层子列表。

老实说，参数名称child（parent看看以下是否更清楚。它利用了 C 是一个 byval-call 系统这一事实，并且实际上使用其中一个参数（节点指针）来查找从给定节点开始的列表的结尾，而无需任何临时指针（我们使用节点指针本身作为走，因为它是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 进行检查。这应该得到显着加强。我选择放弃错误检查和非空验证，只是因为原始代码也忽略了所有这些。如果您想要一个更强大的版本，请告诉我。

于 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 回答
0 
struct node *flatten_nr(struct node *root)
{  


    struct node *temp1, *temp2;

    if (NULL == root) return NULL;
    temp2 = root;
    while (root != NULL)
    {
        if( root->next != NULL)
        {
            temp1 = root;
            /* go to the end of the list and append */
            while (temp1->down != NULL)
            {
                temp1 = temp1->down;
            }
            temp1->down = root->next;
        }
        root = root->down;
    }
    return temp2;
}
于 2014-11-11T18:38:48.540 回答