链表指针问题

Question

有2个createList函数，一个打印出链表的所有元素，而另一个不打印为什么？

/*following createList prints out fine */
node* createList(node* root , int a){
    if(root == NULL) root = new node(a);
    else root->next = createList(root->next , a);

    return root;
}

/*following createList prints out only 1st element, why?*/
node* createList(node* root , int a){
    if(root == NULL) root = new node(a);
    else createList(root->next , a);

    return root;
}

void read(node* root){
    if(root==NULL) return;
    else{
        cout << root->data << " ";
        read(root->next);
    }
}

Answer 1

在这个函数中

/*following createList prints out only 1st element, why?*/
node* createList(node* root , int a){
    if(root == NULL) root = new node(a);
    else createList(root->next , a);

    return root;
}

它的参数root是函数的一个局部变量，保存着传递给函数的参数值的副本。所以更改副本不会影响原始参数。

本函数中与上述函数相反

/*following createList prints out fine */
node* createList(node* root , int a){
    if(root == NULL) root = new node(a);
    else root->next = createList(root->next , a);
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    return root;
}

原始参数已赋值新值。

为了更清楚地考虑一个非常简单的程序

#include <iostream>

int f( int x )
{
    x *= 10;

    return x;
}

int main() 
{
    int x = 10;

    std::cout << "Before call of f: " << x << '\n';

    f( x );

    std::cout << "After  call of f: " << x << '\n';

    x = f( x );

    std::cout << "After  call of f: " << x << '\n';

    return 0;
}

它的输出是

Before call of f: 10
After  call of f: 10
After  call of f: 100

在第一次调用函数 f 后，main 中的变量 x 没有改变，因为该函数处理其参数的副本。

第二次调用该函数后，变量 x 发生了变化，因为它已被新值重新分配。

Answer 2

你的问题可以通过这个例子来模拟（int而不是node来简化）：

void createList (int *node)
{
    node = new int (2);
}

int main()
{
    int *root= new int (5);
    createList (root);

    return 0;
}

虽然函数createList中有地址调用，但是root的值保持不变(5)。这正是你遇到的情况：

createList(root->next , a);

PS : 忽略内存泄漏的问题...

Answer 3

/*following createList prints out only 1st element, why?*/
node* createList(node* root , int a){
    if(root == NULL) root = new node(a);
    else createList(root->next , a);

    return root;
}

这实际上创建了一个新节点，但错过了之前最后一个节点和新节点之间的链接。

所以这实际上等同于：

node *n1 = new node(42);
node *n2 = new node(43);

n1 和 n2 之间没有连接，您需要用以下方法创建：

n1->next = n2;

这是在您的函数的工作版本中完成的，方法是将 root->next 分配给下一次调用的 return 值。

此外，我真的会避免使用递归函数将节点附加到您的列表 - 使用一个巨大的列表调用您的函数可能会导致堆栈溢出

链表指针问题

Linked list pointer issue

c++

recursion

linked-list

singly-linked-list

c++14