Проблема с указателем на связанный список - PullRequest
Новая
       35

Проблема с указателем на связанный список

0 голосов
/ 13 февраля 2020

Есть 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);
    }
}

Ответы [ 3 ]

2 голосов
/ 13 февраля 2020

В этой функции 

/*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 переменная x значение main не было изменено, поскольку функция обрабатывает копию своего аргумента.

После второго вызова функции переменная x была изменена, поскольку она была переназначена новым значением.

0 голосов
/ 13 февраля 2020 
/*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 возвращаемое значение следующего вызова .

Также я бы действительно избегал рекурсивной функции для добавления узла в ваш список - вызов вашей функции с огромным списком может привести к переполнению стека

0 голосов
/ 13 февраля 2020

Ваша проблема может быть смоделирована на этом примере (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: игнорировать проблемы утечек памяти ...

...