Передача двойного указателя заголовка связанного списка

Question

Я видел это в какой-то книге / учебнике.

Когда вы передаете указатель заголовка (связанного списка) в функцию, вам нужно передать его как двойной указатель.

Например: // Это обратный связанный список, в котором head указывает на первый узел.

void nReverse(digit **head)
{
    digit *prev=NULL;
    digit *curr=*head;
    digit *next;

    while(curr!=NULL)
    {
        next=curr->next;
        curr->next=prev;
        prev=curr;
        curr=next;
    }
    *head=prev;
    return;
}

Это отлично работает.

Это также работает, когда я использую один указатель, как,

void nReverse(digit *head)
{
    digit *prev=NULL;
    digit *curr=head;
    digit *next;

    while(curr!=NULL)
    {
        next=curr->next;
        curr->next=prev;
        prev=curr;
        curr=next;
    }
    head=prev;
    return;
}

Я попытался напечатать список с помощью указателя головы. Обе функции работают нормально.

Я что-то упустил?

Спасибо

Answer 1

Это очень C-подобный код, а не C ++.

Обычно, когда что-то передается по значению, функция работает с копией данных:

void foo(int i)
{
    i = 5; // copy is set to 5
}

int x = 7;
foo(x);
// x is still 7

В Cвместо этого вы передаете указатель на переменную и можете изменить его следующим образом:

void foo(int* i)
{
    *i = 5; // whatever i points to is set to 5
}

int x = 7;
foo(&x);
// x is 5

Для вас вместо int это digit*.(В результате указатель на указатель.)

---

В C ++ были введены ссылки.Ссылка - это псевдоним другого объекта.Таким образом, вы должны сделать что-то вроде этого:

void foo(int& i) // i is an alias to another value
{
    i = 5; // x is set to 5
}

int x = 7;
foo(x); // pass x as alias, not address of x.
// x is 5

Ссылка, как правило, предпочтительнее, так как она навязывает вам фактическую ссылку на объект и упрощает как вызов, так и рабочий код.Конечно, в C ++ вы бы не реализовали список самостоятельно, вы бы использовали std::list.

Answer 2

Эта последняя head=prev; не изменяет значение переданного указателя во втором примере. Нужна ли эта линия для целей этой функции, решать вам. Но есть разница.

Как вы проверили, что он "работал нормально"? Удалось ли вам перебрать список и распечатать значения узла и увидеть, что они на самом деле были обращены? Первая функция (предположительно вызываемая как nReverse(&list); меняет , на что указывает list, вторая - нет (так для второй, как узнать, какой узел является началом списка, после того как он был только что изменился ...).

Answer 3

Причиной двойной передачи указателя (первый пример) является то, что вы хотите изменить заголовок списка. Поскольку вы переворачиваете список, заголовок должен указывать на последний элемент списка после того, как вы сделали переворот.

digit* list; 
// initialize list
nReverse(&list); 
// now list is pointing to the last element of the chain (and not the first)

Если вы не используете двойные указатели, то список все равно будет указывать на исходный первый элемент, который затем теперь указывает на NULL, поскольку это последний элемент после обращения. Таким образом, вы теряете все остальные элементы.

Answer 4

Причина двойной косвенности заключается в том, что nReverse может изменить указатель вызывающей стороны, поскольку после обращения к списку заголовок списка теперь становится другим узлом.

Во второй версии вы модифицируете копию head, которая является локальной для функции, поэтому вызывающая сторона все еще имеет ссылку на старый головной узел, который теперь является хвостом.

Answer 5

В первом примере то, что вы передали, все еще указывает на «начало» списка.

Во втором примере он указывает на конец списка (который был началом, когда вы начали, но с тех пор переехал).