链表指针问题

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

/*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赋值给下一次调用的返回值来完成的。

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

Answer 3

您的问题可以通过此示例模拟(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 ：忽略内存泄漏的问题...